--- /dev/null
+////////////////////////////////////////////////////////////////////////////////\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
projects / chaz / yoink / blobdiff