8#ifndef Sawyer_GraphTraversal_H
9#define Sawyer_GraphTraversal_H
11#include <Sawyer/Graph.h>
13#include <Sawyer/BitVector.h>
14#include <Sawyer/Sawyer.h>
75static const unsigned ENTER_LEAVE_EVENTS = ENTER_EVENTS | LEAVE_EVENTS;
76static const unsigned ALL_EVENTS = VERTEX_EVENTS | EDGE_EVENTS;
99template<
class VertexIterator,
class EdgeIterator>
102 return edge->target();
105template<
class VertexIterator,
class EdgeIterator>
108 return edge->source();
118template<
class VertexIterator,
class EdgeIterator>
121 return edge->source();
124template<
class VertexIterator,
class EdgeIterator>
127 return edge->target();
137template<
class EdgeIterator,
class VertexIterator>
138boost::iterator_range<EdgeIterator>
140 return vertex->outEdges();
143template<
class EdgeIterator,
class VertexIterator>
144boost::iterator_range<EdgeIterator>
146 return vertex->inEdges();
156template<
class EdgeIterator,
class VertexIterator>
157boost::iterator_range<EdgeIterator>
159 return vertex->inEdges();
162template<
class EdgeIterator,
class VertexIterator>
163boost::iterator_range<EdgeIterator>
165 return vertex->outEdges();
388template<
class G,
class Order=DepthFirstTraversalTag,
class Direction=ForwardTraversalTag>
417 typedef std::list<Work> WorkList;
421 unsigned significantEvents_;
432 : graph_(
graph), significantEvents_(significantEvents),
433 verticesDiscovered_(
graph.nVertices()), edgesVisited_(
graph.nEdges()) {}
438 ASSERT_forbid(workList_.empty());
439 return workList_.front();
441 const Work& current()
const {
442 ASSERT_forbid(workList_.empty());
443 return workList_.front();
448 return 0 != (
event & significantEvents_);
454 ASSERT_require(
vertex != graph_.vertices().end());
460 ASSERT_require(
edge != graph_.edges().end());
466 verticesDiscovered_.
clear();
467 edgesVisited_.
clear();
468 latestDiscovered_ = Nothing();
475 ASSERT_forbid(startVertex == graph_.vertices().end());
477 Work newWork(graph_.edges().end(), startVertex, nextEdges<EdgeIterator>(startVertex, Direction()));
478 enqueue(newWork, Order());
479 setDiscovered(startVertex);
480 latestDiscovered_ = newWork;
487 ASSERT_forbid(startEdge == graph_.edges().end());
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);
511 throw std::runtime_error(
"attempt to dereference traversal at end");
512 return FOLLOW_EDGE==current().event ?
DISCOVER_VERTEX : current().event;
521 return graph_.vertices().end();
523 ASSERT_require(latestDiscovered_);
524 return latestDiscovered_->vertex;
529 return current().vertex;
533 ASSERT_not_reachable(
"invalid state");
542 return graph_.edges().end();
544 return current().fromEdge;
546 ASSERT_require(latestDiscovered_);
547 return latestDiscovered_->fromEdge;
549 return current().fromEdge;
551 return current().edge;
553 return current().edge;
557 ASSERT_not_reachable(
"invalid state");
565 return workList_.empty();
598 if (workList_.empty())
604 if (workList_.front().edge != workList_.front().endEdge)
605 ++workList_.front().edge;
611 while (workList_.front().edge != workList_.front().endEdge &&
isVisited(workList_.front().edge))
612 ++workList_.front().edge;
613 if (workList_.front().edge == workList_.front().endEdge) {
615 if (isSignificant(
LEAVE_VERTEX) && workList_.front().vertex != graph_.vertices().end())
622 workList_.pop_front();
623 if (workList_.empty())
630 if (isSignificant(
LEAVE_EDGE) && current().
edge != graph_.edges().end())
646 setVisited(current().
edge);
653 current().event = FOLLOW_EDGE;
654 if (current().followEdge) {
655 VertexIterator neighbor = nextVertex<VertexIterator>(workList_.front().edge, Direction());
657 Work newWork(workList_.front().edge, neighbor, nextEdges<EdgeIterator>(neighbor, Direction()));
658 enqueue(newWork, Order());
659 setDiscovered(neighbor);
660 latestDiscovered_ = newWork;
665 current().followEdge =
true;
670 if (current().
event == FOLLOW_EDGE) {
686 throw std::runtime_error(
"GraphTraversal::skipChildren called at end of traversal");
688 current().edge = current().endEdge;
691 current().followEdge =
false;
697 throw std::runtime_error(
"GraphTraversal::skipChildren cannot be called from " +
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);
725 if (
vertex == graph_.vertices().end())
727 return verticesDiscovered_.
get(
vertex->id());
734 if (
edge == graph_.edges().end())
736 return edgesVisited_.
get(
edge->id());
744 template<
class Functor>
751 template<
class Functor>
765 template<
class Functor>
772 template<
class Functor>
785 void this_type_does_not_support_comparisons()
const {}
797 operator unspecified_bool()
const {
798 return isAtEnd() ? 0 : &GraphTraversal::this_type_does_not_support_comparisons;
805 void enqueue(
const Work &work, BreadthFirstTraversalTag) { workList_.push_back(work); }
827 unsigned significantEvents=ALL_EVENTS)
829 this->
start(startVertex);
834 unsigned significantEvents=ALL_EVENTS)
836 this->
start(startEdge);
858 unsigned significantEvents=ALL_EVENTS)
860 this->
start(startVertex);
865 unsigned significantEvents=ALL_EVENTS)
867 this->
start(startEdge);
889 unsigned significantEvents=ALL_EVENTS)
891 this->
start(startVertex);
896 unsigned significantEvents=ALL_EVENTS)
898 this->
start(startEdge);
920 unsigned significantEvents=ALL_EVENTS)
922 this->
start(startVertex);
927 unsigned significantEvents=ALL_EVENTS)
929 this->
start(startEdge);
949template<
class Graph,
class Order,
class Direction>
984 this->
start(startVertex);
990 this->
start(startEdge);
996 this->
start(graph.vertices().begin());
1011template<
class Graph>
1017 this->
start(startVertex);
1023 this->
start(startEdge);
1029 this->
start(graph.vertices().begin());
1044template<
class Graph>
1050 this->
start(startVertex);
1056 this->
start(startEdge);
1062 this->
start(graph.vertices().begin());
1077template<
class Graph>
1083 this->
start(startVertex);
1089 this->
start(startEdge);
1095 this->
start(graph.vertices().begin());
1115template<
class Graph,
class Order,
class Direction>
1123 return *this->
edge();
1128 return &*this->
edge();
1144template<
class Graph>
1150 this->
start(startVertex);
1156 this->
start(startEdge);
1162 this->
start(graph.edges().begin());
1177template<
class Graph>
1183 this->
start(startVertex);
1189 this->
start(startEdge);
1195 this->
start(graph.edges().begin());
1210template<
class Graph>
1216 this->
start(startVertex);
1222 this->
start(startEdge);
1228 this->
start(graph.edges().begin());
1243template<
class Graph>
1249 this->
start(startVertex);
1255 this->
start(startEdge);
1261 this->
start(graph.edges().begin());
1292template<
class Traversal,
class Functor>
1294 std::vector<bool> visited(t.graph().nVertices(),
false);
1297 for (
typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
1298 typename Traversal::VertexIterator vertex = t.vertex();
1299 if (visited[vertex->id()]) {
1303 visited[vertex->id()] =
true;
1307 while (rootId < visited.size() && visited[rootId])
1309 if (rootId >= visited.size())
1311 t.start(t.graph().findVertex(rootId));
1314template<
class Traversal,
class Functor>
1316 std::vector<bool> visited(t.graph().nVertices(),
false);
1319 for (
typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
1320 typename Traversal::VertexIterator vertex = t.vertex();
1321 if (visited[vertex->id()]) {
1325 visited[vertex->id()] =
true;
1329 while (rootId < visited.size() && visited[rootId])
1331 if (rootId >= visited.size())
1333 t.start(t.graph().findVertex(rootId));
1351template<
class Traversal,
class Functor>
1353 std::vector<bool> visited(t.graph().nEdges(),
false);
1356 for (
typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
1357 typename Traversal::EdgeIterator edge = t.edge();
1358 if (visited[edge->id()]) {
1362 visited[edge->id()] =
true;
1366 while (rootId < visited.size() && visited[rootId])
1368 if (rootId >= visited.size())
1370 t.start(t.graph().findEdge(rootId));
1373template<
class Traversal,
class Functor>
1375 std::vector<bool> visited(t.graph().nEdges(),
false);
1378 for (
typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
1379 typename Traversal::EdgeIterator edge = t.edge();
1380 if (visited[edge->id()]) {
1384 visited[edge->id()] =
true;
1388 while (rootId < visited.size() && visited[rootId])
1390 if (rootId >= visited.size())
1392 t.start(t.graph().findEdge(rootId));
1401template<
class Graph>
1404 std::vector<size_t> ids;
1409 ids.push_back(v->id());
1412 ids.push_back(v->id());
1415 ids.push_back(e->id());
1418 ids.push_back(e->id());
1426template<
class Traversal>
1429 t.mapVertices(accum);
1436template<
class Traversal>
1448template<
class Traversal,
class Graph>
1460template<
class Traversal,
class Graph>
Breadth-first, forward traversal for edges.
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, reverse traversal for edges.
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.
Order tag for breadth-first traversals.
Depth-first, forward traversal for edges.
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, reverse traversal for edges.
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.
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.
Accumulates vertex or edge IDs.
Direction tag for reverse traversals.
BitVector & clear(const BitRange &range)
Assign zero to some bits.
BitVector & setValue(const BitRange &range, bool value)
Assign true/false to some bits.
bool get(size_t idx) const
Retrieve one bit.
Graph containing user-defined vertices and edges.
boost::iterator_range< EdgeIterator > edges()
Iterators for all edges.
size_t nVertices() const
Total number of vertices.
boost::iterator_range< VertexIterator > vertices()
Iterators for all vertices.
size_t nEdges() const
Total number of edges.
Holds a value or nothing.
void graphTraverseAllEdges(Traversal t, Functor &f)
Visit all edges of a graph.
TraversalEvent
Events returned by a graph traversal.
@ ENTER_EDGE
Edge is entered.
@ DISCOVER_VERTEX
Neighboring vertex discovered for the first time.
@ ENTER_VERTEX
Vertex entered for first time.
@ LEAVE_VERTEX
Leaving vertex.
@ LEAVE_EDGE
Leaving edge.
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.
G::EdgeIterator EdgeIterator
Const or non-const edge iterator.
G::VertexIterator VertexIterator
Const or non-const vertex iterator.