Dogcows Code - chaz/yoink/blob - src/stlplus/containers/digraph.tpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2
   3 //   Author:    Andy Rushton
   4 //   Copyright: (c) Southampton University 1999-2004
   5 //              (c) Andy Rushton           2004-2009
   6 //   License:   BSD License, see ../docs/license.html
   7
   8 //   Note: I tried to write this using STL lists for the node and arc lists, but
   9 //   it got far too hairy. The specific problem is that I wanted a digraph
  10 //   iterator to contain a list::iterator so I needed to be able to generate a
  11 //   list::iterator from a node or arc and STL list iterators don't give you that
  12 //   functionality. I tried burgling the data structures, but that was
  13 //   non-portable between different STL implementations so needed lots of #ifdefs
  14 //   and so was mind-bogglingly awful and unreadable - in other words a
  15 //   maintenance nightmare. I gave up and impemented my own lists - not difficult.
  16
  17 //   I use circular double-linked lists. The circular design means that both
  18 //   ends of the list are equally accessible in unit time. An empty list
  19 //   contains no objects. There is no end node in the list - unlike the STL
  20 //   lists which have a dummy node for end iterators to point to -
  21 //   conceptually the end iterator points one element beyond the end of the
  22 //   list. However, I implement the end iterator concept in the iterator
  23 //   itself, so do not need the dummy end node.
  24
  25 ////////////////////////////////////////////////////////////////////////////////
  26 #include <algorithm>
  27 #include <deque>
  28
  29 ////////////////////////////////////////////////////////////////////////////////
  30 // Internals
  31
  32 namespace stlplus
  33 {
  34
  35   template<typename NT, typename AT>
  36   class digraph_node
  37   {
  38   public:
  39     master_iterator<digraph<NT,AT>, digraph_node<NT,AT> > m_master;
  40     NT m_data;
  41     digraph_node<NT,AT>* m_prev;
  42     digraph_node<NT,AT>* m_next;
  43     std::vector<digraph_arc<NT,AT>*> m_inputs;
  44     std::vector<digraph_arc<NT,AT>*> m_outputs;
  45   public:
  46     digraph_node(const digraph<NT,AT>* owner, const NT& d = NT()) :
  47       m_master(owner,this), m_data(d), m_prev(0), m_next(0)
  48       {
  49       }
  50     ~digraph_node(void)
  51       {
  52       }
  53   };
  54
  55   template<typename NT, typename AT>
  56   class digraph_arc
  57   {
  58   public:
  59     master_iterator<digraph<NT,AT>, digraph_arc<NT,AT> > m_master;
  60     AT m_data;
  61     digraph_arc<NT,AT>* m_prev;
  62     digraph_arc<NT,AT>* m_next;
  63     digraph_node<NT,AT>* m_from;
  64     digraph_node<NT,AT>* m_to;
  65     digraph_arc(const digraph<NT,AT>* owner, digraph_node<NT,AT>* from = 0, digraph_node<NT,AT>* to = 0, const AT& d = AT()) :
  66       m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to)
  67       {
  68       }
  69   };
  70
  71   ////////////////////////////////////////////////////////////////////////////////
  72   // Iterators
  73   ////////////////////////////////////////////////////////////////////////////////
  74
  75   ////////////////////////////////////////////////////////////////////////////////
  76   // Node iterator
  77
  78   // construct a null iterator
  79   template<typename NT, typename AT, typename NRef, typename NPtr>
  80   digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(void)
  81   {
  82   }
  83
  84   // valid iterator
  85   template<typename NT, typename AT, typename NRef, typename NPtr>
  86   digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(digraph_node<NT,AT>* node) :
  87     safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(node->m_master)
  88   {
  89   }
  90
  91   // end iterator
  92   template<typename NT, typename AT, typename NRef, typename NPtr>
  93   digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const digraph<NT,AT>* owner) :
  94     safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(owner)
  95   {
  96   }
  97
  98   // alias an iterator
  99   template<typename NT, typename AT, typename NRef, typename NPtr>
 100   digraph_iterator<NT,AT,NRef,NPtr>::digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator) :
 101     safe_iterator<digraph<NT,AT>,digraph_node<NT,AT> >(iterator)
 102   {
 103   }
 104
 105   // destructor
 106   template<typename NT, typename AT, typename NRef, typename NPtr>
 107   digraph_iterator<NT,AT,NRef,NPtr>::~digraph_iterator(void)
 108   {
 109   }
 110
 111   template<typename NT, typename AT, typename NRef, typename NPtr>
 112   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_iterator<NT,AT,NRef,NPtr>::constify (void) const
 113   {
 114     return digraph_iterator<NT,AT,const NT&,const NT*>(*this);
 115   }
 116
 117   template<typename NT, typename AT, typename NRef, typename NPtr>
 118   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::iterator digraph_iterator<NT,AT,NRef,NPtr>::deconstify (void) const
 119   {
 120     return digraph_iterator<NT,AT,NT&,NT*>(*this);
 121   }
 122
 123   template<typename NT, typename AT, typename NRef, typename NPtr>
 124   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (void)
 125     throw(null_dereference,end_dereference)
 126   {
 127     this->assert_valid();
 128     if (this->node()->m_next)
 129       this->set(this->node()->m_next->m_master);
 130     else
 131       this->set_end();
 132     return *this;
 133   }
 134
 135   template<typename NT, typename AT, typename NRef, typename NPtr>
 136   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator ++ (int)
 137     throw(null_dereference,end_dereference)
 138   {
 139     // post-increment is defined in terms of the pre-increment
 140     digraph_iterator<NT,AT,NRef,NPtr> result(*this);
 141     ++(*this);
 142     return result;
 143   }
 144
 145   template<typename NT, typename AT, typename NRef, typename NPtr>
 146   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& digraph_iterator<NT,AT,NRef,NPtr>::operator -- (void)
 147     throw(null_dereference,end_dereference)
 148   {
 149     this->assert_valid();
 150     if (this->node()->m_prev)
 151       this->set(this->node()->m_prev->m_master);
 152     else
 153       this->set_end();
 154     return *this;
 155   }
 156
 157   template<typename NT, typename AT, typename NRef, typename NPtr>
 158   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator digraph_iterator<NT,AT,NRef,NPtr>::operator -- (int)
 159     throw(null_dereference,end_dereference)
 160   {
 161     // post-decrement is defined in terms of the pre-decrement
 162     digraph_iterator<NT,AT,NRef,NPtr> result(*this);
 163     --(*this);
 164     return result;
 165   }
 166
 167   template<typename NT, typename AT, typename NRef, typename NPtr>
 168   bool digraph_iterator<NT,AT,NRef,NPtr>::operator == (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
 169   {
 170     return equal(r);
 171   }
 172
 173   template<typename NT, typename AT, typename NRef, typename NPtr>
 174   bool digraph_iterator<NT,AT,NRef,NPtr>::operator != (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
 175   {
 176     return !operator==(r);
 177   }
 178
 179   template<typename NT, typename AT, typename NRef, typename NPtr>
 180   bool digraph_iterator<NT,AT,NRef,NPtr>::operator < (const TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::this_iterator& r) const
 181   {
 182     return compare(r) < 0;
 183   }
 184
 185   template<typename NT, typename AT, typename NRef, typename NPtr>
 186   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::reference digraph_iterator<NT,AT,NRef,NPtr>::operator*(void) const
 187     throw(null_dereference,end_dereference)
 188   {
 189     this->assert_valid();
 190     return this->node()->m_data;
 191   }
 192
 193   template<typename NT, typename AT, typename NRef, typename NPtr>
 194   TYPENAME digraph_iterator<NT,AT,NRef,NPtr>::pointer digraph_iterator<NT,AT,NRef,NPtr>::operator->(void) const
 195     throw(null_dereference,end_dereference)
 196   {
 197     return &(operator*());
 198   }
 199
 200   ////////////////////////////////////////////////////////////////////////////////
 201   // Arc Iterator
 202
 203   template<typename NT, typename AT, typename ARef, typename APtr>
 204   digraph_arc_iterator<NT,AT,ARef,APtr>::digraph_arc_iterator(void)
 205   {
 206   }
 207
 208   // valid iterator
 209   template<typename NT, typename AT, typename NRef, typename NPtr>
 210   digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(digraph_arc<NT,AT>* arc) :
 211     safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(arc->m_master)
 212   {
 213   }
 214
 215   // end iterator
 216   template<typename NT, typename AT, typename NRef, typename NPtr>
 217   digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const digraph<NT,AT>* owner) :
 218     safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(owner)
 219   {
 220   }
 221
 222   // alias an iterator
 223   template<typename NT, typename AT, typename NRef, typename NPtr>
 224   digraph_arc_iterator<NT,AT,NRef,NPtr>::digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator) :
 225     safe_iterator<digraph<NT,AT>,digraph_arc<NT,AT> >(iterator)
 226   {
 227   }
 228
 229   template<typename NT, typename AT, typename ARef, typename APtr>
 230   digraph_arc_iterator<NT,AT,ARef,APtr>::~digraph_arc_iterator(void)
 231   {
 232   }
 233
 234   template<typename NT, typename AT, typename NRef, typename NPtr>
 235   TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::const_iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::constify (void) const
 236   {
 237     return digraph_arc_iterator<NT,AT,const AT&,const AT*>(*this);
 238   }
 239
 240   template<typename NT, typename AT, typename NRef, typename NPtr>
 241   TYPENAME digraph_arc_iterator<NT,AT,NRef,NPtr>::iterator digraph_arc_iterator<NT,AT,NRef,NPtr>::deconstify (void) const
 242   {
 243     return digraph_arc_iterator<NT,AT,AT&,AT*>(*this);
 244   }
 245
 246   template<typename NT, typename AT, typename ARef, typename APtr>
 247   TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (void)
 248     throw(null_dereference,end_dereference)
 249   {
 250     this->assert_valid();
 251     if (this->node()->m_next)
 252       this->set(this->node()->m_next->m_master);
 253     else
 254       this->set_end();
 255     return *this;
 256   }
 257
 258   template<typename NT, typename AT, typename ARef, typename APtr>
 259   TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator ++ (int)
 260     throw(null_dereference,end_dereference)
 261   {
 262     // post-increment is defined in terms of the pre-increment
 263     digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);
 264     ++(*this);
 265     return result;
 266   }
 267
 268   template<typename NT, typename AT, typename ARef, typename APtr>
 269   TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (void)
 270     throw(null_dereference,end_dereference)
 271   {
 272     this->assert_valid();
 273     if (this->node()->m_prev)
 274       this->set(this->node()->m_prev->m_master);
 275     else
 276       this->set_end();
 277     return *this;
 278   }
 279
 280   template<typename NT, typename AT, typename ARef, typename APtr>
 281   TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator digraph_arc_iterator<NT,AT,ARef,APtr>::operator -- (int)
 282     throw(null_dereference,end_dereference)
 283   {
 284     // post-decrement is defined in terms of the pre-decrement
 285     digraph_arc_iterator<NT,AT,ARef,APtr> result(*this);
 286     --(*this);
 287     return result;
 288   }
 289
 290   template<typename NT, typename AT, typename ARef, typename APtr>
 291   bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator == (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
 292   {
 293     return equal(r);
 294   }
 295
 296   template<typename NT, typename AT, typename ARef, typename APtr>
 297   bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator != (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
 298   {
 299     return !operator==(r);
 300   }
 301
 302   template<typename NT, typename AT, typename ARef, typename APtr>
 303   bool digraph_arc_iterator<NT,AT,ARef,APtr>::operator < (const TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::this_iterator& r) const
 304   {
 305     return compare(r) < 0;
 306   }
 307
 308   template<typename NT, typename AT, typename ARef, typename APtr>
 309   TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::reference digraph_arc_iterator<NT,AT,ARef,APtr>::operator*(void) const
 310     throw(null_dereference,end_dereference)
 311   {
 312     this->assert_valid();
 313     return this->node()->m_data;
 314   }
 315
 316   template<typename NT, typename AT, typename ARef, typename APtr>
 317   TYPENAME digraph_arc_iterator<NT,AT,ARef,APtr>::pointer digraph_arc_iterator<NT,AT,ARef,APtr>::operator->(void) const
 318     throw(null_dereference,end_dereference)
 319   {
 320     return &(operator*());
 321   }
 322
 323   ////////////////////////////////////////////////////////////////////////////////
 324   // subtype utilities
 325
 326   template<typename NT, typename AT>
 327   TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::constify_arcs(const TYPENAME digraph<NT,AT>::arc_vector& arcs) const
 328     throw(wrong_object,null_dereference,end_dereference)
 329   {
 330     std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;
 331     for (unsigned i = 0; i < arcs.size(); i++)
 332     {
 333       arcs[i].assert_valid(this);
 334       result.push_back(arcs[i].constify());
 335     }
 336     return result;
 337   }
 338
 339   template<typename NT, typename AT>
 340   TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::deconstify_arcs(const TYPENAME digraph<NT,AT>::const_arc_vector& arcs) const
 341     throw(wrong_object,null_dereference,end_dereference)
 342   {
 343     std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
 344     for (unsigned i = 0; i < arcs.size(); i++)
 345     {
 346       arcs[i].assert_valid(this);
 347       result.push_back(arcs[i].deconstify());
 348     }
 349     return result;
 350   }
 351
 352   template<typename NT, typename AT>
 353   TYPENAME digraph<NT,AT>::const_path_vector digraph<NT,AT>::constify_paths(const TYPENAME digraph<NT,AT>::path_vector& paths) const
 354     throw(wrong_object,null_dereference,end_dereference)
 355   {
 356     std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
 357     for (unsigned i = 0; i < paths.size(); i++)
 358       result.push_back(constify_arcs(paths[i]));
 359     return result;
 360   }
 361
 362   template<typename NT, typename AT>
 363   TYPENAME digraph<NT,AT>::path_vector digraph<NT,AT>::deconstify_paths(const TYPENAME digraph<NT,AT>::const_path_vector& paths) const
 364     throw(wrong_object,null_dereference,end_dereference)
 365   {
 366     std::vector<std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result;
 367     for (unsigned i = 0; i < paths.size(); i++)
 368       result.push_back(deconstify_arcs(paths[i]));
 369     return result;
 370   }
 371
 372   template<typename NT, typename AT>
 373   TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::constify_nodes(const TYPENAME digraph<NT,AT>::node_vector& nodes) const
 374     throw(wrong_object,null_dereference,end_dereference)
 375   {
 376     std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
 377     for (unsigned i = 0; i < nodes.size(); i++)
 378     {
 379       nodes[i].assert_valid(this);
 380       result.push_back(nodes[i].constify());
 381     }
 382     return result;
 383   }
 384
 385   template<typename NT, typename AT>
 386   TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::deconstify_nodes(const TYPENAME digraph<NT,AT>::const_node_vector& nodes) const
 387     throw(wrong_object,null_dereference,end_dereference)
 388   {
 389     std::vector<digraph_iterator<NT,AT,NT&,NT*> > result;
 390     for (unsigned i = 0; i < nodes.size(); i++)
 391     {
 392       nodes[i].assert_valid(this);
 393       result.push_back(nodes[i].deconstify());
 394     }
 395     return result;
 396   }
 397
 398   template<typename NT, typename AT>
 399   unsigned digraph<NT,AT>::npos(void)
 400   {
 401     return(unsigned)-1;
 402   }
 403
 404   ////////////////////////////////////////////////////////////////////////////////
 405   // Constructors etc.
 406
 407   template<typename NT, typename AT>
 408   digraph<NT,AT>::digraph(void) :
 409     m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)
 410   {
 411     // node and arc lists are circular double-linked lists
 412     // they start out empty (no dummy end node)
 413   }
 414
 415   template<typename NT, typename AT>
 416   digraph<NT,AT>::~digraph(void)
 417   {
 418     clear();
 419   }
 420
 421   template<typename NT, typename AT>
 422   digraph<NT,AT>::digraph(const digraph<NT,AT>& r) :
 423     m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0)
 424   {
 425     *this = r;
 426   }
 427
 428   template<typename NT, typename AT>
 429   digraph<NT,AT>& digraph<NT,AT>::operator=(const digraph<NT,AT>& r)
 430   {
 431     // make it self-copy safe i.e. a=a; is a valid instruction
 432     if (this == &r) return *this;
 433     clear();
 434     // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents
 435     std::map<digraph_iterator<NT,AT,const NT&,const NT*>, digraph_iterator<NT,AT,NT&,NT*> > xref;
 436     for (digraph_iterator<NT,AT,const NT&,const NT*> n = r.begin(); n != r.end(); n++)
 437       xref[n] = insert(*n);
 438     // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes
 439     for (digraph_arc_iterator<NT,AT, const AT&,const AT*> a = r.arc_begin(); a != r.arc_end(); a++)
 440       arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a);
 441     return *this;
 442   }
 443
 444   ////////////////////////////////////////////////////////////////////////////////
 445   // Basic Node functions
 446
 447   template<typename NT, typename AT>
 448   bool digraph<NT,AT>::empty(void) const
 449   {
 450     return m_nodes_begin == 0;
 451   }
 452
 453   template<typename NT, typename AT>
 454   unsigned digraph<NT,AT>::size(void) const
 455   {
 456     unsigned count = 0;
 457     for (digraph_iterator<NT,AT,const NT&,const NT*> i = begin(); i != end(); i++)
 458       count++;
 459     return count;
 460   }
 461
 462   template<typename NT, typename AT>
 463   TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::insert(const NT& node_data)
 464   {
 465     digraph_node<NT,AT>* new_node = new digraph_node<NT,AT>(this,node_data);
 466     if (!m_nodes_end)
 467     {
 468       // insert into an empty list
 469       m_nodes_begin = new_node;
 470       m_nodes_end = new_node;
 471     }
 472     else
 473     {
 474       // insert at the end of the list
 475       new_node->m_prev = m_nodes_end;
 476       m_nodes_end->m_next = new_node;
 477       m_nodes_end = new_node;
 478     }
 479     return digraph_iterator<NT,AT,NT&,NT*>(new_node);
 480   }
 481
 482   template<typename NT, typename AT>
 483   TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::erase(TYPENAME digraph<NT,AT>::iterator iter)
 484     throw(wrong_object,null_dereference,end_dereference)
 485   {
 486     iter.assert_valid(this);
 487     // remove all arcs connected to this node first
 488     // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too
 489     for (unsigned i = fanin(iter); i--; )
 490       arc_erase(input(iter,i));
 491     for (unsigned j = fanout(iter); j--; )
 492       arc_erase(output(iter,j));
 493     // now unlink the node from the list and delete it
 494     if (iter.node()->m_next)
 495       iter.node()->m_next->m_prev = iter.node()->m_prev;
 496     if (iter.node()->m_prev)
 497       iter.node()->m_prev->m_next = iter.node()->m_next;
 498     digraph_node<NT,AT>* next = iter.node()->m_next;
 499     delete iter.node();
 500     // return the next node in the list
 501     if (next)
 502       return digraph_iterator<NT,AT,NT&,NT*>(next);
 503     else
 504       return digraph_iterator<NT,AT,NT&,NT*>(this);
 505   }
 506
 507   template<typename NT, typename AT>
 508   void digraph<NT,AT>::clear(void)
 509   {
 510     // clearing the nodes also clears the arcs
 511     for (digraph_iterator<NT,AT,NT&,NT*> i = begin(); i != end(); )
 512       i = erase(i);
 513   }
 514
 515   template<typename NT, typename AT>
 516   TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::begin(void) const
 517   {
 518     if (m_nodes_begin)
 519       return digraph_iterator<NT,AT,const NT&,const NT*>(m_nodes_begin);
 520     else
 521       return digraph_iterator<NT,AT,const NT&,const NT*>(this);
 522   }
 523
 524   template<typename NT, typename AT>
 525   TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::begin(void)
 526   {
 527     if (m_nodes_begin)
 528       return digraph_iterator<NT,AT,NT&,NT*>(m_nodes_begin);
 529     else
 530       return digraph_iterator<NT,AT,NT&,NT*>(this);
 531   }
 532
 533   template<typename NT, typename AT>
 534   TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::end(void) const
 535   {
 536     return digraph_iterator<NT,AT,const NT&,const NT*>(this);
 537   }
 538
 539   template<typename NT, typename AT>
 540   TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::end(void)
 541   {
 542     return digraph_iterator<NT,AT,NT&,NT*>(this);
 543   }
 544
 545   template<typename NT, typename AT>
 546   unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::const_iterator iter) const
 547     throw(wrong_object,null_dereference,end_dereference)
 548   {
 549     iter.assert_valid(this);
 550     return iter.node()->m_inputs.size();
 551   }
 552
 553   template<typename NT, typename AT>
 554   unsigned digraph<NT,AT>::fanin(TYPENAME digraph<NT,AT>::iterator iter)
 555     throw(wrong_object,null_dereference,end_dereference)
 556   {
 557     iter.assert_valid(this);
 558     return iter.node()->m_inputs.size();
 559   }
 560
 561   template<typename NT, typename AT>
 562   TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const
 563     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 564   {
 565     iter.assert_valid(this);
 566     if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");
 567     return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_inputs[i]);
 568   }
 569
 570   template<typename NT, typename AT>
 571   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::input(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)
 572     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 573   {
 574     iter.assert_valid(this);
 575     if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input");
 576     return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_inputs[i]);
 577   }
 578
 579   template<typename NT, typename AT>
 580   unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::const_iterator iter) const
 581     throw(wrong_object,null_dereference,end_dereference)
 582   {
 583     iter.assert_valid(this);
 584     return iter.node()->m_outputs.size();
 585   }
 586
 587   template<typename NT, typename AT>
 588   unsigned digraph<NT,AT>::fanout(TYPENAME digraph<NT,AT>::iterator iter)
 589     throw(wrong_object,null_dereference,end_dereference)
 590   {
 591     iter.assert_valid(this);
 592     return iter.node()->m_outputs.size();
 593   }
 594
 595   template<typename NT, typename AT>
 596   TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::const_iterator iter, unsigned i) const
 597     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 598   {
 599     iter.assert_valid(this);
 600     if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");
 601     return digraph_arc_iterator<NT,AT, const AT&,const AT*>(iter.node()->m_outputs[i]);
 602   }
 603
 604   template<typename NT, typename AT>
 605   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::output(TYPENAME digraph<NT,AT>::iterator iter, unsigned i)
 606     throw(wrong_object,null_dereference,end_dereference,std::out_of_range)
 607   {
 608     iter.assert_valid(this);
 609     if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output");
 610     return digraph_arc_iterator<NT,AT,AT&,AT*>(iter.node()->m_outputs[i]);
 611   }
 612
 613   template<typename NT, typename AT>
 614   TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::const_iterator node) const
 615     throw(wrong_object,null_dereference,end_dereference)
 616   {
 617     node.assert_valid(this);
 618     std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;
 619     for (unsigned i = 0; i < fanin(node); i++)
 620       result.push_back(input(node,i));
 621     return result;
 622   }
 623
 624   template<typename NT, typename AT>
 625   TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::inputs(TYPENAME digraph<NT,AT>::iterator node)
 626     throw(wrong_object,null_dereference,end_dereference)
 627   {
 628     node.assert_valid(this);
 629     std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
 630     for (unsigned i = 0; i < fanin(node); i++)
 631       result.push_back(input(node,i));
 632     return result;
 633   }
 634
 635   template<typename NT, typename AT>
 636   TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::const_iterator node) const
 637     throw(wrong_object,null_dereference,end_dereference)
 638   {
 639     node.assert_valid(this);
 640     std::vector<digraph_arc_iterator<NT,AT,const AT&, const AT*> > result;
 641     for (unsigned i = 0; i < fanout(node); i++)
 642       result.push_back(output(node,i));
 643     return result;
 644   }
 645
 646   template<typename NT, typename AT>
 647   TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::outputs(TYPENAME digraph<NT,AT>::iterator node)
 648     throw(wrong_object,null_dereference,end_dereference)
 649   {
 650     node.assert_valid(this);
 651     std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > result;
 652     for (unsigned i = 0; i < fanout(node); i++)
 653       result.push_back(output(node,i));
 654     return result;
 655   }
 656
 657   template<typename NT, typename AT>
 658   unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::const_iterator from,
 659                                          TYPENAME digraph<NT,AT>::const_arc_iterator arc) const
 660     throw(wrong_object,null_dereference,end_dereference)
 661   {
 662     from.assert_valid(this);
 663     arc.assert_valid(this);
 664     for (unsigned i = 0; i < fanout(from); i++)
 665     {
 666       if (output(from,i) == arc)
 667         return i;
 668     }
 669     return digraph<NT,AT>::npos();
 670   }
 671
 672   template<typename NT, typename AT>
 673   unsigned digraph<NT,AT>::output_offset(TYPENAME digraph<NT,AT>::iterator from,
 674                                          TYPENAME digraph<NT,AT>::arc_iterator arc)
 675     throw(wrong_object,null_dereference,end_dereference)
 676   {
 677     from.assert_valid(this);
 678     arc.assert_valid(this);
 679     for (unsigned i = 0; i < fanout(from); i++)
 680     {
 681       if (output(from,i) == arc)
 682         return i;
 683     }
 684     return digraph<NT,AT>::npos();
 685   }
 686
 687   template<typename NT, typename AT>
 688   unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::const_iterator to,
 689                                         TYPENAME digraph<NT,AT>::const_arc_iterator arc) const
 690     throw(wrong_object,null_dereference,end_dereference)
 691   {
 692     to.assert_valid(this);
 693     arc.assert_valid(this);
 694     for (unsigned i = 0; i < fanin(to); i++)
 695     {
 696       if (input(to,i) == arc)
 697         return i;
 698     }
 699     return digraph<NT,AT>::npos();
 700   }
 701
 702   template<typename NT, typename AT>
 703   unsigned digraph<NT,AT>::input_offset(TYPENAME digraph<NT,AT>::iterator to,
 704                                         TYPENAME digraph<NT,AT>::arc_iterator arc)
 705     throw(wrong_object,null_dereference,end_dereference)
 706   {
 707     to.assert_valid(this);
 708     arc.assert_valid(this);
 709     for (unsigned i = 0; i < fanin(to); i++)
 710     {
 711       if (input(to,i) == arc)
 712         return i;
 713     }
 714     return digraph<NT,AT>::npos();
 715   }
 716
 717   ////////////////////////////////////////////////////////////////////////////////
 718   // Basic Arc functions
 719
 720   template<typename NT, typename AT>
 721   bool digraph<NT,AT>::arc_empty(void) const
 722   {
 723     return m_arcs_end == 0;
 724   }
 725
 726   template<typename NT, typename AT>
 727   unsigned digraph<NT,AT>::arc_size(void) const
 728   {
 729     unsigned count = 0;
 730     for (digraph_arc_iterator<NT,AT, const AT&,const AT*> i = arc_begin(); i != arc_end(); i++)
 731       count++;
 732     return count;
 733   }
 734
 735   template<typename NT, typename AT>
 736   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_insert(TYPENAME digraph<NT,AT>::iterator from,
 737                                                                    TYPENAME digraph<NT,AT>::iterator to,
 738                                                                    const AT& arc_data)
 739     throw(wrong_object,null_dereference,end_dereference)
 740   {
 741     from.assert_valid(this);
 742     to.assert_valid(this);
 743     // create the new arc and link it in to the arc list
 744     digraph_arc<NT,AT>* new_arc = new digraph_arc<NT,AT>(this, from.node(), to.node(), arc_data);
 745     if (!m_arcs_end)
 746     {
 747       // insert into an empty list
 748       m_arcs_begin = new_arc;
 749       m_arcs_end = new_arc;
 750     }
 751     else
 752     {
 753       // insert at the end of the list
 754       new_arc->m_prev = m_arcs_end;
 755       m_arcs_end->m_next = new_arc;
 756       m_arcs_end = new_arc;
 757     }
 758     // add this arc to the inputs and outputs of the end nodes
 759     from.node()->m_outputs.push_back(new_arc);
 760     to.node()->m_inputs.push_back(new_arc);
 761     return digraph_arc_iterator<NT,AT,AT&,AT*>(new_arc);
 762   }
 763
 764   template<typename NT, typename AT>
 765   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_erase(TYPENAME digraph<NT,AT>::arc_iterator iter)
 766     throw(wrong_object,null_dereference,end_dereference)
 767   {
 768     iter.assert_valid(this);
 769     // first remove this arc's pointers from the from/to nodes
 770     for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); )
 771     {
 772       if (*i == iter.node())
 773         i = iter.node()->m_to->m_inputs.erase(i);
 774       else
 775         i++;
 776     }
 777     for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); )
 778     {
 779       if (*o == iter.node())
 780         o = iter.node()->m_from->m_outputs.erase(o);
 781       else
 782         o++;
 783     }
 784     // now unlink the arc from the list and delete it
 785     if (iter.node()->m_next)
 786       iter.node()->m_next->m_prev = iter.node()->m_prev;
 787     if (iter.node()->m_prev)
 788       iter.node()->m_prev->m_next = iter.node()->m_next;
 789     digraph_arc<NT,AT>* next = iter.node()->m_next;
 790     delete iter.node();
 791     if (next)
 792       return digraph_arc_iterator<NT,AT,AT&,AT*>(next);
 793     else
 794       return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
 795   }
 796
 797   template<typename NT, typename AT>
 798   void digraph<NT,AT>::arc_clear(void)
 799   {
 800     for (digraph_arc_iterator<NT,AT,AT&,AT*> a = arc_begin(); a != arc_end(); )
 801       a = arc_erase(a);
 802   }
 803
 804   template<typename NT, typename AT>
 805   TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_begin(void) const
 806   {
 807     if (m_arcs_begin)
 808       return digraph_arc_iterator<NT,AT, const AT&,const AT*>(m_arcs_begin);
 809     else
 810       return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);
 811   }
 812
 813   template<typename NT, typename AT>
 814   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_begin(void)
 815   {
 816     if (m_arcs_begin)
 817       return digraph_arc_iterator<NT,AT,AT&,AT*>(m_arcs_begin);
 818     else
 819       return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
 820   }
 821
 822   template<typename NT, typename AT>
 823   TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::arc_end(void) const
 824   {
 825     return digraph_arc_iterator<NT,AT, const AT&,const AT*>(this);
 826   }
 827
 828   template<typename NT, typename AT>
 829   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::arc_end(void)
 830   {
 831     return digraph_arc_iterator<NT,AT,AT&,AT*>(this);
 832   }
 833
 834   template<typename NT, typename AT>
 835   TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const
 836     throw(wrong_object,null_dereference,end_dereference)
 837   {
 838     iter.assert_valid(this);
 839     return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_from);
 840   }
 841
 842   template<typename NT, typename AT>
 843   TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_from(TYPENAME digraph<NT,AT>::arc_iterator iter)
 844     throw(wrong_object,null_dereference,end_dereference)
 845   {
 846     iter.assert_valid(this);
 847     return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_from);
 848   }
 849
 850   template<typename NT, typename AT>
 851   TYPENAME digraph<NT,AT>::const_iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::const_arc_iterator iter) const
 852     throw(wrong_object,null_dereference,end_dereference)
 853   {
 854     iter.assert_valid(this);
 855     return digraph_iterator<NT,AT,const NT&,const NT*>(iter.node()->m_to);
 856   }
 857
 858   template<typename NT, typename AT>
 859   TYPENAME digraph<NT,AT>::iterator digraph<NT,AT>::arc_to(TYPENAME digraph<NT,AT>::arc_iterator iter)
 860     throw(wrong_object,null_dereference,end_dereference)
 861   {
 862     iter.assert_valid(this);
 863     return digraph_iterator<NT,AT,NT&,NT*>(iter.node()->m_to);
 864   }
 865
 866   template<typename NT, typename AT>
 867   void digraph<NT,AT>::arc_move(TYPENAME digraph<NT,AT>::arc_iterator arc,
 868                                 TYPENAME digraph<NT,AT>::iterator from,
 869                                 TYPENAME digraph<NT,AT>::iterator to)
 870     throw(wrong_object,null_dereference,end_dereference)
 871   {
 872     arc_move_to(arc,to);
 873     arc_move_from(arc,from);
 874   }
 875
 876   template<typename NT, typename AT>
 877   void digraph<NT,AT>::arc_move_from(TYPENAME digraph<NT,AT>::arc_iterator arc,
 878                                      TYPENAME digraph<NT,AT>::iterator from)
 879     throw(wrong_object,null_dereference,end_dereference)
 880   {
 881     arc.assert_valid(this);
 882     from.assert_valid(this);
 883     for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator o = arc.node()->m_from->m_outputs.begin(); o != arc.node()->m_from->m_outputs.end(); )
 884     {
 885       if (*o == arc.node())
 886         o = arc.node()->m_from->m_outputs.erase(o);
 887       else
 888         o++;
 889     }
 890     from.node()->m_outputs.push_back(arc.node());
 891     arc.node()->m_from = from.node();
 892   }
 893
 894   template<typename NT, typename AT>
 895   void digraph<NT,AT>::arc_move_to(TYPENAME digraph<NT,AT>::arc_iterator arc,
 896                                    TYPENAME digraph<NT,AT>::iterator to)
 897     throw(wrong_object,null_dereference,end_dereference)
 898   {
 899     arc.assert_valid(this);
 900     to.assert_valid(this);
 901     for (TYPENAME std::vector<digraph_arc<NT,AT>*>::iterator i = arc.node()->m_to->m_inputs.begin(); i != arc.node()->m_to->m_inputs.end(); )
 902     {
 903       if (*i == arc.node())
 904         i = arc.node()->m_to->m_inputs.erase(i);
 905       else
 906         i++;
 907     }
 908     to.node()->m_inputs.push_back(arc.node());
 909     arc.node()->m_to = to.node();
 910   }
 911
 912   template<typename NT, typename AT>
 913   void digraph<NT,AT>::arc_flip(TYPENAME digraph<NT,AT>::arc_iterator arc)
 914     throw(wrong_object,null_dereference,end_dereference)
 915   {
 916     arc_move(arc,arc_to(arc),arc_from(arc));
 917   }
 918
 919   ////////////////////////////////////////////////////////////////////////////////
 920   // Adjacency Algorithms
 921
 922   template<typename NT, typename AT>
 923   bool digraph<NT,AT>::adjacent(TYPENAME digraph<NT,AT>::const_iterator from,
 924                                 TYPENAME digraph<NT,AT>::const_iterator to) const
 925     throw(wrong_object,null_dereference,end_dereference)
 926   {
 927     return adjacent_arc(from,to) != arc_end();
 928   }
 929
 930   template<typename NT, typename AT>
 931   bool digraph<NT,AT>::adjacent(TYPENAME digraph<NT,AT>::iterator from,
 932                                 TYPENAME digraph<NT,AT>::iterator to)
 933     throw(wrong_object,null_dereference,end_dereference)
 934   {
 935     return adjacent_arc(from,to) != arc_end();
 936   }
 937
 938   template<typename NT, typename AT>
 939   TYPENAME digraph<NT,AT>::const_arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::const_iterator from,
 940                                                                            TYPENAME digraph<NT,AT>::const_iterator to) const
 941     throw(wrong_object,null_dereference,end_dereference)
 942   {
 943     from.assert_valid(this);
 944     to.assert_valid(this);
 945     for (unsigned arc = 0; arc < fanout(from); arc++)
 946     {
 947       if (arc_to(output(from, arc)) == to)
 948         return output(from,arc);
 949     }
 950     return arc_end();
 951   }
 952
 953   template<typename NT, typename AT>
 954   TYPENAME digraph<NT,AT>::arc_iterator digraph<NT,AT>::adjacent_arc(TYPENAME digraph<NT,AT>::iterator from,
 955                                                                      TYPENAME digraph<NT,AT>::iterator to)
 956     throw(wrong_object,null_dereference,end_dereference)
 957   {
 958     return adjacent_arc(from.constify(), to.constify()).deconstify();
 959   }
 960
 961   template<typename NT, typename AT>
 962   TYPENAME digraph<NT,AT>::const_arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::const_iterator from,
 963                                                                           TYPENAME digraph<NT,AT>::const_iterator to) const
 964     throw(wrong_object,null_dereference,end_dereference)
 965   {
 966     from.assert_valid(this);
 967     to.assert_valid(this);
 968     std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > result;
 969     for (unsigned arc = 0; arc < fanout(from); arc++)
 970     {
 971       if (arc_to(output(from, arc)) == to)
 972         result.push_back(output(from,arc));
 973     }
 974     return result;
 975   }
 976
 977   template<typename NT, typename AT>
 978   TYPENAME digraph<NT,AT>::arc_vector digraph<NT,AT>::adjacent_arcs(TYPENAME digraph<NT,AT>::iterator from,
 979                                                                     TYPENAME digraph<NT,AT>::iterator to)
 980     throw(wrong_object,null_dereference,end_dereference)
 981   {
 982     return deconstify_arcs(adjacent_arcs(from.constify(), to.constify()));
 983   }
 984
 985   template<typename NT, typename AT>
 986   TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::const_iterator to) const
 987     throw(wrong_object,null_dereference,end_dereference)
 988   {
 989     std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
 990     for (unsigned arc = 0; arc < fanin(to); arc++)
 991     {
 992       digraph_iterator<NT,AT,const NT&,const NT*> from = arc_from(input(to, arc));
 993       if (std::find(result.begin(), result.end(), from) == result.end())
 994         result.push_back(from);
 995     }
 996     return result;
 997   }
 998
 999   template<typename NT, typename AT>
1000   TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::input_adjacencies(TYPENAME digraph<NT,AT>::iterator to)
1001     throw(wrong_object,null_dereference,end_dereference)
1002   {
1003     return deconstify_nodes(input_adjacencies(to.constify()));
1004   }
1005
1006   template<typename NT, typename AT>
1007   TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::const_iterator from) const
1008     throw(wrong_object,null_dereference,end_dereference)
1009   {
1010     std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1011     for (unsigned arc = 0; arc < fanout(from); arc++)
1012     {
1013       digraph_iterator<NT,AT,const NT&,const NT*> to = arc_to(output(from, arc));
1014       if (find(result.begin(), result.end(), to) == result.end())
1015         result.push_back(to);
1016     }
1017     return result;
1018   }
1019
1020   template<typename NT, typename AT>
1021   TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::output_adjacencies(TYPENAME digraph<NT,AT>::iterator from)
1022     throw(wrong_object,null_dereference,end_dereference)
1023   {
1024     return deconstify_nodes(output_adjacencies(from.constify()));
1025   }
1026
1027   ////////////////////////////////////////////////////////////////////////////////
1028   // Topographical Sort Algorithms
1029
1030   template<typename NT, typename AT>
1031   std::pair<TYPENAME digraph<NT,AT>::const_node_vector, TYPENAME digraph<NT,AT>::const_arc_vector>
1032   digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const
1033   {
1034     std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1035     std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > errors;
1036     // build a map containing the number of fanins to each node that must be visited before this one
1037     std::map<digraph_iterator<NT,AT,const NT&,const NT*>,unsigned> fanin_map;
1038     for (digraph_iterator<NT,AT,const NT&,const NT*> n = begin(); n != end(); n++)
1039     {
1040       unsigned predecessors = 0;
1041       // only count predecessors connected by selected arcs
1042       for (unsigned f = 0; f < fanin(n); f++)
1043       {
1044         digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(n,f);
1045         digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);
1046         if (!select || select(*this,input_arc))
1047           predecessors++;
1048       }
1049       if (predecessors == 0)
1050       {
1051         result.push_back(n);
1052       }
1053       else
1054       {
1055         fanin_map[n] = predecessors;
1056       }
1057     }
1058     // main algorithm applies the topographical sort repeatedly. For a DAG, it
1059     // will complete first time. However, with backward arcs, the first
1060     // iteration will fail. The algorithm then tries breaking random arcs to try
1061     // to get an ordering.
1062     for(unsigned i = 0; !fanin_map.empty(); )
1063     {
1064       // now visit each node in traversal order, decrementing the fanin count of
1065       // all successors. As each successor's fanin count goes to zero, it is
1066       // appended to the result.
1067       for (; i < result.size(); i++)
1068       {
1069         // Note: dereferencing gives us a node iterator
1070         digraph_iterator<NT,AT,const NT&,const NT*> current = result[i];
1071         for (unsigned f = 0; f < fanout(current); f++)
1072         {
1073           // only consider successors connected by selected arcs
1074           digraph_arc_iterator<NT,AT, const AT&,const AT*> output_arc = output(current, f);
1075           digraph_iterator<NT,AT,const NT&,const NT*> successor = arc_to(output_arc);
1076           if (!select || select(*this,output_arc))
1077           {
1078             // don't consider arcs that have been eliminated to break a loop
1079             if (fanin_map.find(successor) != fanin_map.end())
1080             {
1081               --fanin_map[successor];
1082               if ((fanin_map[successor]) == 0)
1083               {
1084                 result.push_back(successor);
1085                 fanin_map.erase(fanin_map.find(successor));
1086               }
1087             }
1088           }
1089         }
1090       }
1091       if (!fanin_map.empty())
1092       {
1093         // there must be backward arcs preventing completion
1094         // try removing arcs from the sort to get a partial ordering containing all the nodes
1095
1096         // select an arc that is still relevant to the sort and break it
1097         // first select a node that has non-zero fanin and its predecessor that has non-zero fanin
1098         digraph_iterator<NT,AT,const NT&,const NT*> stuck_node = fanin_map.begin()->first;
1099         for (unsigned f = 0; f < fanin(stuck_node); f++)
1100         {
1101           // now successively remove input arcs that are still part of the sort until the fanin reduces to zero
1102           // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm
1103           digraph_arc_iterator<NT,AT, const AT&,const AT*> input_arc = input(stuck_node, f);
1104           if (!select || select(*this,input_arc))
1105           {
1106             digraph_iterator<NT,AT,const NT&,const NT*> predecessor = arc_from(input_arc);
1107             if (fanin_map.find(predecessor) != fanin_map.end())
1108             {
1109               // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop
1110               errors.push_back(input_arc);
1111               --fanin_map[stuck_node];
1112               if ((fanin_map[stuck_node]) == 0)
1113               {
1114                 result.push_back(stuck_node);
1115                 fanin_map.erase(fanin_map.find(stuck_node));
1116                 break;
1117               }
1118             }
1119           }
1120         }
1121       }
1122     }
1123     return std::make_pair(result,errors);
1124   }
1125
1126   template<typename NT, typename AT>
1127   std::pair<TYPENAME digraph<NT,AT>::node_vector, TYPENAME digraph<NT,AT>::arc_vector>
1128   digraph<NT,AT>::sort(TYPENAME digraph<NT,AT>::arc_select_fn select)
1129   {
1130     std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,
1131               std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > const_result =
1132       const_cast<const digraph<NT,AT>*>(this)->sort(select);
1133
1134     std::pair<std::vector<digraph_iterator<NT,AT,NT&,NT*> >,
1135               std::vector<digraph_arc_iterator<NT,AT,AT&,AT*> > > result =
1136       std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second));
1137     return result;
1138   }
1139
1140   template<typename NT, typename AT>
1141   TYPENAME digraph<NT,AT>::const_node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select) const
1142   {
1143     std::pair<std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >,
1144               std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result = sort(select);
1145     if (result.second.empty()) return result.first;
1146     return std::vector<digraph_iterator<NT,AT,const NT&,const NT*> >();
1147   }
1148
1149   template<typename NT, typename AT>
1150   TYPENAME digraph<NT,AT>::node_vector digraph<NT,AT>::dag_sort(TYPENAME digraph<NT,AT>::arc_select_fn select)
1151   {
1152     return deconstify_nodes(const_cast<const digraph<NT,AT>*>(this)->dag_sort(select));
1153   }
1154   ////////////////////////////////////////////////////////////////////////////////
1155   // Path Algorithms
1156
1157   template<typename NT, typename AT>
1158   bool digraph<NT,AT>::path_exists_r(TYPENAME digraph<NT,AT>::const_iterator from,
1159                                      TYPENAME digraph<NT,AT>::const_iterator to,
1160                                      TYPENAME digraph<NT,AT>::const_iterator_set& visited,
1161                                      TYPENAME digraph<NT,AT>::arc_select_fn select) const
1162     throw(wrong_object,null_dereference,end_dereference)
1163   {
1164     // Recursive part of the digraph::path_exists function. This is based on a
1165     // depth first search algorithm and stops the moment it finds a path
1166     // regardless of its length. Simply traverse every output and recurse on that
1167     // node until we find the to node or run out of things to recurse on. However,
1168     // to avoid infinite recursion due to cycles in the graph, I need to maintain
1169     // a set of visited nodes. The visited set is updated when a candidate is
1170     // found but tested before the recursion on the candidate so that the number of
1171     // function calls is minimised.
1172     for (unsigned i = 0; i < fanout(from); i++)
1173     {
1174       digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);
1175       if (!select || select(*this, arc))
1176       {
1177         digraph_iterator<NT,AT,const NT&,const NT*> node = arc_to(arc);
1178         // if the node is the target, return immediately
1179         if (node == to) return true;
1180         // update the visited set and give up if the insert fails, which indicates that the node has already been visited
1181         if (!(visited.insert(node).second)) return false;
1182         // now recurse - a path exists from from to to if a path exists from an adjacent node to to
1183         if (path_exists_r(node,to,visited,select)) return true;
1184       }
1185     }
1186     return false;
1187   }
1188
1189   template<typename NT, typename AT>
1190   bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::const_iterator from,
1191                                    TYPENAME digraph<NT,AT>::const_iterator to,
1192                                    TYPENAME digraph<NT,AT>::arc_select_fn select) const
1193     throw(wrong_object,null_dereference,end_dereference)
1194   {
1195     // set up the recursion with its initial visited set and then recurse
1196     std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
1197     visited.insert(from);
1198     return path_exists_r(from, to, visited, select);
1199   }
1200
1201   template<typename NT, typename AT>
1202   bool digraph<NT,AT>::path_exists(TYPENAME digraph<NT,AT>::iterator from,
1203                                    TYPENAME digraph<NT,AT>::iterator to,
1204                                    TYPENAME digraph<NT,AT>::arc_select_fn select)
1205     throw(wrong_object,null_dereference,end_dereference)
1206   {
1207     return path_exists(from.constify(), to.constify(), select);
1208   }
1209
1210   template<typename NT, typename AT>
1211   void digraph<NT,AT>::all_paths_r(TYPENAME digraph<NT,AT>::const_iterator from,
1212                                    TYPENAME digraph<NT,AT>::const_iterator to,
1213                                    TYPENAME digraph<NT,AT>::const_arc_vector& so_far,
1214                                    TYPENAME digraph<NT,AT>::const_path_vector& result,
1215                                    TYPENAME digraph<NT,AT>::arc_select_fn select) const
1216     throw(wrong_object,null_dereference,end_dereference)
1217   {
1218     // This is the recursive part of the all_paths function. The field so_far
1219     // contains the path so far so that when 'to' is reached, the path is
1220     // complete. It serves the same purpose as the visited set in the path_exists
1221     // function except that it also preserves the path order. It also serves the
1222     // purpose of detecting cycles and thus stopping infinite recursion. Every
1223     // time the recursion reaches the to node, a copy of so_far is appended to the
1224     // path set.
1225     for (unsigned i = 0; i < fanout(from); i++)
1226     {
1227       digraph_arc_iterator<NT,AT, const AT&,const AT*> candidate = output(from,i);
1228       // assert_valid that the arc is selected and then assert_valid that the candidate has not
1229       // been visited on this path and only allow further recursion if it hasn't
1230       if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end())
1231       {
1232         // extend the path tracing the route to this arc
1233         so_far.push_back(candidate);
1234         // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse
1235         if (arc_to(candidate) == to)
1236           result.push_back(so_far);
1237         else
1238           all_paths_r(arc_to(candidate),to,so_far,result,select);
1239         so_far.pop_back();
1240       }
1241     }
1242   }
1243
1244   template<typename NT, typename AT>
1245   TYPENAME digraph<NT,AT>::const_path_vector
1246   digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::const_iterator from,
1247                             TYPENAME digraph<NT,AT>::const_iterator to,
1248                             TYPENAME digraph<NT,AT>::arc_select_fn select) const
1249     throw(wrong_object,null_dereference,end_dereference)
1250   {
1251     // set up the recursion with empty data fields and then recurse
1252     std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
1253     std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > so_far;
1254     all_paths_r(from, to, so_far, result, select);
1255     return result;
1256   }
1257
1258   template<typename NT, typename AT>
1259   TYPENAME digraph<NT,AT>::path_vector
1260   digraph<NT,AT>::all_paths(TYPENAME digraph<NT,AT>::iterator from,
1261                             TYPENAME digraph<NT,AT>::iterator to,
1262                             TYPENAME digraph<NT,AT>::arc_select_fn select)
1263     throw(wrong_object,null_dereference,end_dereference)
1264   {
1265     return deconstify_paths(all_paths(from.constify(), to.constify(), select));
1266   }
1267
1268   template<typename NT, typename AT>
1269   void digraph<NT,AT>::reachable_nodes_r(TYPENAME digraph<NT,AT>::const_iterator from,
1270                                          TYPENAME digraph<NT,AT>::const_iterator_set& visited,
1271                                          TYPENAME digraph<NT,AT>::arc_select_fn select) const
1272     throw(wrong_object,null_dereference,end_dereference)
1273   {
1274     // The recursive part of the reachable_nodes function.
1275     // This is a depth-first traversal again but this time it carries on to find all the reachable nodes
1276     // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles
1277     for (unsigned i = 0; i < fanout(from); i++)
1278     {
1279       digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = output(from,i);
1280       if (!select || select(*this,arc))
1281       {
1282         digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_to(arc);
1283         if (visited.insert(candidate).second)
1284           reachable_nodes_r(candidate,visited,select);
1285       }
1286     }
1287   }
1288
1289   template<typename NT, typename AT>
1290   TYPENAME digraph<NT,AT>::const_node_vector
1291   digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::const_iterator from,
1292                                   TYPENAME digraph<NT,AT>::arc_select_fn select) const
1293     throw(wrong_object,null_dereference,end_dereference)
1294   {
1295     // seed the recursion, marking the starting node as already visited
1296     std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
1297     visited.insert(from);
1298     reachable_nodes_r(from, visited, select);
1299     // convert the visited set into the required output form
1300     // exclude the starting node
1301     std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1302     for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)
1303       if (*i != from)
1304         result.push_back(*i);
1305     return result;
1306   }
1307
1308   template<typename NT, typename AT>
1309   TYPENAME digraph<NT,AT>::node_vector
1310   digraph<NT,AT>::reachable_nodes(TYPENAME digraph<NT,AT>::iterator from,
1311                                   TYPENAME digraph<NT,AT>::arc_select_fn select)
1312     throw(wrong_object,null_dereference,end_dereference)
1313   {
1314     return deconstify_nodes(reachable_nodes(from.constify(), select));
1315   }
1316
1317   template<typename NT, typename AT>
1318   void digraph<NT,AT>::reaching_nodes_r(TYPENAME digraph<NT,AT>::const_iterator to,
1319                                         TYPENAME digraph<NT,AT>::const_iterator_set& visited,
1320                                         TYPENAME digraph<NT,AT>::arc_select_fn select) const
1321     throw(wrong_object,null_dereference,end_dereference)
1322   {
1323     // The recursive part of the reaching_nodes function.
1324     // Just like the reachable_nodes_r function but it goes backwards
1325     for (unsigned i = 0; i < fanin(to); i++)
1326     {
1327       digraph_arc_iterator<NT,AT, const AT&,const AT*> arc = input(to,i);
1328       if (!select || select(*this,arc))
1329       {
1330         digraph_iterator<NT,AT,const NT&,const NT*> candidate = arc_from(input(to,i));
1331         if (visited.insert(candidate).second)
1332           reaching_nodes_r(candidate,visited,select);
1333       }
1334     }
1335   }
1336
1337   template<typename NT, typename AT>
1338   TYPENAME digraph<NT,AT>::const_node_vector
1339   digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::const_iterator to,
1340                                  TYPENAME digraph<NT,AT>::arc_select_fn select) const
1341     throw(wrong_object,null_dereference,end_dereference)
1342   {
1343     // seed the recursion, marking the starting node as already visited
1344     std::set<digraph_iterator<NT,AT,const NT&,const NT*> > visited;
1345     visited.insert(to);
1346     reaching_nodes_r(to,visited,select);
1347     // convert the visited set into the required output form
1348     // exclude the end node
1349     std::vector<digraph_iterator<NT,AT,const NT&,const NT*> > result;
1350     for (TYPENAME std::set<digraph_iterator<NT,AT,const NT&,const NT*> >::iterator i = visited.begin(); i != visited.end(); i++)
1351       if (*i != to)
1352         result.push_back(*i);
1353     return result;
1354   }
1355
1356   template<typename NT, typename AT>
1357   TYPENAME digraph<NT,AT>::node_vector
1358   digraph<NT,AT>::reaching_nodes(TYPENAME digraph<NT,AT>::iterator to,
1359                                  TYPENAME digraph<NT,AT>::arc_select_fn select)
1360     throw(wrong_object,null_dereference,end_dereference)
1361   {
1362     return deconstify_nodes(reaching_nodes(to.constify(),select));
1363   }
1364
1365   ////////////////////////////////////////////////////////////////////////////////
1366   // Shortest Path Algorithms
1367
1368   template<typename NT, typename AT>
1369   TYPENAME digraph<NT,AT>::const_arc_vector
1370   digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::const_iterator from,
1371                                 TYPENAME digraph<NT,AT>::const_iterator to,
1372                                 TYPENAME digraph<NT,AT>::arc_select_fn select) const
1373     throw(wrong_object,null_dereference,end_dereference)
1374   {
1375     std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > paths = all_paths(from,to,select);
1376     std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > shortest;
1377     for (TYPENAME std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > >::iterator i = paths.begin(); i != paths.end(); i++)
1378       if (shortest.empty() || i->size() < shortest.size())
1379         shortest = *i;
1380     return shortest;
1381   }
1382
1383   template<typename NT, typename AT>
1384   TYPENAME digraph<NT,AT>::arc_vector
1385   digraph<NT,AT>::shortest_path(TYPENAME digraph<NT,AT>::iterator from,
1386                                 TYPENAME digraph<NT,AT>::iterator to,
1387                                 TYPENAME digraph<NT,AT>::arc_select_fn select)
1388     throw(wrong_object,null_dereference,end_dereference)
1389   {
1390     return deconstify_arcs(shortest_path(from.constify(),to.constify(),select));
1391   }
1392
1393   template<typename NT, typename AT>
1394   TYPENAME digraph<NT,AT>::const_path_vector
1395   digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::const_iterator from,
1396                                  TYPENAME digraph<NT,AT>::arc_select_fn select) const
1397     throw(wrong_object,null_dereference,end_dereference)
1398   {
1399     from.assert_valid(this);
1400     // This is an unweighted shortest path algorithm based on the algorithm from
1401     // Weiss's book. This is essentially a breadth-first traversal or graph
1402     // colouring algorithm. It is an iterative algorithm, so no recursion here! It
1403     // works by creating a node queue initialised with the starting node. It then
1404     // consumes the queue from front to back. For each node, it finds the
1405     // successors and appends them to the queue. If a node is already 'known' it
1406     // is not added - this avoids cycles. Thus the queue insert ordering
1407     // represents the breadth-first ordering. On the way it creates a map of
1408     // visited nodes. This is a map not a set because it also stores the arc that
1409     // nominated this node as a shortest path. The full path can then be recreated
1410     // from the map by just walking back through the predecessors. The depth (or
1411     // colour) can be determined by the path length.
1412     std::vector<std::vector<digraph_arc_iterator<NT,AT,const AT&,const AT*> > > result;
1413     // initialise the iteration by creating a queue and adding the start node
1414     std::deque<digraph_iterator<NT,AT,const NT&,const NT*> > nodes;
1415     nodes.push_back(from);
1416     // Create a map to store the set of known nodes mapped to their predecessor
1417     // arcs. Initialise it with the current node, which has no predecessor. Note
1418     // that the algorithm uses the feature of digraph iterators that they can be
1419     // null iterators and that all null iterators are equal.
1420     typedef std::map<digraph_iterator<NT,AT,const NT&,const NT*>,
1421                      digraph_arc_iterator<NT,AT,const AT&,const AT*> > known_map;
1422     known_map known;
1423     known.insert(std::make_pair(from,digraph_arc_iterator<NT,AT, const AT&,const AT*>()));
1424     // now the iterative part of the algorithm
1425     while(!nodes.empty())
1426     {
1427       // pop the queue to get the next node to process - unfortunately the STL
1428       // deque::pop does not return the popped value
1429       digraph_iterator<NT,AT,const NT&,const NT*> current = nodes.front();
1430       nodes.pop_front();
1431       // now visit all the successors
1432       for (unsigned i = 0; i < fanout(current); i++)
1433       {
1434         digraph_arc_iterator<NT,AT, const AT&,const AT*> next_arc = output(current,i);
1435         // assert_valid whether the successor arc is a selected arc and can be part of a path
1436         if (!select || select(*this,next_arc))
1437         {
1438           digraph_iterator<NT,AT,const NT&,const NT*> next = arc_to(next_arc);
1439           // Discard any successors that are known because to be known already they
1440           // must have another shorter path. Otherwise add the successor node to the
1441           // queue to be visited later. To minimise the overhead of map lookup I use
1442           // the usual trick of trying to insert the node and determining whether
1443           // the node was known by the success or failure of the insertion - this is
1444           // a Good STL Trick (TM).
1445           if (known.insert(std::make_pair(next,next_arc)).second)
1446             nodes.push_back(next);
1447         }
1448       }
1449     }
1450     // The map contains the results as an unordered set of nodes, mapped to their
1451     // predecessor arcs and weight. This now needs to be converted into a set of
1452     // paths. This is done by starting with a node from the map, finding its
1453     // predecessor arc and therefore its predecessor node, looking that up in the
1454     // map to find its predecessor and so on until the start node is reached (it
1455     // has a null predecessor). Note that the known set includes the from node
1456     // which does not generate a path.
1457     for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++)
1458     {
1459       if (i->first != from)
1460       {
1461         const_arc_vector this_path;
1462         for (TYPENAME known_map::iterator node = i;
1463              node->second.valid();
1464              node = known.find(arc_from(node->second)))
1465           this_path.insert(this_path.begin(),node->second);
1466         result.push_back(this_path);
1467       }
1468     }
1469     return result;
1470   }
1471
1472   template<typename NT, typename AT>
1473   TYPENAME digraph<NT,AT>::path_vector
1474   digraph<NT,AT>::shortest_paths(TYPENAME digraph<NT,AT>::iterator from,
1475                                  TYPENAME digraph<NT,AT>::arc_select_fn select)
1476     throw(wrong_object,null_dereference,end_dereference)
1477   {
1478     return deconstify_paths(shortest_paths(from.constify(),select));
1479   }
1480
1481   ////////////////////////////////////////////////////////////////////////////////
1482
1483 } // end namespace stlplus