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