Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph > Class Template Reference

Description

template<class Graph>
class Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph >

Depth-first, reverse traversal for all event types.

This traversal follows edges in their reverse order from target to source visiting children before siblings. The advancing methods and operators stop at the next event that matches a list of significant event types supplied as a constructor argument.

See also

GraphTraversal

Definition at line 854 of file GraphTraversal.h.

#include <Sawyer/GraphTraversal.h>

Inheritance diagram for Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph >:

Collaboration diagram for Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph >:

Public Member Functions
	DepthFirstReverseGraphTraversal (Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex, unsigned significantEvents=ALL_EVENTS)
	Start traversal at specified vertex.
	DepthFirstReverseGraphTraversal (Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge, unsigned significantEvents=ALL_EVENTS)
	Start traversal at specified edge.
DepthFirstReverseGraphTraversal &	operator++ ()
	Advance traversal to next event.
Public Member Functions inherited from Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >
	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.
void	mapVertices (Functor &f)
	Call the specified functor for each vertex.
void	mapVertices (const Functor &f)
	Call the specified functor for each vertex.
void	mapEdges (Functor &f)
	Call the specified functor for each edge.
void	mapEdges (const Functor &f)
	Call the specified functor for each edge.

Additional Inherited Members
Public Types inherited from Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >
typedef Graph	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.
Protected Types inherited from Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >
typedef std::list< Work >	WorkList
Protected Member Functions inherited from Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >
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 inherited from Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >
WorkList	workList_

Constructor & Destructor Documentation

DepthFirstReverseGraphTraversal() [1/2]

template<class Graph >

Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph >::DepthFirstReverseGraphTraversal ( Graph &  graph, typename GraphTraits< Graph >::VertexIterator  startVertex, unsigned  significantEvents = ALL_EVENTS  )

inline

Start traversal at specified vertex.

Definition at line 857 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >::start().

DepthFirstReverseGraphTraversal() [2/2]

template<class Graph >

Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph >::DepthFirstReverseGraphTraversal ( Graph &  graph, typename GraphTraits< Graph >::EdgeIterator  startEdge, unsigned  significantEvents = ALL_EVENTS  )

inline

Start traversal at specified edge.

Definition at line 864 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >::start().

Member Function Documentation

operator++()

template<class Graph >

DepthFirstReverseGraphTraversal & Sawyer::Container::Algorithm::DepthFirstReverseGraphTraversal< Graph >::operator++ ( )

inline

Advance traversal to next event.

Definition at line 871 of file GraphTraversal.h.

References Sawyer::Container::Algorithm::GraphTraversal< Graph, DepthFirstTraversalTag, ReverseTraversalTag >::advance().

---

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

• GraphTraversal.h