--- /dev/null
+#ifndef STLPLUS_DIGRAPH\r
+#define STLPLUS_DIGRAPH\r
+////////////////////////////////////////////////////////////////////////////////\r
+\r
+// Author: Andy Rushton\r
+// Copyright: (c) Southampton University 1999-2004\r
+// (c) Andy Rushton 2004-2009\r
+// License: BSD License, see ../docs/license.html\r
+\r
+// STL-style Directed graph template component\r
+// Digraph stands for directed-graph, i.e. all arcs have a direction\r
+\r
+////////////////////////////////////////////////////////////////////////////////\r
+#include "containers_fixes.hpp"\r
+#include "safe_iterator.hpp"\r
+#include "exceptions.hpp"\r
+#include <vector>\r
+#include <map>\r
+#include <set>\r
+\r
+namespace stlplus\r
+{\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Internals\r
+\r
+ template<typename NT, typename AT> class digraph_node;\r
+ template<typename NT, typename AT> class digraph_arc;\r
+ template<typename NT, typename AT> class digraph;\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // The Digraph iterator classes\r
+ // a digraph_iterator points to a node whilst a digraph_arc_iterator points to an arc\r
+ // Note that these are redefined as:\r
+ // digraph<NT,AT>::iterator - points to a non-const node\r
+ // digraph<NT,AT>::const_iterator - points to a const node\r
+ // digraph<NT,AT>::arc_iterator - points to a non-const arc\r
+ // digraph<NT,AT>::const_arc_iterator - points to a const arc\r
+ // and this is the form in which they should be used\r
+\r
+ template<typename NT, typename AT, typename NRef, typename NPtr>\r
+ class digraph_iterator : public safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >\r
+ {\r
+ public:\r
+ friend class digraph<NT,AT>;\r
+\r
+ // local type definitions\r
+ // an iterator points to an object whilst a const_iterator points to a const object\r
+ typedef digraph_iterator<NT,AT,NT&,NT*> iterator;\r
+ typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;\r
+ typedef digraph_iterator<NT,AT,NRef,NPtr> this_iterator;\r
+ typedef NRef reference;\r
+ typedef NPtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ digraph_iterator(void);\r
+ ~digraph_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ // convert an iterator/const_iterator to an iterator\r
+ iterator deconstify(void) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+ // pre-decrement\r
+ this_iterator& operator -- (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-decrement\r
+ this_iterator operator -- (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // test useful for testing whether iteration has completed and for inclusion in other containers\r
+ // Note: this class also inherits the safe_iterator methods: valid(), null(), end()\r
+ bool operator == (const this_iterator& r) const;\r
+ bool operator != (const this_iterator& r) const;\r
+ bool operator < (const this_iterator& r) const;\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ public:\r
+ // constructor used by digraph to create a non-null iterator\r
+ explicit digraph_iterator(digraph_node<NT,AT>* node);\r
+ // constructor used by digraph to create an end iterator\r
+ explicit digraph_iterator(const digraph<NT,AT>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit digraph_iterator(const safe_iterator<digraph<NT,AT>, digraph_node<NT,AT> >& iterator);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename NT, typename AT, typename ARef, typename APtr>\r
+ class digraph_arc_iterator : public safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >\r
+ {\r
+ public:\r
+ friend class digraph<NT,AT>;\r
+\r
+ // local type definitions\r
+ // an iterator points to an object whilst a const_iterator points to a const object\r
+ typedef digraph_arc_iterator<NT,AT,AT&,AT*> iterator;\r
+ typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_iterator;\r
+ typedef digraph_arc_iterator<NT,AT,ARef,APtr> this_iterator;\r
+ typedef ARef reference;\r
+ typedef APtr pointer;\r
+\r
+ // constructor to create a null iterator - you must assign a valid value to this iterator before using it\r
+ digraph_arc_iterator(void);\r
+ ~digraph_arc_iterator(void);\r
+\r
+ // Type conversion methods allow const_iterator and iterator to be converted\r
+ // convert an iterator/const_iterator to a const_iterator\r
+ const_iterator constify(void) const;\r
+ // convert an iterator/const_iterator to an iterator\r
+ iterator deconstify(void) const;\r
+\r
+ // increment/decrement operators used to step through the set of all nodes in a graph\r
+ // it is only legal to increment a valid iterator\r
+ // pre-increment\r
+ this_iterator& operator ++ (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-increment\r
+ this_iterator operator ++ (int)\r
+ throw(null_dereference,end_dereference);\r
+ // pre-decrement\r
+ this_iterator& operator -- (void)\r
+ throw(null_dereference,end_dereference);\r
+ // post-decrement\r
+ this_iterator operator -- (int)\r
+ throw(null_dereference,end_dereference);\r
+\r
+ // test useful for testing whether iteration has completed and for inclusion in other containers\r
+ // Note: this class also inherits the safe_iterator methods: valid(), null(), end()\r
+ bool operator == (const this_iterator&) const;\r
+ bool operator != (const this_iterator&) const;\r
+ bool operator < (const this_iterator&) const;\r
+\r
+ // access the node data - a const_iterator gives you a const element, an iterator a non-const element\r
+ // it is illegal to dereference an invalid (i.e. null or end) iterator\r
+ reference operator*(void) const\r
+ throw(null_dereference,end_dereference);\r
+ pointer operator->(void) const\r
+ throw(null_dereference,end_dereference);\r
+\r
+ public:\r
+ // constructor used by digraph to create a non-null iterator\r
+ explicit digraph_arc_iterator(digraph_arc<NT,AT>* arc);\r
+ // constructor used by digraph to create an end iterator\r
+ explicit digraph_arc_iterator(const digraph<NT,AT>* owner);\r
+ // used to create an alias of an iterator\r
+ explicit digraph_arc_iterator(const safe_iterator<digraph<NT,AT>, digraph_arc<NT,AT> >& iterator);\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // The Graph class\r
+ // NT is the Node type and AT is the Arc type\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+ template<typename NT, typename AT>\r
+ class digraph\r
+ {\r
+ public:\r
+ // STL-like typedefs for the types and iterators\r
+ typedef NT node_type;\r
+ typedef AT arc_type;\r
+ typedef digraph_iterator<NT,AT,NT&,NT*> iterator;\r
+ typedef digraph_iterator<NT,AT,const NT&,const NT*> const_iterator;\r
+ typedef digraph_arc_iterator<NT,AT,AT&,AT*> arc_iterator;\r
+ typedef digraph_arc_iterator<NT,AT,const AT&,const AT*> const_arc_iterator;\r
+\r
+ // supplementary types used throughout\r
+\r
+ // a path is represented as a vector of arcs so the forward traversal is\r
+ // done by going from begin() to end() or 0 to size-1 - of course a backward\r
+ // traversal can be done by traversing the vector backwards\r
+ typedef std::vector<arc_iterator> arc_vector;\r
+ typedef std::vector<const_arc_iterator> const_arc_vector;\r
+ const_arc_vector constify_arcs(const arc_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector deconstify_arcs(const const_arc_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // a path vector is a vector of paths used to represent all the paths from one node to another\r
+ // there is no particular ordering to the paths in the vector\r
+ typedef std::vector<arc_vector> path_vector;\r
+ typedef std::vector<const_arc_vector> const_path_vector;\r
+ const_path_vector constify_paths(const path_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ path_vector deconstify_paths(const const_path_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // a node vector is a simple vector of nodes used to represent the reachable sets\r
+ // there is no particular ordering to the nodes in the vector\r
+ typedef std::vector<iterator> node_vector;\r
+ typedef std::vector<const_iterator> const_node_vector;\r
+ const_node_vector constify_nodes(const node_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector deconstify_nodes(const const_node_vector&) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // callback used in the path algorithms to select which arcs to consider\r
+ typedef bool (*arc_select_fn) (const digraph<NT,AT>&, const_arc_iterator);\r
+\r
+ // a value representing an unknown offset\r
+ // Note that it's static so use in the form digraph<NT,AT>::npos()\r
+ static unsigned npos(void);\r
+\r
+ //////////////////////////////////////////////////////////////////////////\r
+ // Constructors, destructors and copies\r
+\r
+ digraph(void);\r
+ ~digraph(void);\r
+\r
+ // copy constructor and assignment both copy the graph\r
+ digraph(const digraph<NT,AT>&);\r
+ digraph<NT,AT>& operator=(const digraph<NT,AT>&);\r
+\r
+ //////////////////////////////////////////////////////////////////////////\r
+ // Basic Node functions\r
+ // Nodes are referred to by iterators created when the node is inserted.\r
+ // Iterators remain valid unless the node is erased (they are list iterators, so no resize problems)\r
+ // It is also possible to walk through all the nodes using a list-like start() to end() loop\r
+ // Each node has a set of input arcs and output arcs. These are indexed by an unsigned i.e. they form a vector.\r
+ // The total number of inputs is the fanin and the total number of outputs is the fanout.\r
+ // The contents of the node (type NT) are accessed, of course, by dereferencing the node iterator.\r
+\r
+ // tests for the number of nodes and the special test for zero nodes\r
+ bool empty(void) const;\r
+ unsigned size(void) const;\r
+\r
+ // add a new node and return its iterator\r
+ iterator insert(const NT& node_data);\r
+\r
+ // remove a node and return the iterator to the next node\r
+ // erasing a node erases its arcs\r
+ iterator erase(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // remove all nodes\r
+ void clear(void);\r
+\r
+ // traverse all the nodes in no particular order using STL-style iteration\r
+ const_iterator begin(void) const;\r
+ iterator begin(void);\r
+ const_iterator end(void) const;\r
+ iterator end(void);\r
+\r
+ // access the inputs of this node\r
+ // the fanin is the number of inputs and the inputs are accessed using an index from 0..fanin-1\r
+ unsigned fanin(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned fanin(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_arc_iterator input(const_iterator, unsigned) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ arc_iterator input(iterator, unsigned)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ // access the outputs of this node\r
+ // the fanout is the number of outputs and the outputs are accessed using an index from 0..fanout-1\r
+ unsigned fanout(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned fanout(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_arc_iterator output(const_iterator, unsigned) const\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+ arc_iterator output(iterator, unsigned)\r
+ throw(wrong_object,null_dereference,end_dereference,std::out_of_range);\r
+\r
+ // convenience routines for getting the set of all inputs or all outputs as vectors\r
+ const_arc_vector inputs(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector inputs(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_arc_vector outputs(const_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector outputs(iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // find the output index of an arc which goes from this node\r
+ // returns digraph<NT,AT>::npos if the arc is not an output of from\r
+ unsigned output_offset(const_iterator from, const_arc_iterator arc) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned output_offset(iterator from, arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // ditto for an input arc\r
+ unsigned input_offset(const_iterator to, const_arc_iterator arc) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ unsigned input_offset(iterator to, arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ //////////////////////////////////////////////////////////////////////////\r
+ // Basic Arc functions\r
+ // to avoid name conflicts, arc functions have the arc_ prefix \r
+ // Arcs, like nodes, are referred to by a list iterator which is returned by the arc_insert function\r
+ // They may also be visited from arc_begin() to arc_end()\r
+ // Each arc has a from field and a to field which contain the node iterators of the endpoints of the arc\r
+ // Of course, the arc data can be accessed by simply dereferencing the iterator\r
+\r
+ // tests for the number of arcs and the special test for zero arcs\r
+ bool arc_empty (void) const;\r
+ unsigned arc_size(void) const;\r
+\r
+ // add a new arc and return its iterator\r
+ arc_iterator arc_insert(iterator from, iterator to, const AT& arc_data = AT())\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // remove an arc and return the iterator to the next arc\r
+ arc_iterator arc_erase(arc_iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // remove all arcs\r
+ void arc_clear(void);\r
+\r
+ // traverse all the arcs in no particular order using STL-style iteration\r
+ const_arc_iterator arc_begin(void) const;\r
+ arc_iterator arc_begin(void);\r
+ const_arc_iterator arc_end(void) const;\r
+ arc_iterator arc_end(void);\r
+\r
+ // find the node that an arc points from or to\r
+ const_iterator arc_from(const_arc_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ iterator arc_from(arc_iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_iterator arc_to(const_arc_iterator) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ iterator arc_to(arc_iterator)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // reconnect an arc to a different from and to node\r
+ void arc_move(arc_iterator arc, iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // reconnect just the from node\r
+ void arc_move_from(arc_iterator arc, iterator from)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // reconnect just the to node\r
+ void arc_move_to(arc_iterator arc, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ // reverse the arc direction so that to becomes from and vice-versa\r
+ void arc_flip(arc_iterator arc)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Adjacency algorithms\r
+\r
+ // test whether the nodes are adjacent i.e. whether there is an arc going from from to to\r
+ bool adjacent(const_iterator from, const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ bool adjacent(iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // as above, but returns the arc that makes the nodes adjacent\r
+ // returns the first arc if there's more than one, returns arc_end() if there are none\r
+ const_arc_iterator adjacent_arc(const_iterator from, const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_iterator adjacent_arc(iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // as above, but returns the set of all arcs that make two nodes adjacent (there may be more than one)\r
+ // returns an empty vector if there are none\r
+ const_arc_vector adjacent_arcs(const_iterator from, const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector adjacent_arcs(iterator from, iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // return the adjacency sets for the node inputs or outputs, i.e. the set of nodes adjacent to this node\r
+ // each adjacent node will only be entered once even if there are multiple arcs between the nodes\r
+ const_node_vector input_adjacencies(const_iterator to) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector input_adjacencies(iterator to)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ const_node_vector output_adjacencies(const_iterator from) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector output_adjacencies(iterator from)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Topographical Sort Algorithm\r
+ // This generates a node ordering such that each node is visited after its fanin nodes.\r
+\r
+ // This only generates a valid ordering for a DAG. \r
+\r
+ // The return value is a pair : \r
+ // - the node vector which is a set of iterators to the nodes in sorted order\r
+ // - the arc vector is the set of backward ards that were broken to achieve the sort\r
+ // If the arc vector is empty then the graph formed a DAG.\r
+\r
+ // The arc selection callback can be used to ignore arcs that are not part\r
+ // of the ordering, i.e. arcs that are meant to be backwards arcs\r
+\r
+ std::pair<const_node_vector,const_arc_vector> sort(arc_select_fn = 0) const;\r
+ std::pair<node_vector,arc_vector> sort(arc_select_fn = 0);\r
+\r
+ // Simplified variant of above for graphs that are known to be DAGs.\r
+ // If the sort fails due to backward arcs, the\r
+ // return vector is empty. Note that this will also be empty if the graph\r
+ // has no nodes in it, so use the empty() method to differentiate.\r
+\r
+ const_node_vector dag_sort(arc_select_fn = 0) const;\r
+ node_vector dag_sort(arc_select_fn = 0);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Basic Path Algorithms\r
+ // A path is a series of arcs - you can use arc_from and arc_to to convert\r
+ // that into a series of nodes. All the path algorithms take an arc_select\r
+ // which allows arcs to be selected or rejected for consideration in a path.\r
+\r
+ // A selection callback function is applied to each arc in the traversal and\r
+ // returns true if the arc is to be selected and false if the arc is to be\r
+ // rejected. If no function is provided the arc is selected. If you want to\r
+ // use arc selection you should create a function with the type profile given\r
+ // by the arc_select_fn type. The select function is passed both the graph and\r
+ // the arc iterator so that it is possible to select an arc on the basis of\r
+ // the nodes it is connected to.\r
+\r
+ // Note: I used a callback because the STL-like predicate idea wasn't working for me...\r
+\r
+ // test for the existence of a path from from to to\r
+ bool path_exists(const_iterator from, const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ bool path_exists(iterator from, iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // get the set of all paths from from to to\r
+ const_path_vector all_paths(const_iterator from, const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ path_vector all_paths(iterator from, iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // get the set of all nodes that can be reached by any path from from\r
+ const_node_vector reachable_nodes(const_iterator from, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector reachable_nodes(iterator from, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // get the set of all nodes that can reach to to by any path\r
+ const_node_vector reaching_nodes(const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ node_vector reaching_nodes(iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+ // Unweighted Shortest path algorithms\r
+\r
+ // find the shortest path from from to to\r
+ // This is an unweighted shortest path algorithm, i.e. the weight of each\r
+ // arc is assumed to be 1, so just counts the number of arcs\r
+ // if there is more than one shortest path it returns the first one\r
+ // If there are no paths, returns an empty path\r
+ const_arc_vector shortest_path(const_iterator from, const_iterator to, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ arc_vector shortest_path(iterator from, iterator to, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ // find the set of shortest paths from from to any other node in the graph\r
+ // that is reachable (i.e. for which path_exists() is true)\r
+ // This is an unweighted shortest path, so just counts the number of arcs\r
+ // if there is more than one shortest path to a node it returns the first one\r
+ // If there are no paths, returns an empty list\r
+ const_path_vector shortest_paths(const_iterator from, arc_select_fn = 0) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+ path_vector shortest_paths(iterator from, arc_select_fn = 0)\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ private:\r
+ friend class digraph_iterator<NT,AT,NT&,NT*>;\r
+ friend class digraph_iterator<NT,AT,const NT&,const NT*>;\r
+ friend class digraph_arc_iterator<NT,AT,AT&,AT*>;\r
+ friend class digraph_arc_iterator<NT,AT,const AT&, const AT*>;\r
+\r
+ typedef std::set<const_iterator> const_iterator_set;\r
+ typedef TYPENAME const_iterator_set::iterator const_iterator_set_iterator;\r
+\r
+ bool path_exists_r(const_iterator from, const_iterator to, const_iterator_set& visited, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void all_paths_r(const_iterator from, const_iterator to, const_arc_vector& so_far, const_path_vector& result, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void reachable_nodes_r(const_iterator from, const_iterator_set& visited, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ void reaching_nodes_r(const_iterator to, const_iterator_set& visited, arc_select_fn) const\r
+ throw(wrong_object,null_dereference,end_dereference);\r
+\r
+ digraph_node<NT,AT>* m_nodes_begin;\r
+ digraph_node<NT,AT>* m_nodes_end;\r
+ digraph_arc<NT,AT>* m_arcs_begin;\r
+ digraph_arc<NT,AT>* m_arcs_end;\r
+ };\r
+\r
+ ////////////////////////////////////////////////////////////////////////////////\r
+\r
+} // end namespace stlplus\r
+\r
+#include "digraph.tpp"\r
+#endif\r
projects / chaz / yoink / blobdiff