X-Git-Url: https://git.dogcows.com/gitweb?p=chaz%2Fyoink;a=blobdiff_plain;f=src%2Fstlplus%2Fcontainers%2Fdigraph.tpp;h=ea6f84e3da28eaab1d2d732179c8fb9632cca2b7;hp=804954a0db72e70bd33d2c36cd32986736e1aaf6;hb=4f6e4488a55f7e3ba3f7485d78177f793c0eab9a;hpb=574af38ed616d1adfa5e6ce35f67cda1f707f89d diff --git a/src/stlplus/containers/digraph.tpp b/src/stlplus/containers/digraph.tpp index 804954a..ea6f84e 100644 --- a/src/stlplus/containers/digraph.tpp +++ b/src/stlplus/containers/digraph.tpp @@ -1,1483 +1,1483 @@ -//////////////////////////////////////////////////////////////////////////////// - -// Author: Andy Rushton -// Copyright: (c) Southampton University 1999-2004 -// (c) Andy Rushton 2004-2009 -// License: BSD License, see ../docs/license.html - -// Note: I tried to write this using STL lists for the node and arc lists, but -// it got far too hairy. The specific problem is that I wanted a digraph -// iterator to contain a list::iterator so I needed to be able to generate a -// list::iterator from a node or arc and STL list iterators don't give you that -// functionality. I tried burgling the data structures, but that was -// non-portable between different STL implementations so needed lots of #ifdefs -// and so was mind-bogglingly awful and unreadable - in other words a -// maintenance nightmare. I gave up and impemented my own lists - not difficult. - -// I use circular double-linked lists. The circular design means that both -// ends of the list are equally accessible in unit time. An empty list -// contains no objects. There is no end node in the list - unlike the STL -// lists which have a dummy node for end iterators to point to - -// conceptually the end iterator points one element beyond the end of the -// list. However, I implement the end iterator concept in the iterator -// itself, so do not need the dummy end node. - -//////////////////////////////////////////////////////////////////////////////// -#include -#include - -//////////////////////////////////////////////////////////////////////////////// -// Internals - -namespace stlplus -{ - - template - class digraph_node - { - public: - master_iterator, digraph_node > m_master; - NT m_data; - digraph_node* m_prev; - digraph_node* m_next; - std::vector*> m_inputs; - std::vector*> m_outputs; - public: - digraph_node(const digraph* owner, const NT& d = NT()) : - m_master(owner,this), m_data(d), m_prev(0), m_next(0) - { - } - ~digraph_node(void) - { - } - }; - - template - class digraph_arc - { - public: - master_iterator, digraph_arc > m_master; - AT m_data; - digraph_arc* m_prev; - digraph_arc* m_next; - digraph_node* m_from; - digraph_node* m_to; - digraph_arc(const digraph* owner, digraph_node* from = 0, digraph_node* to = 0, const AT& d = AT()) : - m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to) - { - } - }; - - //////////////////////////////////////////////////////////////////////////////// - // Iterators - //////////////////////////////////////////////////////////////////////////////// - - //////////////////////////////////////////////////////////////////////////////// - // Node iterator - - // construct a null iterator - template - digraph_iterator::digraph_iterator(void) - { - } - - // valid iterator - template - digraph_iterator::digraph_iterator(digraph_node* node) : - safe_iterator,digraph_node >(node->m_master) - { - } - - // end iterator - template - digraph_iterator::digraph_iterator(const digraph* owner) : - safe_iterator,digraph_node >(owner) - { - } - - // alias an iterator - template - digraph_iterator::digraph_iterator(const safe_iterator, digraph_node >& iterator) : - safe_iterator,digraph_node >(iterator) - { - } - - // destructor - template - digraph_iterator::~digraph_iterator(void) - { - } - - template - TYPENAME digraph_iterator::const_iterator digraph_iterator::constify (void) const - { - return digraph_iterator(*this); - } - - template - TYPENAME digraph_iterator::iterator digraph_iterator::deconstify (void) const - { - return digraph_iterator(*this); - } - - template - TYPENAME digraph_iterator::this_iterator& digraph_iterator::operator ++ (void) - throw(null_dereference,end_dereference) - { - this->assert_valid(); - if (this->node()->m_next) - this->set(this->node()->m_next->m_master); - else - this->set_end(); - return *this; - } - - template - TYPENAME digraph_iterator::this_iterator digraph_iterator::operator ++ (int) - throw(null_dereference,end_dereference) - { - // post-increment is defined in terms of the pre-increment - digraph_iterator result(*this); - ++(*this); - return result; - } - - template - TYPENAME digraph_iterator::this_iterator& digraph_iterator::operator -- (void) - throw(null_dereference,end_dereference) - { - this->assert_valid(); - if (this->node()->m_prev) - this->set(this->node()->m_prev->m_master); - else - this->set_end(); - return *this; - } - - template - TYPENAME digraph_iterator::this_iterator digraph_iterator::operator -- (int) - throw(null_dereference,end_dereference) - { - // post-decrement is defined in terms of the pre-decrement - digraph_iterator result(*this); - --(*this); - return result; - } - - template - bool digraph_iterator::operator == (const TYPENAME digraph_iterator::this_iterator& r) const - { - return equal(r); - } - - template - bool digraph_iterator::operator != (const TYPENAME digraph_iterator::this_iterator& r) const - { - return !operator==(r); - } - - template - bool digraph_iterator::operator < (const TYPENAME digraph_iterator::this_iterator& r) const - { - return compare(r) < 0; - } - - template - TYPENAME digraph_iterator::reference digraph_iterator::operator*(void) const - throw(null_dereference,end_dereference) - { - this->assert_valid(); - return this->node()->m_data; - } - - template - TYPENAME digraph_iterator::pointer digraph_iterator::operator->(void) const - throw(null_dereference,end_dereference) - { - return &(operator*()); - } - - //////////////////////////////////////////////////////////////////////////////// - // Arc Iterator - - template - digraph_arc_iterator::digraph_arc_iterator(void) - { - } - - // valid iterator - template - digraph_arc_iterator::digraph_arc_iterator(digraph_arc* arc) : - safe_iterator,digraph_arc >(arc->m_master) - { - } - - // end iterator - template - digraph_arc_iterator::digraph_arc_iterator(const digraph* owner) : - safe_iterator,digraph_arc >(owner) - { - } - - // alias an iterator - template - digraph_arc_iterator::digraph_arc_iterator(const safe_iterator, digraph_arc >& iterator) : - safe_iterator,digraph_arc >(iterator) - { - } - - template - digraph_arc_iterator::~digraph_arc_iterator(void) - { - } - - template - TYPENAME digraph_arc_iterator::const_iterator digraph_arc_iterator::constify (void) const - { - return digraph_arc_iterator(*this); - } - - template - TYPENAME digraph_arc_iterator::iterator digraph_arc_iterator::deconstify (void) const - { - return digraph_arc_iterator(*this); - } - - template - TYPENAME digraph_arc_iterator::this_iterator& digraph_arc_iterator::operator ++ (void) - throw(null_dereference,end_dereference) - { - this->assert_valid(); - if (this->node()->m_next) - this->set(this->node()->m_next->m_master); - else - this->set_end(); - return *this; - } - - template - TYPENAME digraph_arc_iterator::this_iterator digraph_arc_iterator::operator ++ (int) - throw(null_dereference,end_dereference) - { - // post-increment is defined in terms of the pre-increment - digraph_arc_iterator result(*this); - ++(*this); - return result; - } - - template - TYPENAME digraph_arc_iterator::this_iterator& digraph_arc_iterator::operator -- (void) - throw(null_dereference,end_dereference) - { - this->assert_valid(); - if (this->node()->m_prev) - this->set(this->node()->m_prev->m_master); - else - this->set_end(); - return *this; - } - - template - TYPENAME digraph_arc_iterator::this_iterator digraph_arc_iterator::operator -- (int) - throw(null_dereference,end_dereference) - { - // post-decrement is defined in terms of the pre-decrement - digraph_arc_iterator result(*this); - --(*this); - return result; - } - - template - bool digraph_arc_iterator::operator == (const TYPENAME digraph_arc_iterator::this_iterator& r) const - { - return equal(r); - } - - template - bool digraph_arc_iterator::operator != (const TYPENAME digraph_arc_iterator::this_iterator& r) const - { - return !operator==(r); - } - - template - bool digraph_arc_iterator::operator < (const TYPENAME digraph_arc_iterator::this_iterator& r) const - { - return compare(r) < 0; - } - - template - TYPENAME digraph_arc_iterator::reference digraph_arc_iterator::operator*(void) const - throw(null_dereference,end_dereference) - { - this->assert_valid(); - return this->node()->m_data; - } - - template - TYPENAME digraph_arc_iterator::pointer digraph_arc_iterator::operator->(void) const - throw(null_dereference,end_dereference) - { - return &(operator*()); - } - - //////////////////////////////////////////////////////////////////////////////// - // subtype utilities - - template - TYPENAME digraph::const_arc_vector digraph::constify_arcs(const TYPENAME digraph::arc_vector& arcs) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > result; - for (unsigned i = 0; i < arcs.size(); i++) - { - arcs[i].assert_valid(this); - result.push_back(arcs[i].constify()); - } - return result; - } - - template - TYPENAME digraph::arc_vector digraph::deconstify_arcs(const TYPENAME digraph::const_arc_vector& arcs) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > result; - for (unsigned i = 0; i < arcs.size(); i++) - { - arcs[i].assert_valid(this); - result.push_back(arcs[i].deconstify()); - } - return result; - } - - template - TYPENAME digraph::const_path_vector digraph::constify_paths(const TYPENAME digraph::path_vector& paths) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > > result; - for (unsigned i = 0; i < paths.size(); i++) - result.push_back(constify_arcs(paths[i])); - return result; - } - - template - TYPENAME digraph::path_vector digraph::deconstify_paths(const TYPENAME digraph::const_path_vector& paths) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > > result; - for (unsigned i = 0; i < paths.size(); i++) - result.push_back(deconstify_arcs(paths[i])); - return result; - } - - template - TYPENAME digraph::const_node_vector digraph::constify_nodes(const TYPENAME digraph::node_vector& nodes) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > result; - for (unsigned i = 0; i < nodes.size(); i++) - { - nodes[i].assert_valid(this); - result.push_back(nodes[i].constify()); - } - return result; - } - - template - TYPENAME digraph::node_vector digraph::deconstify_nodes(const TYPENAME digraph::const_node_vector& nodes) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > result; - for (unsigned i = 0; i < nodes.size(); i++) - { - nodes[i].assert_valid(this); - result.push_back(nodes[i].deconstify()); - } - return result; - } - - template - unsigned digraph::npos(void) - { - return(unsigned)-1; - } - - //////////////////////////////////////////////////////////////////////////////// - // Constructors etc. - - template - digraph::digraph(void) : - m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0) - { - // node and arc lists are circular double-linked lists - // they start out empty (no dummy end node) - } - - template - digraph::~digraph(void) - { - clear(); - } - - template - digraph::digraph(const digraph& r) : - m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0) - { - *this = r; - } - - template - digraph& digraph::operator=(const digraph& r) - { - // make it self-copy safe i.e. a=a; is a valid instruction - if (this == &r) return *this; - clear(); - // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents - std::map, digraph_iterator > xref; - for (digraph_iterator n = r.begin(); n != r.end(); n++) - xref[n] = insert(*n); - // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes - for (digraph_arc_iterator a = r.arc_begin(); a != r.arc_end(); a++) - arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a); - return *this; - } - - //////////////////////////////////////////////////////////////////////////////// - // Basic Node functions - - template - bool digraph::empty(void) const - { - return m_nodes_begin == 0; - } - - template - unsigned digraph::size(void) const - { - unsigned count = 0; - for (digraph_iterator i = begin(); i != end(); i++) - count++; - return count; - } - - template - TYPENAME digraph::iterator digraph::insert(const NT& node_data) - { - digraph_node* new_node = new digraph_node(this,node_data); - if (!m_nodes_end) - { - // insert into an empty list - m_nodes_begin = new_node; - m_nodes_end = new_node; - } - else - { - // insert at the end of the list - new_node->m_prev = m_nodes_end; - m_nodes_end->m_next = new_node; - m_nodes_end = new_node; - } - return digraph_iterator(new_node); - } - - template - TYPENAME digraph::iterator digraph::erase(TYPENAME digraph::iterator iter) - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - // remove all arcs connected to this node first - // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too - for (unsigned i = fanin(iter); i--; ) - arc_erase(input(iter,i)); - for (unsigned j = fanout(iter); j--; ) - arc_erase(output(iter,j)); - // now unlink the node from the list and delete it - if (iter.node()->m_next) - iter.node()->m_next->m_prev = iter.node()->m_prev; - if (iter.node()->m_prev) - iter.node()->m_prev->m_next = iter.node()->m_next; - digraph_node* next = iter.node()->m_next; - delete iter.node(); - // return the next node in the list - if (next) - return digraph_iterator(next); - else - return digraph_iterator(this); - } - - template - void digraph::clear(void) - { - // clearing the nodes also clears the arcs - for (digraph_iterator i = begin(); i != end(); ) - i = erase(i); - } - - template - TYPENAME digraph::const_iterator digraph::begin(void) const - { - if (m_nodes_begin) - return digraph_iterator(m_nodes_begin); - else - return digraph_iterator(this); - } - - template - TYPENAME digraph::iterator digraph::begin(void) - { - if (m_nodes_begin) - return digraph_iterator(m_nodes_begin); - else - return digraph_iterator(this); - } - - template - TYPENAME digraph::const_iterator digraph::end(void) const - { - return digraph_iterator(this); - } - - template - TYPENAME digraph::iterator digraph::end(void) - { - return digraph_iterator(this); - } - - template - unsigned digraph::fanin(TYPENAME digraph::const_iterator iter) const - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return iter.node()->m_inputs.size(); - } - - template - unsigned digraph::fanin(TYPENAME digraph::iterator iter) - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return iter.node()->m_inputs.size(); - } - - template - TYPENAME digraph::const_arc_iterator digraph::input(TYPENAME digraph::const_iterator iter, unsigned i) const - throw(wrong_object,null_dereference,end_dereference,std::out_of_range) - { - iter.assert_valid(this); - if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input"); - return digraph_arc_iterator(iter.node()->m_inputs[i]); - } - - template - TYPENAME digraph::arc_iterator digraph::input(TYPENAME digraph::iterator iter, unsigned i) - throw(wrong_object,null_dereference,end_dereference,std::out_of_range) - { - iter.assert_valid(this); - if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input"); - return digraph_arc_iterator(iter.node()->m_inputs[i]); - } - - template - unsigned digraph::fanout(TYPENAME digraph::const_iterator iter) const - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return iter.node()->m_outputs.size(); - } - - template - unsigned digraph::fanout(TYPENAME digraph::iterator iter) - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return iter.node()->m_outputs.size(); - } - - template - TYPENAME digraph::const_arc_iterator digraph::output(TYPENAME digraph::const_iterator iter, unsigned i) const - throw(wrong_object,null_dereference,end_dereference,std::out_of_range) - { - iter.assert_valid(this); - if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output"); - return digraph_arc_iterator(iter.node()->m_outputs[i]); - } - - template - TYPENAME digraph::arc_iterator digraph::output(TYPENAME digraph::iterator iter, unsigned i) - throw(wrong_object,null_dereference,end_dereference,std::out_of_range) - { - iter.assert_valid(this); - if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output"); - return digraph_arc_iterator(iter.node()->m_outputs[i]); - } - - template - TYPENAME digraph::const_arc_vector digraph::inputs(TYPENAME digraph::const_iterator node) const - throw(wrong_object,null_dereference,end_dereference) - { - node.assert_valid(this); - std::vector > result; - for (unsigned i = 0; i < fanin(node); i++) - result.push_back(input(node,i)); - return result; - } - - template - TYPENAME digraph::arc_vector digraph::inputs(TYPENAME digraph::iterator node) - throw(wrong_object,null_dereference,end_dereference) - { - node.assert_valid(this); - std::vector > result; - for (unsigned i = 0; i < fanin(node); i++) - result.push_back(input(node,i)); - return result; - } - - template - TYPENAME digraph::const_arc_vector digraph::outputs(TYPENAME digraph::const_iterator node) const - throw(wrong_object,null_dereference,end_dereference) - { - node.assert_valid(this); - std::vector > result; - for (unsigned i = 0; i < fanout(node); i++) - result.push_back(output(node,i)); - return result; - } - - template - TYPENAME digraph::arc_vector digraph::outputs(TYPENAME digraph::iterator node) - throw(wrong_object,null_dereference,end_dereference) - { - node.assert_valid(this); - std::vector > result; - for (unsigned i = 0; i < fanout(node); i++) - result.push_back(output(node,i)); - return result; - } - - template - unsigned digraph::output_offset(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_arc_iterator arc) const - throw(wrong_object,null_dereference,end_dereference) - { - from.assert_valid(this); - arc.assert_valid(this); - for (unsigned i = 0; i < fanout(from); i++) - { - if (output(from,i) == arc) - return i; - } - return digraph::npos(); - } - - template - unsigned digraph::output_offset(TYPENAME digraph::iterator from, - TYPENAME digraph::arc_iterator arc) - throw(wrong_object,null_dereference,end_dereference) - { - from.assert_valid(this); - arc.assert_valid(this); - for (unsigned i = 0; i < fanout(from); i++) - { - if (output(from,i) == arc) - return i; - } - return digraph::npos(); - } - - template - unsigned digraph::input_offset(TYPENAME digraph::const_iterator to, - TYPENAME digraph::const_arc_iterator arc) const - throw(wrong_object,null_dereference,end_dereference) - { - to.assert_valid(this); - arc.assert_valid(this); - for (unsigned i = 0; i < fanin(to); i++) - { - if (input(to,i) == arc) - return i; - } - return digraph::npos(); - } - - template - unsigned digraph::input_offset(TYPENAME digraph::iterator to, - TYPENAME digraph::arc_iterator arc) - throw(wrong_object,null_dereference,end_dereference) - { - to.assert_valid(this); - arc.assert_valid(this); - for (unsigned i = 0; i < fanin(to); i++) - { - if (input(to,i) == arc) - return i; - } - return digraph::npos(); - } - - //////////////////////////////////////////////////////////////////////////////// - // Basic Arc functions - - template - bool digraph::arc_empty(void) const - { - return m_arcs_end == 0; - } - - template - unsigned digraph::arc_size(void) const - { - unsigned count = 0; - for (digraph_arc_iterator i = arc_begin(); i != arc_end(); i++) - count++; - return count; - } - - template - TYPENAME digraph::arc_iterator digraph::arc_insert(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to, - const AT& arc_data) - throw(wrong_object,null_dereference,end_dereference) - { - from.assert_valid(this); - to.assert_valid(this); - // create the new arc and link it in to the arc list - digraph_arc* new_arc = new digraph_arc(this, from.node(), to.node(), arc_data); - if (!m_arcs_end) - { - // insert into an empty list - m_arcs_begin = new_arc; - m_arcs_end = new_arc; - } - else - { - // insert at the end of the list - new_arc->m_prev = m_arcs_end; - m_arcs_end->m_next = new_arc; - m_arcs_end = new_arc; - } - // add this arc to the inputs and outputs of the end nodes - from.node()->m_outputs.push_back(new_arc); - to.node()->m_inputs.push_back(new_arc); - return digraph_arc_iterator(new_arc); - } - - template - TYPENAME digraph::arc_iterator digraph::arc_erase(TYPENAME digraph::arc_iterator iter) - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - // first remove this arc's pointers from the from/to nodes - for (TYPENAME std::vector*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); ) - { - if (*i == iter.node()) - i = iter.node()->m_to->m_inputs.erase(i); - else - i++; - } - for (TYPENAME std::vector*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); ) - { - if (*o == iter.node()) - o = iter.node()->m_from->m_outputs.erase(o); - else - o++; - } - // now unlink the arc from the list and delete it - if (iter.node()->m_next) - iter.node()->m_next->m_prev = iter.node()->m_prev; - if (iter.node()->m_prev) - iter.node()->m_prev->m_next = iter.node()->m_next; - digraph_arc* next = iter.node()->m_next; - delete iter.node(); - if (next) - return digraph_arc_iterator(next); - else - return digraph_arc_iterator(this); - } - - template - void digraph::arc_clear(void) - { - for (digraph_arc_iterator a = arc_begin(); a != arc_end(); ) - a = arc_erase(a); - } - - template - TYPENAME digraph::const_arc_iterator digraph::arc_begin(void) const - { - if (m_arcs_begin) - return digraph_arc_iterator(m_arcs_begin); - else - return digraph_arc_iterator(this); - } - - template - TYPENAME digraph::arc_iterator digraph::arc_begin(void) - { - if (m_arcs_begin) - return digraph_arc_iterator(m_arcs_begin); - else - return digraph_arc_iterator(this); - } - - template - TYPENAME digraph::const_arc_iterator digraph::arc_end(void) const - { - return digraph_arc_iterator(this); - } - - template - TYPENAME digraph::arc_iterator digraph::arc_end(void) - { - return digraph_arc_iterator(this); - } - - template - TYPENAME digraph::const_iterator digraph::arc_from(TYPENAME digraph::const_arc_iterator iter) const - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return digraph_iterator(iter.node()->m_from); - } - - template - TYPENAME digraph::iterator digraph::arc_from(TYPENAME digraph::arc_iterator iter) - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return digraph_iterator(iter.node()->m_from); - } - - template - TYPENAME digraph::const_iterator digraph::arc_to(TYPENAME digraph::const_arc_iterator iter) const - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return digraph_iterator(iter.node()->m_to); - } - - template - TYPENAME digraph::iterator digraph::arc_to(TYPENAME digraph::arc_iterator iter) - throw(wrong_object,null_dereference,end_dereference) - { - iter.assert_valid(this); - return digraph_iterator(iter.node()->m_to); - } - - template - void digraph::arc_move(TYPENAME digraph::arc_iterator arc, - TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to) - throw(wrong_object,null_dereference,end_dereference) - { - arc_move_to(arc,to); - arc_move_from(arc,from); - } - - template - void digraph::arc_move_from(TYPENAME digraph::arc_iterator arc, - TYPENAME digraph::iterator from) - throw(wrong_object,null_dereference,end_dereference) - { - arc.assert_valid(this); - from.assert_valid(this); - for (TYPENAME std::vector*>::iterator o = arc.node()->m_from->m_outputs.begin(); o != arc.node()->m_from->m_outputs.end(); ) - { - if (*o == arc.node()) - o = arc.node()->m_from->m_outputs.erase(o); - else - o++; - } - from.node()->m_outputs.push_back(arc.node()); - arc.node()->m_from = from.node(); - } - - template - void digraph::arc_move_to(TYPENAME digraph::arc_iterator arc, - TYPENAME digraph::iterator to) - throw(wrong_object,null_dereference,end_dereference) - { - arc.assert_valid(this); - to.assert_valid(this); - for (TYPENAME std::vector*>::iterator i = arc.node()->m_to->m_inputs.begin(); i != arc.node()->m_to->m_inputs.end(); ) - { - if (*i == arc.node()) - i = arc.node()->m_to->m_inputs.erase(i); - else - i++; - } - to.node()->m_inputs.push_back(arc.node()); - arc.node()->m_to = to.node(); - } - - template - void digraph::arc_flip(TYPENAME digraph::arc_iterator arc) - throw(wrong_object,null_dereference,end_dereference) - { - arc_move(arc,arc_to(arc),arc_from(arc)); - } - - //////////////////////////////////////////////////////////////////////////////// - // Adjacency Algorithms - - template - bool digraph::adjacent(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to) const - throw(wrong_object,null_dereference,end_dereference) - { - return adjacent_arc(from,to) != arc_end(); - } - - template - bool digraph::adjacent(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to) - throw(wrong_object,null_dereference,end_dereference) - { - return adjacent_arc(from,to) != arc_end(); - } - - template - TYPENAME digraph::const_arc_iterator digraph::adjacent_arc(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to) const - throw(wrong_object,null_dereference,end_dereference) - { - from.assert_valid(this); - to.assert_valid(this); - for (unsigned arc = 0; arc < fanout(from); arc++) - { - if (arc_to(output(from, arc)) == to) - return output(from,arc); - } - return arc_end(); - } - - template - TYPENAME digraph::arc_iterator digraph::adjacent_arc(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to) - throw(wrong_object,null_dereference,end_dereference) - { - return adjacent_arc(from.constify(), to.constify()).deconstify(); - } - - template - TYPENAME digraph::const_arc_vector digraph::adjacent_arcs(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to) const - throw(wrong_object,null_dereference,end_dereference) - { - from.assert_valid(this); - to.assert_valid(this); - std::vector > result; - for (unsigned arc = 0; arc < fanout(from); arc++) - { - if (arc_to(output(from, arc)) == to) - result.push_back(output(from,arc)); - } - return result; - } - - template - TYPENAME digraph::arc_vector digraph::adjacent_arcs(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_arcs(adjacent_arcs(from.constify(), to.constify())); - } - - template - TYPENAME digraph::const_node_vector digraph::input_adjacencies(TYPENAME digraph::const_iterator to) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > result; - for (unsigned arc = 0; arc < fanin(to); arc++) - { - digraph_iterator from = arc_from(input(to, arc)); - if (std::find(result.begin(), result.end(), from) == result.end()) - result.push_back(from); - } - return result; - } - - template - TYPENAME digraph::node_vector digraph::input_adjacencies(TYPENAME digraph::iterator to) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_nodes(input_adjacencies(to.constify())); - } - - template - TYPENAME digraph::const_node_vector digraph::output_adjacencies(TYPENAME digraph::const_iterator from) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > result; - for (unsigned arc = 0; arc < fanout(from); arc++) - { - digraph_iterator to = arc_to(output(from, arc)); - if (find(result.begin(), result.end(), to) == result.end()) - result.push_back(to); - } - return result; - } - - template - TYPENAME digraph::node_vector digraph::output_adjacencies(TYPENAME digraph::iterator from) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_nodes(output_adjacencies(from.constify())); - } - - //////////////////////////////////////////////////////////////////////////////// - // Topographical Sort Algorithms - - template - std::pair::const_node_vector, TYPENAME digraph::const_arc_vector> - digraph::sort(TYPENAME digraph::arc_select_fn select) const - { - std::vector > result; - std::vector > errors; - // build a map containing the number of fanins to each node that must be visited before this one - std::map,unsigned> fanin_map; - for (digraph_iterator n = begin(); n != end(); n++) - { - unsigned predecessors = 0; - // only count predecessors connected by selected arcs - for (unsigned f = 0; f < fanin(n); f++) - { - digraph_arc_iterator input_arc = input(n,f); - digraph_iterator predecessor = arc_from(input_arc); - if (!select || select(*this,input_arc)) - predecessors++; - } - if (predecessors == 0) - { - result.push_back(n); - } - else - { - fanin_map[n] = predecessors; - } - } - // main algorithm applies the topographical sort repeatedly. For a DAG, it - // will complete first time. However, with backward arcs, the first - // iteration will fail. The algorithm then tries breaking random arcs to try - // to get an ordering. - for(unsigned i = 0; !fanin_map.empty(); ) - { - // now visit each node in traversal order, decrementing the fanin count of - // all successors. As each successor's fanin count goes to zero, it is - // appended to the result. - for (; i < result.size(); i++) - { - // Note: dereferencing gives us a node iterator - digraph_iterator current = result[i]; - for (unsigned f = 0; f < fanout(current); f++) - { - // only consider successors connected by selected arcs - digraph_arc_iterator output_arc = output(current, f); - digraph_iterator successor = arc_to(output_arc); - if (!select || select(*this,output_arc)) - { - // don't consider arcs that have been eliminated to break a loop - if (fanin_map.find(successor) != fanin_map.end()) - { - --fanin_map[successor]; - if ((fanin_map[successor]) == 0) - { - result.push_back(successor); - fanin_map.erase(fanin_map.find(successor)); - } - } - } - } - } - if (!fanin_map.empty()) - { - // there must be backward arcs preventing completion - // try removing arcs from the sort to get a partial ordering containing all the nodes - - // select an arc that is still relevant to the sort and break it - // first select a node that has non-zero fanin and its predecessor that has non-zero fanin - digraph_iterator stuck_node = fanin_map.begin()->first; - for (unsigned f = 0; f < fanin(stuck_node); f++) - { - // now successively remove input arcs that are still part of the sort until the fanin reduces to zero - // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm - digraph_arc_iterator input_arc = input(stuck_node, f); - if (!select || select(*this,input_arc)) - { - digraph_iterator predecessor = arc_from(input_arc); - if (fanin_map.find(predecessor) != fanin_map.end()) - { - // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop - errors.push_back(input_arc); - --fanin_map[stuck_node]; - if ((fanin_map[stuck_node]) == 0) - { - result.push_back(stuck_node); - fanin_map.erase(fanin_map.find(stuck_node)); - break; - } - } - } - } - } - } - return std::make_pair(result,errors); - } - - template - std::pair::node_vector, TYPENAME digraph::arc_vector> - digraph::sort(TYPENAME digraph::arc_select_fn select) - { - std::pair >, - std::vector > > const_result = - const_cast*>(this)->sort(select); - - std::pair >, - std::vector > > result = - std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second)); - return result; - } - - template - TYPENAME digraph::const_node_vector digraph::dag_sort(TYPENAME digraph::arc_select_fn select) const - { - std::pair >, - std::vector > > result = sort(select); - if (result.second.empty()) return result.first; - return std::vector >(); - } - - template - TYPENAME digraph::node_vector digraph::dag_sort(TYPENAME digraph::arc_select_fn select) - { - return deconstify_nodes(const_cast*>(this)->dag_sort(select)); - } - //////////////////////////////////////////////////////////////////////////////// - // Path Algorithms - - template - bool digraph::path_exists_r(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to, - TYPENAME digraph::const_iterator_set& visited, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // Recursive part of the digraph::path_exists function. This is based on a - // depth first search algorithm and stops the moment it finds a path - // regardless of its length. Simply traverse every output and recurse on that - // node until we find the to node or run out of things to recurse on. However, - // to avoid infinite recursion due to cycles in the graph, I need to maintain - // a set of visited nodes. The visited set is updated when a candidate is - // found but tested before the recursion on the candidate so that the number of - // function calls is minimised. - for (unsigned i = 0; i < fanout(from); i++) - { - digraph_arc_iterator arc = output(from,i); - if (!select || select(*this, arc)) - { - digraph_iterator node = arc_to(arc); - // if the node is the target, return immediately - if (node == to) return true; - // update the visited set and give up if the insert fails, which indicates that the node has already been visited - if (!(visited.insert(node).second)) return false; - // now recurse - a path exists from from to to if a path exists from an adjacent node to to - if (path_exists_r(node,to,visited,select)) return true; - } - } - return false; - } - - template - bool digraph::path_exists(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // set up the recursion with its initial visited set and then recurse - std::set > visited; - visited.insert(from); - return path_exists_r(from, to, visited, select); - } - - template - bool digraph::path_exists(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to, - TYPENAME digraph::arc_select_fn select) - throw(wrong_object,null_dereference,end_dereference) - { - return path_exists(from.constify(), to.constify(), select); - } - - template - void digraph::all_paths_r(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to, - TYPENAME digraph::const_arc_vector& so_far, - TYPENAME digraph::const_path_vector& result, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // This is the recursive part of the all_paths function. The field so_far - // contains the path so far so that when 'to' is reached, the path is - // complete. It serves the same purpose as the visited set in the path_exists - // function except that it also preserves the path order. It also serves the - // purpose of detecting cycles and thus stopping infinite recursion. Every - // time the recursion reaches the to node, a copy of so_far is appended to the - // path set. - for (unsigned i = 0; i < fanout(from); i++) - { - digraph_arc_iterator candidate = output(from,i); - // assert_valid that the arc is selected and then assert_valid that the candidate has not - // been visited on this path and only allow further recursion if it hasn't - if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end()) - { - // extend the path tracing the route to this arc - so_far.push_back(candidate); - // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse - if (arc_to(candidate) == to) - result.push_back(so_far); - else - all_paths_r(arc_to(candidate),to,so_far,result,select); - so_far.pop_back(); - } - } - } - - template - TYPENAME digraph::const_path_vector - digraph::all_paths(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // set up the recursion with empty data fields and then recurse - std::vector > > result; - std::vector > so_far; - all_paths_r(from, to, so_far, result, select); - return result; - } - - template - TYPENAME digraph::path_vector - digraph::all_paths(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to, - TYPENAME digraph::arc_select_fn select) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_paths(all_paths(from.constify(), to.constify(), select)); - } - - template - void digraph::reachable_nodes_r(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator_set& visited, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // The recursive part of the reachable_nodes function. - // This is a depth-first traversal again but this time it carries on to find all the reachable nodes - // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles - for (unsigned i = 0; i < fanout(from); i++) - { - digraph_arc_iterator arc = output(from,i); - if (!select || select(*this,arc)) - { - digraph_iterator candidate = arc_to(arc); - if (visited.insert(candidate).second) - reachable_nodes_r(candidate,visited,select); - } - } - } - - template - TYPENAME digraph::const_node_vector - digraph::reachable_nodes(TYPENAME digraph::const_iterator from, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // seed the recursion, marking the starting node as already visited - std::set > visited; - visited.insert(from); - reachable_nodes_r(from, visited, select); - // convert the visited set into the required output form - // exclude the starting node - std::vector > result; - for (TYPENAME std::set >::iterator i = visited.begin(); i != visited.end(); i++) - if (*i != from) - result.push_back(*i); - return result; - } - - template - TYPENAME digraph::node_vector - digraph::reachable_nodes(TYPENAME digraph::iterator from, - TYPENAME digraph::arc_select_fn select) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_nodes(reachable_nodes(from.constify(), select)); - } - - template - void digraph::reaching_nodes_r(TYPENAME digraph::const_iterator to, - TYPENAME digraph::const_iterator_set& visited, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // The recursive part of the reaching_nodes function. - // Just like the reachable_nodes_r function but it goes backwards - for (unsigned i = 0; i < fanin(to); i++) - { - digraph_arc_iterator arc = input(to,i); - if (!select || select(*this,arc)) - { - digraph_iterator candidate = arc_from(input(to,i)); - if (visited.insert(candidate).second) - reaching_nodes_r(candidate,visited,select); - } - } - } - - template - TYPENAME digraph::const_node_vector - digraph::reaching_nodes(TYPENAME digraph::const_iterator to, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - // seed the recursion, marking the starting node as already visited - std::set > visited; - visited.insert(to); - reaching_nodes_r(to,visited,select); - // convert the visited set into the required output form - // exclude the end node - std::vector > result; - for (TYPENAME std::set >::iterator i = visited.begin(); i != visited.end(); i++) - if (*i != to) - result.push_back(*i); - return result; - } - - template - TYPENAME digraph::node_vector - digraph::reaching_nodes(TYPENAME digraph::iterator to, - TYPENAME digraph::arc_select_fn select) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_nodes(reaching_nodes(to.constify(),select)); - } - - //////////////////////////////////////////////////////////////////////////////// - // Shortest Path Algorithms - - template - TYPENAME digraph::const_arc_vector - digraph::shortest_path(TYPENAME digraph::const_iterator from, - TYPENAME digraph::const_iterator to, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - std::vector > > paths = all_paths(from,to,select); - std::vector > shortest; - for (TYPENAME std::vector > >::iterator i = paths.begin(); i != paths.end(); i++) - if (shortest.empty() || i->size() < shortest.size()) - shortest = *i; - return shortest; - } - - template - TYPENAME digraph::arc_vector - digraph::shortest_path(TYPENAME digraph::iterator from, - TYPENAME digraph::iterator to, - TYPENAME digraph::arc_select_fn select) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_arcs(shortest_path(from.constify(),to.constify(),select)); - } - - template - TYPENAME digraph::const_path_vector - digraph::shortest_paths(TYPENAME digraph::const_iterator from, - TYPENAME digraph::arc_select_fn select) const - throw(wrong_object,null_dereference,end_dereference) - { - from.assert_valid(this); - // This is an unweighted shortest path algorithm based on the algorithm from - // Weiss's book. This is essentially a breadth-first traversal or graph - // colouring algorithm. It is an iterative algorithm, so no recursion here! It - // works by creating a node queue initialised with the starting node. It then - // consumes the queue from front to back. For each node, it finds the - // successors and appends them to the queue. If a node is already 'known' it - // is not added - this avoids cycles. Thus the queue insert ordering - // represents the breadth-first ordering. On the way it creates a map of - // visited nodes. This is a map not a set because it also stores the arc that - // nominated this node as a shortest path. The full path can then be recreated - // from the map by just walking back through the predecessors. The depth (or - // colour) can be determined by the path length. - std::vector > > result; - // initialise the iteration by creating a queue and adding the start node - std::deque > nodes; - nodes.push_back(from); - // Create a map to store the set of known nodes mapped to their predecessor - // arcs. Initialise it with the current node, which has no predecessor. Note - // that the algorithm uses the feature of digraph iterators that they can be - // null iterators and that all null iterators are equal. - typedef std::map, - digraph_arc_iterator > known_map; - known_map known; - known.insert(std::make_pair(from,digraph_arc_iterator())); - // now the iterative part of the algorithm - while(!nodes.empty()) - { - // pop the queue to get the next node to process - unfortunately the STL - // deque::pop does not return the popped value - digraph_iterator current = nodes.front(); - nodes.pop_front(); - // now visit all the successors - for (unsigned i = 0; i < fanout(current); i++) - { - digraph_arc_iterator next_arc = output(current,i); - // assert_valid whether the successor arc is a selected arc and can be part of a path - if (!select || select(*this,next_arc)) - { - digraph_iterator next = arc_to(next_arc); - // Discard any successors that are known because to be known already they - // must have another shorter path. Otherwise add the successor node to the - // queue to be visited later. To minimise the overhead of map lookup I use - // the usual trick of trying to insert the node and determining whether - // the node was known by the success or failure of the insertion - this is - // a Good STL Trick (TM). - if (known.insert(std::make_pair(next,next_arc)).second) - nodes.push_back(next); - } - } - } - // The map contains the results as an unordered set of nodes, mapped to their - // predecessor arcs and weight. This now needs to be converted into a set of - // paths. This is done by starting with a node from the map, finding its - // predecessor arc and therefore its predecessor node, looking that up in the - // map to find its predecessor and so on until the start node is reached (it - // has a null predecessor). Note that the known set includes the from node - // which does not generate a path. - for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++) - { - if (i->first != from) - { - const_arc_vector this_path; - for (TYPENAME known_map::iterator node = i; - node->second.valid(); - node = known.find(arc_from(node->second))) - this_path.insert(this_path.begin(),node->second); - result.push_back(this_path); - } - } - return result; - } - - template - TYPENAME digraph::path_vector - digraph::shortest_paths(TYPENAME digraph::iterator from, - TYPENAME digraph::arc_select_fn select) - throw(wrong_object,null_dereference,end_dereference) - { - return deconstify_paths(shortest_paths(from.constify(),select)); - } - - //////////////////////////////////////////////////////////////////////////////// - -} // end namespace stlplus +//////////////////////////////////////////////////////////////////////////////// + +// Author: Andy Rushton +// Copyright: (c) Southampton University 1999-2004 +// (c) Andy Rushton 2004 onwards +// License: BSD License, see ../docs/license.html + +// Note: I tried to write this using STL lists for the node and arc lists, but +// it got far too hairy. The specific problem is that I wanted a digraph +// iterator to contain a list::iterator so I needed to be able to generate a +// list::iterator from a node or arc and STL list iterators don't give you that +// functionality. I tried burgling the data structures, but that was +// non-portable between different STL implementations so needed lots of #ifdefs +// and so was mind-bogglingly awful and unreadable - in other words a +// maintenance nightmare. I gave up and impemented my own lists - not difficult. + +// I use circular double-linked lists. The circular design means that both +// ends of the list are equally accessible in unit time. An empty list +// contains no objects. There is no end node in the list - unlike the STL +// lists which have a dummy node for end iterators to point to - +// conceptually the end iterator points one element beyond the end of the +// list. However, I implement the end iterator concept in the iterator +// itself, so do not need the dummy end node. + +//////////////////////////////////////////////////////////////////////////////// +#include +#include + +//////////////////////////////////////////////////////////////////////////////// +// Internals + +namespace stlplus +{ + + template + class digraph_node + { + public: + master_iterator, digraph_node > m_master; + NT m_data; + digraph_node* m_prev; + digraph_node* m_next; + std::vector*> m_inputs; + std::vector*> m_outputs; + public: + digraph_node(const digraph* owner, const NT& d = NT()) : + m_master(owner,this), m_data(d), m_prev(0), m_next(0) + { + } + ~digraph_node(void) + { + } + }; + + template + class digraph_arc + { + public: + master_iterator, digraph_arc > m_master; + AT m_data; + digraph_arc* m_prev; + digraph_arc* m_next; + digraph_node* m_from; + digraph_node* m_to; + digraph_arc(const digraph* owner, digraph_node* from = 0, digraph_node* to = 0, const AT& d = AT()) : + m_master(owner,this), m_data(d), m_prev(0), m_next(0), m_from(from), m_to(to) + { + } + }; + + //////////////////////////////////////////////////////////////////////////////// + // Iterators + //////////////////////////////////////////////////////////////////////////////// + + //////////////////////////////////////////////////////////////////////////////// + // Node iterator + + // construct a null iterator + template + digraph_iterator::digraph_iterator(void) + { + } + + // valid iterator + template + digraph_iterator::digraph_iterator(digraph_node* node) : + safe_iterator,digraph_node >(node->m_master) + { + } + + // end iterator + template + digraph_iterator::digraph_iterator(const digraph* owner) : + safe_iterator,digraph_node >(owner) + { + } + + // alias an iterator + template + digraph_iterator::digraph_iterator(const safe_iterator, digraph_node >& iterator) : + safe_iterator,digraph_node >(iterator) + { + } + + // destructor + template + digraph_iterator::~digraph_iterator(void) + { + } + + template + TYPENAME digraph_iterator::const_iterator digraph_iterator::constify (void) const + { + return digraph_iterator(*this); + } + + template + TYPENAME digraph_iterator::iterator digraph_iterator::deconstify (void) const + { + return digraph_iterator(*this); + } + + template + TYPENAME digraph_iterator::this_iterator& digraph_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_next) + this->set(this->node()->m_next->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_iterator::this_iterator digraph_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + // post-increment is defined in terms of the pre-increment + digraph_iterator result(*this); + ++(*this); + return result; + } + + template + TYPENAME digraph_iterator::this_iterator& digraph_iterator::operator -- (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_prev) + this->set(this->node()->m_prev->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_iterator::this_iterator digraph_iterator::operator -- (int) + throw(null_dereference,end_dereference) + { + // post-decrement is defined in terms of the pre-decrement + digraph_iterator result(*this); + --(*this); + return result; + } + + template + bool digraph_iterator::operator == (const TYPENAME digraph_iterator::this_iterator& r) const + { + return equal(r); + } + + template + bool digraph_iterator::operator != (const TYPENAME digraph_iterator::this_iterator& r) const + { + return !operator==(r); + } + + template + bool digraph_iterator::operator < (const TYPENAME digraph_iterator::this_iterator& r) const + { + return compare(r) < 0; + } + + template + TYPENAME digraph_iterator::reference digraph_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + this->assert_valid(); + return this->node()->m_data; + } + + template + TYPENAME digraph_iterator::pointer digraph_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return &(operator*()); + } + + //////////////////////////////////////////////////////////////////////////////// + // Arc Iterator + + template + digraph_arc_iterator::digraph_arc_iterator(void) + { + } + + // valid iterator + template + digraph_arc_iterator::digraph_arc_iterator(digraph_arc* arc) : + safe_iterator,digraph_arc >(arc->m_master) + { + } + + // end iterator + template + digraph_arc_iterator::digraph_arc_iterator(const digraph* owner) : + safe_iterator,digraph_arc >(owner) + { + } + + // alias an iterator + template + digraph_arc_iterator::digraph_arc_iterator(const safe_iterator, digraph_arc >& iterator) : + safe_iterator,digraph_arc >(iterator) + { + } + + template + digraph_arc_iterator::~digraph_arc_iterator(void) + { + } + + template + TYPENAME digraph_arc_iterator::const_iterator digraph_arc_iterator::constify (void) const + { + return digraph_arc_iterator(*this); + } + + template + TYPENAME digraph_arc_iterator::iterator digraph_arc_iterator::deconstify (void) const + { + return digraph_arc_iterator(*this); + } + + template + TYPENAME digraph_arc_iterator::this_iterator& digraph_arc_iterator::operator ++ (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_next) + this->set(this->node()->m_next->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_arc_iterator::this_iterator digraph_arc_iterator::operator ++ (int) + throw(null_dereference,end_dereference) + { + // post-increment is defined in terms of the pre-increment + digraph_arc_iterator result(*this); + ++(*this); + return result; + } + + template + TYPENAME digraph_arc_iterator::this_iterator& digraph_arc_iterator::operator -- (void) + throw(null_dereference,end_dereference) + { + this->assert_valid(); + if (this->node()->m_prev) + this->set(this->node()->m_prev->m_master); + else + this->set_end(); + return *this; + } + + template + TYPENAME digraph_arc_iterator::this_iterator digraph_arc_iterator::operator -- (int) + throw(null_dereference,end_dereference) + { + // post-decrement is defined in terms of the pre-decrement + digraph_arc_iterator result(*this); + --(*this); + return result; + } + + template + bool digraph_arc_iterator::operator == (const TYPENAME digraph_arc_iterator::this_iterator& r) const + { + return equal(r); + } + + template + bool digraph_arc_iterator::operator != (const TYPENAME digraph_arc_iterator::this_iterator& r) const + { + return !operator==(r); + } + + template + bool digraph_arc_iterator::operator < (const TYPENAME digraph_arc_iterator::this_iterator& r) const + { + return compare(r) < 0; + } + + template + TYPENAME digraph_arc_iterator::reference digraph_arc_iterator::operator*(void) const + throw(null_dereference,end_dereference) + { + this->assert_valid(); + return this->node()->m_data; + } + + template + TYPENAME digraph_arc_iterator::pointer digraph_arc_iterator::operator->(void) const + throw(null_dereference,end_dereference) + { + return &(operator*()); + } + + //////////////////////////////////////////////////////////////////////////////// + // subtype utilities + + template + TYPENAME digraph::const_arc_vector digraph::constify_arcs(const TYPENAME digraph::arc_vector& arcs) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < arcs.size(); i++) + { + arcs[i].assert_valid(this); + result.push_back(arcs[i].constify()); + } + return result; + } + + template + TYPENAME digraph::arc_vector digraph::deconstify_arcs(const TYPENAME digraph::const_arc_vector& arcs) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < arcs.size(); i++) + { + arcs[i].assert_valid(this); + result.push_back(arcs[i].deconstify()); + } + return result; + } + + template + TYPENAME digraph::const_path_vector digraph::constify_paths(const TYPENAME digraph::path_vector& paths) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > > result; + for (unsigned i = 0; i < paths.size(); i++) + result.push_back(constify_arcs(paths[i])); + return result; + } + + template + TYPENAME digraph::path_vector digraph::deconstify_paths(const TYPENAME digraph::const_path_vector& paths) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > > result; + for (unsigned i = 0; i < paths.size(); i++) + result.push_back(deconstify_arcs(paths[i])); + return result; + } + + template + TYPENAME digraph::const_node_vector digraph::constify_nodes(const TYPENAME digraph::node_vector& nodes) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < nodes.size(); i++) + { + nodes[i].assert_valid(this); + result.push_back(nodes[i].constify()); + } + return result; + } + + template + TYPENAME digraph::node_vector digraph::deconstify_nodes(const TYPENAME digraph::const_node_vector& nodes) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned i = 0; i < nodes.size(); i++) + { + nodes[i].assert_valid(this); + result.push_back(nodes[i].deconstify()); + } + return result; + } + + template + unsigned digraph::npos(void) + { + return(unsigned)-1; + } + + //////////////////////////////////////////////////////////////////////////////// + // Constructors etc. + + template + digraph::digraph(void) : + m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0) + { + // node and arc lists are circular double-linked lists + // they start out empty (no dummy end node) + } + + template + digraph::~digraph(void) + { + clear(); + } + + template + digraph::digraph(const digraph& r) : + m_nodes_begin(0), m_nodes_end(0), m_arcs_begin(0), m_arcs_end(0) + { + *this = r; + } + + template + digraph& digraph::operator=(const digraph& r) + { + // make it self-copy safe i.e. a=a; is a valid instruction + if (this == &r) return *this; + clear(); + // first phase is to copy the nodes, creating a map of cross references from the old nodes to their new equivalents + std::map, digraph_iterator > xref; + for (digraph_iterator n = r.begin(); n != r.end(); n++) + xref[n] = insert(*n); + // second phase is to copy the arcs, using the map to convert the old to and from nodes to the new nodes + for (digraph_arc_iterator a = r.arc_begin(); a != r.arc_end(); a++) + arc_insert(xref[r.arc_from(a)],xref[r.arc_to(a)],*a); + return *this; + } + + //////////////////////////////////////////////////////////////////////////////// + // Basic Node functions + + template + bool digraph::empty(void) const + { + return m_nodes_begin == 0; + } + + template + unsigned digraph::size(void) const + { + unsigned count = 0; + for (digraph_iterator i = begin(); i != end(); i++) + count++; + return count; + } + + template + TYPENAME digraph::iterator digraph::insert(const NT& node_data) + { + digraph_node* new_node = new digraph_node(this,node_data); + if (!m_nodes_end) + { + // insert into an empty list + m_nodes_begin = new_node; + m_nodes_end = new_node; + } + else + { + // insert at the end of the list + new_node->m_prev = m_nodes_end; + m_nodes_end->m_next = new_node; + m_nodes_end = new_node; + } + return digraph_iterator(new_node); + } + + template + TYPENAME digraph::iterator digraph::erase(TYPENAME digraph::iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + // remove all arcs connected to this node first + // use arc_erase rather than arcs.erase because that tidies up the node at the other end of the arc too + for (unsigned i = fanin(iter); i--; ) + arc_erase(input(iter,i)); + for (unsigned j = fanout(iter); j--; ) + arc_erase(output(iter,j)); + // now unlink the node from the list and delete it + if (iter.node()->m_next) + iter.node()->m_next->m_prev = iter.node()->m_prev; + if (iter.node()->m_prev) + iter.node()->m_prev->m_next = iter.node()->m_next; + digraph_node* next = iter.node()->m_next; + delete iter.node(); + // return the next node in the list + if (next) + return digraph_iterator(next); + else + return digraph_iterator(this); + } + + template + void digraph::clear(void) + { + // clearing the nodes also clears the arcs + for (digraph_iterator i = begin(); i != end(); ) + i = erase(i); + } + + template + TYPENAME digraph::const_iterator digraph::begin(void) const + { + if (m_nodes_begin) + return digraph_iterator(m_nodes_begin); + else + return digraph_iterator(this); + } + + template + TYPENAME digraph::iterator digraph::begin(void) + { + if (m_nodes_begin) + return digraph_iterator(m_nodes_begin); + else + return digraph_iterator(this); + } + + template + TYPENAME digraph::const_iterator digraph::end(void) const + { + return digraph_iterator(this); + } + + template + TYPENAME digraph::iterator digraph::end(void) + { + return digraph_iterator(this); + } + + template + unsigned digraph::fanin(TYPENAME digraph::const_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_inputs.size(); + } + + template + unsigned digraph::fanin(TYPENAME digraph::iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_inputs.size(); + } + + template + TYPENAME digraph::const_arc_iterator digraph::input(TYPENAME digraph::const_iterator iter, unsigned i) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input"); + return digraph_arc_iterator(iter.node()->m_inputs[i]); + } + + template + TYPENAME digraph::arc_iterator digraph::input(TYPENAME digraph::iterator iter, unsigned i) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_inputs.size()) throw std::out_of_range("digraph::input"); + return digraph_arc_iterator(iter.node()->m_inputs[i]); + } + + template + unsigned digraph::fanout(TYPENAME digraph::const_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_outputs.size(); + } + + template + unsigned digraph::fanout(TYPENAME digraph::iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return iter.node()->m_outputs.size(); + } + + template + TYPENAME digraph::const_arc_iterator digraph::output(TYPENAME digraph::const_iterator iter, unsigned i) const + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output"); + return digraph_arc_iterator(iter.node()->m_outputs[i]); + } + + template + TYPENAME digraph::arc_iterator digraph::output(TYPENAME digraph::iterator iter, unsigned i) + throw(wrong_object,null_dereference,end_dereference,std::out_of_range) + { + iter.assert_valid(this); + if (i >= iter.node()->m_outputs.size()) throw std::out_of_range("digraph::output"); + return digraph_arc_iterator(iter.node()->m_outputs[i]); + } + + template + TYPENAME digraph::const_arc_vector digraph::inputs(TYPENAME digraph::const_iterator node) const + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanin(node); i++) + result.push_back(input(node,i)); + return result; + } + + template + TYPENAME digraph::arc_vector digraph::inputs(TYPENAME digraph::iterator node) + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanin(node); i++) + result.push_back(input(node,i)); + return result; + } + + template + TYPENAME digraph::const_arc_vector digraph::outputs(TYPENAME digraph::const_iterator node) const + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanout(node); i++) + result.push_back(output(node,i)); + return result; + } + + template + TYPENAME digraph::arc_vector digraph::outputs(TYPENAME digraph::iterator node) + throw(wrong_object,null_dereference,end_dereference) + { + node.assert_valid(this); + std::vector > result; + for (unsigned i = 0; i < fanout(node); i++) + result.push_back(output(node,i)); + return result; + } + + template + unsigned digraph::output_offset(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_arc_iterator arc) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanout(from); i++) + { + if (output(from,i) == arc) + return i; + } + return digraph::npos(); + } + + template + unsigned digraph::output_offset(TYPENAME digraph::iterator from, + TYPENAME digraph::arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanout(from); i++) + { + if (output(from,i) == arc) + return i; + } + return digraph::npos(); + } + + template + unsigned digraph::input_offset(TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_arc_iterator arc) const + throw(wrong_object,null_dereference,end_dereference) + { + to.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanin(to); i++) + { + if (input(to,i) == arc) + return i; + } + return digraph::npos(); + } + + template + unsigned digraph::input_offset(TYPENAME digraph::iterator to, + TYPENAME digraph::arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference) + { + to.assert_valid(this); + arc.assert_valid(this); + for (unsigned i = 0; i < fanin(to); i++) + { + if (input(to,i) == arc) + return i; + } + return digraph::npos(); + } + + //////////////////////////////////////////////////////////////////////////////// + // Basic Arc functions + + template + bool digraph::arc_empty(void) const + { + return m_arcs_end == 0; + } + + template + unsigned digraph::arc_size(void) const + { + unsigned count = 0; + for (digraph_arc_iterator i = arc_begin(); i != arc_end(); i++) + count++; + return count; + } + + template + TYPENAME digraph::arc_iterator digraph::arc_insert(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + const AT& arc_data) + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + to.assert_valid(this); + // create the new arc and link it in to the arc list + digraph_arc* new_arc = new digraph_arc(this, from.node(), to.node(), arc_data); + if (!m_arcs_end) + { + // insert into an empty list + m_arcs_begin = new_arc; + m_arcs_end = new_arc; + } + else + { + // insert at the end of the list + new_arc->m_prev = m_arcs_end; + m_arcs_end->m_next = new_arc; + m_arcs_end = new_arc; + } + // add this arc to the inputs and outputs of the end nodes + from.node()->m_outputs.push_back(new_arc); + to.node()->m_inputs.push_back(new_arc); + return digraph_arc_iterator(new_arc); + } + + template + TYPENAME digraph::arc_iterator digraph::arc_erase(TYPENAME digraph::arc_iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + // first remove this arc's pointers from the from/to nodes + for (TYPENAME std::vector*>::iterator i = iter.node()->m_to->m_inputs.begin(); i != iter.node()->m_to->m_inputs.end(); ) + { + if (*i == iter.node()) + i = iter.node()->m_to->m_inputs.erase(i); + else + i++; + } + for (TYPENAME std::vector*>::iterator o = iter.node()->m_from->m_outputs.begin(); o != iter.node()->m_from->m_outputs.end(); ) + { + if (*o == iter.node()) + o = iter.node()->m_from->m_outputs.erase(o); + else + o++; + } + // now unlink the arc from the list and delete it + if (iter.node()->m_next) + iter.node()->m_next->m_prev = iter.node()->m_prev; + if (iter.node()->m_prev) + iter.node()->m_prev->m_next = iter.node()->m_next; + digraph_arc* next = iter.node()->m_next; + delete iter.node(); + if (next) + return digraph_arc_iterator(next); + else + return digraph_arc_iterator(this); + } + + template + void digraph::arc_clear(void) + { + for (digraph_arc_iterator a = arc_begin(); a != arc_end(); ) + a = arc_erase(a); + } + + template + TYPENAME digraph::const_arc_iterator digraph::arc_begin(void) const + { + if (m_arcs_begin) + return digraph_arc_iterator(m_arcs_begin); + else + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::arc_iterator digraph::arc_begin(void) + { + if (m_arcs_begin) + return digraph_arc_iterator(m_arcs_begin); + else + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::const_arc_iterator digraph::arc_end(void) const + { + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::arc_iterator digraph::arc_end(void) + { + return digraph_arc_iterator(this); + } + + template + TYPENAME digraph::const_iterator digraph::arc_from(TYPENAME digraph::const_arc_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_from); + } + + template + TYPENAME digraph::iterator digraph::arc_from(TYPENAME digraph::arc_iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_from); + } + + template + TYPENAME digraph::const_iterator digraph::arc_to(TYPENAME digraph::const_arc_iterator iter) const + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_to); + } + + template + TYPENAME digraph::iterator digraph::arc_to(TYPENAME digraph::arc_iterator iter) + throw(wrong_object,null_dereference,end_dereference) + { + iter.assert_valid(this); + return digraph_iterator(iter.node()->m_to); + } + + template + void digraph::arc_move(TYPENAME digraph::arc_iterator arc, + TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + arc_move_to(arc,to); + arc_move_from(arc,from); + } + + template + void digraph::arc_move_from(TYPENAME digraph::arc_iterator arc, + TYPENAME digraph::iterator from) + throw(wrong_object,null_dereference,end_dereference) + { + arc.assert_valid(this); + from.assert_valid(this); + for (TYPENAME std::vector*>::iterator o = arc.node()->m_from->m_outputs.begin(); o != arc.node()->m_from->m_outputs.end(); ) + { + if (*o == arc.node()) + o = arc.node()->m_from->m_outputs.erase(o); + else + o++; + } + from.node()->m_outputs.push_back(arc.node()); + arc.node()->m_from = from.node(); + } + + template + void digraph::arc_move_to(TYPENAME digraph::arc_iterator arc, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + arc.assert_valid(this); + to.assert_valid(this); + for (TYPENAME std::vector*>::iterator i = arc.node()->m_to->m_inputs.begin(); i != arc.node()->m_to->m_inputs.end(); ) + { + if (*i == arc.node()) + i = arc.node()->m_to->m_inputs.erase(i); + else + i++; + } + to.node()->m_inputs.push_back(arc.node()); + arc.node()->m_to = to.node(); + } + + template + void digraph::arc_flip(TYPENAME digraph::arc_iterator arc) + throw(wrong_object,null_dereference,end_dereference) + { + arc_move(arc,arc_to(arc),arc_from(arc)); + } + + //////////////////////////////////////////////////////////////////////////////// + // Adjacency Algorithms + + template + bool digraph::adjacent(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + return adjacent_arc(from,to) != arc_end(); + } + + template + bool digraph::adjacent(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return adjacent_arc(from,to) != arc_end(); + } + + template + TYPENAME digraph::const_arc_iterator digraph::adjacent_arc(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + to.assert_valid(this); + for (unsigned arc = 0; arc < fanout(from); arc++) + { + if (arc_to(output(from, arc)) == to) + return output(from,arc); + } + return arc_end(); + } + + template + TYPENAME digraph::arc_iterator digraph::adjacent_arc(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return adjacent_arc(from.constify(), to.constify()).deconstify(); + } + + template + TYPENAME digraph::const_arc_vector digraph::adjacent_arcs(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + to.assert_valid(this); + std::vector > result; + for (unsigned arc = 0; arc < fanout(from); arc++) + { + if (arc_to(output(from, arc)) == to) + result.push_back(output(from,arc)); + } + return result; + } + + template + TYPENAME digraph::arc_vector digraph::adjacent_arcs(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_arcs(adjacent_arcs(from.constify(), to.constify())); + } + + template + TYPENAME digraph::const_node_vector digraph::input_adjacencies(TYPENAME digraph::const_iterator to) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned arc = 0; arc < fanin(to); arc++) + { + digraph_iterator from = arc_from(input(to, arc)); + if (std::find(result.begin(), result.end(), from) == result.end()) + result.push_back(from); + } + return result; + } + + template + TYPENAME digraph::node_vector digraph::input_adjacencies(TYPENAME digraph::iterator to) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(input_adjacencies(to.constify())); + } + + template + TYPENAME digraph::const_node_vector digraph::output_adjacencies(TYPENAME digraph::const_iterator from) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > result; + for (unsigned arc = 0; arc < fanout(from); arc++) + { + digraph_iterator to = arc_to(output(from, arc)); + if (find(result.begin(), result.end(), to) == result.end()) + result.push_back(to); + } + return result; + } + + template + TYPENAME digraph::node_vector digraph::output_adjacencies(TYPENAME digraph::iterator from) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(output_adjacencies(from.constify())); + } + + //////////////////////////////////////////////////////////////////////////////// + // Topographical Sort Algorithms + + template + std::pair::const_node_vector, TYPENAME digraph::const_arc_vector> + digraph::sort(TYPENAME digraph::arc_select_fn select) const + { + std::vector > result; + std::vector > errors; + // build a map containing the number of fanins to each node that must be visited before this one + std::map,unsigned> fanin_map; + for (digraph_iterator n = begin(); n != end(); n++) + { + unsigned predecessors = 0; + // only count predecessors connected by selected arcs + for (unsigned f = 0; f < fanin(n); f++) + { + digraph_arc_iterator input_arc = input(n,f); + digraph_iterator predecessor = arc_from(input_arc); + if (!select || select(*this,input_arc)) + predecessors++; + } + if (predecessors == 0) + { + result.push_back(n); + } + else + { + fanin_map[n] = predecessors; + } + } + // main algorithm applies the topographical sort repeatedly. For a DAG, it + // will complete first time. However, with backward arcs, the first + // iteration will fail. The algorithm then tries breaking random arcs to try + // to get an ordering. + for(unsigned i = 0; !fanin_map.empty(); ) + { + // now visit each node in traversal order, decrementing the fanin count of + // all successors. As each successor's fanin count goes to zero, it is + // appended to the result. + for (; i < result.size(); i++) + { + // Note: dereferencing gives us a node iterator + digraph_iterator current = result[i]; + for (unsigned f = 0; f < fanout(current); f++) + { + // only consider successors connected by selected arcs + digraph_arc_iterator output_arc = output(current, f); + digraph_iterator successor = arc_to(output_arc); + if (!select || select(*this,output_arc)) + { + // don't consider arcs that have been eliminated to break a loop + if (fanin_map.find(successor) != fanin_map.end()) + { + --fanin_map[successor]; + if ((fanin_map[successor]) == 0) + { + result.push_back(successor); + fanin_map.erase(fanin_map.find(successor)); + } + } + } + } + } + if (!fanin_map.empty()) + { + // there must be backward arcs preventing completion + // try removing arcs from the sort to get a partial ordering containing all the nodes + + // select an arc that is still relevant to the sort and break it + // first select a node that has non-zero fanin and its predecessor that has non-zero fanin + digraph_iterator stuck_node = fanin_map.begin()->first; + for (unsigned f = 0; f < fanin(stuck_node); f++) + { + // now successively remove input arcs that are still part of the sort until the fanin reduces to zero + // first find a relevant arc - this must be a selected arc that has not yet been traversed by the first half of the algorithm + digraph_arc_iterator input_arc = input(stuck_node, f); + if (!select || select(*this,input_arc)) + { + digraph_iterator predecessor = arc_from(input_arc); + if (fanin_map.find(predecessor) != fanin_map.end()) + { + // found the right combination - remove this arc and then drop out of the fanin loop to restart the outer sort loop + errors.push_back(input_arc); + --fanin_map[stuck_node]; + if ((fanin_map[stuck_node]) == 0) + { + result.push_back(stuck_node); + fanin_map.erase(fanin_map.find(stuck_node)); + break; + } + } + } + } + } + } + return std::make_pair(result,errors); + } + + template + std::pair::node_vector, TYPENAME digraph::arc_vector> + digraph::sort(TYPENAME digraph::arc_select_fn select) + { + std::pair >, + std::vector > > const_result = + const_cast*>(this)->sort(select); + + std::pair >, + std::vector > > result = + std::make_pair(deconstify_nodes(const_result.first),deconstify_arcs(const_result.second)); + return result; + } + + template + TYPENAME digraph::const_node_vector digraph::dag_sort(TYPENAME digraph::arc_select_fn select) const + { + std::pair >, + std::vector > > result = sort(select); + if (result.second.empty()) return result.first; + return std::vector >(); + } + + template + TYPENAME digraph::node_vector digraph::dag_sort(TYPENAME digraph::arc_select_fn select) + { + return deconstify_nodes(const_cast*>(this)->dag_sort(select)); + } + //////////////////////////////////////////////////////////////////////////////// + // Path Algorithms + + template + bool digraph::path_exists_r(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_iterator_set& visited, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // Recursive part of the digraph::path_exists function. This is based on a + // depth first search algorithm and stops the moment it finds a path + // regardless of its length. Simply traverse every output and recurse on that + // node until we find the to node or run out of things to recurse on. However, + // to avoid infinite recursion due to cycles in the graph, I need to maintain + // a set of visited nodes. The visited set is updated when a candidate is + // found but tested before the recursion on the candidate so that the number of + // function calls is minimised. + for (unsigned i = 0; i < fanout(from); i++) + { + digraph_arc_iterator arc = output(from,i); + if (!select || select(*this, arc)) + { + digraph_iterator node = arc_to(arc); + // if the node is the target, return immediately + if (node == to) return true; + // update the visited set and give up if the insert fails, which indicates that the node has already been visited + if (!(visited.insert(node).second)) return false; + // now recurse - a path exists from from to to if a path exists from an adjacent node to to + if (path_exists_r(node,to,visited,select)) return true; + } + } + return false; + } + + template + bool digraph::path_exists(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // set up the recursion with its initial visited set and then recurse + std::set > visited; + visited.insert(from); + return path_exists_r(from, to, visited, select); + } + + template + bool digraph::path_exists(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return path_exists(from.constify(), to.constify(), select); + } + + template + void digraph::all_paths_r(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_arc_vector& so_far, + TYPENAME digraph::const_path_vector& result, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // This is the recursive part of the all_paths function. The field so_far + // contains the path so far so that when 'to' is reached, the path is + // complete. It serves the same purpose as the visited set in the path_exists + // function except that it also preserves the path order. It also serves the + // purpose of detecting cycles and thus stopping infinite recursion. Every + // time the recursion reaches the to node, a copy of so_far is appended to the + // path set. + for (unsigned i = 0; i < fanout(from); i++) + { + digraph_arc_iterator candidate = output(from,i); + // assert_valid that the arc is selected and then assert_valid that the candidate has not + // been visited on this path and only allow further recursion if it hasn't + if ((!select || select(*this, candidate)) && std::find(so_far.begin(), so_far.end(), candidate) == so_far.end()) + { + // extend the path tracing the route to this arc + so_far.push_back(candidate); + // if the candidate arc points to the target, update the result set and prevent further recursion, otherwise recurse + if (arc_to(candidate) == to) + result.push_back(so_far); + else + all_paths_r(arc_to(candidate),to,so_far,result,select); + so_far.pop_back(); + } + } + } + + template + TYPENAME digraph::const_path_vector + digraph::all_paths(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // set up the recursion with empty data fields and then recurse + std::vector > > result; + std::vector > so_far; + all_paths_r(from, to, so_far, result, select); + return result; + } + + template + TYPENAME digraph::path_vector + digraph::all_paths(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_paths(all_paths(from.constify(), to.constify(), select)); + } + + template + void digraph::reachable_nodes_r(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator_set& visited, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // The recursive part of the reachable_nodes function. + // This is a depth-first traversal again but this time it carries on to find all the reachable nodes + // Just keep recursing on all the adjacent nodes of each node, skipping already visited nodes to avoid cycles + for (unsigned i = 0; i < fanout(from); i++) + { + digraph_arc_iterator arc = output(from,i); + if (!select || select(*this,arc)) + { + digraph_iterator candidate = arc_to(arc); + if (visited.insert(candidate).second) + reachable_nodes_r(candidate,visited,select); + } + } + } + + template + TYPENAME digraph::const_node_vector + digraph::reachable_nodes(TYPENAME digraph::const_iterator from, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // seed the recursion, marking the starting node as already visited + std::set > visited; + visited.insert(from); + reachable_nodes_r(from, visited, select); + // convert the visited set into the required output form + // exclude the starting node + std::vector > result; + for (TYPENAME std::set >::iterator i = visited.begin(); i != visited.end(); i++) + if (*i != from) + result.push_back(*i); + return result; + } + + template + TYPENAME digraph::node_vector + digraph::reachable_nodes(TYPENAME digraph::iterator from, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(reachable_nodes(from.constify(), select)); + } + + template + void digraph::reaching_nodes_r(TYPENAME digraph::const_iterator to, + TYPENAME digraph::const_iterator_set& visited, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // The recursive part of the reaching_nodes function. + // Just like the reachable_nodes_r function but it goes backwards + for (unsigned i = 0; i < fanin(to); i++) + { + digraph_arc_iterator arc = input(to,i); + if (!select || select(*this,arc)) + { + digraph_iterator candidate = arc_from(input(to,i)); + if (visited.insert(candidate).second) + reaching_nodes_r(candidate,visited,select); + } + } + } + + template + TYPENAME digraph::const_node_vector + digraph::reaching_nodes(TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + // seed the recursion, marking the starting node as already visited + std::set > visited; + visited.insert(to); + reaching_nodes_r(to,visited,select); + // convert the visited set into the required output form + // exclude the end node + std::vector > result; + for (TYPENAME std::set >::iterator i = visited.begin(); i != visited.end(); i++) + if (*i != to) + result.push_back(*i); + return result; + } + + template + TYPENAME digraph::node_vector + digraph::reaching_nodes(TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_nodes(reaching_nodes(to.constify(),select)); + } + + //////////////////////////////////////////////////////////////////////////////// + // Shortest Path Algorithms + + template + TYPENAME digraph::const_arc_vector + digraph::shortest_path(TYPENAME digraph::const_iterator from, + TYPENAME digraph::const_iterator to, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + std::vector > > paths = all_paths(from,to,select); + std::vector > shortest; + for (TYPENAME std::vector > >::iterator i = paths.begin(); i != paths.end(); i++) + if (shortest.empty() || i->size() < shortest.size()) + shortest = *i; + return shortest; + } + + template + TYPENAME digraph::arc_vector + digraph::shortest_path(TYPENAME digraph::iterator from, + TYPENAME digraph::iterator to, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_arcs(shortest_path(from.constify(),to.constify(),select)); + } + + template + TYPENAME digraph::const_path_vector + digraph::shortest_paths(TYPENAME digraph::const_iterator from, + TYPENAME digraph::arc_select_fn select) const + throw(wrong_object,null_dereference,end_dereference) + { + from.assert_valid(this); + // This is an unweighted shortest path algorithm based on the algorithm from + // Weiss's book. This is essentially a breadth-first traversal or graph + // colouring algorithm. It is an iterative algorithm, so no recursion here! It + // works by creating a node queue initialised with the starting node. It then + // consumes the queue from front to back. For each node, it finds the + // successors and appends them to the queue. If a node is already 'known' it + // is not added - this avoids cycles. Thus the queue insert ordering + // represents the breadth-first ordering. On the way it creates a map of + // visited nodes. This is a map not a set because it also stores the arc that + // nominated this node as a shortest path. The full path can then be recreated + // from the map by just walking back through the predecessors. The depth (or + // colour) can be determined by the path length. + std::vector > > result; + // initialise the iteration by creating a queue and adding the start node + std::deque > nodes; + nodes.push_back(from); + // Create a map to store the set of known nodes mapped to their predecessor + // arcs. Initialise it with the current node, which has no predecessor. Note + // that the algorithm uses the feature of digraph iterators that they can be + // null iterators and that all null iterators are equal. + typedef std::map, + digraph_arc_iterator > known_map; + known_map known; + known.insert(std::make_pair(from,digraph_arc_iterator())); + // now the iterative part of the algorithm + while(!nodes.empty()) + { + // pop the queue to get the next node to process - unfortunately the STL + // deque::pop does not return the popped value + digraph_iterator current = nodes.front(); + nodes.pop_front(); + // now visit all the successors + for (unsigned i = 0; i < fanout(current); i++) + { + digraph_arc_iterator next_arc = output(current,i); + // assert_valid whether the successor arc is a selected arc and can be part of a path + if (!select || select(*this,next_arc)) + { + digraph_iterator next = arc_to(next_arc); + // Discard any successors that are known because to be known already they + // must have another shorter path. Otherwise add the successor node to the + // queue to be visited later. To minimise the overhead of map lookup I use + // the usual trick of trying to insert the node and determining whether + // the node was known by the success or failure of the insertion - this is + // a Good STL Trick (TM). + if (known.insert(std::make_pair(next,next_arc)).second) + nodes.push_back(next); + } + } + } + // The map contains the results as an unordered set of nodes, mapped to their + // predecessor arcs and weight. This now needs to be converted into a set of + // paths. This is done by starting with a node from the map, finding its + // predecessor arc and therefore its predecessor node, looking that up in the + // map to find its predecessor and so on until the start node is reached (it + // has a null predecessor). Note that the known set includes the from node + // which does not generate a path. + for (TYPENAME known_map::iterator i = known.begin(); i != known.end(); i++) + { + if (i->first != from) + { + const_arc_vector this_path; + for (TYPENAME known_map::iterator node = i; + node->second.valid(); + node = known.find(arc_from(node->second))) + this_path.insert(this_path.begin(),node->second); + result.push_back(this_path); + } + } + return result; + } + + template + TYPENAME digraph::path_vector + digraph::shortest_paths(TYPENAME digraph::iterator from, + TYPENAME digraph::arc_select_fn select) + throw(wrong_object,null_dereference,end_dereference) + { + return deconstify_paths(shortest_paths(from.constify(),select)); + } + + //////////////////////////////////////////////////////////////////////////////// + +} // end namespace stlplus