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