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