ROSE
0.11.5.0

Base class for graph traversals.
Graph traversals are similar to singlepass, 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:
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:
The examples in this section assume the following context:
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.
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:
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 depthfirst traversal by getting control on both ENTER_VERTEX and LEAVE_VERTEX events, like this:
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.
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 depthfirst traversal. It operates on const or nonconst 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/nonconst vertex iterator type.
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 interfunction edge such as a function call, INTRAFUNC are functioninternal 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 edgevertexedge in the destination where the vertex is marked as ADJUST. The destination graph edges carry no information and thus cannot be copyconstructed from the source graph's edges.
Definition at line 389 of file GraphTraversal.h.
#include <GraphTraversal.h>
Classes  
struct  Work 
Public Types  
typedef G  Graph 
typedef GraphTraits< Graph >::VertexIterator  VertexIterator 
Const or nonconst vertex node iterator. More...  
typedef GraphTraits< Graph >::EdgeIterator  EdgeIterator 
Const or nonconst edge node iterator. More...  
Public Member Functions  
GraphTraversal (Graph &graph, unsigned significantEvents)  
Construct traversal for graph. More...  
void  start (VertexIterator startVertex) 
Restart the traversal at the specified vertex. More...  
void  start (EdgeIterator startEdge) 
Restart the traversal at the specified edge. More...  
Graph &  graph () const 
The graph over which iteration occurs. More...  
TraversalEvent  event () const 
Current event on which traversal is stopped. More...  
VertexIterator  vertex () const 
Vertex to which traversal is pointing. More...  
EdgeIterator  edge () const 
Edge to which traversal is pointing. More...  
bool  isAtEnd () const 
Returns true when traversal reaches the end. More...  
bool  hasNext () const 
Returns true when a traversal can be advanced. More...  
TraversalEvent  advance () 
Advance traversal to next interesting event. More...  
void  skipChildren () 
Causes traversal to skip children. More...  
void  allowRediscovery (VertexIterator vertex) 
Allow a vertex to be discovered again. More...  
bool  isDiscovered (VertexIterator vertex) const 
True if the vertex has been discovered. More...  
bool  isVisited (EdgeIterator edge) const 
True if the edge has been entered. More...  
operator unspecified_bool () const  
Type for Boolean context. More...  
template<class Functor >  
void  mapVertices (Functor &f) 
Call the specified functor for each vertex. More...  
template<class Functor >  
void  mapVertices (const Functor &f) 
Call the specified functor for each vertex. More...  
template<class Functor >  
void  mapEdges (Functor &f) 
Call the specified functor for each edge. More...  
template<class Functor >  
void  mapEdges (const Functor &f) 
Call the specified functor for each edge. More...  
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_ 
typedef GraphTraits<Graph>::VertexIterator Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::VertexIterator 
Const or nonconst vertex node iterator.
Definition at line 394 of file GraphTraversal.h.
typedef GraphTraits<Graph>::EdgeIterator Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >::EdgeIterator 
Const or nonconst edge node iterator.
Definition at line 397 of file GraphTraversal.h.

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.

inline 
Restart the traversal at the specified vertex.
Definition at line 474 of file GraphTraversal.h.

inline 
Restart the traversal at the specified edge.
Definition at line 486 of file GraphTraversal.h.

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.

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::advance(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::edge(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::skipChildren(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::start(), and Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::vertex().

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::allowRediscovery(), and Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::mapVertices().

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::mapEdges().

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::event(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::hasNext(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::mapEdges(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::mapVertices(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::operator unspecified_bool(), and Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::start().

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:
An iterator evaluated in a Boolean context will return a value equivalent to what hasNext returns:
Definition at line 584 of file GraphTraversal.h.

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::mapEdges(), Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::mapVertices(), and Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::start().

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.

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 depthfirst traversal will result in a traversal that finds all noncyclic paths, possibly visiting some vertices more than once.
Definition at line 710 of file GraphTraversal.h.

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::advance().

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.
Referenced by Sawyer::Container::Algorithm::GraphTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >::advance().

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.

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.

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.

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.

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:
Definition at line 797 of file GraphTraversal.h.