+++ /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