rz::graph::Graph< V, E, G > Class Template Reference

A template class for representing Graph objects. More...

#include <Graph.hpp>

Collaboration diagram for rz::graph::Graph< V, E, G >:

Public Member Functions
	Graph (std::size_t prealloc=0) noexcept
	Default constructor. More...
Vertex< V, E > &	operator[] (std::size_t index)
	Get's a reference to the Vertex with id == index. More...
void	breadthFirstTraversal (std::size_t origin)
	Performs a breadth first traversal of the Graph. More...
void	depthFirstTraversal (std::size_t origin)
	Performs a depth first traversal of the Graph. More...
void	branchTraversal (std::size_t origin)
	Performs a branch-by-branch traversal of the Graph. More...
void	addEdge (std::size_t source, std::size_t target, E edgeData=E{})
	Constructs and adds a new Edge to the Graph. More...
void	reset (bool resetFuncs=true)
	Resets the state of all Edge and Vertex objects belonging to the Graph to State::WHITE. More...
std::size_t	order ()
	Returns the number of Vertex objects. More...
std::size_t	size ()
std::string	getDOT (std::function< std::string(const Vertex< V, E > &)> vertexAttributes=nullptr, std::function< std::string(const Edge< E > &)> edgeAttributes=nullptr)
	Converts the graph into a string representing a directed graph in the DOT language. More...

Public Attributes
G	data {}
	The data held by this Graph.
std::map< State, VertexFunc >	vertexFuncs
	The function to run on Vertex discovery. More...
std::map< State, EdgeFunc >	edgeFuncs

Detailed Description

template<class V, class E, class G>
class rz::graph::Graph< V, E, G >

A template class for representing Graph objects.

Template Parameters

V	The data type held by Vertex objects
E	The data type held by Edge objects
G	The data type held by Graph objects

Constructor & Destructor Documentation

template<class V , class E , class G >

rz::graph::Graph< V, E, G >::Graph ( std::size_t  prealloc = 0 )

inlinenoexcept

Default constructor.

Member Function Documentation

template<class V , class E, class G >

void rz::graph::Graph< V, E, G >::addEdge ( std::size_t  source, std::size_t  target, E  edgeData = E{}  )

inline

Constructs and adds a new Edge to the Graph.

If no Vertex objects exist with the IDs source or target, constructs and adds new Vertex objects for the missing IDs to the Graph.

Parameters

source	The ID of the source Vertex.
target	The ID of the target Vertex.
edgeData	The data held by the edge.

template<class V , class E , class G >

void rz::graph::Graph< V, E, G >::branchTraversal ( std::size_t  origin )

inline

Performs a branch-by-branch traversal of the Graph.

Starting at the Vertex with the ID origin, traverses the Graph in depth first order. However, instead of ignoring visited nodes, it retraces its steps from the origin to the last unvisited node. Runs the defined discovery function for every Vertex and Edge.

Sets the state of every Vertex and Edge that won't be visited again to State::GREY unless specified otherwise in their discovery functions.

Parameters

origin

The ID of the Vertex to start the traversal from.

template<class V , class E , class G >

void rz::graph::Graph< V, E, G >::breadthFirstTraversal ( std::size_t  origin )

inline

Performs a breadth first traversal of the Graph.

Starting at the Vertex with the ID origin, traverses the Graph in breadth first order. Runs the defined discovery function for every Vertex and Edge.

By default, sets the state of every touched Vertex and Edge with State::WHITE to State::GREY unless specified otherwise in their discovery functions.

Parameters

origin

The ID of the Vertex to start the traversal from.

template<class V , class E , class G >

void rz::graph::Graph< V, E, G >::depthFirstTraversal ( std::size_t  origin )

inline

Performs a depth first traversal of the Graph.

Starting at the Vertex with the ID origin, traverses the Graph in depth first order. Never repeats visited nodes, so works for cyclic graphs. Runs the defined discovery function for every Vertex and Edge.

By default, sets the state of every touched Vertex and Edge with State::WHITE to State::GREY unless specified otherwise in their discovery functions.

Parameters

origin

The ID of the Vertex to start the traversal from.

template<class V, class E, class G >

std::string rz::graph::Graph< V, E, G >::getDOT ( std::function< std::string(const Vertex< V, E > &)>  vertexAttributes = nullptr, std::function< std::string(const Edge< E > &)>  edgeAttributes = nullptr  )

inline

Converts the graph into a string representing a directed graph in the DOT language.

Unless otherwise specified: Styling is default, vertices are labeled with their ID and edges have no label.

Parameters

vertexAttributes	A functor to add tags to the vertices. Must return in the format [tag=value tag=value]
edgeAttributes	A functor to add tags to the edges. Must return in the format [tag=value tag=value]

Returns

The graph converted into the DOT language.

template<class V , class E , class G >

Vertex< V, E > & rz::graph::Graph< V, E, G >::operator[] ( std::size_t  index )

inline

Get's a reference to the Vertex with id == index.

Exceptions

std::out_of_range

index out of range for _vertices.

Returns

A reference to Vertex object.

template<class V, class E, class G>

std::size_t rz::graph::Graph< V, E, G >::order ( )

inline

Returns the number of Vertex objects.

template<class V , class E , class G >

void rz::graph::Graph< V, E, G >::reset ( bool  resetFuncs = true )

inline

Resets the state of all Edge and Vertex objects belonging to the Graph to State::WHITE.

Also resets Vertex and Edge discovery functions to nullptr.

Parameters

resetFuncs

If true sets discovery functions to nullptr, else leaves them as is.

Member Data Documentation

template<class V, class E, class G>

std::map<State, VertexFunc> rz::graph::Graph< V, E, G >::vertexFuncs

The function to run on Vertex discovery.

---

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

• /home/travis/build/razaron/engine-mk1/framework/Graph.hpp