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

   1 #ifndef STLPLUS_DIGRAPH
   2 #define STLPLUS_DIGRAPH
   3 ////////////////////////////////////////////////////////////////////////////////
   4
   5 //   Author:    Andy Rushton
   6 //   Copyright: (c) Southampton University 1999-2004
   7 //              (c) Andy Rushton           2004 onwards
   8 //   License:   BSD License, see ../docs/license.html
   9
  10 //   STL-style Directed graph template component
  11 //   Digraph stands for directed-graph, i.e. all arcs have a direction
  12
  13 ////////////////////////////////////////////////////////////////////////////////
  14 #include "containers_fixes.hpp"
  15 #include "safe_iterator.hpp"
  16 #include "exceptions.hpp"
  17 #include <vector>
  18 #include <map>
  19 #include <set>
  20
  21 namespace stlplus
  22 {
  23
  24   ////////////////////////////////////////////////////////////////////////////////
  25   // Internals
  26
  27   template<typename NT, typename AT> class digraph_node;
  28   template<typename NT, typename AT> class digraph_arc;
  29   template<typename NT, typename AT> class digraph;
  30
  31   ////////////////////////////////////////////////////////////////////////////////
  32   // The Digraph iterator classes
  33   // a digraph_iterator points to a node whilst a digraph_arc_iterator points to an arc
  34   // Note that these are redefined as:
  35   //   digraph<NT,AT>::iterator           - points to a non-const node
  36   //   digraph<NT,AT>::const_iterator     - points to a const node
  37   //   digraph<NT,AT>::arc_iterator       - points to a non-const arc
  38   //   digraph<NT,AT>::const_arc_iterator - points to a const arc
  39   // and this is the form in which they should be used
  40
  41   template<typename NT, typename AT, typename NRef, typename NPtr>
  42   class digraph_iterator : public safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >
  43   {
  44   public:
  45     friend class digraph<NT,AT>;
  46
  47     // local type definitions
  48     // an iterator points to an object whilst a const_iterator points to a const object
  49     typedef digraph_iterator<NT,AT,NT&,NT*> iterator;
  50     typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;
  51     typedef digraph_iterator<NT,AT,NRef,NPtr> this_iterator;
  52     typedef NRef reference;
  53     typedef NPtr pointer;
  54
  55     // constructor to create a null iterator - you must assign a valid value to this iterator before using it
  56     digraph_iterator(void);
  57     ~digraph_iterator(void);
  58
  59     // Type conversion methods allow const_iterator and iterator to be converted
  60     // convert an iterator/const_iterator to a const_iterator
  61     const_iterator constify(void) const;
  62     // convert an iterator/const_iterator to an iterator
  63     iterator deconstify(void) const;
  64
  65     // increment/decrement operators used to step through the set of all nodes in a graph
  66     // it is only legal to increment a valid iterator
  67     // pre-increment
  68     this_iterator& operator ++ (void)
  69       throw(null_dereference,end_dereference);
  70     // post-increment
  71     this_iterator operator ++ (int)
  72       throw(null_dereference,end_dereference);
  73     // pre-decrement
  74     this_iterator& operator -- (void)
  75       throw(null_dereference,end_dereference);
  76     // post-decrement
  77     this_iterator operator -- (int)
  78       throw(null_dereference,end_dereference);
  79
  80     // test useful for testing whether iteration has completed and for inclusion in other containers
  81     // Note: this class also inherits the safe_iterator methods: valid(), null(), end()
  82     bool operator == (const this_iterator& r) const;
  83     bool operator != (const this_iterator& r) const;
  84     bool operator < (const this_iterator& r) const;
  85
  86     // access the node data - a const_iterator gives you a const element, an iterator a non-const element
  87     // it is illegal to dereference an invalid (i.e. null or end) iterator
  88     reference operator*(void) const
  89       throw(null_dereference,end_dereference);
  90     pointer operator->(void) const
  91       throw(null_dereference,end_dereference);
  92
  93   public:
  94     // constructor used by digraph to create a non-null iterator
  95     explicit digraph_iterator(digraph_node<NT,AT>* node);
  96     // constructor used by digraph to create an end iterator
  97     explicit digraph_iterator(const digraph<NT,AT>* owner);
  98     // used to create an alias of an iterator
  99     explicit digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator);
 100   };
 101
 102   ////////////////////////////////////////////////////////////////////////////////
 103
 104   template<typename NT, typename AT, typename ARef, typename APtr>
 105   class digraph_arc_iterator : public safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >
 106   {
 107   public:
 108     friend class digraph<NT,AT>;
 109
 110     // local type definitions
 111     // an iterator points to an object whilst a const_iterator points to a const object
 112     typedef digraph_arc_iterator<NT,AT,AT&,AT*> iterator;
 113     typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_iterator;
 114     typedef digraph_arc_iterator<NT,AT,ARef,APtr> this_iterator;
 115     typedef ARef reference;
 116     typedef APtr pointer;
 117
 118     // constructor to create a null iterator - you must assign a valid value to this iterator before using it
 119     digraph_arc_iterator(void);
 120     ~digraph_arc_iterator(void);
 121
 122     // Type conversion methods allow const_iterator and iterator to be converted
 123     // convert an iterator/const_iterator to a const_iterator
 124     const_iterator constify(void) const;
 125     // convert an iterator/const_iterator to an iterator
 126     iterator deconstify(void) const;
 127
 128     // increment/decrement operators used to step through the set of all nodes in a graph
 129     // it is only legal to increment a valid iterator
 130     // pre-increment
 131     this_iterator& operator ++ (void)
 132       throw(null_dereference,end_dereference);
 133     // post-increment
 134     this_iterator operator ++ (int)
 135       throw(null_dereference,end_dereference);
 136     // pre-decrement
 137     this_iterator& operator -- (void)
 138       throw(null_dereference,end_dereference);
 139     // post-decrement
 140     this_iterator operator -- (int)
 141       throw(null_dereference,end_dereference);
 142
 143     // test useful for testing whether iteration has completed and for inclusion in other containers
 144     // Note: this class also inherits the safe_iterator methods: valid(), null(), end()
 145     bool operator == (const this_iterator&) const;
 146     bool operator != (const this_iterator&) const;
 147     bool operator < (const this_iterator&) const;
 148
 149     // access the node data - a const_iterator gives you a const element, an iterator a non-const element
 150     // it is illegal to dereference an invalid (i.e. null or end) iterator
 151     reference operator*(void) const
 152       throw(null_dereference,end_dereference);
 153     pointer operator->(void) const
 154       throw(null_dereference,end_dereference);
 155
 156   public:
 157     // constructor used by digraph to create a non-null iterator
 158     explicit digraph_arc_iterator(digraph_arc<NT,AT>* arc);
 159     // constructor used by digraph to create an end iterator
 160     explicit digraph_arc_iterator(const digraph<NT,AT>* owner);
 161     // used to create an alias of an iterator
 162     explicit digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator);
 163   };
 164
 165   ////////////////////////////////////////////////////////////////////////////////
 166   // The Graph class
 167   // NT is the Node type and AT is the Arc type
 168   ////////////////////////////////////////////////////////////////////////////////
 169
 170   template<typename NT, typename AT>
 171   class digraph
 172   {
 173   public:
 174     // STL-like typedefs for the types and iterators
 175     typedef NT node_type;
 176     typedef AT arc_type;
 177     typedef digraph_iterator<NT,AT,NT&,NT*> iterator;
 178     typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;
 179     typedef digraph_arc_iterator<NT,AT,AT&,AT*> arc_iterator;
 180     typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_arc_iterator;
 181
 182     // supplementary types used throughout
 183
 184     // a path is represented as a vector of arcs so the forward traversal is
 185     // done by going from begin() to end() or 0 to size-1 - of course a backward
 186     // traversal can be done by traversing the vector backwards
 187     typedef std::vector<arc_iterator> arc_vector;
 188     typedef std::vector<const_arc_iterator> const_arc_vector;
 189     const_arc_vector constify_arcs(const arc_vector&) const
 190       throw(wrong_object,null_dereference,end_dereference);
 191     arc_vector deconstify_arcs(const const_arc_vector&) const
 192       throw(wrong_object,null_dereference,end_dereference);
 193
 194     // a path vector is a vector of paths used to represent all the paths from one node to another
 195     // there is no particular ordering to the paths in the vector
 196     typedef std::vector<arc_vector> path_vector;
 197     typedef std::vector<const_arc_vector> const_path_vector;
 198     const_path_vector constify_paths(const path_vector&) const
 199       throw(wrong_object,null_dereference,end_dereference);
 200     path_vector deconstify_paths(const const_path_vector&) const
 201       throw(wrong_object,null_dereference,end_dereference);
 202
 203     // a node vector is a simple vector of nodes used to represent the reachable sets
 204     // there is no particular ordering to the nodes in the vector
 205     typedef std::vector<iterator> node_vector;
 206     typedef std::vector<const_iterator> const_node_vector;
 207     const_node_vector constify_nodes(const node_vector&) const
 208       throw(wrong_object,null_dereference,end_dereference);
 209     node_vector deconstify_nodes(const const_node_vector&) const
 210       throw(wrong_object,null_dereference,end_dereference);
 211
 212     // callback used in the path algorithms to select which arcs to consider
 213     typedef bool (*arc_select_fn) (const digraph<NT,AT>&, const_arc_iterator);
 214
 215     // a value representing an unknown offset
 216     // Note that it's static so use in the form digraph<NT,AT>::npos()
 217     static unsigned npos(void);
 218
 219     //////////////////////////////////////////////////////////////////////////
 220     // Constructors, destructors and copies
 221
 222     digraph(void);
 223     ~digraph(void);
 224
 225     // copy constructor and assignment both copy the graph
 226     digraph(const digraph<NT,AT>&);
 227     digraph<NT,AT>& operator=(const digraph<NT,AT>&);
 228
 229     //////////////////////////////////////////////////////////////////////////
 230     // Basic Node functions
 231     // Nodes are referred to by iterators created when the node is inserted.
 232     // Iterators remain valid unless the node is erased (they are list iterators, so no resize problems)
 233     // It is also possible to walk through all the nodes using a list-like start() to end() loop
 234     // Each node has a set of input arcs and output arcs. These are indexed by an unsigned i.e. they form a vector.
 235     // The total number of inputs is the fanin and the total number of outputs is the fanout.
 236     // The contents of the node (type NT) are accessed, of course, by dereferencing the node iterator.
 237
 238     // tests for the number of nodes and the special test for zero nodes
 239     bool empty(void) const;
 240     unsigned size(void) const;
 241
 242     // add a new node and return its iterator
 243     iterator insert(const NT& node_data);
 244
 245     // remove a node and return the iterator to the next node
 246     // erasing a node erases its arcs
 247     iterator erase(iterator)
 248       throw(wrong_object,null_dereference,end_dereference);
 249     // remove all nodes
 250     void clear(void);
 251
 252     // traverse all the nodes in no particular order using STL-style iteration
 253     const_iterator begin(void) const;
 254     iterator begin(void);
 255     const_iterator end(void) const;
 256     iterator end(void);
 257
 258     // access the inputs of this node
 259     // the fanin is the number of inputs and the inputs are accessed using an index from 0..fanin-1
 260     unsigned fanin(const_iterator) const
 261       throw(wrong_object,null_dereference,end_dereference);
 262     unsigned fanin(iterator)
 263       throw(wrong_object,null_dereference,end_dereference);
 264     const_arc_iterator input(const_iterator, unsigned) const
 265       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 266     arc_iterator input(iterator, unsigned)
 267       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 268
 269     // access the outputs of this node
 270     // the fanout is the number of outputs and the outputs are accessed using an index from 0..fanout-1
 271     unsigned fanout(const_iterator) const
 272       throw(wrong_object,null_dereference,end_dereference);
 273     unsigned fanout(iterator)
 274       throw(wrong_object,null_dereference,end_dereference);
 275     const_arc_iterator output(const_iterator, unsigned) const
 276       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 277     arc_iterator output(iterator, unsigned)
 278       throw(wrong_object,null_dereference,end_dereference,std::out_of_range);
 279
 280     // convenience routines for getting the set of all inputs or all outputs as vectors
 281     const_arc_vector inputs(const_iterator) const
 282       throw(wrong_object,null_dereference,end_dereference);
 283     arc_vector inputs(iterator)
 284       throw(wrong_object,null_dereference,end_dereference);
 285     const_arc_vector outputs(const_iterator) const
 286       throw(wrong_object,null_dereference,end_dereference);
 287     arc_vector outputs(iterator)
 288       throw(wrong_object,null_dereference,end_dereference);
 289
 290     // find the output index of an arc which goes from this node
 291     // returns digraph<NT,AT>::npos if the arc is not an output of from
 292     unsigned output_offset(const_iterator from, const_arc_iterator arc) const
 293       throw(wrong_object,null_dereference,end_dereference);
 294     unsigned output_offset(iterator from, arc_iterator arc)
 295       throw(wrong_object,null_dereference,end_dereference);
 296     // ditto for an input arc
 297     unsigned input_offset(const_iterator to, const_arc_iterator arc) const
 298       throw(wrong_object,null_dereference,end_dereference);
 299     unsigned input_offset(iterator to, arc_iterator arc)
 300       throw(wrong_object,null_dereference,end_dereference);
 301
 302     //////////////////////////////////////////////////////////////////////////
 303     // Basic Arc functions
 304     // to avoid name conflicts, arc functions have the arc_ prefix
 305     // Arcs, like nodes, are referred to by a list iterator which is returned by the arc_insert function
 306     // They may also be visited from arc_begin() to arc_end()
 307     // Each arc has a from field and a to field which contain the node iterators of the endpoints of the arc
 308     // Of course, the arc data can be accessed by simply dereferencing the iterator
 309
 310     // tests for the number of arcs and the special test for zero arcs
 311     bool arc_empty (void) const;
 312     unsigned arc_size(void) const;
 313
 314     // add a new arc and return its iterator
 315     arc_iterator arc_insert(iterator from, iterator to, const AT& arc_data = AT())
 316       throw(wrong_object,null_dereference,end_dereference);
 317
 318     // remove an arc and return the iterator to the next arc
 319     arc_iterator arc_erase(arc_iterator)
 320       throw(wrong_object,null_dereference,end_dereference);
 321     // remove all arcs
 322     void arc_clear(void);
 323
 324     // traverse all the arcs in no particular order using STL-style iteration
 325     const_arc_iterator arc_begin(void) const;
 326     arc_iterator arc_begin(void);
 327     const_arc_iterator arc_end(void) const;
 328     arc_iterator arc_end(void);
 329
 330     // find the node that an arc points from or to
 331     const_iterator arc_from(const_arc_iterator) const
 332       throw(wrong_object,null_dereference,end_dereference);
 333     iterator arc_from(arc_iterator)
 334       throw(wrong_object,null_dereference,end_dereference);
 335     const_iterator arc_to(const_arc_iterator) const
 336       throw(wrong_object,null_dereference,end_dereference);
 337     iterator arc_to(arc_iterator)
 338       throw(wrong_object,null_dereference,end_dereference);
 339
 340     // reconnect an arc to a different from and to node
 341     void arc_move(arc_iterator arc, iterator from, iterator to)
 342       throw(wrong_object,null_dereference,end_dereference);
 343     // reconnect just the from node
 344     void arc_move_from(arc_iterator arc, iterator from)
 345       throw(wrong_object,null_dereference,end_dereference);
 346     // reconnect just the to node
 347     void arc_move_to(arc_iterator arc, iterator to)
 348       throw(wrong_object,null_dereference,end_dereference);
 349     // reverse the arc direction so that to becomes from and vice-versa
 350     void arc_flip(arc_iterator arc)
 351       throw(wrong_object,null_dereference,end_dereference);
 352
 353     ////////////////////////////////////////////////////////////////////////////////
 354     // Adjacency algorithms
 355
 356     // test whether the nodes are adjacent i.e. whether there is an arc going from from to to
 357     bool adjacent(const_iterator from, const_iterator to) const
 358       throw(wrong_object,null_dereference,end_dereference);
 359     bool adjacent(iterator from, iterator to)
 360       throw(wrong_object,null_dereference,end_dereference);
 361
 362     // as above, but returns the arc that makes the nodes adjacent
 363     // returns the first arc if there's more than one, returns arc_end() if there are none
 364     const_arc_iterator adjacent_arc(const_iterator from, const_iterator to) const
 365       throw(wrong_object,null_dereference,end_dereference);
 366     arc_iterator adjacent_arc(iterator from, iterator to)
 367       throw(wrong_object,null_dereference,end_dereference);
 368
 369     // as above, but returns the set of all arcs that make two nodes adjacent (there may be more than one)
 370     // returns an empty vector if there are none
 371     const_arc_vector adjacent_arcs(const_iterator from, const_iterator to) const
 372       throw(wrong_object,null_dereference,end_dereference);
 373     arc_vector adjacent_arcs(iterator from, iterator to)
 374       throw(wrong_object,null_dereference,end_dereference);
 375
 376     // return the adjacency sets for the node inputs or outputs, i.e. the set of nodes adjacent to this node
 377     // each adjacent node will only be entered once even if there are multiple arcs between the nodes
 378     const_node_vector input_adjacencies(const_iterator to) const
 379       throw(wrong_object,null_dereference,end_dereference);
 380     node_vector input_adjacencies(iterator to)
 381       throw(wrong_object,null_dereference,end_dereference);
 382     const_node_vector output_adjacencies(const_iterator from) const
 383       throw(wrong_object,null_dereference,end_dereference);
 384     node_vector output_adjacencies(iterator from)
 385       throw(wrong_object,null_dereference,end_dereference);
 386
 387     ////////////////////////////////////////////////////////////////////////////////
 388     // Topographical Sort Algorithm
 389     // This generates a node ordering such that each node is visited after its fanin nodes.
 390
 391     // This only generates a valid ordering for a DAG.
 392
 393     // The return value is a pair :
 394     //  - the node vector which is a set of iterators to the nodes in sorted order
 395     //  - the arc vector is the set of backward ards that were broken to achieve the sort
 396     // If the arc vector is empty then the graph formed a DAG.
 397
 398     // The arc selection callback can be used to ignore arcs that are not part
 399     // of the ordering, i.e. arcs that are meant to be backwards arcs
 400
 401     std::pair<const_node_vector,const_arc_vector> sort(arc_select_fn = 0) const;
 402     std::pair<node_vector,arc_vector> sort(arc_select_fn = 0);
 403
 404     // Simplified variant of above for graphs that are known to be DAGs.
 405     // If the sort fails due to backward arcs, the
 406     // return vector is empty. Note that this will also be empty if the graph
 407     // has no nodes in it, so use the empty() method to differentiate.
 408
 409     const_node_vector dag_sort(arc_select_fn = 0) const;
 410     node_vector dag_sort(arc_select_fn = 0);
 411
 412     ////////////////////////////////////////////////////////////////////////////////
 413     // Basic Path Algorithms
 414     // A path is a series of arcs - you can use arc_from and arc_to to convert
 415     // that into a series of nodes. All the path algorithms take an arc_select
 416     // which allows arcs to be selected or rejected for consideration in a path.
 417
 418     // A selection callback function is applied to each arc in the traversal and
 419     // returns true if the arc is to be selected and false if the arc is to be
 420     // rejected. If no function is provided the arc is selected. If you want to
 421     // use arc selection you should create a function with the type profile given
 422     // by the arc_select_fn type. The select function is passed both the graph and
 423     // the arc iterator so that it is possible to select an arc on the basis of
 424     // the nodes it is connected to.
 425
 426     // Note: I used a callback because the STL-like predicate idea wasn't working for me...
 427
 428     // test for the existence of a path from from to to
 429     bool path_exists(const_iterator from, const_iterator to, arc_select_fn = 0) const
 430       throw(wrong_object,null_dereference,end_dereference);
 431     bool path_exists(iterator from, iterator to, arc_select_fn = 0)
 432       throw(wrong_object,null_dereference,end_dereference);
 433
 434     // get the set of all paths from from to to
 435     const_path_vector all_paths(const_iterator from, const_iterator to, arc_select_fn = 0) const
 436       throw(wrong_object,null_dereference,end_dereference);
 437     path_vector all_paths(iterator from, iterator to, arc_select_fn = 0)
 438       throw(wrong_object,null_dereference,end_dereference);
 439
 440     // get the set of all nodes that can be reached by any path from from
 441     const_node_vector reachable_nodes(const_iterator from, arc_select_fn = 0) const
 442       throw(wrong_object,null_dereference,end_dereference);
 443     node_vector reachable_nodes(iterator from, arc_select_fn = 0)
 444       throw(wrong_object,null_dereference,end_dereference);
 445
 446     // get the set of all nodes that can reach to to by any path
 447     const_node_vector reaching_nodes(const_iterator to, arc_select_fn = 0) const
 448       throw(wrong_object,null_dereference,end_dereference);
 449     node_vector reaching_nodes(iterator to, arc_select_fn = 0)
 450       throw(wrong_object,null_dereference,end_dereference);
 451
 452     ////////////////////////////////////////////////////////////////////////////////
 453     // Unweighted Shortest path algorithms
 454
 455     // find the shortest path from from to to
 456     // This is an unweighted shortest path algorithm, i.e. the weight of each
 457     // arc is assumed to be 1, so just counts the number of arcs
 458     // if there is more than one shortest path it returns the first one
 459     // If there are no paths, returns an empty path
 460     const_arc_vector shortest_path(const_iterator from, const_iterator to, arc_select_fn = 0) const
 461       throw(wrong_object,null_dereference,end_dereference);
 462     arc_vector shortest_path(iterator from, iterator to, arc_select_fn = 0)
 463       throw(wrong_object,null_dereference,end_dereference);
 464
 465     // find the set of shortest paths from from to any other node in the graph
 466     // that is reachable (i.e. for which path_exists() is true)
 467     // This is an unweighted shortest path, so just counts the number of arcs
 468     // if there is more than one shortest path to a node it returns the first one
 469     // If there are no paths, returns an empty list
 470     const_path_vector shortest_paths(const_iterator from, arc_select_fn = 0) const
 471       throw(wrong_object,null_dereference,end_dereference);
 472     path_vector shortest_paths(iterator from, arc_select_fn = 0)
 473       throw(wrong_object,null_dereference,end_dereference);
 474
 475   private:
 476     friend class digraph_iterator<NT,AT,NT&,NT*>;
 477     friend class digraph_iterator<NT,AT,const NT&,const NT*>;
 478     friend class digraph_arc_iterator<NT,AT,AT&,AT*>;
 479     friend class digraph_arc_iterator<NT,AT,const AT&, const AT*>;
 480
 481     typedef std::set<const_iterator> const_iterator_set;
 482     typedef TYPENAME const_iterator_set::iterator const_iterator_set_iterator;
 483
 484     bool path_exists_r(const_iterator from, const_iterator to, const_iterator_set& visited, arc_select_fn) const
 485       throw(wrong_object,null_dereference,end_dereference);
 486
 487     void all_paths_r(const_iterator from, const_iterator to, const_arc_vector& so_far, const_path_vector& result, arc_select_fn) const
 488       throw(wrong_object,null_dereference,end_dereference);
 489
 490     void reachable_nodes_r(const_iterator from, const_iterator_set& visited, arc_select_fn) const
 491       throw(wrong_object,null_dereference,end_dereference);
 492
 493     void reaching_nodes_r(const_iterator to, const_iterator_set& visited, arc_select_fn) const
 494       throw(wrong_object,null_dereference,end_dereference);
 495
 496     digraph_node<NT,AT>* m_nodes_begin;
 497     digraph_node<NT,AT>* m_nodes_end;
 498     digraph_arc<NT,AT>* m_arcs_begin;
 499     digraph_arc<NT,AT>* m_arcs_end;
 500   };
 501
 502   ////////////////////////////////////////////////////////////////////////////////
 503
 504 } // end namespace stlplus
 505
 506 #include "digraph.tpp"
 507 #endif