#ifndef STLPLUS_DIGRAPH #define STLPLUS_DIGRAPH //////////////////////////////////////////////////////////////////////////////// // Author: Andy Rushton // Copyright: (c) Southampton University 1999-2004 // (c) Andy Rushton 2004 onwards // 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 #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; // iterator traits, were inherited from std::iterator but inheriting from that was deprecated in C++17 // the digraph iterators are bidirectional but not random-access typedef std::bidirectional_iterator_tag iterator_category; typedef NT value_type; typedef NPtr pointer; typedef NRef reference; // this is not random access, so declare a void difference type, not sure this is supported by everything // typedef std::ptrdiff_t difference_type; typedef void difference_type; // 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; // 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 // exceptions: null_dereference,end_dereference this_iterator& operator ++ (void); // post-increment // exceptions: null_dereference,end_dereference this_iterator operator ++ (int); // pre-decrement // exceptions: null_dereference,end_dereference this_iterator& operator -- (void); // post-decrement // exceptions: null_dereference,end_dereference this_iterator operator -- (int); // 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 // exceptions: null_dereference,end_dereference reference operator*(void) const; // exceptions: null_dereference,end_dereference pointer operator->(void) const; 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; // iterator traits, were inherited from std::iterator but inheriting from that was deprecated in C++17 // the digraph iterators are bidirectional but not random-access typedef std::bidirectional_iterator_tag iterator_category; typedef AT value_type; typedef APtr pointer; typedef ARef reference; // this is not random access, so declare a void difference type, not sure this is supported by everything // typedef std::ptrdiff_t difference_type; typedef void difference_type; // 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; // 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 // exceptions: null_dereference,end_dereference this_iterator& operator ++ (void); // post-increment // exceptions: null_dereference,end_dereference this_iterator operator ++ (int); // pre-decrement // exceptions: null_dereference,end_dereference this_iterator& operator -- (void); // post-decrement // exceptions: null_dereference,end_dereference this_iterator operator -- (int); // 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 // exceptions: null_dereference,end_dereference reference operator*(void) const; // exceptions: null_dereference,end_dereference pointer operator->(void) const; 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; // iterator ownership - can check whether the graph owns an iterator bool owns(iterator) const; bool owns(const_iterator) const; bool owns(arc_iterator) const; bool owns(const_arc_iterator) const; // 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; // exceptions: wrong_object,null_dereference,end_dereference const_arc_vector constify_arcs(const arc_vector&) const; // exceptions: wrong_object,null_dereference,end_dereference arc_vector deconstify_arcs(const const_arc_vector&) const; // 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; // exceptions: wrong_object,null_dereference,end_dereference const_path_vector constify_paths(const path_vector&) const; // exceptions: wrong_object,null_dereference,end_dereference path_vector deconstify_paths(const const_path_vector&) const; // 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; // exceptions: wrong_object,null_dereference,end_dereference const_node_vector constify_nodes(const node_vector&) const; // exceptions: wrong_object,null_dereference,end_dereference node_vector deconstify_nodes(const const_node_vector&) const; // 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 // exceptions: wrong_object,null_dereference,end_dereference iterator erase(iterator); // 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 // exceptions: wrong_object,null_dereference,end_dereference unsigned fanin(const_iterator) const; // exceptions: wrong_object,null_dereference,end_dereference unsigned fanin(iterator); // exceptions: wrong_object,null_dereference,end_dereference,std::out_of_range const_arc_iterator input(const_iterator, unsigned) const; // exceptions: wrong_object,null_dereference,end_dereference,std::out_of_range arc_iterator input(iterator, unsigned); // 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 // exceptions: wrong_object,null_dereference,end_dereference unsigned fanout(const_iterator) const; // exceptions: wrong_object,null_dereference,end_dereference unsigned fanout(iterator); // exceptions: wrong_object,null_dereference,end_dereference,std::out_of_range const_arc_iterator output(const_iterator, unsigned) const; // exceptions: wrong_object,null_dereference,end_dereference,std::out_of_range arc_iterator output(iterator, unsigned); // convenience routines for getting the set of all inputs or all outputs as vectors // exceptions: wrong_object,null_dereference,end_dereference const_arc_vector inputs(const_iterator) const; // exceptions: wrong_object,null_dereference,end_dereference arc_vector inputs(iterator); // exceptions: wrong_object,null_dereference,end_dereference const_arc_vector outputs(const_iterator) const; // exceptions: wrong_object,null_dereference,end_dereference arc_vector outputs(iterator); // find the output index of an arc which goes from this node // returns digraph::npos if the arc is not an output of from // exceptions: wrong_object,null_dereference,end_dereference unsigned output_offset(const_iterator from, const_arc_iterator arc) const; // exceptions: wrong_object,null_dereference,end_dereference unsigned output_offset(iterator from, arc_iterator arc); // ditto for an input arc // exceptions: wrong_object,null_dereference,end_dereference unsigned input_offset(const_iterator to, const_arc_iterator arc) const; // exceptions: wrong_object,null_dereference,end_dereference unsigned input_offset(iterator to, arc_iterator arc); ////////////////////////////////////////////////////////////////////////// // 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 // exceptions: wrong_object,null_dereference,end_dereference arc_iterator arc_insert(iterator from, iterator to, const AT& arc_data = AT()); // remove an arc and return the iterator to the next arc // exceptions: wrong_object,null_dereference,end_dereference arc_iterator arc_erase(arc_iterator); // 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 // exceptions: wrong_object,null_dereference,end_dereference const_iterator arc_from(const_arc_iterator) const; // exceptions: wrong_object,null_dereference,end_dereference iterator arc_from(arc_iterator); // exceptions: wrong_object,null_dereference,end_dereference const_iterator arc_to(const_arc_iterator) const; // exceptions: wrong_object,null_dereference,end_dereference iterator arc_to(arc_iterator); // reconnect an arc to a different from and to node // exceptions: wrong_object,null_dereference,end_dereference void arc_move(arc_iterator arc, iterator from, iterator to); // reconnect just the from node // exceptions: wrong_object,null_dereference,end_dereference void arc_move_from(arc_iterator arc, iterator from); // reconnect just the to node // exceptions: wrong_object,null_dereference,end_dereference void arc_move_to(arc_iterator arc, iterator to); // reverse the arc direction so that to becomes from and vice-versa // exceptions: wrong_object,null_dereference,end_dereference void arc_flip(arc_iterator arc); //////////////////////////////////////////////////////////////////////////////// // whole graph manipulations // move one graph into another by moving all its nodes/arcs // this leaves the source graph empty // all iterators to nodes/arcs in the source graph will still work and will be owned by this void move(digraph& source); //////////////////////////////////////////////////////////////////////////////// // Adjacency algorithms // test whether the nodes are adjacent i.e. whether there is an arc going from from to to // exceptions: wrong_object,null_dereference,end_dereference bool adjacent(const_iterator from, const_iterator to) const; // exceptions: wrong_object,null_dereference,end_dereference bool adjacent(iterator from, iterator to); // 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 // exceptions: wrong_object,null_dereference,end_dereference const_arc_iterator adjacent_arc(const_iterator from, const_iterator to) const; // exceptions: wrong_object,null_dereference,end_dereference arc_iterator adjacent_arc(iterator from, iterator to); // 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 // exceptions: wrong_object,null_dereference,end_dereference const_arc_vector adjacent_arcs(const_iterator from, const_iterator to) const; // exceptions: wrong_object,null_dereference,end_dereference arc_vector adjacent_arcs(iterator from, iterator to); // 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 // exceptions: wrong_object,null_dereference,end_dereference const_node_vector input_adjacencies(const_iterator to) const; // exceptions: wrong_object,null_dereference,end_dereference node_vector input_adjacencies(iterator to); // exceptions: wrong_object,null_dereference,end_dereference const_node_vector output_adjacencies(const_iterator from) const; // exceptions: wrong_object,null_dereference,end_dereference node_vector output_adjacencies(iterator from); //////////////////////////////////////////////////////////////////////////////// // 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 Directed Acyclic Graph (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 arcs 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 // exceptions: wrong_object,null_dereference,end_dereference bool path_exists(const_iterator from, const_iterator to, arc_select_fn = 0) const; // exceptions: wrong_object,null_dereference,end_dereference bool path_exists(iterator from, iterator to, arc_select_fn = 0); // get the set of all paths from from to to // exceptions: wrong_object,null_dereference,end_dereference const_path_vector all_paths(const_iterator from, const_iterator to, arc_select_fn = 0) const; // exceptions: wrong_object,null_dereference,end_dereference path_vector all_paths(iterator from, iterator to, arc_select_fn = 0); // get the set of all nodes that can be reached by any path from from // exceptions: wrong_object,null_dereference,end_dereference const_node_vector reachable_nodes(const_iterator from, arc_select_fn = 0) const; // exceptions: wrong_object,null_dereference,end_dereference node_vector reachable_nodes(iterator from, arc_select_fn = 0); // get the set of all nodes that can reach to to by any path // exceptions: wrong_object,null_dereference,end_dereference const_node_vector reaching_nodes(const_iterator to, arc_select_fn = 0) const; // exceptions: wrong_object,null_dereference,end_dereference node_vector reaching_nodes(iterator to, arc_select_fn = 0); //////////////////////////////////////////////////////////////////////////////// // 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 // exceptions: wrong_object,null_dereference,end_dereference const_arc_vector shortest_path(const_iterator from, const_iterator to, arc_select_fn = 0) const; // exceptions: wrong_object,null_dereference,end_dereference arc_vector shortest_path(iterator from, iterator to, arc_select_fn = 0); // 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 // exceptions: wrong_object,null_dereference,end_dereference const_path_vector shortest_paths(const_iterator from, arc_select_fn = 0) const; // exceptions: wrong_object,null_dereference,end_dereference path_vector shortest_paths(iterator from, arc_select_fn = 0); 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; // exceptions: wrong_object,null_dereference,end_dereference bool path_exists_r(const_iterator from, const_iterator to, const_iterator_set& visited, arc_select_fn) const; // exceptions: 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; // exceptions: wrong_object,null_dereference,end_dereference void reachable_nodes_r(const_iterator from, const_iterator_set& visited, arc_select_fn) const; // exceptions: wrong_object,null_dereference,end_dereference void reaching_nodes_r(const_iterator to, const_iterator_set& visited, arc_select_fn) const; 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