Description

template<class G, class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>
class Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >

Base class for graph traversals.

Graph traversals are similar to single-pass, forward iterators in that a traversal object points to a particular node (vertex or edge) in a graph and supports dereference and increment operations. The dereference operator returns a reference to the node and the increment operator advances the traversal object so it points to the next node.

Traversals come in a variety of dimensions:

A graph traversal can traverse over a constant graph or a mutable graph. When traversing over constant graphs, the traversal object returns constant nodes (vertices or edges depending on the traversal kind). When traversing over a mutable graph it returns mutable nodes which are permitted to be modified during the traversal. The connectivity of a graph should not be modified while a traversal is in progress; i.e., traversals are unstable over insertion and erasure and the traversal will have undefined behavior.

A graph traversal can be depth-first or breadth-first. A depth-first traversal will follow edges immediately, quickly moving away from an initial vertex as far as possible before eventually backtracking to follow another edge. A breadth-first traversal will follow each of the edges from a single vertex before moving to another vertex.

A graph traversal can be in a forward or reverse direction. Forward traversals flow along edges in their natural direction from source to target. Reverse traversals are identical in every respect except they flow backward across edges.

Regardless of the type of traversal, it will normally visit each reachable vertex and edge exactly one time. However, the user may adjust the visited state of vertices and edges during the traversal, may change the current position of the traversal, and may cause the traversal to skip over parts of a graph.

The basic traversal advancing operation is the advance method upon which other advancing methods and operators are built. When a traversal is constructed the user (or a subclass) supplies a set of events that are of interest and the advance method will return control when any of those event points are reached. For instance, in a traversal that's being used to calculate which vertices are reachable from an initial vertex the user is probably only interested in ENTER_VERTEX events. When control is returned to the user the event, vertex, and edge methods can be used to get information about why and where the traversal stopped. The isAtEnd method will indicate whether the traversal is completed.

The following subclasses are implemented. Their names follow the pattern Order, Direction, Visiter. For instance "DepthFirstForwardEdgeTraversal" visits nodes in a "DepthFirst" order, follows edges in their natural forward direction (from source to target), stops only at ENTER_EDGE events, and returns edges when dereferenced. The orders are "DepthFirst" or "BreadthFirst". The directions are "Forward" and "Reverse". The visitors are "Edge" (only ENTER_EDGE events), "Vertex" (only ENTER_VERTEX events), and "Graph" (user specified events defaulting to all events).

Although graph traversals have functionality similar to iterators, there are some important differences to keep in mind:

Iterators are lightweight objects typically a few bytes that can be passed around efficiently by value, whereas a traversal's size is linear with respect to the size of the graph over which it traverses. The reason for this is that a traversal must keep track of which nodes have been visited.
Advancing an iterator takes constant time but advancing a traversal can take longer.
Iterators can be incremented and decremented to move the pointer forward and backward along a list of nodes, but traversals can only be advanced in one direction per traversal object.
Iterating requires two iterators–the current position and an end position; traversing requires only one traversal object which keeps track of its own state.
Iterators are copyable and comparable, traversals are not.
Graph iterators are insert and erase stable, traversals are not.
Iterators do not follow connectivity, but that's the main point for traversals.
Iterators are a core feature of a graph. Traversals are implemented in terms of iterators and don't provide any functionality that isn't already available to the user through the Graph API.

Examples

The examples in this section assume the following context:

#include <Sawyer/GraphTraversal.h>
 
using namespace Sawyer::Container;
using namespace Sawyer::Container::Algorithm;
 
typedef ... MyVertexType;   // User data for vertices; any default-constructable, copyable type
typedef ... MyEdgeType;     // Ditto for edges. These can be Sawyer::Nothing if desired.
 
typedef Graph<MyVertexType, MyEdgeType> MyGraph;
MyGraph graph;

This example shows how to build a reachability vector. The vector is indexed by vertex ID number and is true when the vertex is reachable from the starting vertex by following edges in their natural direction. The starting point is a vertex, but it could just as well have been an edge that points to the first vertex. One could also create edge reachability vectors by using an edge traversal instead. The next method returns the current vertex and advances the traversal to the next vertex.

MyGraph::VertexIterator startingVertex = ....;
std::vector<bool> reachable(graph.nVertices(), false);
 
DepthFirstForwardVertexTraversal<MyGraph> traversal(graph, startingVertex);
while (traversal.hasNext())
    reachable[traversal.next().id()] = true;

A more typical C++ iterator paradigm can be used instead. However, traversals are not comparable and there is no "end" traversal like there is for iterators. Evaluating a traversal in Boolean context returns true unless the traversal is at the end. Here's the same loop again:

typedef DepthFirstForwardVertexTraversal<MyGraph> Traversal;
for (Traversal traversal(graph, start); traversal; ++traversal)
    reachable[traversal->id()] = true;

The traversals whose names end with "GraphTraversal", such as DepthFirstForwardGraphTraversal, can be used if one needs to gain control more frequently than just entering vertices. For instance, one can count the depth of a vertex in a depth-first traversal by getting control on both ENTER_VERTEX and LEAVE_VERTEX events, like this:

typedef DepthFirstForwardGraphTraversal<MyGraph> Traversal;
size_t depth = 0;
std::vector<size_t> depthOfVertex(graph.nVertices(), 0);
 
for (Traversal t(graph, start, ENTER_VERTEX|LEAVE_VERTEX); t; ++t) {
    if (t.event()==ENTER_VERTEX) {
        ++depth;
    } else {
        depthOfVertex[t.vertex()->id()] = --depth;
    }
}

All traversals support skipping over parts of the graph by using the skipChildren method. If this method is called during an ENTER_VERTEX event then no edges of that vertex are visited, and if called during an ENTER_EDGE event, then no neighbor vertex is discovered at the far end of the edge (although it might be discovered by other edges). For instance, the following code computes a vertex reachability vector for a control flow graph but does not follow edges that are marked as function calls. The value method returns a reference to a MyEdgeType (see typedef example above) which we assume has a isFunctionCall method.

MyGraph::VertexIterator startingVertex = ...;
std::vector<bool> reachable(graph.nVertices(), false);
typedef DepthFirstForwardGraphTraversal<MyGraph> Traversal;
 
for (Traversal t(graph, startingVertex, ENTER_EVENTS); t; ++t) {
    if (t.event() == ENTER_VERTEX) {
        reachable[t.vertex()->id()] = true;
    } else if (t.edge()->value().isFunctionCall()) {
        ASSERT_require(t.event() == ENTER_EDGE);
        t.skipChildren();
    }
}

Traversals are suitable for using in generic functions as well. For instance, the next example is a generic function that prints a graph using a depth-first traversal. It operates on const or non-const graphs for demonstration purposes; in real life one might advertise that the function doesn't modify the graph by having an explicit const qualifier. The GraphTraits is used to obtain the appropriate const/non-const vertex iterator type.

template<class Graph>
void printGraph(std::ostream &out, Graph &graph,
                typename GraphTraits<Graph>::VertexIterator start) {
    for (DepthFirstForwardGraphTraversal t(graph, start, ENTER_EVENTS); t; ++t) {
        if (t.event() == ENTER_VERTEX) {
            out <<"vertex " <<t->vertex()->id() <<"\t= " <<t->vertex()->value() <<"\n";
        } else {
            ASSERT_require(t.event() == ENTER_EDGE);
            out <<"edge   " <<t->edge()->id() <<"\t= " <<t->edge()->value() <<"\n";
        }
    }
}

The following example shows one way to construct a new graph from an existing graph. Although graphs can be copy constructed from related graphs as long as the destination graph's vertices and edges can be copy constructed from the source graph's vertices and edges, this is not always the situation encountered. One often needs to construct a new graph whose edges and vertices cannot be copy constructed, where certain edges or vertices should not be copied, or where certain extra vertices or edges need to be inserted. A combination of traversal and vertex lookup tables can be convenient in this situation. For instance, consider a program control flow graph (CFG) where each vertex represents a sequence of machine instructions and each edge is a possible transfer of control. Assume that the source graph has three edge types: INTERFUNC is an inter-function edge such as a function call, INTRAFUNC are function-internal edges, and ADJUST is a special kind of INTRAFUNC edge. We want to create a new graph that contains only vertices that belong to a single function, and any ADJUST edge in the source should result in an edge-vertex-edge in the destination where the vertex is marked as ADJUST. The destination graph edges carry no information and thus cannot be copy-constructed from the source graph's edges.

typedef Graph<CfgVertex, CfgEdge> Cfg;
typedef Graph<DfVertex> DfCfg;
typedef DepthFirstGraphTraversal<Cfg> Traversal;
 
Cfg cfg = ...;
Cfg::VertexIterator startVertex = ...;
 
DfCfg dfCfg;
Map<size_t, DfCfg::VertexIterator> vmap;
 
for (Traversal t(cfg, startVertex, ENTER_EVENTS|LEAVE_EDGE); t; ++t) {
    if (t.event() == ENTER_VERTEX) {
        // Insert each vertex before we visit any edge going into that vertex
        DfCfg::VertexIterator v = dfCfg.insertVertex(NORMAL);
        vmap.insert(t.vertex()->id(), v);
    } else if (t.event() == ENTER_EDGE && t.edge()->value().type() == INTERFUNC) {
        // Don't traverse edges that cross function boundaries
        t.skipChildren();
    } else if (vmap.exists(t.edge()->source()->id()) && vmap.exists(t.edge()->target()->id())) {
        // Insert an edge provided we have both of its endpoints
        DfCfg::VertexIterator source = vmap[t.edge()->source()->id()];
        DfCfg::VertexIterator target = vmap[t.edge()->target()->id()];
        if (t.edge()->value().type() == ADJUST) {
            DfCfg::VertexIterator v = dfCfg.insertVertex(ADJUST);
            dfCfg.insertEdge(source, v);
            dfCfg.insertEdge(v,target);
        } else {
            dfCfg.insertEdge(source,target);
        }
    }
}

Definition at line 389 of file GraphTraversal.h.

#include <Sawyer/GraphTraversal.h>

Inheritance diagram for Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >:

[legend]

Collaboration diagram for Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >:

[legend]

Classes
struct	Work

Public Types
typedef G	Graph

typedef GraphTraits< Graph >::VertexIterator	VertexIterator
	Const or non-const vertex node iterator.

typedef GraphTraits< Graph >::EdgeIterator	EdgeIterator
	Const or non-const edge node iterator.

Public Member Functions
	GraphTraversal (Graph &graph, unsigned significantEvents)
	Construct traversal for graph.

void	start (VertexIterator startVertex)
	Restart the traversal at the specified vertex.

void	start (EdgeIterator startEdge)
	Restart the traversal at the specified edge.

Graph &	graph () const
	The graph over which iteration occurs.

TraversalEvent	event () const
	Current event on which traversal is stopped.

VertexIterator	vertex () const
	Vertex to which traversal is pointing.

EdgeIterator	edge () const
	Edge to which traversal is pointing.

bool	isAtEnd () const
	Returns true when traversal reaches the end.

bool	hasNext () const
	Returns true when a traversal can be advanced.

TraversalEvent	advance ()
	Advance traversal to next interesting event.

void	skipChildren ()
	Causes traversal to skip children.

void	allowRediscovery (VertexIterator vertex)
	Allow a vertex to be discovered again.

bool	isDiscovered (VertexIterator vertex) const
	True if the vertex has been discovered.

bool	isVisited (EdgeIterator edge) const
	True if the edge has been entered.

	operator unspecified_bool () const
	Type for Boolean context.


template<class Functor >
void	mapVertices (Functor &f)
	Call the specified functor for each vertex.

template<class Functor >
void	mapVertices (const Functor &f)
	Call the specified functor for each vertex.


template<class Functor >
void	mapEdges (Functor &f)
	Call the specified functor for each edge.

template<class Functor >
void	mapEdges (const Functor &f)
	Call the specified functor for each edge.

Protected Types
typedef std::list< Work >	WorkList

Protected Member Functions
Work &	current ()

const Work &	current () const

bool	isSignificant (TraversalEvent event) const

void	setDiscovered (VertexIterator vertex, bool isDiscovered=true)

void	setVisited (EdgeIterator edge, bool isVisited=true)

void	clear ()

Protected Attributes
WorkList	workList_

Member Typedef Documentation

◆ Graph

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

typedef G Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::Graph

Definition at line 391 of file GraphTraversal.h.

◆ VertexIterator

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

typedef GraphTraits<Graph>::VertexIterator Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::VertexIterator

Const or non-const vertex node iterator.

Definition at line 394 of file GraphTraversal.h.

◆ EdgeIterator

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

typedef GraphTraits<Graph>::EdgeIterator Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::EdgeIterator

Const or non-const edge node iterator.

Definition at line 397 of file GraphTraversal.h.

◆ WorkList

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

typedef std::list<Work> Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::WorkList

protected

Definition at line 417 of file GraphTraversal.h.

Constructor & Destructor Documentation

◆ GraphTraversal()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::GraphTraversal	(	Graph &	graph,
		unsigned	significantEvents
	)

inline

Construct traversal for graph.

This traversal will stop at the specified events. You must call the start method before using the traversal. This constructor is normally called from subclasses that call start as part of their constructors.

Definition at line 431 of file GraphTraversal.h.

Member Function Documentation

◆ current() [1/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

Work & Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::current ( )

inlineprotected

Definition at line 437 of file GraphTraversal.h.

◆ current() [2/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

const Work & Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::current ( ) const

inlineprotected

Definition at line 441 of file GraphTraversal.h.

◆ isSignificant()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

bool Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isSignificant ( TraversalEvent event ) const

inlineprotected

Definition at line 447 of file GraphTraversal.h.

◆ setDiscovered()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::setDiscovered	(	VertexIterator	vertex,
		bool	isDiscovered = `true`
	)

inlineprotected

Definition at line 453 of file GraphTraversal.h.

◆ setVisited()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::setVisited	(	EdgeIterator	edge,
		bool	isVisited = `true`
	)

inlineprotected

Definition at line 459 of file GraphTraversal.h.

◆ clear()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::clear ( )

inlineprotected

Definition at line 465 of file GraphTraversal.h.

◆ start() [1/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::start ( VertexIterator startVertex )

inline

Restart the traversal at the specified vertex.

Definition at line 474 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::event(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

◆ start() [2/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::start ( EdgeIterator startEdge )

inline

Restart the traversal at the specified edge.

Definition at line 486 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::ENTER_EDGE, Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::event(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

◆ graph()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

Graph & Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::graph ( ) const

inline

The graph over which iteration occurs.

The connectivity of this graph should not be modified while the traversal is in progress.

Definition at line 502 of file GraphTraversal.h.

◆ event()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

TraversalEvent Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::event ( ) const

inline

Current event on which traversal is stopped.

See TraversalEvent for a complete description of possible events and the vertex and edge values at those events.

Definition at line 509 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::DISCOVER_VERTEX, and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

Referenced by Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::edge(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::skipChildren(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::start(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::start(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::vertex().

◆ vertex()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

VertexIterator Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::vertex ( ) const

inline

Vertex to which traversal is pointing.

See TraversalEvent for details about which vertex is returned for various events.

Definition at line 518 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::DISCOVER_VERTEX, Sawyer::Container::Algorithm::ENTER_EDGE, Sawyer::Container::Algorithm::ENTER_VERTEX, Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::event(), Sawyer::Container::Algorithm::LEAVE_EDGE, Sawyer::Container::Algorithm::LEAVE_VERTEX, and Sawyer::Container::Algorithm::NO_EVENT.

Referenced by Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::allowRediscovery(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isDiscovered(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapVertices(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapVertices().

◆ edge()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

EdgeIterator Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::edge ( ) const

inline

Edge to which traversal is pointing.

See TraversalEvent for details about which edge is returned for various events.

Definition at line 539 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::DISCOVER_VERTEX, Sawyer::Container::Algorithm::ENTER_EDGE, Sawyer::Container::Algorithm::ENTER_VERTEX, Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::event(), Sawyer::Container::Algorithm::LEAVE_EDGE, Sawyer::Container::Algorithm::LEAVE_VERTEX, and Sawyer::Container::Algorithm::NO_EVENT.

Referenced by Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isVisited(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapEdges(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapEdges().

◆ isAtEnd()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

bool Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd ( ) const

inline

Returns true when traversal reaches the end.

A traversal for which isAtEnd returns true does not point to a meaningful vertex or edge and should not be advanced further. The isAtEnd return value is the inverse of what hasNext returns.

Definition at line 564 of file GraphTraversal.h.

◆ hasNext()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

bool Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::hasNext ( ) const

inline

Returns true when a traversal can be advanced.

The hasNext return value is the inverse of what isAtEnd returns. This predicate is often used with the next method in subclasses that have one:

Traversal t(graph, start);
while (t.hasNext())
    f(t.next());

An iterator evaluated in a Boolean context will return a value equivalent to what hasNext returns:

for (Traversal t(graph, start); t; ++t) ...

Definition at line 584 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

◆ advance()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

TraversalEvent Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance ( )

inline

Advance traversal to next interesting event.

The traversal advances until it reaches a state that is deemed to be interesting to the user according to the list of event types supplied when the traversal was created. It then returns the event that was reached. Most subclasses define the list of interesting events themselves. For instance, an edge traversal will probably only be interested in ENTER_EDGE events.

Returns a valid event type on success, or NO_EVENT when the traversal reaches the end state.

Definition at line 596 of file GraphTraversal.h.

◆ skipChildren()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::skipChildren ( )

inline

Causes traversal to skip children.

If the current event is ENTER_VERTEX then no edges will be followed out of the current vertex. If the current event is ENTER_EDGE then no vertex will be discovered from the current edge (but it might still be discovered by some other edge). This method cannot be called in any other state.

Definition at line 683 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::DISCOVER_VERTEX, Sawyer::Container::Algorithm::ENTER_EDGE, Sawyer::Container::Algorithm::ENTER_VERTEX, Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::event(), Sawyer::Container::Algorithm::LEAVE_EDGE, Sawyer::Container::Algorithm::LEAVE_VERTEX, Sawyer::Container::Algorithm::NO_EVENT, and Sawyer::Container::Algorithm::traversalEventName().

◆ allowRediscovery()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::allowRediscovery ( VertexIterator vertex )

inline

Allow a vertex to be discovered again.

Under normal operation, once a vertex is discovered all of its incoming or outgoing edges (depending on the traversal direction) are inserted into the worklist. This discovery normally happens once per vertex. However, the vertex can be forgotten so that if it's ever discovered by some other edge its incoming or outgoing edges will be inserted into the worklist again. Calling allowRediscovery each time a traversal leaves a vertex during a depth-first traversal will result in a traversal that finds all non-cyclic paths, possibly visiting some vertices more than once.

Definition at line 710 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::vertex().

◆ isDiscovered()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

bool Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isDiscovered ( VertexIterator vertex ) const

inline

True if the vertex has been discovered.

Returns true if the specified vertex has ever existed on the work list. Vertices are normally discovered between the ENTER_EDGE and LEAVE_EDGE events for the edge that flows into the vertex, and are only discovered once regardless of how many edges flow into them.

Definition at line 724 of file GraphTraversal.h.

References Sawyer::Container::BitVector::get(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::vertex().

Referenced by Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance().

◆ isVisited()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

bool Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isVisited ( EdgeIterator edge ) const

inline

True if the edge has been entered.

Returns true if the traversal has ever returned a ENTER_EDGE event for the specified edge.

Definition at line 733 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::edge(), and Sawyer::Container::BitVector::get().

Referenced by Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance().

◆ mapVertices() [1/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

template<class Functor >

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapVertices ( Functor & f )

inline

Call the specified functor for each vertex.

Iterates over the traversal invoking the functor on the current vertex at each step.

Definition at line 745 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::vertex().

◆ mapVertices() [2/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

template<class Functor >

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapVertices ( const Functor & f )

inline

Call the specified functor for each vertex.

Iterates over the traversal invoking the functor on the current vertex at each step.

Definition at line 752 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::vertex().

◆ mapEdges() [1/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

template<class Functor >

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapEdges ( Functor & f )

inline

Call the specified functor for each edge.

Iterates over the invoking the functor on the current edge at each step.

Definition at line 766 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::edge(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

◆ mapEdges() [2/2]

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

template<class Functor >

void Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::mapEdges ( const Functor & f )

inline

Call the specified functor for each edge.

Iterates over the invoking the functor on the current edge at each step.

Definition at line 773 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::advance(), Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::edge(), and Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

◆ operator unspecified_bool()

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::operator unspecified_bool ( ) const

inline

Type for Boolean context.

Implicit conversion to a type that can be used in a boolean context such as an if or while statement. For instance:

typedef DepthFirstForwardVertexTraversal<MyGraph> Traversal;
for (Traversal t(graph, startVertex); t; ++t)
    reachable[t->id()] = true;

Definition at line 797 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::isAtEnd().

Member Data Documentation

◆ workList_

template<class G , class Order = DepthFirstTraversalTag, class Direction = ForwardTraversalTag>

WorkList Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::workList_

protected

Definition at line 418 of file GraphTraversal.h.

The documentation for this class was generated from the following file:

GraphTraversal.h

Description

Examples

Classes

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Member Typedef Documentation

◆ Graph

◆ VertexIterator

◆ EdgeIterator

◆ WorkList

Constructor & Destructor Documentation

◆ GraphTraversal()

Member Function Documentation

◆ current() [1/2]

◆ current() [2/2]

◆ isSignificant()

◆ setDiscovered()

◆ setVisited()

◆ clear()

◆ start() [1/2]

◆ start() [2/2]

◆ graph()

◆ event()

◆ vertex()

◆ edge()

◆ isAtEnd()

◆ hasNext()

◆ advance()

◆ skipChildren()

◆ allowRediscovery()

◆ isDiscovered()

◆ isVisited()

◆ mapVertices() [1/2]

◆ mapVertices() [2/2]

◆ mapEdges() [1/2]

◆ mapEdges() [2/2]

◆ operator unspecified_bool()

Member Data Documentation

◆ workList_