+++ /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