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

Directed graph. More...

#include <Digraph.h>

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.
bool	connect (Vertex source, Vertex target)
	Connect two vertices using default constructed edge data.
bool	disconnect (Vertex source, Vertex target)
	Disconnect two vertices.
std::optional< EdgeData >	edge (Vertex source, Vertex target) const
	Return edge data between two vertices.
bool	connected (Vertex source, Vertex target) const
	Check if two vertices are connected.
auto	outVertices () const
	Range over vertices in the graph.
auto	outVertices (Vertex source) const
	Range over target vertices.
auto	outEdges (Vertex source) const
	Range of out edges.
std::size_t	outDegree (Vertex source) const
	Vertex out-degree.
template<class VertexName >
void	saveDot (std::ostream &out, VertexName &&vertexName) const
	Save GraphViz dot file.
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 xrpl::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 36 of file Digraph.h.

Member Typedef Documentation

Links

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

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

private

Definition at line 38 of file Digraph.h.

Graph

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

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

private

Definition at line 39 of file Digraph.h.

Member Function Documentation

connect() [1/2]

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

bool xrpl::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 55 of file Digraph.h.

connect() [2/2]

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

bool xrpl::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 68 of file Digraph.h.

disconnect()

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

bool xrpl::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 82 of file Digraph.h.

edge()

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

std::optional< EdgeData > xrpl::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 100 of file Digraph.h.

connected()

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

bool xrpl::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 119 of file Digraph.h.

outVertices() [1/2]

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

auto xrpl::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 130 of file Digraph.h.

outVertices() [2/2]

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

auto xrpl::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 143 of file Digraph.h.

outEdges()

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

auto xrpl::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 171 of file Digraph.h.

outDegree()

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

std::size_t xrpl::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 190 of file Digraph.h.

saveDot() [1/2]

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

template<class VertexName >

void xrpl::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 invocable T vertexName(Vertex const &) that returns the name target use for the vertex in the file T must be ostream-able

Definition at line 208 of file Digraph.h.

saveDot() [2/2]

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

template<class VertexName >

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

Definition at line 225 of file Digraph.h.

Member Data Documentation

graph_

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

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

private

Definition at line 40 of file Digraph.h.

empty

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

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

private

Definition at line 43 of file Digraph.h.