ROSE 0.11.145.147
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://gitlab.com/charger7534/sawyer.git.
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
18namespace Sawyer {
19namespace Container {
20
22namespace Algorithm {
23
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
71static const unsigned VERTEX_EVENTS = ENTER_VERTEX | DISCOVER_VERTEX | LEAVE_VERTEX;
72static const unsigned EDGE_EVENTS = ENTER_EDGE | LEAVE_EDGE;
73static const unsigned ENTER_EVENTS = ENTER_VERTEX | ENTER_EDGE;
74static const unsigned LEAVE_EVENTS = LEAVE_VERTEX | LEAVE_EDGE;
75static const unsigned ENTER_LEAVE_EVENTS = ENTER_EVENTS | LEAVE_EVENTS;
76static const unsigned ALL_EVENTS = VERTEX_EVENTS | EDGE_EVENTS;
77
79SAWYER_EXPORT std::string traversalEventName(TraversalEvent);
80
83
86
89
92
99template<class VertexIterator, class EdgeIterator>
100VertexIterator
101nextVertex(EdgeIterator edge, ForwardTraversalTag) {
102 return edge->target();
103}
104
105template<class VertexIterator, class EdgeIterator>
106VertexIterator
107nextVertex(EdgeIterator edge, ReverseTraversalTag) {
108 return edge->source();
109}
118template<class VertexIterator, class EdgeIterator>
119VertexIterator
121 return edge->source();
122}
123
124template<class VertexIterator, class EdgeIterator>
125VertexIterator
127 return edge->target();
128}
137template<class EdgeIterator, class VertexIterator>
138boost::iterator_range<EdgeIterator>
139nextEdges(VertexIterator vertex, ForwardTraversalTag) {
140 return vertex->outEdges();
141}
142
143template<class EdgeIterator, class VertexIterator>
144boost::iterator_range<EdgeIterator>
145nextEdges(VertexIterator vertex, ReverseTraversalTag) {
146 return vertex->inEdges();
147}
156template<class EdgeIterator, class VertexIterator>
157boost::iterator_range<EdgeIterator>
158previousEdges(VertexIterator vertex, ForwardTraversalTag) {
159 return vertex->inEdges();
160}
161
162template<class EdgeIterator, class VertexIterator>
163boost::iterator_range<EdgeIterator>
164previousEdges(VertexIterator vertex, ReverseTraversalTag) {
165 return vertex->outEdges();
166}
170
388template<class G, class Order=DepthFirstTraversalTag, class Direction=ForwardTraversalTag>
390public:
391 typedef G Graph;
392
395
398
399private:
400 Graph &graph_;
401
402protected:
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
420private:
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
426public:
431 GraphTraversal(Graph &graph, unsigned significantEvents)
432 : graph_(graph), significantEvents_(significantEvents),
433 verticesDiscovered_(graph.nVertices()), edgesVisited_(graph.nEdges()) {}
434
435protected:
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
472public:
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
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
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
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
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
725 if (vertex == graph_.vertices().end())
726 return false;
727 return verticesDiscovered_.get(vertex->id());
728 }
729
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.
783private:
784 typedef void(GraphTraversal::*unspecified_bool)() const;
785 void this_type_does_not_support_comparisons() const {}
786public:
797 operator unspecified_bool() const {
798 return isAtEnd() ? 0 : &GraphTraversal::this_type_does_not_support_comparisons;
799 }
800
801private:
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
822template<class Graph>
823class DepthFirstForwardGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
824public:
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
853template<class Graph>
854class DepthFirstReverseGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
855public:
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
884template<class Graph>
885class BreadthFirstForwardGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
886public:
889 unsigned significantEvents=ALL_EVENTS)
891 this->start(startVertex);
892 }
893
896 unsigned significantEvents=ALL_EVENTS)
898 this->start(startEdge);
899 }
900
903 this->advance();
904 return *this;
905 }
906};
907
915template<class Graph>
916class BreadthFirstReverseGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
917public:
920 unsigned significantEvents=ALL_EVENTS)
922 this->start(startVertex);
923 }
924
927 unsigned significantEvents=ALL_EVENTS)
929 this->start(startEdge);
930 }
931
934 this->advance();
935 return *this;
936 }
937};
938
940//
941// Subclasses {Order}{Direction}VertexTraversal
942//
944
949template<class Graph, class Order, class Direction>
950class GraphVertexTraversal: public GraphTraversal<Graph, Order, Direction> {
951protected:
953
954public:
957 return *this->vertex();
958 }
959
962 return &*this->vertex();
963 }
964
968 this->advance();
969 return retval;
970 }
971};
972
978template<class Graph>
979class DepthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
980public:
986
992
996 this->start(graph.vertices().begin());
997 }
998
1001 this->advance();
1002 return *this;
1003 }
1004};
1005
1011template<class Graph>
1012class DepthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
1013public:
1019
1025
1029 this->start(graph.vertices().begin());
1030 }
1031
1034 this->advance();
1035 return *this;
1036 }
1037};
1038
1044template<class Graph>
1045class BreadthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
1046public:
1052
1058
1062 this->start(graph.vertices().begin());
1063 }
1064
1067 this->advance();
1068 return *this;
1069 }
1070};
1071
1077template<class Graph>
1078class BreadthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
1079public:
1085
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
1115template<class Graph, class Order, class Direction>
1116class GraphEdgeTraversal: public GraphTraversal<Graph, Order, Direction> {
1117protected:
1119
1120public:
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
1144template<class Graph>
1145class DepthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
1146public:
1152
1158
1162 this->start(graph.edges().begin());
1163 }
1164
1167 this->advance();
1168 return *this;
1169 }
1170};
1171
1177template<class Graph>
1178class DepthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
1179public:
1185
1191
1195 this->start(graph.edges().begin());
1196 }
1197
1200 this->advance();
1201 return *this;
1202 }
1203};
1204
1210template<class Graph>
1211class BreadthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
1212public:
1218
1224
1228 this->start(graph.edges().begin());
1229 }
1230
1233 this->advance();
1234 return *this;
1235 }
1236};
1237
1243template<class Graph>
1244class BreadthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
1245public:
1251
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
1292template<class Traversal, class Functor>
1293void 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}
1314template<class Traversal, class Functor>
1315void 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}
1351template<class Traversal, class Functor>
1352void 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}
1373template<class Traversal, class Functor>
1374void 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}
1401template<class Graph>
1403public:
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
1426template<class Traversal>
1427std::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
1436template<class Traversal>
1437std::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
1448template<class Traversal, class Graph>
1449std::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
1460template<class Traversal, class Graph>
1461std::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
BreadthFirstForwardEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
BreadthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
BreadthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
BreadthFirstForwardEdgeTraversal & operator++()
Advance traversal to next event.
Breadth-first, forward traversal for all event types.
BreadthFirstForwardGraphTraversal & operator++()
Advance traversal to next event.
BreadthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
BreadthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
Breadth-first, forward traversal for vertices.
BreadthFirstForwardVertexTraversal & operator++()
Advance traversal to next event.
BreadthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
BreadthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
BreadthFirstForwardVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
BreadthFirstReverseEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
BreadthFirstReverseEdgeTraversal & operator++()
Advance traversal to next event.
BreadthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
BreadthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
Breadth-first, reverse traversal for all event types.
BreadthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
BreadthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
BreadthFirstReverseGraphTraversal & operator++()
Advance traversal to next event.
Breadth-first, reverse traversal for vertices.
BreadthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
BreadthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
BreadthFirstReverseVertexTraversal & operator++()
Advance traversal to next event.
BreadthFirstReverseVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
Order tag for breadth-first traversals.
DepthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
DepthFirstForwardEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
DepthFirstForwardEdgeTraversal & operator++()
Advance traversal to next event.
DepthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
Depth-first, forward traversal for all event types.
DepthFirstForwardGraphTraversal & operator++()
Advance traversal to next event.
DepthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
DepthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
Depth-first, forward traversal for vertices.
DepthFirstForwardVertexTraversal & operator++()
Advance traversal to next event.
DepthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
DepthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
DepthFirstForwardVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
DepthFirstReverseEdgeTraversal(Graph &graph)
Start traversal at edge number zero.
DepthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
DepthFirstReverseEdgeTraversal & operator++()
Advance traversal to next event.
DepthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
Depth-first, reverse traversal for all event types.
DepthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified edge.
DepthFirstReverseGraphTraversal & operator++()
Advance traversal to next event.
DepthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
Start traversal at specified vertex.
DepthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
Start traversal at specified vertex.
DepthFirstReverseVertexTraversal & operator++()
Advance traversal to next event.
DepthFirstReverseVertexTraversal(Graph &graph)
Start traversal at vertex number zero.
DepthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
Start traversal at specified edge.
Order tag for depth-first traversals.
Direction tag for forward traversals.
Base class for graph edge traversals.
GraphTraits< Graph >::EdgeIterator::Reference next()
Return reference to current edge and advance.
GraphTraits< Graph >::EdgeIterator::Pointer operator->()
Return pointer to current edge.
GraphTraits< Graph >::EdgeIterator::Reference operator*()
Return reference to current edge.
Base class for graph traversals.
GraphTraits< Graph >::EdgeIterator EdgeIterator
Const or non-const edge node iterator.
void start(VertexIterator startVertex)
Restart the traversal at the specified vertex.
void mapVertices(const Functor &f)
Call the specified functor for each vertex.
void start(EdgeIterator startEdge)
Restart the traversal at the specified edge.
TraversalEvent advance()
Advance traversal to next interesting event.
void skipChildren()
Causes traversal to skip children.
bool hasNext() const
Returns true when a traversal can be advanced.
void mapVertices(Functor &f)
Call the specified functor for each vertex.
bool isDiscovered(VertexIterator vertex) const
True if the vertex has been discovered.
bool isVisited(EdgeIterator edge) const
True if the edge has been entered.
GraphTraversal(Graph &graph, unsigned significantEvents)
Construct traversal for graph.
void allowRediscovery(VertexIterator vertex)
Allow a vertex to be discovered again.
VertexIterator vertex() const
Vertex to which traversal is pointing.
void mapEdges(const Functor &f)
Call the specified functor for each edge.
EdgeIterator edge() const
Edge to which traversal is pointing.
bool isAtEnd() const
Returns true when traversal reaches the end.
void mapEdges(Functor &f)
Call the specified functor for each edge.
TraversalEvent event() const
Current event on which traversal is stopped.
GraphTraits< Graph >::VertexIterator VertexIterator
Const or non-const vertex node iterator.
Graph & graph() const
The graph over which iteration occurs.
Base class for graph vertex traversals.
GraphTraits< Graph >::VertexIterator::Reference operator*()
Return reference to current vertex.
GraphTraits< Graph >::VertexIterator::Reference next()
Return reference to current vertex and advance.
GraphTraits< Graph >::VertexIterator::Pointer operator->()
Return pointer to current vertex.
Direction tag for reverse traversals.
BitVector & clear(const BitRange &range)
Assign zero to some bits.
Definition BitVector.h:281
BitVector & setValue(const BitRange &range, bool value)
Assign true/false to some bits.
Definition BitVector.h:319
bool get(size_t idx) const
Retrieve one bit.
Definition BitVector.h:271
Graph containing user-defined vertices and edges.
Definition Graph.h:634
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
Definition Graph.h:1647
size_t nVertices() const
Total number of vertices.
Definition Graph.h:1754
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
Definition Graph.h:1538
size_t nEdges() const
Total number of edges.
Definition Graph.h:1764
Holds a value or nothing.
Definition Optional.h:56
void graphTraverseAllEdges(Traversal t, Functor &f)
Visit all edges of a graph.
TraversalEvent
Events returned by a graph traversal.
@ DISCOVER_VERTEX
Neighboring vertex discovered for the first time.
@ ENTER_VERTEX
Vertex entered for first time.
std::vector< size_t > graphReachableVertices(Traversal t)
IDs of vertices reachable from root.
void graphTraverseAllVertices(Traversal t, Functor &f)
Visit all vertices of a graph.
std::vector< size_t > graphAllEdges(Graph &graph)
IDs of all edges.
std::string traversalEventName(TraversalEvent)
Event name from constant.
VertexIterator nextVertex(EdgeIterator edge, ForwardTraversalTag)
Next vertex in traversal order.
boost::iterator_range< EdgeIterator > nextEdges(VertexIterator vertex, ForwardTraversalTag)
Next edges in traversal order.
std::vector< size_t > graphReachableEdges(Traversal t)
IDs of edges reachable from root.
boost::iterator_range< EdgeIterator > previousEdges(VertexIterator vertex, ForwardTraversalTag)
Previous edges in traversal order.
VertexIterator previousVertex(EdgeIterator edge, ForwardTraversalTag)
Previous vertex in traversal order.
std::vector< size_t > graphAllVertices(Graph &graph)
IDs of all vertices.
Sawyer support library.
Traits for graphs.
Definition Graph.h:284
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
Definition Graph.h:286
G::VertexIterator VertexIterator
Const or non-const vertex iterator.
Definition Graph.h:292