ROSE  0.9.10.54
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 <Sawyer/Sawyer.h>
15 #include <list>
16 #include <vector>
17 
18 namespace Sawyer {
19 namespace Container {
20 
22 namespace Algorithm {
23 
40  NO_EVENT = 0,
41  ENTER_VERTEX = 0x0001,
44  ENTER_EDGE = 0x0002,
50  DISCOVER_VERTEX = 0x0004,
54  LEAVE_EDGE = 0x0008,
60  LEAVE_VERTEX = 0x0010,
67  FOLLOW_EDGE = 0x0020 // Internal: current edge was followed to find neighbor vertex
68 };
69 
70 // Event sets (doxygen doesn't pick these up, so they're documented in the TraversalEvent enum
71 static const unsigned VERTEX_EVENTS = ENTER_VERTEX | DISCOVER_VERTEX | LEAVE_VERTEX;
72 static const unsigned EDGE_EVENTS = ENTER_EDGE | LEAVE_EDGE;
73 static const unsigned ENTER_EVENTS = ENTER_VERTEX | ENTER_EDGE;
74 static const unsigned LEAVE_EVENTS = LEAVE_VERTEX | LEAVE_EDGE;
75 static const unsigned ENTER_LEAVE_EVENTS = ENTER_EVENTS | LEAVE_EVENTS;
76 static const unsigned ALL_EVENTS = VERTEX_EVENTS | EDGE_EVENTS;
77 
79 SAWYER_EXPORT std::string traversalEventName(TraversalEvent);
80 
83 
86 
89 
92 
99 template<class VertexIterator, class EdgeIterator>
100 VertexIterator
101 nextVertex(EdgeIterator edge, ForwardTraversalTag) {
102  return edge->target();
103 }
104 
105 template<class VertexIterator, class EdgeIterator>
106 VertexIterator
107 nextVertex(EdgeIterator edge, ReverseTraversalTag) {
108  return edge->source();
109 }
118 template<class VertexIterator, class EdgeIterator>
119 VertexIterator
120 previousVertex(EdgeIterator edge, ForwardTraversalTag) {
121  return edge->source();
122 }
123 
124 template<class VertexIterator, class EdgeIterator>
125 VertexIterator
126 previousVertex(EdgeIterator edge, ReverseTraversalTag) {
127  return edge->target();
128 }
137 template<class EdgeIterator, class VertexIterator>
138 boost::iterator_range<EdgeIterator>
139 nextEdges(VertexIterator vertex, ForwardTraversalTag) {
140  return vertex->outEdges();
141 }
142 
143 template<class EdgeIterator, class VertexIterator>
144 boost::iterator_range<EdgeIterator>
145 nextEdges(VertexIterator vertex, ReverseTraversalTag) {
146  return vertex->inEdges();
147 }
156 template<class EdgeIterator, class VertexIterator>
157 boost::iterator_range<EdgeIterator>
158 previousEdges(VertexIterator vertex, ForwardTraversalTag) {
159  return vertex->inEdges();
160 }
161 
162 template<class EdgeIterator, class VertexIterator>
163 boost::iterator_range<EdgeIterator>
164 previousEdges(VertexIterator vertex, ReverseTraversalTag) {
165  return vertex->outEdges();
166 }
169 
388 template<class G, class Order=DepthFirstTraversalTag, class Direction=ForwardTraversalTag>
390 public:
391  typedef G Graph;
392 
395 
398 
399 private:
400  Graph &graph_;
401 
402 protected:
403  // Work that needs to be performed. The current item is always at the front of this list. Depth-first subclasses will push
404  // new work onto the front of the list and breadth-first subclasses will push it onto the end. When the list becomes empty
405  // then the iterator has reached its end state.
406  struct Work {
407  TraversalEvent event; // last event returned from this work item
408  EdgeIterator fromEdge; // edge that brought us to this vertex (or edges().end())
409  VertexIterator vertex; // vertex being visited
410  EdgeIterator edge; // edge being visited
411  EdgeIterator endEdge; // end edge for this vertex
412  bool followEdge; // follow edge to discover the neighbor vertex?
413  Work(EdgeIterator fromEdge, VertexIterator vertex, const boost::iterator_range<EdgeIterator> &nextEdges)
414  : event(DISCOVER_VERTEX), fromEdge(fromEdge), vertex(vertex), edge(nextEdges.begin()), endEdge(nextEdges.end()),
415  followEdge(true) {}
416  };
417  typedef std::list<Work> WorkList;
418  WorkList workList_;
419 
420 private:
421  unsigned significantEvents_; // events for which advance() will return to the caller
422  BitVector verticesDiscovered_; // vertices that are (or have been) on the work list
423  BitVector edgesVisited_; // edges that have been visited
424  Optional<Work> latestDiscovered_; // most recent work discovered
425 
426 public:
431  GraphTraversal(Graph &graph, unsigned significantEvents)
432  : graph_(graph), significantEvents_(significantEvents),
433  verticesDiscovered_(graph.nVertices()), edgesVisited_(graph.nEdges()) {}
434 
435 protected:
436  // Current work item.
437  Work& current() {
438  ASSERT_forbid(workList_.empty());
439  return workList_.front();
440  }
441  const Work& current() const {
442  ASSERT_forbid(workList_.empty());
443  return workList_.front();
444  }
445 
446  // True if event is significant to the user.
447  bool isSignificant(TraversalEvent event) const {
448  return 0 != (event & significantEvents_);
449  }
450 
451  // Mark a vertex as being discovered. A vertex so marked will not be added to the work list, but will remain in the
452  // worklist if it is already present.
453  void setDiscovered(VertexIterator vertex, bool isDiscovered=true) {
454  ASSERT_require(vertex != graph_.vertices().end());
455  verticesDiscovered_.setValue(vertex->id(), isDiscovered);
456  }
457 
458  // Mark an edge as having been entered. An edge so marked will not be entered again.
459  void setVisited(EdgeIterator edge, bool isVisited=true) {
460  ASSERT_require(edge != graph_.edges().end());
461  edgesVisited_.setValue(edge->id(), isVisited);
462  }
463 
464  // Reset to an inital empty state.
465  void clear() {
466  verticesDiscovered_.clear();
467  edgesVisited_.clear();
468  latestDiscovered_ = Nothing();
469  workList_.clear();
470  }
471 
472 public:
474  void start(VertexIterator startVertex) {
475  ASSERT_forbid(startVertex == graph_.vertices().end());
476  clear();
477  Work newWork(graph_.edges().end(), startVertex, nextEdges<EdgeIterator>(startVertex, Direction()));
478  enqueue(newWork, Order());
479  setDiscovered(startVertex);
480  latestDiscovered_ = newWork;
481  while (!isAtEnd() && !isSignificant(event()))
482  advance();
483  }
484 
486  void start(EdgeIterator startEdge) {
487  ASSERT_forbid(startEdge == graph_.edges().end());
488  clear();
489  EdgeIterator endEdge = startEdge; ++endEdge;
490  boost::iterator_range<EdgeIterator> edges(startEdge, endEdge);
491  Work newWork(graph_.edges().end(), graph_.vertices().end(), edges);
492  enqueue(newWork, Order());
493  setVisited(startEdge);
494  workList_.front().event = ENTER_EDGE;
495  while (!isAtEnd() && !isSignificant(event()))
496  advance();
497  }
498 
502  Graph& graph() const {
503  return graph_;
504  }
505 
510  if (isAtEnd())
511  throw std::runtime_error("attempt to dereference traversal at end");
512  return FOLLOW_EDGE==current().event ? DISCOVER_VERTEX : current().event;
513  }
514 
518  VertexIterator vertex() const {
519  switch (event()) {
520  case NO_EVENT:
521  return graph_.vertices().end();
522  case DISCOVER_VERTEX:
523  ASSERT_require(latestDiscovered_);
524  return latestDiscovered_->vertex;
525  case ENTER_VERTEX:
526  case ENTER_EDGE:
527  case LEAVE_VERTEX:
528  case LEAVE_EDGE:
529  return current().vertex;
530  default:
531  break;
532  }
533  ASSERT_not_reachable("invalid state");
534  }
535 
539  EdgeIterator edge() const {
540  switch (event()) {
541  case NO_EVENT:
542  return graph_.edges().end();
543  case ENTER_VERTEX:
544  return current().fromEdge;
545  case DISCOVER_VERTEX:
546  ASSERT_require(latestDiscovered_);
547  return latestDiscovered_->fromEdge;
548  case LEAVE_VERTEX:
549  return current().fromEdge;
550  case ENTER_EDGE:
551  return current().edge;
552  case LEAVE_EDGE:
553  return current().edge;
554  default:
555  break;
556  }
557  ASSERT_not_reachable("invalid state");
558  }
559 
564  bool isAtEnd() const {
565  return workList_.empty();
566  }
567 
584  bool hasNext() const {
585  return !isAtEnd();
586  }
587 
597  while (1) {
598  if (workList_.empty())
599  return NO_EVENT;
600 
601  // After leaving an edge advance to the next edge if any. The state is set to ENTER_VERTEX so that it looks like
602  // we're entering the vertex again, but this time at a different initial edge.
603  if (current().event == LEAVE_EDGE) {
604  if (workList_.front().edge != workList_.front().endEdge)
605  ++workList_.front().edge;
606  current().event = ENTER_VERTEX;
607  }
608 
609  // Leave the vertex if we're all done processing edges (or if it has none)
610  if (current().event == ENTER_VERTEX) {
611  while (workList_.front().edge != workList_.front().endEdge && isVisited(workList_.front().edge))
612  ++workList_.front().edge;
613  if (workList_.front().edge == workList_.front().endEdge) {
614  current().event = LEAVE_VERTEX;
615  if (isSignificant(LEAVE_VERTEX) && workList_.front().vertex != graph_.vertices().end())
616  return LEAVE_VERTEX;
617  }
618  }
619 
620  // All done with the current work?
621  if (current().event == LEAVE_VERTEX) {
622  workList_.pop_front();
623  if (workList_.empty())
624  return NO_EVENT; // end of traversal
625  }
626 
627  // We've left the vertex; now leave the edge that got us to that vertex (if any).
628  if (current().event == LEAVE_VERTEX) {
629  current().event = LEAVE_EDGE;
630  if (isSignificant(LEAVE_EDGE) && current().edge != graph_.edges().end())
631  return LEAVE_EDGE;
632  continue;
633  }
634 
635  // Enter a discovered vertex
636  if (current().event == DISCOVER_VERTEX) {
637  current().event = ENTER_VERTEX;
638  if (isSignificant(ENTER_VERTEX))
639  return ENTER_VERTEX;
640  continue;
641  }
642 
643  // Visit the edge after entering the vertex or returning from another edge
644  if (current().event == ENTER_VERTEX || current().event == LEAVE_EDGE) {
645  current().event = ENTER_EDGE;
646  setVisited(current().edge);
647  if (isSignificant(ENTER_EDGE))
648  return ENTER_EDGE;
649  }
650 
651  // Discover the neighbor vertex at the other end of this edge
652  if (current().event == ENTER_EDGE) {
653  current().event = FOLLOW_EDGE; // never escapes to the user
654  if (current().followEdge) {
655  VertexIterator neighbor = nextVertex<VertexIterator>(workList_.front().edge, Direction());
656  if (!isDiscovered(neighbor)) {
657  Work newWork(workList_.front().edge, neighbor, nextEdges<EdgeIterator>(neighbor, Direction()));
658  enqueue(newWork, Order());
659  setDiscovered(neighbor);
660  latestDiscovered_ = newWork;
661  if (isSignificant(DISCOVER_VERTEX))
662  return DISCOVER_VERTEX;
663  }
664  } else {
665  current().followEdge = true;
666  }
667  }
668 
669  // Leave the edge
670  if (current().event == FOLLOW_EDGE) {
671  current().event = LEAVE_EDGE;
672  if (isSignificant(LEAVE_EDGE))
673  return LEAVE_EDGE;
674  }
675  }
676  }
677 
683  void skipChildren() {
684  switch (event()) {
685  case NO_EVENT:
686  throw std::runtime_error("GraphTraversal::skipChildren called at end of traversal");
687  case ENTER_VERTEX:
688  current().edge = current().endEdge;
689  return;
690  case ENTER_EDGE:
691  current().followEdge = false;
692  return;
693  case DISCOVER_VERTEX:
694  case LEAVE_VERTEX:
695  case LEAVE_EDGE:
696  case FOLLOW_EDGE:
697  throw std::runtime_error("GraphTraversal::skipChildren cannot be called from " +
698  traversalEventName(event()) + " event");
699  }
700  ASSERT_not_reachable("invalid state: event=" + traversalEventName(event()));
701  }
702 
710  void allowRediscovery(VertexIterator vertex) {
711  if (vertex != graph_.vertices().end()) {
712  setDiscovered(vertex, false);
713  boost::iterator_range<EdgeIterator> edges = nextEdges<EdgeIterator>(vertex, Direction());
714  for (EdgeIterator iter=edges.begin(); iter!=edges.end(); ++iter)
715  setVisited(iter, false);
716  }
717  }
718 
724  bool isDiscovered(VertexIterator vertex) const {
725  if (vertex == graph_.vertices().end())
726  return false;
727  return verticesDiscovered_.get(vertex->id());
728  }
729 
733  bool isVisited(EdgeIterator edge) const {
734  if (edge == graph_.edges().end())
735  return false;
736  return edgesVisited_.get(edge->id());
737  }
738 
744  template<class Functor>
745  void mapVertices(Functor &f) {
746  while (!isAtEnd()) {
747  f(vertex());
748  advance();
749  }
750  }
751  template<class Functor>
752  void mapVertices(const Functor &f) {
753  while (!isAtEnd()) {
754  f(vertex());
755  advance();
756  }
757  }
765  template<class Functor>
766  void mapEdges(Functor &f) {
767  while (!isAtEnd()) {
768  f(edge());
769  advance();
770  }
771  }
772  template<class Functor>
773  void mapEdges(const Functor &f) {
774  while (!isAtEnd()) {
775  f(edge());
776  advance();
777  }
778  }
781  // The following trickery is to allow things like "if (x)" to work but without having an implicit
782  // conversion to bool which would cause no end of other problems. This is fixed in C++11.
783 private:
784  typedef void(GraphTraversal::*unspecified_bool)() const;
785  void this_type_does_not_support_comparisons() const {}
786 public:
797  operator unspecified_bool() const {
798  return isAtEnd() ? 0 : &GraphTraversal::this_type_does_not_support_comparisons;
799  }
800 
801 private:
802  // Adds new work to the list. Depth-first subclasses will push work onto the front of the list and breadth-first
803  // subclasses will push it onto the end.
804  void enqueue(const Work &work, DepthFirstTraversalTag) { workList_.push_front(work); }
805  void enqueue(const Work &work, BreadthFirstTraversalTag) { workList_.push_back(work); }
806 };
807 
808 
810 //
811 // Subclasses {Order}{Direction}GraphTraversal
812 //
814 
822 template<class Graph>
823 class DepthFirstForwardGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
824 public:
827  unsigned significantEvents=ALL_EVENTS)
828  : GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
829  this->start(startVertex);
830  }
831 
834  unsigned significantEvents=ALL_EVENTS)
835  : GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
836  this->start(startEdge);
837  }
838 
841  this->advance();
842  return *this;
843  }
844 };
845 
853 template<class Graph>
854 class DepthFirstReverseGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
855 public:
858  unsigned significantEvents=ALL_EVENTS)
859  : GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
860  this->start(startVertex);
861  }
862 
865  unsigned significantEvents=ALL_EVENTS)
866  : GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
867  this->start(startEdge);
868  }
869 
872  this->advance();
873  return *this;
874  }
875 };
876 
884 template<class Graph>
885 class BreadthFirstForwardGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
886 public:
889  unsigned significantEvents=ALL_EVENTS)
890  : GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
891  this->start(startVertex);
892  }
893 
896  unsigned significantEvents=ALL_EVENTS)
897  : GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
898  this->start(startEdge);
899  }
900 
903  this->advance();
904  return *this;
905  }
906 };
907 
915 template<class Graph>
916 class BreadthFirstReverseGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
917 public:
920  unsigned significantEvents=ALL_EVENTS)
921  : GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
922  this->start(startVertex);
923  }
924 
927  unsigned significantEvents=ALL_EVENTS)
928  : GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
929  this->start(startEdge);
930  }
931 
934  this->advance();
935  return *this;
936  }
937 };
938 
940 //
941 // Subclasses {Order}{Direction}VertexTraversal
942 //
944 
949 template<class Graph, class Order, class Direction>
950 class GraphVertexTraversal: public GraphTraversal<Graph, Order, Direction> {
951 protected:
953 
954 public:
957  return *this->vertex();
958  }
959 
962  return &*this->vertex();
963  }
964 
967  typename GraphTraits<Graph>::VertexIterator::Reference retval = this->vertex();
968  this->advance();
969  return retval;
970  }
971 };
972 
978 template<class Graph>
979 class DepthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
980 public:
984  this->start(startVertex);
985  }
986 
990  this->start(startEdge);
991  }
992 
996  this->start(graph.vertices().begin());
997  }
998 
1001  this->advance();
1002  return *this;
1003  }
1004 };
1005 
1011 template<class Graph>
1012 class DepthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
1013 public:
1017  this->start(startVertex);
1018  }
1019 
1023  this->start(startEdge);
1024  }
1025 
1029  this->start(graph.vertices().begin());
1030  }
1031 
1034  this->advance();
1035  return *this;
1036  }
1037 };
1038 
1044 template<class Graph>
1045 class BreadthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
1046 public:
1050  this->start(startVertex);
1051  }
1052 
1056  this->start(startEdge);
1057  }
1058 
1062  this->start(graph.vertices().begin());
1063  }
1064 
1067  this->advance();
1068  return *this;
1069  }
1070 };
1071 
1077 template<class Graph>
1078 class BreadthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
1079 public:
1083  this->start(startVertex);
1084  }
1085 
1089  this->start(startEdge);
1090  }
1091 
1095  this->start(graph.vertices().begin());
1096  }
1097 
1100  this->advance();
1101  return *this;
1102  }
1103 };
1104 
1106 //
1107 // Subclasses {Order}{Direction}EdgeTraversal
1108 //
1110 
1115 template<class Graph, class Order, class Direction>
1116 class GraphEdgeTraversal: public GraphTraversal<Graph, Order, Direction> {
1117 protected:
1119 
1120 public:
1123  return *this->edge();
1124  }
1125 
1128  return &*this->edge();
1129  }
1130 
1133  typename GraphTraits<Graph>::EdgeIterator::Reference retval = this->vertex();
1134  this->advance();
1135  return retval;
1136  }
1137 };
1138 
1144 template<class Graph>
1145 class DepthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
1146 public:
1150  this->start(startVertex);
1151  }
1152 
1156  this->start(startEdge);
1157  }
1158 
1162  this->start(graph.edges().begin());
1163  }
1164 
1167  this->advance();
1168  return *this;
1169  }
1170 };
1171 
1177 template<class Graph>
1178 class DepthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
1179 public:
1183  this->start(startVertex);
1184  }
1185 
1189  this->start(startEdge);
1190  }
1191 
1195  this->start(graph.edges().begin());
1196  }
1197 
1200  this->advance();
1201  return *this;
1202  }
1203 };
1204 
1210 template<class Graph>
1211 class BreadthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
1212 public:
1216  this->start(startVertex);
1217  }
1218 
1222  this->start(startEdge);
1223  }
1224 
1228  this->start(graph.edges().begin());
1229  }
1230 
1233  this->advance();
1234  return *this;
1235  }
1236 };
1237 
1243 template<class Graph>
1244 class BreadthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
1245 public:
1249  this->start(startVertex);
1250  }
1251 
1255  this->start(startEdge);
1256  }
1257 
1261  this->start(graph.edges().begin());
1262  }
1263 
1266  this->advance();
1267  return *this;
1268  }
1269 };
1270 
1271 
1272 
1274 //
1275 // Traversal visitation functions
1276 //
1278 
1292 template<class Traversal, class Functor>
1293 void graphTraverseAllVertices(Traversal t, Functor &f) {
1294  std::vector<bool> visited(t.graph().nVertices(), false);
1295  size_t rootId = 0;
1296  while (true) {
1297  for (typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
1298  typename Traversal::VertexIterator vertex = t.vertex();
1299  if (visited[vertex->id()]) {
1300  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1301  t.skipChildren();
1302  } else {
1303  visited[vertex->id()] = true;
1304  f(vertex, root);
1305  }
1306  }
1307  while (rootId < visited.size() && visited[rootId])
1308  ++rootId;
1309  if (rootId >= visited.size())
1310  return;
1311  t.start(t.graph().findVertex(rootId));
1312  }
1313 }
1314 template<class Traversal, class Functor>
1315 void graphTraverseAllVertices(Traversal t, const Functor &f) { // identical, other than const functor
1316  std::vector<bool> visited(t.graph().nVertices(), false);
1317  size_t rootId = 0;
1318  while (true) {
1319  for (typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
1320  typename Traversal::VertexIterator vertex = t.vertex();
1321  if (visited[vertex->id()]) {
1322  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1323  t.skipChildren();
1324  } else {
1325  visited[vertex->id()] = true;
1326  f(vertex, root);
1327  }
1328  }
1329  while (rootId < visited.size() && visited[rootId])
1330  ++rootId;
1331  if (rootId >= visited.size())
1332  return;
1333  t.start(t.graph().findVertex(rootId));
1334  }
1335 }
1351 template<class Traversal, class Functor>
1352 void graphTraverseAllEdges(Traversal t, Functor &f) {
1353  std::vector<bool> visited(t.graph().nEdges(), false);
1354  size_t rootId = 0;
1355  while (true) {
1356  for (typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
1357  typename Traversal::EdgeIterator edge = t.edge();
1358  if (visited[edge->id()]) {
1359  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1360  t.skipChildren();
1361  } else {
1362  visited[edge->id()] = true;
1363  f(edge, root);
1364  }
1365  }
1366  while (rootId < visited.size() && visited[rootId])
1367  ++rootId;
1368  if (rootId >= visited.size())
1369  return;
1370  t.start(t.graph().findEdge(rootId));
1371  }
1372 }
1373 template<class Traversal, class Functor>
1374 void graphTraverseAllEdges(Traversal t, const Functor &f) { // identical, other than const functor
1375  std::vector<bool> visited(t.graph().nEdges(), false);
1376  size_t rootId = 0;
1377  while (true) {
1378  for (typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
1379  typename Traversal::EdgeIterator edge = t.edge();
1380  if (visited[edge->id()]) {
1381  if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
1382  t.skipChildren();
1383  } else {
1384  visited[edge->id()] = true;
1385  f(edge, root);
1386  }
1387  }
1388  while (rootId < visited.size() && visited[rootId])
1389  ++rootId;
1390  if (rootId >= visited.size())
1391  return;
1392  t.start(t.graph().findEdge(rootId));
1393  }
1394 }
1401 template<class Graph>
1403 public:
1404  std::vector<size_t> ids;
1405 
1406  explicit IdAccumulator(size_t n) { ids.reserve(n); }
1407 
1408  void operator()(typename GraphTraits<Graph>::VertexIterator v) {
1409  ids.push_back(v->id());
1410  }
1411  void operator()(typename GraphTraits<Graph>::VertexIterator v, typename GraphTraits<Graph>::VertexIterator /*root*/) {
1412  ids.push_back(v->id());
1413  }
1414  void operator()(typename GraphTraits<Graph>::EdgeIterator e) {
1415  ids.push_back(e->id());
1416  }
1417  void operator()(typename GraphTraits<Graph>::EdgeIterator e, typename GraphTraits<Graph>::EdgeIterator /*root*/) {
1418  ids.push_back(e->id());
1419  }
1420 };
1421 
1426 template<class Traversal>
1427 std::vector<size_t> graphReachableVertices(Traversal t) {
1428  IdAccumulator<typename Traversal::Graph> accum(t.graph().nVertices());
1429  t.mapVertices(accum);
1430  return accum.ids;
1431 }
1432 
1436 template<class Traversal>
1437 std::vector<size_t> graphReachableEdges(Traversal t) {
1438  IdAccumulator<typename Traversal::Graph> accum(t.graph().nEdges());
1439  t.mapEdges(accum);
1440  return accum.ids;
1441 }
1442 
1448 template<class Traversal, class Graph>
1449 std::vector<size_t> graphAllVertices(Graph &graph) {
1450  IdAccumulator<Graph> accum(graph.nVertices());
1451  graphTraverseAllVertices(Traversal(graph, graph.vertices().begin()), accum);
1452  return accum.ids;
1453 }
1454 
1460 template<class Traversal, class Graph>
1461 std::vector<size_t> graphAllEdges(Graph &graph) {
1462  IdAccumulator<Graph> accum(graph.nEdges());
1463  graphTraverseAllEdges(Traversal(graph, graph.edges().begin()), accum);
1464  return accum.ids;
1465 }
1466 
1467 } // namespace
1468 } // namespace
1469 } // namespace
1470 
1471 #endif
Depth-first, forward traversal for vertices.
size_t nVertices() const
Total number of vertices.
Definition: Graph.h:1664
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:1674
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:1448
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:13
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:1557
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.