ripple::test::csf::Digraph< Vertex, EdgeData > Class Template Reference

Directed graph. More...

Classes
struct	Edge
	Vertices and data associated with an Edge. More...

Public Member Functions
bool	connect (Vertex source, Vertex target, EdgeData e)
	Connect two vertices. More...
bool	connect (Vertex source, Vertex target)
	Connect two vertices using default constructed edge data. More...
bool	disconnect (Vertex source, Vertex target)
	Disconnect two vertices. More...
std::optional< EdgeData >	edge (Vertex source, Vertex target) const
	Return edge data between two vertices. More...
bool	connected (Vertex source, Vertex target) const
	Check if two vertices are connected. More...
auto	outVertices () const
	Range over vertices in the graph. More...
auto	outVertices (Vertex source) const
	Range over target vertices. More...
auto	outEdges (Vertex source) const
	Range of out edges. More...
std::size_t	outDegree (Vertex source) const
	Vertex out-degree. More...
template<class VertexName >
void	saveDot (std::ostream &out, VertexName &&vertexName) const
	Save GraphViz dot file. More...
template<class VertexName >
void	saveDot (std::string const &fileName, VertexName &&vertexName) const

Private Types
using	Links = boost::container::flat_map< Vertex, EdgeData >
using	Graph = boost::container::flat_map< Vertex, Links >

Private Attributes
Graph	graph_
Links	empty

Detailed Description

template<class Vertex, class EdgeData = detail::NoEdgeData>
class ripple::test::csf::Digraph< Vertex, EdgeData >

Directed graph.

Basic directed graph that uses an adjacency list to represent out edges.

Instances of Vertex uniquely identify vertices in the graph. Instances of EdgeData is any data to store in the edge connecting two vertices.

Both Vertex and EdgeData should be lightweight and cheap to copy.

Definition at line 55 of file Digraph.h.

Member Typedef Documentation

Links

template<class Vertex , class EdgeData = detail::NoEdgeData>

using ripple::test::csf::Digraph< Vertex, EdgeData >::Links = boost::container::flat_map<Vertex, EdgeData>

private

Definition at line 57 of file Digraph.h.

Graph

template<class Vertex , class EdgeData = detail::NoEdgeData>

using ripple::test::csf::Digraph< Vertex, EdgeData >::Graph = boost::container::flat_map<Vertex, Links>

private

Definition at line 58 of file Digraph.h.

Member Function Documentation

connect() [1/2]

template<class Vertex , class EdgeData = detail::NoEdgeData>

bool ripple::test::csf::Digraph< Vertex, EdgeData >::connect	(	Vertex	source,
		Vertex	target,
		EdgeData	e
	)

Connect two vertices.

Parameters

source	The source vertex
target	The target vertex
e	The edge data

Returns

true if the edge was created

Definition at line 74 of file Digraph.h.

connect() [2/2]

template<class Vertex , class EdgeData = detail::NoEdgeData>

bool ripple::test::csf::Digraph< Vertex, EdgeData >::connect	(	Vertex	source,
		Vertex	target
	)

Connect two vertices using default constructed edge data.

Parameters

source	The source vertex
target	The target vertex

Returns

true if the edge was created

Definition at line 87 of file Digraph.h.

disconnect()

template<class Vertex , class EdgeData = detail::NoEdgeData>

bool ripple::test::csf::Digraph< Vertex, EdgeData >::disconnect	(	Vertex	source,
		Vertex	target
	)

Disconnect two vertices.

Parameters

source	The source vertex
target	The target vertex

Returns

true if an edge was removed

If source is not connected to target, this function does nothing.

Definition at line 101 of file Digraph.h.

edge()

template<class Vertex , class EdgeData = detail::NoEdgeData>

std::optional<EdgeData> ripple::test::csf::Digraph< Vertex, EdgeData >::edge	(	Vertex	source,
		Vertex	target
	)		const

Return edge data between two vertices.

Parameters

source	The source vertex
target	The target vertex

Returns

optional<Edge> which is std::nullopt if no edge exists

Definition at line 119 of file Digraph.h.

connected()

template<class Vertex , class EdgeData = detail::NoEdgeData>

bool ripple::test::csf::Digraph< Vertex, EdgeData >::connected	(	Vertex	source,
		Vertex	target
	)		const

Check if two vertices are connected.

Parameters

source	The source vertex
target	The target vertex

Returns

true if the source has an out edge to target

Definition at line 138 of file Digraph.h.

outVertices() [1/2]

template<class Vertex , class EdgeData = detail::NoEdgeData>

auto ripple::test::csf::Digraph< Vertex, EdgeData >::outVertices

(

)

const

Range over vertices in the graph.

Returns

A boost transformed range over the vertices with out edges in the graph

Definition at line 149 of file Digraph.h.

outVertices() [2/2]

template<class Vertex , class EdgeData = detail::NoEdgeData>

auto ripple::test::csf::Digraph< Vertex, EdgeData >::outVertices

(

Vertex

source

)

const

Range over target vertices.

Parameters

source

The source vertex

Returns

A boost transformed range over the target vertices of source.

Definition at line 162 of file Digraph.h.

outEdges()

template<class Vertex , class EdgeData = detail::NoEdgeData>

auto ripple::test::csf::Digraph< Vertex, EdgeData >::outEdges

(

Vertex

source

)

const

Range of out edges.

Parameters

source

The source vertex

Returns

A boost transformed range of Edge type for all out edges of source.

Definition at line 190 of file Digraph.h.

outDegree()

template<class Vertex , class EdgeData = detail::NoEdgeData>

std::size_t ripple::test::csf::Digraph< Vertex, EdgeData >::outDegree

(

Vertex

source

)

const

Vertex out-degree.

Parameters

source

The source vertex

Returns

The number of outgoing edges from source

Definition at line 209 of file Digraph.h.

saveDot() [1/2]

template<class Vertex , class EdgeData = detail::NoEdgeData>

template<class VertexName >

void ripple::test::csf::Digraph< Vertex, EdgeData >::saveDot	(	std::ostream &	out,
		VertexName &&	vertexName
	)		const

Save GraphViz dot file.

Save a GraphViz dot description of the graph

Parameters

fileName	The output file (creates)
vertexName	A invokable T vertexName(Vertex const &) that returns the name target use for the vertex in the file T must be be ostream-able

Definition at line 227 of file Digraph.h.

saveDot() [2/2]

template<class Vertex , class EdgeData = detail::NoEdgeData>

template<class VertexName >

void ripple::test::csf::Digraph< Vertex, EdgeData >::saveDot	(	std::string const &	fileName,
		VertexName &&	vertexName
	)		const

Definition at line 244 of file Digraph.h.

Member Data Documentation

graph_

template<class Vertex , class EdgeData = detail::NoEdgeData>

Graph ripple::test::csf::Digraph< Vertex, EdgeData >::graph_

private

Definition at line 59 of file Digraph.h.

empty

template<class Vertex , class EdgeData = detail::NoEdgeData>

Links ripple::test::csf::Digraph< Vertex, EdgeData >::empty

private

Definition at line 62 of file Digraph.h.