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