Directed graph, implemented as an adjacency list. More...

#include <digraph.hxx>

Classes
struct	Vertex

Public Types
typedef VISITOR	Visitor
typedef detail::VertexIterator	VertexIterator
typedef detail::EdgeIterator	EdgeIterator
typedef detail::Adjacencies::const_iterator	AdjacencyIterator
typedef AdjacencyIterator::value_type	AdjacencyType

Public Member Functions
	Digraph (const Visitor &=Visitor())
	Construct a directed graph.
	Digraph (const std::size_t, const Visitor &=Visitor())
	Construct a directed graph with an initial number of vertices.
void	assign (const Visitor &=Visitor())
	Clear a directed graph.
void	assign (const std::size_t, const Visitor &=Visitor())
	Clear a directed graph with an initial number of vertices.
void	reserveVertices (const std::size_t)
	Reserve memory for at least the given total number of vertices.
void	reserveEdges (const std::size_t)
	Reserve memory for at least the given total number of edges.
VertexIterator	verticesFromVertexBegin (const std::size_t) const
	Get an iterator to the beginning of the sequence of vertices reachable from a given vertex via a single edge.
VertexIterator	verticesFromVertexEnd (const std::size_t) const
	Get an iterator to the end of the sequence of vertices reachable from a given vertex via a single edge.
VertexIterator	verticesToVertexBegin (const std::size_t) const
	Get an iterator to the beginning of the sequence of vertices from which a given vertex is reachable via a single edge.
VertexIterator	verticesToVertexEnd (const std::size_t) const
	Get an iterator to the end of the sequence of vertices from which a given vertex is reachable via a single edge.
EdgeIterator	edgesFromVertexBegin (const std::size_t) const
	Get an iterator to the beginning of the sequence of edges that originate from a given vertex.
EdgeIterator	edgesFromVertexEnd (const std::size_t) const
	Get an iterator to the end of the sequence of edges that originate from a given vertex.
EdgeIterator	edgesToVertexBegin (const std::size_t) const
	Get an iterator to the beginning of the sequence of edges that are incident to a given vertex.
EdgeIterator	edgesToVertexEnd (const std::size_t) const
	Get an iterator to the end of the sequence of edges that are incident to a given vertex.
AdjacencyIterator	adjacenciesFromVertexBegin (const std::size_t) const
	Get an iterator to the beginning of the sequence of adjacencies that originate from a given vertex.
AdjacencyIterator	adjacenciesFromVertexEnd (const std::size_t) const
	Get an iterator to the end of the sequence of adjacencies that originate from a given vertex.
AdjacencyIterator	adjacenciesToVertexBegin (const std::size_t) const
	Get an iterator to the beginning of the sequence of adjacencies incident to a given vertex.
AdjacencyIterator	adjacenciesToVertexEnd (const std::size_t) const
	Get an iterator to the end of the sequence of adjacencies incident to a given vertex.
std::size_t	numberOfVertices () const
	Get the number of vertices.
std::size_t	numberOfEdges () const
	Get the number of edges.
std::size_t	numberOfEdgesFromVertex (const std::size_t) const
	Get the number of edges that originate from a given vertex.
std::size_t	numberOfEdgesToVertex (const std::size_t) const
	Get the number of edges that are incident to a given vertex.
std::size_t	vertexOfEdge (const std::size_t, const std::size_t) const
	Get the integer index of a vertex of an edge.
std::size_t	edgeFromVertex (const std::size_t, const std::size_t) const
	Get the integer index of an edge that originates from a given vertex.
std::size_t	edgeToVertex (const std::size_t, const std::size_t) const
	Get the integer index of an edge that is incident to a given vertex.
std::size_t	vertexFromVertex (const std::size_t, const std::size_t) const
	Get the integer index of a vertex reachable from a given vertex via a single edge.
std::size_t	vertexToVertex (const std::size_t, const std::size_t) const
	Get the integer index of a vertex from which a given vertex is reachable via a single edge.
const AdjacencyType &	adjacencyFromVertex (const std::size_t, const std::size_t) const
	Get the j-th adjacency from a vertex.
const AdjacencyType &	adjacencyToVertex (const std::size_t, const std::size_t) const
	Get the j-th adjacency to a vertex.
std::pair< bool, std::size_t >	findEdge (const std::size_t, const std::size_t) const
	Search for an edge (in logarithmic time).
bool	multipleEdgesEnabled () const
	Indicate if multiple edges are enabled.
std::size_t	insertVertex ()
	Insert an additional vertex.
std::size_t	insertVertices (const std::size_t)
	Insert additional vertices.
std::size_t	insertEdge (const std::size_t, const std::size_t)
	Insert an additional edge.
void	eraseVertex (const std::size_t)
	Erase a vertex and all edges connecting this vertex.
void	eraseEdge (const std::size_t)
	Erase an edge.
bool &	multipleEdgesEnabled ()
	Indicate if multiple edges are enabled.

Detailed Description

template<typename VISITOR = IdleGraphVisitor<std::size_t>>
class andres::graph::Digraph< VISITOR >

Directed graph, implemented as an adjacency list.

Definition at line 24 of file digraph.hxx.

Member Typedef Documentation

template<typename VISITOR = IdleGraphVisitor<std::size_t>>

typedef detail::Adjacencies::const_iterator andres::graph::Digraph< VISITOR >::AdjacencyIterator

Definition at line 29 of file digraph.hxx.

template<typename VISITOR = IdleGraphVisitor<std::size_t>>

typedef AdjacencyIterator::value_type andres::graph::Digraph< VISITOR >::AdjacencyType

Definition at line 31 of file digraph.hxx.

template<typename VISITOR = IdleGraphVisitor<std::size_t>>

typedef detail::EdgeIterator andres::graph::Digraph< VISITOR >::EdgeIterator

Definition at line 28 of file digraph.hxx.

template<typename VISITOR = IdleGraphVisitor<std::size_t>>

typedef detail::VertexIterator andres::graph::Digraph< VISITOR >::VertexIterator

Definition at line 27 of file digraph.hxx.

template<typename VISITOR = IdleGraphVisitor<std::size_t>>

typedef VISITOR andres::graph::Digraph< VISITOR >::Visitor

Definition at line 26 of file digraph.hxx.

Constructor & Destructor Documentation

template<typename VISITOR >

andres::graph::Digraph< VISITOR >::Digraph ( const Visitor & visitor = Visitor() )

inline

Construct a directed graph.

Parameters

visitor Visitor to follow changes of integer indices of vertices and edges.

Definition at line 106 of file digraph.hxx.

template<typename VISITOR >

andres::graph::Digraph< VISITOR >::Digraph	(	const std::size_t	numberOfVertices,
		const Visitor &	visitor = `Visitor()`
	)

inline

Construct a directed graph with an initial number of vertices.

Parameters

numberOfVertices	Number of vertices.
visitor	Visitor to follow changes of integer indices of vertices and edges.

Definition at line 122 of file digraph.hxx.

Member Function Documentation

template<typename VISITOR >

Digraph< VISITOR >::AdjacencyIterator andres::graph::Digraph< VISITOR >::adjacenciesFromVertexBegin ( const std::size_t vertex ) const

inline

Get an iterator to the beginning of the sequence of adjacencies that originate from a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: AdjacencyIterator.

See Also: adjacenciesFromVertexEnd()

Definition at line 581 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::AdjacencyIterator andres::graph::Digraph< VISITOR >::adjacenciesFromVertexEnd ( const std::size_t vertex ) const

inline

Get an iterator to the end of the sequence of adjacencies that originate from a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: AdjacencyIterator.

See Also: adjacenciesFromVertexBegin()

Definition at line 596 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::AdjacencyIterator andres::graph::Digraph< VISITOR >::adjacenciesToVertexBegin ( const std::size_t vertex ) const

inline

Get an iterator to the beginning of the sequence of adjacencies incident to a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: AdjacencyIterator.

See Also: adjacenciesToVertexEnd()

Definition at line 611 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::AdjacencyIterator andres::graph::Digraph< VISITOR >::adjacenciesToVertexEnd ( const std::size_t vertex ) const

inline

Get an iterator to the end of the sequence of adjacencies incident to a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: AdjacencyIterator.

See Also: adjacenciesToVertexBegin()

Definition at line 626 of file digraph.hxx.

template<typename VISITOR >

const Digraph< VISITOR >::AdjacencyType & andres::graph::Digraph< VISITOR >::adjacencyFromVertex	(	const std::size_t	vertex,
		const std::size_t	j
	)		const

inline

Get the j-th adjacency from a vertex.

Parameters

vertex	Vertex.
j	Number of the adjacency.

Definition at line 663 of file digraph.hxx.

template<typename VISITOR >

const Digraph< VISITOR >::AdjacencyType & andres::graph::Digraph< VISITOR >::adjacencyToVertex	(	const std::size_t	vertex,
		const std::size_t	j
	)		const

inline

Get the j-th adjacency to a vertex.

Parameters

vertex	Vertex.
j	Number of the adjacency.

Definition at line 677 of file digraph.hxx.

template<typename VISITOR >

void andres::graph::Digraph< VISITOR >::assign ( const Visitor & visitor = Visitor() )

inline

Clear a directed graph.

Parameters

visitor Visitor to follow changes of integer indices of vertices and edges.

Definition at line 140 of file digraph.hxx.

template<typename VISITOR >

void andres::graph::Digraph< VISITOR >::assign	(	const std::size_t	numberOfVertices,
		const Visitor &	visitor = `Visitor()`
	)

inline

Clear a directed graph with an initial number of vertices.

Parameters

numberOfVertices	Number of vertices.
visitor	Visitor to follow changes of integer indices of vertices and edges.

Definition at line 156 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::edgeFromVertex	(	const std::size_t	vertex,
		const std::size_t	j
	)		const

inline

Get the integer index of an edge that originates from a given vertex.

Parameters

vertex	Integer index of a vertex.
j	Number of the edge; between 0 and numberOfEdgesFromVertex(vertex) - 1.

See Also: numberOfEdgesFromVertex()

Definition at line 237 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::EdgeIterator andres::graph::Digraph< VISITOR >::edgesFromVertexBegin ( const std::size_t vertex ) const

inline

Get an iterator to the beginning of the sequence of edges that originate from a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: EdgeIterator.

See Also: edgesFromVertexEnd()

Definition at line 521 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::EdgeIterator andres::graph::Digraph< VISITOR >::edgesFromVertexEnd ( const std::size_t vertex ) const

inline

Get an iterator to the end of the sequence of edges that originate from a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: EdgeIterator.

See Also: edgesFromVertexBegin()

Definition at line 536 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::EdgeIterator andres::graph::Digraph< VISITOR >::edgesToVertexBegin ( const std::size_t vertex ) const

inline

Get an iterator to the beginning of the sequence of edges that are incident to a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: EdgeIterator.

See Also: edgesToVertexEnd()

Definition at line 551 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::EdgeIterator andres::graph::Digraph< VISITOR >::edgesToVertexEnd ( const std::size_t vertex ) const

inline

Get an iterator to the end of the sequence of edges that are incident to a given vertex.

Parameters

vertex Integer index of the vertex.

Returns: EdgeIterator.

See Also: edgesToVertexBegin()

Definition at line 566 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::edgeToVertex	(	const std::size_t	vertex,
		const std::size_t	j
	)		const

inline

Get the integer index of an edge that is incident to a given vertex.

Parameters

vertex	Integer index of a vertex.
j	Number of the edge; between 0 and numberOfEdgesFromVertex(vertex) - 1.

See Also: numberOfEdgesToVertex()

Definition at line 253 of file digraph.hxx.

template<typename VISITOR >

void andres::graph::Digraph< VISITOR >::eraseEdge ( const std::size_t edgeIndex )

inline

Erase an edge.

Parameters

edgeIndex Integer index of the edge to be erased.

Definition at line 431 of file digraph.hxx.

template<typename VISITOR >

void andres::graph::Digraph< VISITOR >::eraseVertex ( const std::size_t vertexIndex )

Erase a vertex and all edges connecting this vertex.

Parameters

vertexIndex Integer index of the vertex to be erased.

Definition at line 364 of file digraph.hxx.

template<typename VISITOR >

std::pair< bool, std::size_t > andres::graph::Digraph< VISITOR >::findEdge	(	const std::size_t	vertex0,
		const std::size_t	vertex1
	)		const

inline

Search for an edge (in logarithmic time).

Parameters

vertex0	first vertex of the edge.
vertex1	second vertex of the edge.

Returns: if an edge from vertex0 to vertex1 exists, pair.first is true and pair.second is the index of such an edge. if no edge from vertex0 to vertex1 exists, pair.first is false and pair.second is undefined.

Definition at line 694 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::insertEdge	(	const std::size_t	vertexIndex0,
		const std::size_t	vertexIndex1
	)

inline

Insert an additional edge.

Parameters

vertexIndex0	Integer index of the first vertex (source) of the edge.
vertexIndex1	Integer index of the second vertex (target) of the edge.

Returns: Integer index of the newly inserted edge.

Definition at line 332 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::insertVertex ( )

inline

Insert an additional vertex.

Returns: Integer index of the newly inserted vertex.

See Also: insertVertices()

Definition at line 300 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::insertVertices ( const std::size_t number )

inline

Insert additional vertices.

Parameters

number Number of new vertices to be inserted.

Returns: Integer index of the first newly inserted vertex.

See Also: insertVertex()

Definition at line 315 of file digraph.hxx.

template<typename VISITOR >

bool andres::graph::Digraph< VISITOR >::multipleEdgesEnabled ( ) const

inline

Indicate if multiple edges are enabled.

Returns: true if multiple edges are enabled, false otherwise.

Definition at line 722 of file digraph.hxx.

template<typename VISITOR >

bool & andres::graph::Digraph< VISITOR >::multipleEdgesEnabled ( )

inline

Indicate if multiple edges are enabled.

Enable multiple edges like this: graph.multipleEdgesEnabled() = true;

Returns: reference the a Boolean flag.

Definition at line 734 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::numberOfEdges ( ) const

inline

Get the number of edges.

Definition at line 180 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::numberOfEdgesFromVertex ( const std::size_t vertex ) const

inline

Get the number of edges that originate from a given vertex.

Parameters

vertex Integer index of a vertex.

See Also: edgeFromVertex()

Definition at line 192 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::numberOfEdgesToVertex ( const std::size_t vertex ) const

inline

Get the number of edges that are incident to a given vertex.

Parameters

vertex Integer index of a vertex.

See Also: edgeToVertex()

Definition at line 206 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::numberOfVertices ( ) const

inline

Get the number of vertices.

Definition at line 172 of file digraph.hxx.

template<typename VISITOR >

void andres::graph::Digraph< VISITOR >::reserveEdges ( const std::size_t number )

inline

Reserve memory for at least the given total number of edges.

Parameters

number Total number of edges.

Definition at line 650 of file digraph.hxx.

template<typename VISITOR >

void andres::graph::Digraph< VISITOR >::reserveVertices ( const std::size_t number )

inline

Reserve memory for at least the given total number of vertices.

Parameters

number Total number of vertices.

Definition at line 638 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::vertexFromVertex	(	const std::size_t	vertex,
		const std::size_t	j
	)		const

inline

Get the integer index of a vertex reachable from a given vertex via a single edge.

Parameters

vertex	Integer index of a vertex.
j	Number of the vertex; between 0 and numberOfEdgesFromVertex(vertex) - 1.

See Also: numberOfEdgesFromVertex()

Definition at line 269 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::vertexOfEdge	(	const std::size_t	edge,
		const std::size_t	j
	)		const

inline

Get the integer index of a vertex of an edge.

Parameters

edge	Integer index of an edge.
j	Number of the vertex in the edge; either 0 or 1.

Definition at line 219 of file digraph.hxx.

template<typename VISITOR >

std::size_t andres::graph::Digraph< VISITOR >::vertexToVertex	(	const std::size_t	vertex,
		const std::size_t	j
	)		const

inline

Get the integer index of a vertex from which a given vertex is reachable via a single edge.

Parameters

vertex	Integer index of a vertex.
j	Number of the vertex; between 0 and numberOfEdgesFromVertex(vertex) - 1.

See Also: numberOfEdgesFromVertex()

Definition at line 285 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::VertexIterator andres::graph::Digraph< VISITOR >::verticesFromVertexBegin ( const std::size_t vertex ) const

inline

Get an iterator to the beginning of the sequence of vertices reachable from a given vertex via a single edge.

Parameters

vertex Integer index of the vertex.

Returns: VertexIterator.

See Also: verticesFromVertexEnd()

Definition at line 461 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::VertexIterator andres::graph::Digraph< VISITOR >::verticesFromVertexEnd ( const std::size_t vertex ) const

inline

Get an iterator to the end of the sequence of vertices reachable from a given vertex via a single edge.

Parameters

vertex Integer index of the vertex.

Returns: VertexIterator.

See Also: verticesFromVertexBegin()

Definition at line 476 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::VertexIterator andres::graph::Digraph< VISITOR >::verticesToVertexBegin ( const std::size_t vertex ) const

inline

Get an iterator to the beginning of the sequence of vertices from which a given vertex is reachable via a single edge.

Parameters

vertex Integer index of the vertex.

Returns: VertexIterator.

See Also: verticesToVertexEnd()

Definition at line 491 of file digraph.hxx.

template<typename VISITOR >

Digraph< VISITOR >::VertexIterator andres::graph::Digraph< VISITOR >::verticesToVertexEnd ( const std::size_t vertex ) const

inline

Get an iterator to the end of the sequence of vertices from which a given vertex is reachable via a single edge.

Parameters

vertex Integer index of the vertex.

Returns: VertexIterator.

See Also: verticesToVertexBegin()

Definition at line 506 of file digraph.hxx.

Classes

Public Types

Public Member Functions

Detailed Description

template<typename VISITOR = IdleGraphVisitor<std::size_t>> class andres::graph::Digraph< VISITOR >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<typename VISITOR = IdleGraphVisitor<std::size_t>>
class andres::graph::Digraph< VISITOR >