X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2Fstlplus%2Fcontainers%2Fdigraph.hpp;h=7b603c11d0f7c5b87bc8e65fb4552d75b29c9e59;hp=8281998d24640512b3b1ddfe94fadcd4b3f9fd1e;hb=5846afb00833cc72fe72422ca896d2387c712cb4;hpb=a97500609dc3c1b11f9786d32bc458eb00de4c36 diff --git a/src/stlplus/containers/digraph.hpp b/src/stlplus/containers/digraph.hpp index 8281998..7b603c1 100644 --- a/src/stlplus/containers/digraph.hpp +++ b/src/stlplus/containers/digraph.hpp @@ -1,507 +1,507 @@ -#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 -#include -#include - -namespace stlplus -{ - - //////////////////////////////////////////////////////////////////////////////// - // Internals - - template class digraph_node; - template class digraph_arc; - template 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::iterator - points to a non-const node - // digraph::const_iterator - points to a const node - // digraph::arc_iterator - points to a non-const arc - // digraph::const_arc_iterator - points to a const arc - // and this is the form in which they should be used - - template - class digraph_iterator : public safe_iterator, digraph_node > - { - public: - friend class digraph; - - // local type definitions - // an iterator points to an object whilst a const_iterator points to a const object - typedef digraph_iterator iterator; - typedef digraph_iterator const_iterator; - typedef digraph_iterator 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* node); - // constructor used by digraph to create an end iterator - explicit digraph_iterator(const digraph* owner); - // used to create an alias of an iterator - explicit digraph_iterator(const safe_iterator, digraph_node >& iterator); - }; - - //////////////////////////////////////////////////////////////////////////////// - - template - class digraph_arc_iterator : public safe_iterator, digraph_arc > - { - public: - friend class digraph; - - // local type definitions - // an iterator points to an object whilst a const_iterator points to a const object - typedef digraph_arc_iterator iterator; - typedef digraph_arc_iterator const_iterator; - typedef digraph_arc_iterator 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* arc); - // constructor used by digraph to create an end iterator - explicit digraph_arc_iterator(const digraph* owner); - // used to create an alias of an iterator - explicit digraph_arc_iterator(const safe_iterator, digraph_arc >& iterator); - }; - - //////////////////////////////////////////////////////////////////////////////// - // The Graph class - // NT is the Node type and AT is the Arc type - //////////////////////////////////////////////////////////////////////////////// - - template - class digraph - { - public: - // STL-like typedefs for the types and iterators - typedef NT node_type; - typedef AT arc_type; - typedef digraph_iterator iterator; - typedef digraph_iterator const_iterator; - typedef digraph_arc_iterator arc_iterator; - typedef digraph_arc_iterator 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_vector; - typedef std::vector 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 path_vector; - typedef std::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 node_vector; - typedef std::vector 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&, const_arc_iterator); - - // a value representing an unknown offset - // Note that it's static so use in the form digraph::npos() - static unsigned npos(void); - - ////////////////////////////////////////////////////////////////////////// - // Constructors, destructors and copies - - digraph(void); - ~digraph(void); - - // copy constructor and assignment both copy the graph - digraph(const digraph&); - digraph& operator=(const digraph&); - - ////////////////////////////////////////////////////////////////////////// - // 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::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 sort(arc_select_fn = 0) const; - std::pair 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; - friend class digraph_iterator; - friend class digraph_arc_iterator; - friend class digraph_arc_iterator; - - typedef std::set 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* m_nodes_begin; - digraph_node* m_nodes_end; - digraph_arc* m_arcs_begin; - digraph_arc* m_arcs_end; - }; - - //////////////////////////////////////////////////////////////////////////////// - -} // end namespace stlplus - -#include "digraph.tpp" -#endif +#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 +#include +#include + +namespace stlplus +{ + + //////////////////////////////////////////////////////////////////////////////// + // Internals + + template class digraph_node; + template class digraph_arc; + template 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::iterator - points to a non-const node + // digraph::const_iterator - points to a const node + // digraph::arc_iterator - points to a non-const arc + // digraph::const_arc_iterator - points to a const arc + // and this is the form in which they should be used + + template + class digraph_iterator : public safe_iterator, digraph_node > + { + public: + friend class digraph; + + // local type definitions + // an iterator points to an object whilst a const_iterator points to a const object + typedef digraph_iterator iterator; + typedef digraph_iterator const_iterator; + typedef digraph_iterator 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* node); + // constructor used by digraph to create an end iterator + explicit digraph_iterator(const digraph* owner); + // used to create an alias of an iterator + explicit digraph_iterator(const safe_iterator, digraph_node >& iterator); + }; + + //////////////////////////////////////////////////////////////////////////////// + + template + class digraph_arc_iterator : public safe_iterator, digraph_arc > + { + public: + friend class digraph; + + // local type definitions + // an iterator points to an object whilst a const_iterator points to a const object + typedef digraph_arc_iterator iterator; + typedef digraph_arc_iterator const_iterator; + typedef digraph_arc_iterator 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* arc); + // constructor used by digraph to create an end iterator + explicit digraph_arc_iterator(const digraph* owner); + // used to create an alias of an iterator + explicit digraph_arc_iterator(const safe_iterator, digraph_arc >& iterator); + }; + + //////////////////////////////////////////////////////////////////////////////// + // The Graph class + // NT is the Node type and AT is the Arc type + //////////////////////////////////////////////////////////////////////////////// + + template + class digraph + { + public: + // STL-like typedefs for the types and iterators + typedef NT node_type; + typedef AT arc_type; + typedef digraph_iterator iterator; + typedef digraph_iterator const_iterator; + typedef digraph_arc_iterator arc_iterator; + typedef digraph_arc_iterator 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_vector; + typedef std::vector 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 path_vector; + typedef std::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 node_vector; + typedef std::vector 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&, const_arc_iterator); + + // a value representing an unknown offset + // Note that it's static so use in the form digraph::npos() + static unsigned npos(void); + + ////////////////////////////////////////////////////////////////////////// + // Constructors, destructors and copies + + digraph(void); + ~digraph(void); + + // copy constructor and assignment both copy the graph + digraph(const digraph&); + digraph& operator=(const digraph&); + + ////////////////////////////////////////////////////////////////////////// + // 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::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 sort(arc_select_fn = 0) const; + std::pair 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; + friend class digraph_iterator; + friend class digraph_arc_iterator; + friend class digraph_arc_iterator; + + typedef std::set 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* m_nodes_begin; + digraph_node* m_nodes_end; + digraph_arc* m_arcs_begin; + digraph_arc* m_arcs_end; + }; + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus + +#include "digraph.tpp" +#endif