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