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

Description

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

Breadth-first, forward traversal for vertices.

This traversal follows edges in their natural order from source to target visiting sibling vertices before children. The advancing methods and operators (advance, next, etc.) stop only at vertex enter events (ENTER_VERTEX). Dereferencing the traversal object returns a graph vertex node.

Definition at line 1045 of file GraphTraversal.h.

#include <Sawyer/GraphTraversal.h>

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

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

Public Member Functions
	BreadthFirstForwardVertexTraversal (Graph &graph, typename GraphTraits< Graph >::VertexIterator startVertex)
	Start traversal at specified vertex.
	BreadthFirstForwardVertexTraversal (Graph &graph, typename GraphTraits< Graph >::EdgeIterator startEdge)
	Start traversal at specified edge.
	BreadthFirstForwardVertexTraversal (Graph &graph)
	Start traversal at vertex number zero.
BreadthFirstForwardVertexTraversal &	operator++ ()
	Advance traversal to next event.
Public Member Functions inherited from Sawyer::Container::Algorithm::GraphVertexTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >
GraphTraits< Graph >::VertexIterator::Reference	operator* ()
	Return reference to current vertex.
GraphTraits< Graph >::VertexIterator::Pointer	operator-> ()
	Return pointer to current vertex.
GraphTraits< Graph >::VertexIterator::Reference	next ()
	Return reference to current vertex and advance.
Public Member Functions inherited from Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >
	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.

Additional Inherited Members
Public Types inherited from Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >
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.
Protected Types inherited from Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >
typedef std::list< Work >	WorkList
Protected Member Functions inherited from Sawyer::Container::Algorithm::GraphVertexTraversal< Graph, BreadthFirstTraversalTag, ForwardTraversalTag >
	GraphVertexTraversal (Graph &graph)
Protected Member Functions inherited from Sawyer::Container::Algorithm::GraphTraversal< G, Order, Direction >
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< G, Order, Direction >
WorkList	workList_

Constructor & Destructor Documentation

BreadthFirstForwardVertexTraversal() [1/3]

template<class Graph >

Sawyer::Container::Algorithm::BreadthFirstForwardVertexTraversal< Graph >::BreadthFirstForwardVertexTraversal ( Graph &  graph, typename GraphTraits< Graph >::VertexIterator  startVertex  )

inline

Start traversal at specified vertex.

Definition at line 1048 of file GraphTraversal.h.

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

BreadthFirstForwardVertexTraversal() [2/3]

template<class Graph >

Sawyer::Container::Algorithm::BreadthFirstForwardVertexTraversal< Graph >::BreadthFirstForwardVertexTraversal ( Graph &  graph, typename GraphTraits< Graph >::EdgeIterator  startEdge  )

inline

Start traversal at specified edge.

Definition at line 1054 of file GraphTraversal.h.

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

BreadthFirstForwardVertexTraversal() [3/3]

template<class Graph >

Sawyer::Container::Algorithm::BreadthFirstForwardVertexTraversal< Graph >::BreadthFirstForwardVertexTraversal ( Graph &  graph )

inline

Start traversal at vertex number zero.

Definition at line 1060 of file GraphTraversal.h.

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

Member Function Documentation

operator++()

template<class Graph >

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

inline

Advance traversal to next event.

Definition at line 1066 of file GraphTraversal.h.

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

---

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

• GraphTraversal.h