Reference Guide: Breadth-First and Depth-First Graph Iterators

In accordance to Graph documentation, API allows following iteration methods:

BreadthFirstSearchGraphIterator: visitation is performed by going deeper and deeper in depth compared to source vertex
DepthFirstSearchGraphIterator: visitation is performed by exploring source vertex as far as possible then backtracking.

Whenever a node is visited, a visit method of UnweightedGraphVertexVisitor or WeightedGraphVertexVisitor instance (depending on type of graph used), already provided to function as argument, is executed. If it returns true iteration continues, otherwise it stops. Since UnweightedGraphVertexVisitor or WeightedGraphVertexVisitor is an interface, end users will need to provide an implementation for it.

BreadthFirstSearchGraphIterator

Function that implements breadth-first-search traversal for Unweighted Graph from start vertex

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
inline void BreadthFirstSearchGraphIterator(UnweightedGraphVertex<T, compare, hash>* const& vertex, UnweightedGraphVertexVisitor<T, compare, hash>* const& visitor)

Function that implements breadth-first-search traversal for Weighted Graph from start vertex

Signature

template <typename T, typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
inline void BreadthFirstSearchGraphIterator(WeightedGraphVertex<T,W,compare,hash>* vertex, WeightedGraphVertexVisitor<T,W,compare,hash>* visitor)

DepthFirstSearchGraphIterator

Function that implements depth-first-search traversal for Unweighted Graph from start vertex

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
inline void DepthFirstSearchGraphIterator(UnweightedGraphVertex<T, compare, hash>* const& vertex, UnweightedGraphVertexVisitor<T, compare, hash>* const& visitor)

Function that implements depth-first-search traversal for Weighted Graph from start vertex

Signature

template <typename T, typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
inline void DepthFirstSearchGraphIterator(WeightedGraphVertex<T,W,compare,hash>* vertex, WeightedGraphVertexVisitor<T,W,compare,hash>* visitor)

UnweightedGraphVertexVisitor

Abstract class implementing blueprints for vertex visitation during Unweighted Graph traversal

Signature

template <typename T, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class UnweightedGraphVertexVisitor

Methods

Method	Signature	Description
~UnweightedGraphVertexVisitor	virtual ~UnweightedGraphVertexVisitor ()	Deallocates all data from heap memory
visit	virtual bool visit (UnweightedGraphVertex<T, compare, hash>* const& element, UnweightedGraphVertex<T, compare, hash>* const& parent) = 0	Visits a vertex during iteration. If false is returned, iteration stops!
isVisited	virtual bool isVisited (UnweightedGraphVertex<T, compare, hash>* const& element) = 0	Checks if a vertex has already been visited

WeightedGraphVertexVisitor

Abstract class implementing blueprints for vertex visitation during Weighted Graph traversal

Signature

template <typename T, typename W, int (*compare)(const T&, const T&) = comparator<T>, std::size_t (*hash)(const T&) = hash<T>>
class WeightedGraphVertexVisitor

Methods

Method	Signature	Description
~WeightedGraphVertexVisitor	virtual ~WeightedGraphVertexVisitor () {	Deallocates all data from heap memory
visit	virtual bool visit (WeightedGraphVertex<T, W, compare, hash>* const& element, WeightedGraphVertex<T, W, compare, hash>* const& parent) = 0	Visits a vertex during iteration. If false is returned, iteration stops!
isVisited	virtual bool isVisited (WeightedGraphVertex<T, W, compare, hash>* const& element) = 0	Checks if a vertex has already been visited