D-dimensional grid graph. More...

#include <grid-graph.hxx>

Classes
class	EdgeCoordinate
	Describes an edge as the integer index of the minimum of the two endpoints and the direction along which it is drawn. More...

Public Types
typedef std::size_t	size_type
typedef VISITOR	Visitor
typedef andres::graph::Adjacency < size_type >	AdjacencyType
typedef std::array< size_type, DIMENSION >	VertexCoordinate

Public Member Functions
	GridGraph (const Visitor &=Visitor())
	AdjacencyIterator.
	GridGraph (const VertexCoordinate &, const Visitor &=Visitor())
	GridGraph (const std::initializer_list< std::size_t >, const Visitor &=Visitor())
	Construct a grid graph with a specified shape.
void	assign (const Visitor &=Visitor())
	Clear a grid graph.
void	assign (const VertexCoordinate &, const Visitor &=Visitor())
	Clear a grid graph and assign a new shape.
VertexIterator	verticesFromVertexBegin (const size_type) const
	Get an iterator to the beginning of the sequence of vertices reachable from a given vertex via a single edge.
VertexIterator	verticesFromVertexEnd (const size_type) const
	Get an iterator to the end of the sequence of vertices reachable from a given vertex via a single edge.
VertexIterator	verticesToVertexBegin (const size_type) 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 size_type) 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 size_type) const
	Get an iterator to the beginning of the sequence of edges that originate from a given vertex.
EdgeIterator	edgesFromVertexEnd (const size_type) const
	Get an iterator to the end of the sequence of edges that originate from a given vertex.
EdgeIterator	edgesToVertexBegin (const size_type) const
	Get an iterator to the beginning of the sequence of edges that are incident to a given vertex.
EdgeIterator	edgesToVertexEnd (const size_type) const
	Get an iterator to the end of the sequence of edges that are incident to a given vertex.
AdjacencyIterator	adjacenciesFromVertexBegin (const size_type) const
	Get an iterator to the beginning of the sequence of adjacencies that originate from a given vertex.
AdjacencyIterator	adjacenciesFromVertexEnd (const size_type) const
	Get an iterator to the end of the sequence of adjacencies that originate from a given vertex.
AdjacencyIterator	adjacenciesToVertexBegin (const size_type) const
	Get an iterator to the beginning of the sequence of adjacencies incident to a given vertex.
AdjacencyIterator	adjacenciesToVertexEnd (const size_type) const
	Get an iterator to the end of the sequence of adjacencies incident to a given vertex.
size_type	numberOfVertices () const
	Get the number of vertices.
size_type	numberOfEdges () const
	Get the number of edges.
size_type	numberOfEdgesFromVertex (const size_type) const
	Get the number of edges that originate from a given vertex.
size_type	numberOfEdgesToVertex (const size_type) const
	Get the number of edges that are incident to a given vertex.
size_type	vertexOfEdge (const size_type, const size_type) const
	Get the integer index of a vertex of an edge.
size_type	edgeFromVertex (const size_type, const size_type) const
	Get the integer index of an edge that originates from a given vertex.
size_type	edgeToVertex (const size_type, const size_type) const
	Get the integer index of an edge that is incident to a given vertex.
size_type	vertexFromVertex (const size_type, const size_type) const
	Get the integer index of a vertex from which a given vertex is reachable via a single edge.
size_type	vertexToVertex (const size_type, const size_type) const
	Get the integer index of a vertex to which a given vertex has a single edge.
AdjacencyType	adjacencyFromVertex (const size_type, const size_type) const
	Get the j-th adjacency from a vertex.
AdjacencyType	adjacencyToVertex (const size_type, const size_type) const
	Get the j-th adjacency to a vertex.
std::pair< bool, size_type >	findEdge (const size_type, const size_type) const
	Search for an edge (in constant time).
bool	multipleEdgesEnabled () const
	Indicate if multiple edges are enabled.
size_type	insertEdge (const size_type, const size_type) const
	Returns the edge between the specified vertices.
size_type	shape (const size_type) const
	Get the size of a specific dimension of the grid graph.
size_type	vertex (const VertexCoordinate &) const
	Retrieve the specified vertex of the graph.
void	vertex (const size_type, VertexCoordinate &) const
	Retrieve the specified vertex of the graph.
size_type	edge (const EdgeCoordinate &) const
	Retrieve the specified edge of the graph.
void	edge (const size_type, EdgeCoordinate &) const
	Retrieve the specified edge of the graph.

Static Public Attributes
static const size_type	DIMENSION = static_cast<size_type> (D)

Detailed Description

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>
class andres::graph::GridGraph< D, VISITOR >

D-dimensional grid graph.

Definition at line 22 of file grid-graph.hxx.

Member Typedef Documentation

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>

typedef andres::graph::Adjacency<size_type> andres::graph::GridGraph< D, VISITOR >::AdjacencyType

Definition at line 26 of file grid-graph.hxx.

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>

typedef std::size_t andres::graph::GridGraph< D, VISITOR >::size_type

Definition at line 24 of file grid-graph.hxx.

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>

typedef std::array<size_type, DIMENSION> andres::graph::GridGraph< D, VISITOR >::VertexCoordinate

Definition at line 30 of file grid-graph.hxx.

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>

typedef VISITOR andres::graph::GridGraph< D, VISITOR >::Visitor

Definition at line 25 of file grid-graph.hxx.

Constructor & Destructor Documentation

template<unsigned char D, class VISITOR >

andres::graph::GridGraph< D, VISITOR >::GridGraph ( const Visitor & visitor = Visitor() )

inline

AdjacencyIterator.

Construct an empty grid graph.

Template Parameters

S	the type of the indices used. It must be an unsigned type (otherwise a compilation error is caused). Defaults to `std::size_t` .
VISITOR	a visitor class to be used. Since this class is immutable appart from resizing, this is a dummy variable meant for compatibility, defaulting to `andres::graph::IdgeGraphVisitor`.

Parameters

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

Definition at line 222 of file grid-graph.hxx.

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>

class VISITOR inline andres::graph::GridGraph< D, VISITOR >::GridGraph	(	const VertexCoordinate &	shape,
		const Visitor &	visitor = `Visitor()`
	)

Definition at line 235 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

andres::graph::GridGraph< D, VISITOR >::GridGraph	(	const std::initializer_list< std::size_t >	shape,
		const Visitor &	visitor = `Visitor()`
	)

inline

Construct a grid graph with a specified shape.

Parameters

shape	the shape of the Grid Graph as an std::array.
visitor	Visitor to follow changes of integer indices of vertices and edges.

Definition at line 250 of file grid-graph.hxx.

Member Function Documentation

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::AdjacencyIterator andres::graph::GridGraph< D, VISITOR >::adjacenciesFromVertexBegin ( const size_type 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 458 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::AdjacencyIterator andres::graph::GridGraph< D, VISITOR >::adjacenciesFromVertexEnd ( const size_type 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 474 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::AdjacencyIterator andres::graph::GridGraph< D, VISITOR >::adjacenciesToVertexBegin ( const size_type 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 490 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::AdjacencyIterator andres::graph::GridGraph< D, VISITOR >::adjacenciesToVertexEnd ( const size_type 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 506 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::AdjacencyType andres::graph::GridGraph< D, VISITOR >::adjacencyFromVertex	(	const size_type	vertex,
		const size_type	j
	)		const

inline

Get the j-th adjacency from a vertex.

Parameters

vertex	Vertex.
j	Number of the adjacency.

Definition at line 690 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::AdjacencyType andres::graph::GridGraph< D, VISITOR >::adjacencyToVertex	(	const size_type	vertex,
		const size_type	j
	)		const

inline

Get the j-th adjacency to a vertex.

Parameters

vertex	Vertex.
j	Number of the adjacency.

Definition at line 716 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

void andres::graph::GridGraph< D, VISITOR >::assign ( const Visitor & visitor = Visitor() )

inline

Clear a grid graph.

Parameters

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

Definition at line 268 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

void andres::graph::GridGraph< D, VISITOR >::assign	(	const VertexCoordinate &	shape,
		const Visitor &	visitor = `Visitor()`
	)

inline

Clear a grid graph and assign a new shape.

Parameters

shape	the shape of the grid graph
visitor	Visitor to follow changes of integer indices of vertices and edges.

Definition at line 283 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::edge ( const EdgeCoordinate & edgeCoordinate ) const

inline

Retrieve the specified edge of the graph.

Parameters

edgeCoordinate the coordinates of the minimum endpoint (pivot) and the direction of the requested edge.

Returns: The integer index of the specified edge.

Warning: For the sake of performance this function does not validate its inputs.

See Also: hasEdge()

Definition at line 878 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

void andres::graph::GridGraph< D, VISITOR >::edge	(	const size_type	edgeIndex,
		EdgeCoordinate &	edgeCoordinate
	)		const

inline

Retrieve the specified edge of the graph.

Parameters

[in]	edgeIndex	the integer index of the requested edge.
[out]	edgeCoordinate	a GridGraph::EdgeCoordinate instance. `edgeCoordinate.pivot` is the integer index of the minimum of the two edge endpoints; `edgeCoordinate.direction` is the dimension along which the edge is drawn, with an assumed positive isSmaller.

Warning: For the sake of performance this function does not validate its inputs.

See Also: GridGraph::bool

Definition at line 910 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::edgeFromVertex	(	const size_type	vertex,
		const size_type	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()exFi

Definition at line 603 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::EdgeIterator andres::graph::GridGraph< D, VISITOR >::edgesFromVertexBegin ( const size_type 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 394 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::EdgeIterator andres::graph::GridGraph< D, VISITOR >::edgesFromVertexEnd ( const size_type 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 410 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::EdgeIterator andres::graph::GridGraph< D, VISITOR >::edgesToVertexBegin ( const size_type 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 426 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::EdgeIterator andres::graph::GridGraph< D, VISITOR >::edgesToVertexEnd ( const size_type 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 442 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::edgeToVertex	(	const size_type	vertex,
		const size_type	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 633 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

std::pair< bool, typename GridGraph< D, VISITOR >::size_type > andres::graph::GridGraph< D, VISITOR >::findEdge	(	const size_type	vertex0,
		const size_type	vertex1
	)		const

inline

Search for an edge (in constant time).

Parameters

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

Return values

pair	an `std::pair`. 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 734 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::insertEdge	(	const size_type	vertexIndex0,
		const size_type	vertexIndex1
	)		const

inline

Returns the edge between the specified vertices.

Parameters

vertexIndex0	Integer index of the first vertex in the edge.
vertexIndex1	Integer index of the second vertex in the edge.

Returns: Integer index of the newly inserted edge.

Exceptions

runtime_error If the edge does not exist.

Definition at line 805 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

bool andres::graph::GridGraph< D, VISITOR >::multipleEdgesEnabled ( ) const

inline

Indicate if multiple edges are enabled.

Returns: false

Definition at line 793 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::numberOfEdges ( ) const

inline

Get the number of edges.

Definition at line 524 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::numberOfEdgesFromVertex ( const size_type 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 536 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::numberOfEdgesToVertex ( const size_type 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 563 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::numberOfVertices ( ) const

inline

Get the number of vertices.

Definition at line 516 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::shape ( const size_type dimension ) const

inline

Get the size of a specific dimension of the grid graph.

Parameters

dimension the index of the dimension index to retrieve.

Returns: the size of the specified dimension.

See Also: mapIndexToCoordinate mapVertexCoordinateToIndex

Definition at line 846 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::vertex ( const VertexCoordinate & vertexCoordinate ) const

Retrieve the specified vertex of the graph.

Parameters

vertexCoordinate the integer index of the requested vertex

Returns: The integer index of the specified vertex.

Warning: For the sake of performance this function does not validate its inputs.

Definition at line 859 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

void andres::graph::GridGraph< D, VISITOR >::vertex	(	const size_type	vertexIndex,
		VertexCoordinate &	vertexCoordinate
	)		const

Retrieve the specified vertex of the graph.

Parameters

[in]	vertexIndex	the integer index of the requested vertex
[out]	vertexCoordinate	The coordinates of the vertex.

Warning: For the sake of performance this function does not validate its inputs.

Definition at line 827 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::vertexFromVertex	(	const size_type	vertex,
		const size_type	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 652 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::vertexOfEdge	(	const size_type	edge,
		const size_type	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 576 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::size_type andres::graph::GridGraph< D, VISITOR >::vertexToVertex	(	const size_type	vertex,
		const size_type	j
	)		const

inline

Get the integer index of a vertex to which a given vertex has 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 676 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::VertexIterator andres::graph::GridGraph< D, VISITOR >::verticesFromVertexBegin ( const size_type 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 330 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::VertexIterator andres::graph::GridGraph< D, VISITOR >::verticesFromVertexEnd ( const size_type 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 346 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::VertexIterator andres::graph::GridGraph< D, VISITOR >::verticesToVertexBegin ( const size_type 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 362 of file grid-graph.hxx.

template<unsigned char D, class VISITOR >

GridGraph< D, VISITOR >::VertexIterator andres::graph::GridGraph< D, VISITOR >::verticesToVertexEnd ( const size_type 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 378 of file grid-graph.hxx.

Member Data Documentation

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>

const size_type andres::graph::GridGraph< D, VISITOR >::DIMENSION = static_cast<size_type> (D)

static

Definition at line 28 of file grid-graph.hxx.

Classes

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>> class andres::graph::GridGraph< D, VISITOR >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<unsigned char D = 2, class VISITOR = IdleGraphVisitor<std::size_t>>
class andres::graph::GridGraph< D, VISITOR >