GraphTraversal.h

// WARNING: Changes to this file must be contributed back to Sawyer or else they will
//          be clobbered by the next update from Sawyer.  The Sawyer repository is at
//          https://github.com/matzke1/sawyer.
 
 
 
 
#ifndef Sawyer_GraphTraversal_H
#define Sawyer_GraphTraversal_H
 
#include <Sawyer/Graph.h>
 
#include <Sawyer/BitVector.h>
#include <Sawyer/Sawyer.h>
#include <list>
#include <vector>
 
namespace Sawyer {
namespace Container {
 
namespace Algorithm {
 
enum TraversalEvent {
    NO_EVENT        = 0,      
    ENTER_VERTEX    = 0x0001, 
    ENTER_EDGE      = 0x0002, 
    DISCOVER_VERTEX = 0x0004, 
    LEAVE_EDGE      = 0x0008, 
    LEAVE_VERTEX    = 0x0010, 
    FOLLOW_EDGE     = 0x0020  // Internal: current edge was followed to find neighbor vertex
};
 
// Event sets (doxygen doesn't pick these up, so they're documented in the TraversalEvent enum
static const unsigned VERTEX_EVENTS = ENTER_VERTEX | DISCOVER_VERTEX | LEAVE_VERTEX;
static const unsigned EDGE_EVENTS = ENTER_EDGE | LEAVE_EDGE;
static const unsigned ENTER_EVENTS = ENTER_VERTEX | ENTER_EDGE;
static const unsigned LEAVE_EVENTS = LEAVE_VERTEX | LEAVE_EDGE;
static const unsigned ENTER_LEAVE_EVENTS = ENTER_EVENTS | LEAVE_EVENTS;
static const unsigned ALL_EVENTS = VERTEX_EVENTS | EDGE_EVENTS;
 
SAWYER_EXPORT std::string traversalEventName(TraversalEvent);
 
class ForwardTraversalTag {};
 
class ReverseTraversalTag {};
 
class DepthFirstTraversalTag {};
 
class BreadthFirstTraversalTag {};
 
template<class VertexIterator, class EdgeIterator>
VertexIterator
nextVertex(EdgeIterator edge, ForwardTraversalTag) {
    return edge->target();
}
 
template<class VertexIterator, class EdgeIterator>
VertexIterator
nextVertex(EdgeIterator edge, ReverseTraversalTag) {
    return edge->source();
}
template<class VertexIterator, class EdgeIterator>
VertexIterator
previousVertex(EdgeIterator edge, ForwardTraversalTag) {
    return edge->source();
}
 
template<class VertexIterator, class EdgeIterator>
VertexIterator
previousVertex(EdgeIterator edge, ReverseTraversalTag) {
    return edge->target();
}
template<class EdgeIterator, class VertexIterator>
boost::iterator_range<EdgeIterator>
nextEdges(VertexIterator vertex, ForwardTraversalTag) {
    return vertex->outEdges();
}
 
template<class EdgeIterator, class VertexIterator>
boost::iterator_range<EdgeIterator>
nextEdges(VertexIterator vertex, ReverseTraversalTag) {
    return vertex->inEdges();
}
template<class EdgeIterator, class VertexIterator>
boost::iterator_range<EdgeIterator>
previousEdges(VertexIterator vertex, ForwardTraversalTag) {
    return vertex->inEdges();
}
 
template<class EdgeIterator, class VertexIterator>
boost::iterator_range<EdgeIterator>
previousEdges(VertexIterator vertex, ReverseTraversalTag) {
    return vertex->outEdges();
}
 
template<class G, class Order=DepthFirstTraversalTag, class Direction=ForwardTraversalTag>
class GraphTraversal {
public:
    typedef G Graph;
 
    typedef typename GraphTraits<Graph>::VertexIterator VertexIterator;
 
    typedef typename GraphTraits<Graph>::EdgeIterator EdgeIterator;
 
private:
    Graph &graph_;
 
protected:
    // Work that needs to be performed.  The current item is always at the front of this list. Depth-first subclasses will push
    // new work onto the front of the list and breadth-first subclasses will push it onto the end.  When the list becomes empty
    // then the iterator has reached its end state.
    struct Work {
        TraversalEvent event;                           // last event returned from this work item
        EdgeIterator fromEdge;                          // edge that brought us to this vertex (or edges().end())
        VertexIterator vertex;                          // vertex being visited
        EdgeIterator edge;                              // edge being visited
        EdgeIterator endEdge;                           // end edge for this vertex
        bool followEdge;                                // follow edge to discover the neighbor vertex?
        Work(EdgeIterator fromEdge, VertexIterator vertex, const boost::iterator_range<EdgeIterator> &nextEdges)
            : event(DISCOVER_VERTEX), fromEdge(fromEdge), vertex(vertex), edge(nextEdges.begin()), endEdge(nextEdges.end()),
              followEdge(true) {}
    };
    typedef std::list<Work> WorkList;
    WorkList workList_;
 
private:
    unsigned significantEvents_;                        // events for which advance() will return to the caller
    BitVector verticesDiscovered_;                      // vertices that are (or have been) on the work list
    BitVector edgesVisited_;                            // edges that have been visited
    Optional<Work> latestDiscovered_;                   // most recent work discovered
 
public:
    GraphTraversal(Graph &graph, unsigned significantEvents)
        : graph_(graph), significantEvents_(significantEvents),
          verticesDiscovered_(graph.nVertices()), edgesVisited_(graph.nEdges()) {}
        
protected:
    // Current work item.
    Work& current() {
        ASSERT_forbid(workList_.empty());
        return workList_.front();
    }
    const Work& current() const {
        ASSERT_forbid(workList_.empty());
        return workList_.front();
    }
 
    // True if event is significant to the user.
    bool isSignificant(TraversalEvent event) const {
        return 0 != (event & significantEvents_);
    }
 
    // Mark a vertex as being discovered.  A vertex so marked will not be added to the work list, but will remain in the
    // worklist if it is already present.
    void setDiscovered(VertexIterator vertex, bool isDiscovered=true) {
        ASSERT_require(vertex != graph_.vertices().end());
        verticesDiscovered_.setValue(vertex->id(), isDiscovered);
    }
 
    // Mark an edge as having been entered.  An edge so marked will not be entered again.
    void setVisited(EdgeIterator edge, bool isVisited=true) {
        ASSERT_require(edge != graph_.edges().end());
        edgesVisited_.setValue(edge->id(), isVisited);
    }
 
    // Reset to an inital empty state.
    void clear() {
        verticesDiscovered_.clear();
        edgesVisited_.clear();
        latestDiscovered_ = Nothing();
        workList_.clear();
    }
 
public:
    void start(VertexIterator startVertex) {
        ASSERT_forbid(startVertex == graph_.vertices().end());
        clear();
        Work newWork(graph_.edges().end(), startVertex, nextEdges<EdgeIterator>(startVertex, Direction()));
        enqueue(newWork, Order());
        setDiscovered(startVertex);
        latestDiscovered_ = newWork;
        while (!isAtEnd() && !isSignificant(event()))
            advance();
    }
 
    void start(EdgeIterator startEdge) {
        ASSERT_forbid(startEdge == graph_.edges().end());
        clear();
        EdgeIterator endEdge = startEdge; ++endEdge;
        boost::iterator_range<EdgeIterator> edges(startEdge, endEdge);
        Work newWork(graph_.edges().end(), graph_.vertices().end(), edges);
        enqueue(newWork, Order());
        setVisited(startEdge);
        workList_.front().event = ENTER_EDGE;
        while (!isAtEnd() && !isSignificant(event()))
            advance();
    }
 
    Graph& graph() const {
        return graph_;
    }
 
    TraversalEvent event() const {
        if (isAtEnd())
            throw std::runtime_error("attempt to dereference traversal at end");
        return FOLLOW_EDGE==current().event ? DISCOVER_VERTEX : current().event;
    }
 
    VertexIterator vertex() const {
        switch (event()) {
            case NO_EVENT:
                return graph_.vertices().end();
            case DISCOVER_VERTEX:
                ASSERT_require(latestDiscovered_);
                return latestDiscovered_->vertex;
            case ENTER_VERTEX:
            case ENTER_EDGE:
            case LEAVE_VERTEX:
            case LEAVE_EDGE:
                return current().vertex;
            default:
                break;
        }
        ASSERT_not_reachable("invalid state");
    }
 
    EdgeIterator edge() const {
        switch (event()) {
            case NO_EVENT:
                return graph_.edges().end();
            case ENTER_VERTEX:
                return current().fromEdge;
            case DISCOVER_VERTEX:
                ASSERT_require(latestDiscovered_);
                return latestDiscovered_->fromEdge;
            case LEAVE_VERTEX:
                return current().fromEdge;
            case ENTER_EDGE:
                return current().edge;
            case LEAVE_EDGE:
                return current().edge;
            default:
                break;
        }
        ASSERT_not_reachable("invalid state");
    }
 
    bool isAtEnd() const {
        return workList_.empty();
    }
 
    bool hasNext() const {
        return !isAtEnd();
    }
 
    TraversalEvent advance() {
        while (1) {
            if (workList_.empty())
                return NO_EVENT;
            
            // After leaving an edge advance to the next edge if any. The state is set to ENTER_VERTEX so that it looks like
            // we're entering the vertex again, but this time at a different initial edge.
            if (current().event == LEAVE_EDGE) {
                if (workList_.front().edge != workList_.front().endEdge)
                    ++workList_.front().edge;
                current().event = ENTER_VERTEX;
            }
 
            // Leave the vertex if we're all done processing edges (or if it has none)
            if (current().event == ENTER_VERTEX) {
                while (workList_.front().edge != workList_.front().endEdge && isVisited(workList_.front().edge))
                    ++workList_.front().edge;
                if (workList_.front().edge == workList_.front().endEdge) {
                    current().event = LEAVE_VERTEX;
                    if (isSignificant(LEAVE_VERTEX) && workList_.front().vertex != graph_.vertices().end())
                        return LEAVE_VERTEX;
                }
            }
            
            // All done with the current work?
            if (current().event == LEAVE_VERTEX) {
                workList_.pop_front();
                if (workList_.empty())
                    return NO_EVENT;                    // end of traversal
            }
 
            // We've left the vertex; now leave the edge that got us to that vertex (if any).
            if (current().event == LEAVE_VERTEX) {
                current().event = LEAVE_EDGE;
                if (isSignificant(LEAVE_EDGE) && current().edge != graph_.edges().end())
                    return LEAVE_EDGE;
                continue;
            }
 
            // Enter a discovered vertex
            if (current().event == DISCOVER_VERTEX) {
                current().event = ENTER_VERTEX;
                if (isSignificant(ENTER_VERTEX))
                    return ENTER_VERTEX;
                continue;
            }
 
            // Visit the edge after entering the vertex or returning from another edge
            if (current().event == ENTER_VERTEX || current().event == LEAVE_EDGE) {
                current().event = ENTER_EDGE;
                setVisited(current().edge);
                if (isSignificant(ENTER_EDGE))
                    return ENTER_EDGE;
            }
            
            // Discover the neighbor vertex at the other end of this edge
            if (current().event == ENTER_EDGE) {
                current().event = FOLLOW_EDGE; // never escapes to the user
                if (current().followEdge) {
                    VertexIterator neighbor = nextVertex<VertexIterator>(workList_.front().edge, Direction());
                    if (!isDiscovered(neighbor)) {
                        Work newWork(workList_.front().edge, neighbor, nextEdges<EdgeIterator>(neighbor, Direction()));
                        enqueue(newWork, Order());
                        setDiscovered(neighbor);
                        latestDiscovered_ = newWork;
                        if (isSignificant(DISCOVER_VERTEX))
                            return DISCOVER_VERTEX;
                    }
                } else {
                    current().followEdge = true;
                }
            }
 
            // Leave the edge
            if (current().event == FOLLOW_EDGE) {
                current().event = LEAVE_EDGE;
                if (isSignificant(LEAVE_EDGE))
                    return LEAVE_EDGE;
            }
        }
    }
 
    void skipChildren() {
        switch (event()) {
            case NO_EVENT:
                throw std::runtime_error("GraphTraversal::skipChildren called at end of traversal");
            case ENTER_VERTEX:
                current().edge = current().endEdge;
                return;
            case ENTER_EDGE:
                current().followEdge = false;
                return;
            case DISCOVER_VERTEX:
            case LEAVE_VERTEX:
            case LEAVE_EDGE:
            case FOLLOW_EDGE:
                throw std::runtime_error("GraphTraversal::skipChildren cannot be called from " +
                                         traversalEventName(event()) + " event");
        }
        ASSERT_not_reachable("invalid state: event=" + traversalEventName(event()));
    }
 
    void allowRediscovery(VertexIterator vertex) {
        if (vertex != graph_.vertices().end()) {
            setDiscovered(vertex, false);
            boost::iterator_range<EdgeIterator> edges = nextEdges<EdgeIterator>(vertex, Direction());
            for (EdgeIterator iter=edges.begin(); iter!=edges.end(); ++iter)
                setVisited(iter, false);
        }
    }
    
    bool isDiscovered(VertexIterator vertex) const {
        if (vertex == graph_.vertices().end())
            return false;
        return verticesDiscovered_.get(vertex->id());
    }
 
    bool isVisited(EdgeIterator edge) const {
        if (edge == graph_.edges().end())
            return false;
        return edgesVisited_.get(edge->id());
    }
 
    template<class Functor>
    void mapVertices(Functor &f) {
        while (!isAtEnd()) {
            f(vertex());
            advance();
        }
    }
    template<class Functor>
    void mapVertices(const Functor &f) {
        while (!isAtEnd()) {
            f(vertex());
            advance();
        }
    }
    template<class Functor>
    void mapEdges(Functor &f) {
        while (!isAtEnd()) {
            f(edge());
            advance();
        }
    }
    template<class Functor>
    void mapEdges(const Functor &f) {
        while (!isAtEnd()) {
            f(edge());
            advance();
        }
    }
    // The following trickery is to allow things like "if (x)" to work but without having an implicit
    // conversion to bool which would cause no end of other problems. This is fixed in C++11.
private:
    typedef void(GraphTraversal::*unspecified_bool)() const;
    void this_type_does_not_support_comparisons() const {}
public:
    operator unspecified_bool() const {
        return isAtEnd() ? 0 : &GraphTraversal::this_type_does_not_support_comparisons;
    }
 
private:
    // Adds new work to the list.  Depth-first subclasses will push work onto the front of the list and breadth-first
    // subclasses will push it onto the end.
    void enqueue(const Work &work, DepthFirstTraversalTag) { workList_.push_front(work); }
    void enqueue(const Work &work, BreadthFirstTraversalTag) { workList_.push_back(work); }
};
 
 
//
//                                      Subclasses {Order}{Direction}GraphTraversal
//
 
template<class Graph>
class DepthFirstForwardGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
public:
    DepthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex,
                                    unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
        this->start(startVertex);
    }
 
    DepthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge,
                                    unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
        this->start(startEdge);
    }
 
    DepthFirstForwardGraphTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
template<class Graph>
class DepthFirstReverseGraphTraversal: public GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
public:
    DepthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex,
                                    unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
        this->start(startVertex);
    }
 
    DepthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge,
                                    unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
        this->start(startEdge);
    }
 
    DepthFirstReverseGraphTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
template<class Graph>
class BreadthFirstForwardGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
public:
    BreadthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex,
                                      unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
        this->start(startVertex);
    }
 
    BreadthFirstForwardGraphTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge,
                                      unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph, significantEvents) {
        this->start(startEdge);
    }
 
    BreadthFirstForwardGraphTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
template<class Graph>
class BreadthFirstReverseGraphTraversal: public GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
public:
    BreadthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex,
                                      unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
        this->start(startVertex);
    }
 
    BreadthFirstReverseGraphTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge,
                                      unsigned significantEvents=ALL_EVENTS)
        : GraphTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph, significantEvents) {
        this->start(startEdge);
    }
 
    BreadthFirstReverseGraphTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
//
//                                      Subclasses {Order}{Direction}VertexTraversal
//
 
template<class Graph, class Order, class Direction>
class GraphVertexTraversal: public GraphTraversal<Graph, Order, Direction> {
protected:
    explicit GraphVertexTraversal(Graph &graph): GraphTraversal<Graph, Order, Direction>(graph, ENTER_VERTEX) {}
 
public:
    typename GraphTraits<Graph>::VertexIterator::Reference operator*() {
        return *this->vertex();
    }
 
    typename GraphTraits<Graph>::VertexIterator::Pointer operator->() {
        return &*this->vertex();
    }
 
    typename GraphTraits<Graph>::VertexIterator::Reference next() {
        typename GraphTraits<Graph>::VertexIterator::Reference retval = this->vertex();
        this->advance();
        return retval;
    }
};
 
template<class Graph>
class DepthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
public:
    DepthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    DepthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    DepthFirstForwardVertexTraversal(Graph &graph)
        : GraphVertexTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(graph.vertices().begin());
    }
 
    DepthFirstForwardVertexTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
template<class Graph>
class DepthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
public:
    DepthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    DepthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    DepthFirstReverseVertexTraversal(Graph &graph)
        : GraphVertexTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(graph.vertices().begin());
    }
 
    DepthFirstReverseVertexTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
template<class Graph>
class BreadthFirstForwardVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
public:
    BreadthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    BreadthFirstForwardVertexTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    BreadthFirstForwardVertexTraversal(Graph &graph)
        : GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(graph.vertices().begin());
    }
 
    BreadthFirstForwardVertexTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
template<class Graph>
class BreadthFirstReverseVertexTraversal: public GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
public:
    BreadthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    BreadthFirstReverseVertexTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    BreadthFirstReverseVertexTraversal(Graph &graph)
        : GraphVertexTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(graph.vertices().begin());
    }
 
    BreadthFirstReverseVertexTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
//
//                                      Subclasses {Order}{Direction}EdgeTraversal
//
 
template<class Graph, class Order, class Direction>
class GraphEdgeTraversal: public GraphTraversal<Graph, Order, Direction> {
protected:
    explicit GraphEdgeTraversal(Graph &graph): GraphTraversal<Graph, Order, Direction>(graph, ENTER_EDGE) {}
 
public:
    typename GraphTraits<Graph>::EdgeIterator::Reference operator*() {
        return *this->edge();
    }
 
    typename GraphTraits<Graph>::EdgeIterator::Pointer operator->() {
        return &*this->edge();
    }
 
    typename GraphTraits<Graph>::EdgeIterator::Reference next() {
        typename GraphTraits<Graph>::EdgeIterator::Reference retval = this->vertex();
        this->advance();
        return retval;
    }
};
 
template<class Graph>
class DepthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag> {
public:
    DepthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    DepthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    DepthFirstForwardEdgeTraversal(Graph &graph)
        : GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(graph.edges().begin());
    }
 
    DepthFirstForwardEdgeTraversal& operator++() {
        this->advance();
        return *this;
    }
};
    
template<class Graph>
class DepthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag> {
public:
    DepthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    DepthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    DepthFirstReverseEdgeTraversal(Graph &graph)
        : GraphEdgeTraversal<Graph, DepthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(graph.edges().begin());
    }
 
    DepthFirstReverseEdgeTraversal& operator++() {
        this->advance();
        return *this;
    }
};
        
template<class Graph>
class BreadthFirstForwardEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag> {
public:
    BreadthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    BreadthFirstForwardEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    BreadthFirstForwardEdgeTraversal(Graph &graph)
        : GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ForwardTraversalTag>(graph) {
        this->start(graph.edges().begin());
    }
    
    BreadthFirstForwardEdgeTraversal& operator++() {
        this->advance();
        return *this;
    }
};
    
template<class Graph>
class BreadthFirstReverseEdgeTraversal: public GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag> {
public:
    BreadthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::VertexIterator startVertex)
        : GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startVertex);
    }
 
    BreadthFirstReverseEdgeTraversal(Graph &graph, typename GraphTraits<Graph>::EdgeIterator startEdge)
        : GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(startEdge);
    }
 
    BreadthFirstReverseEdgeTraversal(Graph &graph)
        : GraphEdgeTraversal<Graph, BreadthFirstTraversalTag, ReverseTraversalTag>(graph) {
        this->start(graph.edges().begin());
    }
    
    BreadthFirstReverseEdgeTraversal& operator++() {
        this->advance();
        return *this;
    }
};
 
 
 
//
//                                      Traversal visitation functions
//
 
template<class Traversal, class Functor>
void graphTraverseAllVertices(Traversal t, Functor &f) {
    std::vector<bool> visited(t.graph().nVertices(), false);
    size_t rootId = 0;
    while (true) {
        for (typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
            typename Traversal::VertexIterator vertex = t.vertex();
            if (visited[vertex->id()]) {
                if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
                    t.skipChildren();
            } else {
                visited[vertex->id()] = true;
                f(vertex, root);
            }
        }
        while (rootId < visited.size() && visited[rootId])
            ++rootId;
        if (rootId >= visited.size())
            return;
        t.start(t.graph().findVertex(rootId));
    }
}
template<class Traversal, class Functor>
void graphTraverseAllVertices(Traversal t, const Functor &f) { // identical, other than const functor
    std::vector<bool> visited(t.graph().nVertices(), false);
    size_t rootId = 0;
    while (true) {
        for (typename Traversal::VertexIterator root=t.vertex(); t; ++t) {
            typename Traversal::VertexIterator vertex = t.vertex();
            if (visited[vertex->id()]) {
                if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
                    t.skipChildren();
            } else {
                visited[vertex->id()] = true;
                f(vertex, root);
            }
        }
        while (rootId < visited.size() && visited[rootId])
            ++rootId;
        if (rootId >= visited.size())
            return;
        t.start(t.graph().findVertex(rootId));
    }
}
template<class Traversal, class Functor>
void graphTraverseAllEdges(Traversal t, Functor &f) {
    std::vector<bool> visited(t.graph().nEdges(), false);
    size_t rootId = 0;
    while (true) {
        for (typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
            typename Traversal::EdgeIterator edge = t.edge();
            if (visited[edge->id()]) {
                if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
                    t.skipChildren();
            } else {
                visited[edge->id()] = true;
                f(edge, root);
            }
        }
        while (rootId < visited.size() && visited[rootId])
            ++rootId;
        if (rootId >= visited.size())
            return;
        t.start(t.graph().findEdge(rootId));
    }
}
template<class Traversal, class Functor>
void graphTraverseAllEdges(Traversal t, const Functor &f) {   // identical, other than const functor
    std::vector<bool> visited(t.graph().nEdges(), false);
    size_t rootId = 0;
    while (true) {
        for (typename Traversal::EdgeIterator root=t.edge(); t; ++t) {
            typename Traversal::EdgeIterator edge = t.edge();
            if (visited[edge->id()]) {
                if (t.event()==ENTER_VERTEX || t.event()==ENTER_EDGE)
                    t.skipChildren();
            } else {
                visited[edge->id()] = true;
                f(edge, root);
            }
        }
        while (rootId < visited.size() && visited[rootId])
            ++rootId;
        if (rootId >= visited.size())
            return;
        t.start(t.graph().findEdge(rootId));
    }
}
template<class Graph>
class IdAccumulator {
public:
    std::vector<size_t> ids;
 
    explicit IdAccumulator(size_t n) { ids.reserve(n); }
 
    void operator()(typename GraphTraits<Graph>::VertexIterator v) {
        ids.push_back(v->id());
    }
    void operator()(typename GraphTraits<Graph>::VertexIterator v, typename GraphTraits<Graph>::VertexIterator /*root*/) {
        ids.push_back(v->id());
    }
    void operator()(typename GraphTraits<Graph>::EdgeIterator e) {
        ids.push_back(e->id());
    }
    void operator()(typename GraphTraits<Graph>::EdgeIterator e, typename GraphTraits<Graph>::EdgeIterator /*root*/) {
        ids.push_back(e->id());
    }
};
 
template<class Traversal>
std::vector<size_t> graphReachableVertices(Traversal t) {
    IdAccumulator<typename Traversal::Graph> accum(t.graph().nVertices());
    t.mapVertices(accum);
    return accum.ids;
}
 
template<class Traversal>
std::vector<size_t> graphReachableEdges(Traversal t) {
    IdAccumulator<typename Traversal::Graph> accum(t.graph().nEdges());
    t.mapEdges(accum);
    return accum.ids;
}
 
template<class Traversal, class Graph>
std::vector<size_t> graphAllVertices(Graph &graph) {
    IdAccumulator<Graph> accum(graph.nVertices());
    graphTraverseAllVertices(Traversal(graph, graph.vertices().begin()), accum);
    return accum.ids;
}
 
template<class Traversal, class Graph>
std::vector<size_t> graphAllEdges(Graph &graph) {
    IdAccumulator<Graph> accum(graph.nEdges());
    graphTraverseAllEdges(Traversal(graph, graph.edges().begin()), accum);
    return accum.ids;
}
 
} // namespace
} // namespace
} // namespace
 
#endif