ROSE  0.9.9.139
GraphTraversal.h
1 // WARNING: Changes to this file must be contributed back to Sawyer or else they will
2 // be clobbered by the next update from Sawyer. The Sawyer repository is at
3 // https://github.com/matzke1/sawyer.
4 
5 
6 
7 
8 #ifndef Sawyer_GraphTraversal_H
9 #define Sawyer_GraphTraversal_H
10 
11 #include <Sawyer/Graph.h>
12 
13 #include <Sawyer/BitVector.h>
14 #include <list>
15 #include <vector>
16 
17 namespace Sawyer {
18 namespace Container {
19 
21 namespace Algorithm {
22 
39  NO_EVENT = 0,
40  ENTER_VERTEX = 0x0001,
43  ENTER_EDGE = 0x0002,
49  DISCOVER_VERTEX = 0x0004,
53  LEAVE_EDGE = 0x0008,
59  LEAVE_VERTEX = 0x0010,
66  FOLLOW_EDGE = 0x0020 // Internal: current edge was followed to find neighbor vertex
67 };
68 
69 // Event sets (doxygen doesn't pick these up, so they're documented in the TraversalEvent enum
70 static const unsigned VERTEX_EVENTS = ENTER_VERTEX | DISCOVER_VERTEX | LEAVE_VERTEX;
71 static const unsigned EDGE_EVENTS = ENTER_EDGE | LEAVE_EDGE;
72 static const unsigned ENTER_EVENTS = ENTER_VERTEX | ENTER_EDGE;
73 static const unsigned LEAVE_EVENTS = LEAVE_VERTEX | LEAVE_EDGE;
74 static const unsigned ENTER_LEAVE_EVENTS = ENTER_EVENTS | LEAVE_EVENTS;
75 static const unsigned ALL_EVENTS = VERTEX_EVENTS | EDGE_EVENTS;
76 
78 SAWYER_EXPORT std::string traversalEventName(TraversalEvent);
79 
82 
85 
88 
91 
98 template<class VertexIterator, class EdgeIterator>
99 VertexIterator
100 nextVertex(EdgeIterator edge, ForwardTraversalTag) {
101  return edge->target();
102 }
103 
104 template<class VertexIterator, class EdgeIterator>
105 VertexIterator
106 nextVertex(EdgeIterator edge, ReverseTraversalTag) {
107  return edge->source();
108 }
117 template<class VertexIterator, class EdgeIterator>
118 VertexIterator
119 previousVertex(EdgeIterator edge, ForwardTraversalTag) {
120  return edge->source();
121 }
122 
123 template<class VertexIterator, class EdgeIterator>
124 VertexIterator
125 previousVertex(EdgeIterator edge, ReverseTraversalTag) {
126  return edge->target();
127 }
136 template<class EdgeIterator, class VertexIterator>
137 boost::iterator_range<EdgeIterator>
138 nextEdges(VertexIterator vertex, ForwardTraversalTag) {
139  return vertex->outEdges();
140 }
141 
142 template<class EdgeIterator, class VertexIterator>
143 boost::iterator_range<EdgeIterator>
144 nextEdges(VertexIterator vertex, ReverseTraversalTag) {
145  return vertex->inEdges();
146 }
155 template<class EdgeIterator, class VertexIterator>
156 boost::iterator_range<EdgeIterator>
157 previousEdges(VertexIterator vertex, ForwardTraversalTag) {
158  return vertex->inEdges();
159 }
160 
161 template<class EdgeIterator, class VertexIterator>
162 boost::iterator_range<EdgeIterator>
163 previousEdges(VertexIterator vertex, ReverseTraversalTag) {
164  return vertex->outEdges();
165 }
168 
387 template<class G, class Order=DepthFirstTraversalTag, class Direction=ForwardTraversalTag>
389 public:
390  typedef G Graph;
391 
394 
397 
398 private:
399  Graph &graph_;
400 
401 protected:
402  // Work that needs to be performed. The current item is always at the front of this list. Depth-first subclasses will push
403  // new work onto the front of the list and breadth-first subclasses will push it onto the end. When the list becomes empty
404  // then the iterator has reached its end state.
405  struct Work {
406  TraversalEvent event; // last event returned from this work item
407  EdgeIterator fromEdge; // edge that brought us to this vertex (or edges().end())
408  VertexIterator vertex; // vertex being visited
409  EdgeIterator edge; // edge being visited
410  EdgeIterator endEdge; // end edge for this vertex
411  bool followEdge; // follow edge to discover the neighbor vertex?
412  Work(EdgeIterator fromEdge, VertexIterator vertex, const boost::iterator_range<EdgeIterator> &nextEdges)
413  : event(DISCOVER_VERTEX), fromEdge(fromEdge), vertex(vertex), edge(nextEdges.begin()), endEdge(nextEdges.end()),
414  followEdge(true) {}
415  };
416  typedef std::list<Work> WorkList;
417  WorkList workList_;
418 
419 private:
420  unsigned significantEvents_; // events for which advance() will return to the caller
421  BitVector verticesDiscovered_; // vertices that are (or have been) on the work list
422  BitVector edgesVisited_; // edges that have been visited
423  Optional<Work> latestDiscovered_; // most recent work discovered
424 
425 public:
430  GraphTraversal(Graph &graph, unsigned significantEvents)
431  : graph_(graph), significantEvents_(significantEvents),
432  verticesDiscovered_(graph.nVertices()), edgesVisited_(graph.nEdges()) {}
433 
434 protected:
435  // Current work item.
436  Work& current() {
437  ASSERT_forbid(workList_.empty());
438  return workList_.front();
439  }
440  const Work& current() const {
441  ASSERT_forbid(workList_.empty());
442  return workList_.front();
443  }
444 
445  // True if event is significant to the user.
446  bool isSignificant(TraversalEvent event) const {
447  return 0 != (event & significantEvents_);
448  }
449 
450  // Mark a vertex as being discovered. A vertex so marked will not be added to the work list, but will remain in the
451  // worklist if it is already present.
452  void setDiscovered(VertexIterator vertex, bool isDiscovered=true) {
453  ASSERT_require(vertex != graph_.vertices().end());
454  verticesDiscovered_.setValue(vertex->id(), isDiscovered);
455  }
456 
457  // Mark an edge as having been entered. An edge so marked will not be entered again.
458  void setVisited(EdgeIterator edge, bool isVisited=true) {
459  ASSERT_require(edge != graph_.edges().end());
460  edgesVisited_.setValue(edge->id(), isVisited);
461  }
462 
463  // Reset to an inital empty state.
464  void clear() {
465  verticesDiscovered_.clear();
466  edgesVisited_.clear();
467  latestDiscovered_ = Nothing();
468  workList_.clear();
469  }
470 
471 public:
473  void start(VertexIterator startVertex) {
474  ASSERT_forbid(startVertex == graph_.vertices().end());
475  clear();
476  Work newWork(graph_.edges().end(), startVertex, nextEdges<EdgeIterator>(startVertex, Direction()));
477  enqueue(newWork, Order());
478  setDiscovered(startVertex);
479  latestDiscovered_ = newWork;
480  while (!isAtEnd() && !isSignificant(event()))
481  advance();
482  }
483 
485  void start(EdgeIterator startEdge) {
486  ASSERT_forbid(startEdge == graph_.edges().end());
487  clear();
488  EdgeIterator endEdge = startEdge; ++endEdge;
489  boost::iterator_range<EdgeIterator> edges(startEdge, endEdge);
490  Work newWork(graph_.edges().end(), graph_.vertices().end(), edges);
491  enqueue(newWork, Order());
492  setVisited(startEdge);
493  workList_.front().event = ENTER_EDGE;
494  while (!isAtEnd() && !isSignificant(event()))
495  advance();
496  }
497 
501  Graph& graph() const {
502  return graph_;
503  }
504 
509  if (isAtEnd())
510  throw std::runtime_error("attempt to dereference traversal at end");
511  return FOLLOW_EDGE==current().event ? DISCOVER_VERTEX : current().event;
512  }
513 
517  VertexIterator vertex() const {
518  switch (event()) {
519  case NO_EVENT:
520  return graph_.vertices().end();
521  case DISCOVER_VERTEX:
522  ASSERT_require(latestDiscovered_);
523  return latestDiscovered_->vertex;
524  case ENTER_VERTEX:
525  case ENTER_EDGE:
526  case LEAVE_VERTEX:
527  case LEAVE_EDGE:
528  return current().vertex;
529  default:
530  break;
531  }
532  ASSERT_not_reachable("invalid state");
533  }
534 
538  EdgeIterator edge() const {
539  switch (event()) {
540  case NO_EVENT:
541  return graph_.edges().end();
542  case ENTER_VERTEX:
543  return current().fromEdge;
544  case DISCOVER_VERTEX:
545  ASSERT_require(latestDiscovered_);
546  return latestDiscovered_->fromEdge;
547  case LEAVE_VERTEX:
548  return current().fromEdge;
549  case ENTER_EDGE:
550  return current().edge;
551  case LEAVE_EDGE:
552  return current().edge;
553  default:
554  break;
555  }
556  ASSERT_not_reachable("invalid state");
557  }
558 
563  bool isAtEnd() const {
564  return workList_.empty();
565  }
566 
583  bool hasNext() const {
584  return !isAtEnd();
585  }
586 
596  while (1) {
597  if (workList_.empty())
598  return NO_EVENT;
599 
600  // After leaving an edge advance to the next edge if any. The state is set to ENTER_VERTEX so that it looks like
601  // we're entering the vertex again, but this time at a different initial edge.
602  if (current().event == LEAVE_EDGE) {
603  if (workList_.front().edge != workList_.front().endEdge)
604  ++workList_.front().edge;
605  current().event = ENTER_VERTEX;
606  }
607 
608  // Leave the vertex if we're all done processing edges (or if it has none)
609  if (current().event == ENTER_VERTEX) {
610  while (workList_.front().edge != workList_.front().endEdge && isVisited(workList_.front().edge))
611  ++workList_.front().edge;
612  if (workList_.front().edge == workList_.front().endEdge) {
613  current().event = LEAVE_VERTEX;
614  if (isSignificant(LEAVE_VERTEX) && workList_.front().vertex != graph_.vertices().end())
615  return LEAVE_VERTEX;
616  }
617  }
618 
619  // All done with the current work?
620  if (current().event == LEAVE_VERTEX) {
621  workList_.pop_front();
622  if (workList_.empty())
623  return NO_EVENT; // end of traversal
624  }
625 
626  // We've left the vertex; now leave the edge that got us to that vertex (if any).
627  if (current().event == LEAVE_VERTEX) {
628  current().event = LEAVE_EDGE;
629  if (isSignificant(LEAVE_EDGE) && current().edge != graph_.edges().end())
630  return LEAVE_EDGE;
631  continue;
632  }
633 
634  // Enter a discovered vertex
635  if (current().event == DISCOVER_VERTEX) {
636  current().event = ENTER_VERTEX;
637  if (isSignificant(ENTER_VERTEX))
638  return ENTER_VERTEX;
639  continue;
640  }
641 
642  // Visit the edge after entering the vertex or returning from another edge
643  if (current().event == ENTER_VERTEX || current().event == LEAVE_EDGE) {
644  current().event = ENTER_EDGE;
645  setVisited(current().edge);
646  if (isSignificant(ENTER_EDGE))
647  return ENTER_EDGE;
648  }
649 
650  // Discover the neighbor vertex at the other end of this edge
651  if (current().event == ENTER_EDGE) {
652  current().event = FOLLOW_EDGE; // never escapes to the user
653  if (current().followEdge) {
654  VertexIterator neighbor = nextVertex<VertexIterator>(workList_.front().edge, Direction());
655  if (!isDiscovered(neighbor)) {
656  Work newWork(workList_.front().edge, neighbor, nextEdges<EdgeIterator>(neighbor, Direction()));
657  enqueue(newWork, Order());
658  setDiscovered(neighbor);
659  latestDiscovered_ = newWork;
660  if (isSignificant(DISCOVER_VERTEX))
661  return DISCOVER_VERTEX;
662  }
663  } else {
664  current().followEdge = true;
665  }
666  }
667 
668  // Leave the edge
669  if (current().event == FOLLOW_EDGE) {
670  current().event = LEAVE_EDGE;
671  if (isSignificant(LEAVE_EDGE))
672  return LEAVE_EDGE;
673  }
674  }
675  }
676 
682  void skipChildren() {
683  switch (event()) {
684  case NO_EVENT:
685  throw std::runtime_error("GraphTraversal::skipChildren called at end of traversal");
686  case ENTER_VERTEX:
687  current().edge = current().endEdge;
688  return;
689  case ENTER_EDGE:
690  current().followEdge = false;
691  return;
692  case DISCOVER_VERTEX:
693  case LEAVE_VERTEX:
694  case LEAVE_EDGE:
695  case FOLLOW_EDGE:
696  throw std::runtime_error("GraphTraversal::skipChildren cannot be called from " +
697  traversalEventName(event()) + " event");
698  }
699  ASSERT_not_reachable("invalid state: event=" + traversalEventName(event()));
700  }
701 
709  void allowRediscovery(VertexIterator vertex) {
710  if (vertex != graph_.vertices().end()) {
711  setDiscovered(vertex, false);
712  boost::iterator_range<EdgeIterator> edges = nextEdges<EdgeIterator>(vertex, Direction());
713  for (EdgeIterator iter=edges.begin(); iter!=edges.end(); ++iter)
714  setVisited(iter, false);
715  }
716  }
717 
723  bool isDiscovered(VertexIterator vertex) const {
724  if (vertex == graph_.vertices().end())
725  return false;
726  return verticesDiscovered_.get(vertex->id());
727  }
728 
732  bool isVisited(EdgeIterator edge) const {
733  if (edge == graph_.edges().end())
734  return false;
735  return edgesVisited_.get(edge->id());
736  }
737 
743  template<class Functor>
744  void mapVertices(Functor &f) {
745  while (!isAtEnd()) {
746  f(vertex());
747  advance();
748  }
749  }
750  template<class Functor>
751  void mapVertices(const Functor &f) {
752  while (!isAtEnd()) {
753  f(vertex());
754  advance();
755  }
756  }
764  template<class Functor>
765  void mapEdges(Functor &f) {
766  while (!isAtEnd()) {
767  f(edge());
768  advance();
769  }
770  }
771  template<class Functor>
772  void mapEdges(const Functor &f) {
773  while (!isAtEnd()) {
774  f(edge());
775  advance();
776  }
777  }
780  // The following trickery is to allow things like "if (x)" to work but without having an implicit
781  // conversion to bool which would cause no end of other problems. This is fixed in C++11.
782 private:
783  typedef void(GraphTraversal::*unspecified_bool)() const;
784  void this_type_does_not_support_comparisons() const {}
785 public:
796  operator unspecified_bool() const {
797  return isAtEnd() ? 0 : &GraphTraversal::this_type_does_not_support_comparisons;
798  }
799 
800 private:
801  // Adds new work to the list. Depth-first subclasses will push work onto the front of the list and breadth-first
802  // subclasses will push it onto the end.
803  void enqueue(const Work &work, DepthFirstTraversalTag) { workList_.push_front(work); }
804  void enqueue(const Work &work, BreadthFirstTraversalTag) { workList_.push_back(work); }
805 };
806 
807 
809 //
810 // Subclasses {Order}{Direction}GraphTraversal
811 //
813 
821 template<class Graph>
822 class DepthFirstForwardGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
823 public:
826  unsigned significantEvents=ALL_EVENTS)
827  : GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
828  this->start(startVertex);
829  }
830 
833  unsigned significantEvents=ALL_EVENTS)
834  : GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
835  this->start(startEdge);
836  }
837 
840  this->advance();
841  return *this;
842  }
843 };
844 
852 template<class Graph>
853 class DepthFirstReverseGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
854 public:
857  unsigned significantEvents=ALL_EVENTS)
858  : GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
859  this->start(startVertex);
860  }
861 
864  unsigned significantEvents=ALL_EVENTS)
865  : GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
866  this->start(startEdge);
867  }
868 
871  this->advance();
872  return *this;
873  }
874 };
875 
883 template<class Graph>
884 class BreadthFirstForwardGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
885 public:
888  unsigned significantEvents=ALL_EVENTS)
889  : GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
890  this->start(startVertex);
891  }
892 
895  unsigned significantEvents=ALL_EVENTS)
896  : GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
897  this->start(startEdge);
898  }
899 
902  this->advance();
903  return *this;
904  }
905 };
906 
914 template<class Graph>
915 class BreadthFirstReverseGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
916 public:
919  unsigned significantEvents=ALL_EVENTS)
920  : GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
921  this->start(startVertex);
922  }
923 
926  unsigned significantEvents=ALL_EVENTS)
927  : GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
928  this->start(startEdge);
929  }
930 
933  this->advance();
934  return *this;
935  }
936 };
937 
939 //
940 // Subclasses {Order}{Direction}VertexTraversal
941 //
943 
948 template<class Graph, class Order, class Direction>
949 class GraphVertexTraversal: public GraphTraversal<Graph, Order, Direction> {
950 protected:
952 
953 public:
956  return *this->vertex();
957  }
958 
961  return &*this->vertex();
962  }
963 
966  typename GraphTraits<Graph>::VertexIterator::Reference retval = this->vertex();
967  this->advance();
968  return retval;
969  }
970 };
971 
977 template<class Graph>
978 class DepthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
979 public:
983  this->start(startVertex);
984  }
985 
989  this->start(startEdge);
990  }
991 
995  this->start(graph.vertices().begin());
996  }
997 
1000  this->advance();
1001  return *this;
1002  }
1003 };
1004 
1010 template<class Graph>
1011 class DepthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
1012 public:
1016  this->start(startVertex);
1017  }
1018 
1022  this->start(startEdge);
1023  }
1024 
1028  this->start(graph.vertices().begin());
1029  }
1030 
1033  this->advance();
1034  return *this;
1035  }
1036 };
1037 
1043 template<class Graph>
1044 class BreadthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
1045 public:
1049  this->start(startVertex);
1050  }
1051 
1055  this->start(startEdge);
1056  }
1057 
1061  this->start(graph.vertices().begin());
1062  }
1063 
1066  this->advance();
1067  return *this;
1068  }
1069 };
1070 
1076 template<class Graph>
1077 class BreadthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
1078 public:
1082  this->start(startVertex);
1083  }
1084 
1088  this->start(startEdge);
1089  }
1090 
1094  this->start(graph.vertices().begin());
1095  }
1096 
1099  this->advance();
1100  return *this;
1101  }
1102 };
1103 
1105 //
1106 // Subclasses {Order}{Direction}EdgeTraversal
1107 //
1109 
1114 template<class Graph, class Order, class Direction>
1115 class GraphEdgeTraversal: public GraphTraversal<Graph, Order, Direction> {
1116 protected:
1118 
1119 public:
1122  return *this->edge();
1123  }
1124 
1127  return &*this->edge();
1128  }
1129 
1132  typename GraphTraits<Graph>::EdgeIterator::Reference retval = this->vertex();
1133  this->advance();
1134  return retval;
1135  }
1136 };
1137 
1143 template<class Graph>
1144 class DepthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
1145 public:
1149  this->start(startVertex);
1150  }
1151 
1155  this->start(startEdge);
1156  }
1157 
1161  this->start(graph.edges().begin());
1162  }
1163 
1166  this->advance();
1167  return *this;
1168  }
1169 };
1170 
1176 template<class Graph>
1177 class DepthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
1178 public:
1182  this->start(startVertex);
1183  }
1184 
1188  this->start(startEdge);
1189  }
1190 
1194  this->start(graph.edges().begin());
1195  }
1196 
1199  this->advance();
1200  return *this;
1201  }
1202 };
1203 
1209 template<class Graph>
1210 class BreadthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
1211 public:
1215  this->start(startVertex);
1216  }
1217 
1221  this->start(startEdge);
1222  }
1223 
1227  this->start(graph.edges().begin());
1228  }
1229 
1232  this->advance();
1233  return *this;
1234  }
1235 };
1236 
1242 template<class Graph>
1243 class BreadthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
1244 public:
1248  this->start(startVertex);
1249  }
1250 
1254  this->start(startEdge);
1255  }
1256 
1260  this->start(graph.edges().begin());
1261  }
1262 
1265  this->advance();
1266  return *this;
1267  }
1268 };
1269 
1270 
1271 
1273 //
1274 // Traversal visitation functions
1275 //
1277 
1291 template<class Traversal, class Functor>
1292 void graphTraverseAllVertices(Traversal t, Functor &f) {
1293  std::vector<bool> visited(t.graph().nVertices(), false);
1294  size_t rootId = 0;
1295  while (true) {
1296  for (typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
1297  typename Traversal::VertexIterator vertex = t.vertex();
1298  if (visited[vertex->id()]) {
1299  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1300  t.skipChildren();
1301  } else {
1302  visited[vertex->id()] = true;
1303  f(vertex, root);
1304  }
1305  }
1306  while (rootId < visited.size() && visited[rootId])
1307  ++rootId;
1308  if (rootId >= visited.size())
1309  return;
1310  t.start(t.graph().findVertex(rootId));
1311  }
1312 }
1313 template<class Traversal, class Functor>
1314 void graphTraverseAllVertices(Traversal t, const Functor &f) { // identical, other than const functor
1315  std::vector<bool> visited(t.graph().nVertices(), false);
1316  size_t rootId = 0;
1317  while (true) {
1318  for (typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
1319  typename Traversal::VertexIterator vertex = t.vertex();
1320  if (visited[vertex->id()]) {
1321  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1322  t.skipChildren();
1323  } else {
1324  visited[vertex->id()] = true;
1325  f(vertex, root);
1326  }
1327  }
1328  while (rootId < visited.size() && visited[rootId])
1329  ++rootId;
1330  if (rootId >= visited.size())
1331  return;
1332  t.start(t.graph().findVertex(rootId));
1333  }
1334 }
1350 template<class Traversal, class Functor>
1351 void graphTraverseAllEdges(Traversal t, Functor &f) {
1352  std::vector<bool> visited(t.graph().nEdges(), false);
1353  size_t rootId = 0;
1354  while (true) {
1355  for (typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
1356  typename Traversal::EdgeIterator edge = t.edge();
1357  if (visited[edge->id()]) {
1358  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1359  t.skipChildren();
1360  } else {
1361  visited[edge->id()] = true;
1362  f(edge, root);
1363  }
1364  }
1365  while (rootId < visited.size() && visited[rootId])
1366  ++rootId;
1367  if (rootId >= visited.size())
1368  return;
1369  t.start(t.graph().findEdge(rootId));
1370  }
1371 }
1372 template<class Traversal, class Functor>
1373 void graphTraverseAllEdges(Traversal t, const Functor &f) { // identical, other than const functor
1374  std::vector<bool> visited(t.graph().nEdges(), false);
1375  size_t rootId = 0;
1376  while (true) {
1377  for (typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
1378  typename Traversal::EdgeIterator edge = t.edge();
1379  if (visited[edge->id()]) {
1380  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1381  t.skipChildren();
1382  } else {
1383  visited[edge->id()] = true;
1384  f(edge, root);
1385  }
1386  }
1387  while (rootId < visited.size() && visited[rootId])
1388  ++rootId;
1389  if (rootId >= visited.size())
1390  return;
1391  t.start(t.graph().findEdge(rootId));
1392  }
1393 }
1400 template<class Graph>
1402 public:
1403  std::vector<size_t> ids;
1404 
1405  explicit IdAccumulator(size_t n) { ids.reserve(n); }
1406 
1407  void operator()(typename GraphTraits<Graph>::VertexIterator v) {
1408  ids.push_back(v->id());
1409  }
1410  void operator()(typename GraphTraits<Graph>::VertexIterator v, typename GraphTraits<Graph>::VertexIterator /*root*/) {
1411  ids.push_back(v->id());
1412  }
1413  void operator()(typename GraphTraits<Graph>::EdgeIterator e) {
1414  ids.push_back(e->id());
1415  }
1416  void operator()(typename GraphTraits<Graph>::EdgeIterator e, typename GraphTraits<Graph>::EdgeIterator /*root*/) {
1417  ids.push_back(e->id());
1418  }
1419 };
1420 
1425 template<class Traversal>
1426 std::vector<size_t> graphReachableVertices(Traversal t) {
1427  IdAccumulator<typename Traversal::Graph> accum(t.graph().nVertices());
1428  t.mapVertices(accum);
1429  return accum.ids;
1430 }
1431 
1435 template<class Traversal>
1436 std::vector<size_t> graphReachableEdges(Traversal t) {
1437  IdAccumulator<typename Traversal::Graph> accum(t.graph().nEdges());
1438  t.mapEdges(accum);
1439  return accum.ids;
1440 }
1441 
1447 template<class Traversal, class Graph>
1448 std::vector<size_t> graphAllVertices(Graph &graph) {
1449  IdAccumulator<Graph> accum(graph.nVertices());
1450  graphTraverseAllVertices(Traversal(graph, graph.vertices().begin()), accum);
1451  return accum.ids;
1452 }
1453 
1459 template<class Traversal, class Graph>
1460 std::vector<size_t> graphAllEdges(Graph &graph) {
1461  IdAccumulator<Graph> accum(graph.nEdges());
1462  graphTraverseAllEdges(Traversal(graph, graph.edges().begin()), accum);
1463  return accum.ids;
1464 }
1465 
1466 } // namespace
1467 } // namespace
1468 } // namespace
1469 
1470 #endif
Depth-first, forward traversal for vertices.
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1670
Order tag for breadth-first traversals.
Direction tag for reverse traversals.
void start(EdgeIterator startEdge)
Restart the traversal at the specified edge.
void skipChildren()
Causes traversal to skip children.
void graphTraverseAllVertices(Traversal t, Functor &f)
Visit all vertices of a graph.
void mapVertices(Functor &f)
Call the specified functor for each vertex.
DepthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
BreadthFirstForwardVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
Base class for graph vertex traversals.
DepthFirstReverseVertexTraversal & operator++()
Advance traversal to next event.
size_t nEdges() const
Total number of edges.
Definition: Graph.h:1680
DepthFirstForwardEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
TraversalEvent advance()
Advance traversal to next interesting event.
bool hasNext() const
Returns true when a traversal can be advanced.
Depth-first, reverse traversal for vertices.
Breadth-first, reverse traversal for edges.
BreadthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
Graph & graph() const
The graph over which iteration occurs.
BreadthFirstForwardVertexTraversal & operator++()
Advance traversal to next event.
Traits for graphs.
Definition: Graph.h:287
GraphTraits< Graph >::EdgeIterator::Reference operator*()
Return reference to current edge.
Order tag for depth-first traversals.
VertexIterator previousVertex(EdgeIterator edge, ForwardTraversalTag)
Previous vertex in traversal order.
Neighboring vertex discovered for the first time.
BreadthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
Breadth-first, forward traversal for edges.
BreadthFirstReverseGraphTraversal & operator++()
Advance traversal to next event.
BreadthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
Depth-first, forward traversal for edges.
BitVector & clear(const BitRange &range)
Assign zero to some bits.
Definition: BitVector.h:262
Holds a value or nothing.
Definition: Optional.h:49
DepthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
void mapEdges(Functor &f)
Call the specified functor for each edge.
Breadth-first, reverse traversal for all event types.
bool get(size_t idx) const
Retrieve one bit.
Definition: BitVector.h:252
GraphTraits< Graph >::EdgeIterator::Reference next()
Return reference to current edge and advance.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition: Graph.h:1454
Accumulates vertex or edge IDs.
DepthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
DepthFirstForwardVertexTraversal & operator++()
Advance traversal to next event.
TraversalEvent
Events returned by a graph traversal.
EdgeIterator edge() const
Edge to which traversal is pointing.
std::string traversalEventName(TraversalEvent)
Event name from constant.
Base class for graph edge traversals.
void allowRediscovery(VertexIterator vertex)
Allow a vertex to be discovered again.
BreadthFirstForwardEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
boost::iterator_range< EdgeIterator > previousEdges(VertexIterator vertex, ForwardTraversalTag)
Previous edges in traversal order.
DepthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
Name space for the entire library.
Definition: Access.h:11
DepthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
DepthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
DepthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
BreadthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
DepthFirstForwardVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
void mapVertices(const Functor &f)
Call the specified functor for each vertex.
BreadthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
GraphTraits< Graph >::EdgeIterator EdgeIterator
Const or non-const edge node iterator.
BreadthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
Depth-first, reverse traversal for edges.
bool isAtEnd() const
Returns true when traversal reaches the end.
DepthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
DepthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
BreadthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
DepthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
VertexIterator vertex() const
Vertex to which traversal is pointing.
DepthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
GraphTraits< Graph >::VertexIterator::Reference operator*()
Return reference to current vertex.
DepthFirstReverseEdgeTraversal & operator++()
Advance traversal to next event.
BreadthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
Depth-first, reverse traversal for all event types.
GraphTraits< Graph >::VertexIterator::Pointer operator->()
Return pointer to current vertex.
BreadthFirstReverseVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
BreadthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
BreadthFirstForwardGraphTraversal & operator++()
Advance traversal to next event.
std::vector< size_t > graphAllEdges(Graph &graph)
IDs of all edges.
DepthFirstForwardEdgeTraversal & operator++()
Advance traversal to next event.
DepthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
GraphTraits< Graph >::EdgeIterator::Pointer operator->()
Return pointer to current edge.
BreadthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
BreadthFirstReverseEdgeTraversal & operator++()
Advance traversal to next event.
TraversalEvent event() const
Current event on which traversal is stopped.
GraphTraits< Graph >::VertexIterator VertexIterator
Const or non-const vertex node iterator.
BreadthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
Vertex entered for first time.
bool isDiscovered(VertexIterator vertex) const
True if the vertex has been discovered.
boost::iterator_range< EdgeIterator > nextEdges(VertexIterator vertex, ForwardTraversalTag)
Next edges in traversal order.
DepthFirstReverseEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
bool isVisited(EdgeIterator edge) const
True if the edge has been entered.
GraphTraversal(Graph &graph, unsigned significantEvents)
Construct traversal for graph.
BreadthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
Direction tag for forward traversals.
Breadth-first, forward traversal for vertices.
BitVector & setValue(const BitRange &range, bool value)
Assign true/false to some bits.
Definition: BitVector.h:300
DepthFirstReverseVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
Depth-first, forward traversal for all event types.
DepthFirstReverseGraphTraversal & operator++()
Advance traversal to next event.
void start(VertexIterator startVertex)
Restart the traversal at the specified vertex.
Base class for graph traversals.
std::vector< size_t > graphReachableEdges(Traversal t)
IDs of edges reachable from root.
void mapEdges(const Functor &f)
Call the specified functor for each edge.
BreadthFirstForwardEdgeTraversal & operator++()
Advance traversal to next event.
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition: Graph.h:1563
GraphTraits< Graph >::VertexIterator::Reference next()
Return reference to current vertex and advance.
Breadth-first, reverse traversal for vertices.
std::vector< size_t > graphAllVertices(Graph &graph)
IDs of all vertices.
DepthFirstForwardGraphTraversal & operator++()
Advance traversal to next event.
VertexIterator nextVertex(EdgeIterator edge, ForwardTraversalTag)
Next vertex in traversal order.
BreadthFirstReverseEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
BreadthFirstReverseVertexTraversal & operator++()
Advance traversal to next event.
void graphTraverseAllEdges(Traversal t, Functor &f)
Visit all edges of a graph.
Breadth-first, forward traversal for all event types.
std::vector< size_t > graphReachableVertices(Traversal t)
IDs of vertices reachable from root.