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 34 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 36 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 37 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 53 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 66 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 80 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

nodiscard

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 98 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

nodiscard

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 117 of file Digraph.h.

outVertices() [1/2]

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

auto xrpl::test::csf::Digraph< Vertex, EdgeData >::outVertices ( ) const

nodiscard

Range over vertices in the graph.

Returns

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

Definition at line 128 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

nodiscard

Range over target vertices.

Parameters

source

The source vertex

Returns

A boost transformed range over the target vertices of source.

Definition at line 140 of file Digraph.h.

outEdges()

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

auto xrpl::test::csf::Digraph< Vertex, EdgeData >::outEdges ( Vertex source ) const

nodiscard

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 166 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

nodiscard

Vertex out-degree.

Parameters

source

The source vertex

Returns

The number of outgoing edges from source

Definition at line 185 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 203 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 220 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 38 of file Digraph.h.

empty_

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

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

private

Definition at line 41 of file Digraph.h.