Ignition Math

API Reference

6.9.3~pre2
Graph< V, E, EdgeType > Class Template Reference

A generic graph class. Both vertices and edges can store user information. A vertex could be created passing a custom Id if needed, otherwise it will be choosen internally. The vertices also have a name that could be reused among other vertices if needed. This class supports the use of different edge types (e.g. directed or undirected edges). More...

#include <Graph.hh>

Public Member Functions

 Graph ()=default
 Default constructor. More...
 
 Graph (const std::vector< Vertex< V >> &_vertices, const std::vector< EdgeInitializer< E >> &_edges)
 Constructor. More...
 
EdgeType & AddEdge (const VertexId_P &_vertices, const E &_data, const double _weight=1.0)
 Add a new edge to the graph. More...
 
Vertex< V > & AddVertex (const std::string &_name, const V &_data, const VertexId &_id=kNullId)
 Add a new vertex to the graph. More...
 
VertexRef_M< V > AdjacentsFrom (const VertexId &_vertex) const
 Get all vertices that are directly connected with one edge from a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex). E.g. j is adjacent from i (the given vertex) if there is an edge (i->j). More...
 
VertexRef_M< V > AdjacentsFrom (const Vertex< V > &_vertex) const
 Get all vertices that are directly connected with one edge from a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex). E.g. j is adjacent from i (the given vertex) if there is an edge (i->j). More...
 
VertexRef_M< V > AdjacentsTo (const VertexId &_vertex) const
 Get all vertices that are directly connected with one edge to a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex). More...
 
VertexRef_M< V > AdjacentsTo (const Vertex< V > &_vertex) const
 Get all vertices that are directly connected with one edge to a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex). More...
 
const EdgeType & EdgeFromId (const EdgeId &_id) const
 Get a reference to an edge using its Id. More...
 
const EdgeType & EdgeFromVertices (const VertexId _sourceId, const VertexId _destId) const
 Get a reference to an edge based on two vertices. A NullEdge object reference is returned if an edge with the two vertices is not found. If there are multiple edges that match the provided vertices, then first is returned. More...
 
const EdgeRef_M< EdgeType > Edges () const
 The collection of all edges in the graph. More...
 
bool Empty () const
 Get whether the graph is empty. More...
 
const EdgeRef_M< EdgeType > IncidentsFrom (const VertexId &_vertex) const
 Get the set of outgoing edges from a given vertex. More...
 
const EdgeRef_M< EdgeType > IncidentsFrom (const Vertex< V > &_vertex) const
 Get the set of outgoing edges from a given vertex. More...
 
const EdgeRef_M< EdgeType > IncidentsTo (const VertexId &_vertex) const
 Get the set of incoming edges to a given vertex. More...
 
const EdgeRef_M< EdgeType > IncidentsTo (const Vertex< V > &_vertex) const
 Get the set of incoming edges to a given vertex. More...
 
size_t InDegree (const VertexId &_vertex) const
 Get the number of edges incident to a vertex. More...
 
size_t InDegree (const Vertex< V > &_vertex) const
 Get the number of edges incident to a vertex. More...
 
EdgeType & LinkEdge (const EdgeType &_edge)
 Links an edge to the graph. This function verifies that the edge's two vertices exist in the graph, copies the edge into the graph's internal data structure, and returns a reference to this new edge. More...
 
size_t OutDegree (const VertexId &_vertex) const
 Get the number of edges incident from a vertex. More...
 
size_t OutDegree (const Vertex< V > &_vertex) const
 Get the number of edges incident from a vertex. More...
 
bool RemoveEdge (const EdgeId &_edge)
 Remove an existing edge from the graph. After the removal, it won't be possible to reach any of the vertices from the edge, unless there are other edges that connect the to vertices. More...
 
bool RemoveEdge (EdgeType &_edge)
 Remove an existing edge from the graph. After the removal, it won't be possible to reach any of the vertices from the edge, unless there are other edges that connect the to vertices. More...
 
bool RemoveVertex (const VertexId &_vertex)
 Remove an existing vertex from the graph. More...
 
bool RemoveVertex (Vertex< V > &_vertex)
 Remove an existing vertex from the graph. More...
 
size_t RemoveVertices (const std::string &_name)
 Remove all vertices with name == _name. More...
 
const Vertex< V > & VertexFromId (const VertexId &_id) const
 Get a reference to a vertex using its Id. More...
 
Vertex< V > & VertexFromId (const VertexId &_id)
 Get a mutable reference to a vertex using its Id. More...
 
const VertexRef_M< V > Vertices () const
 The collection of all vertices in the graph. More...
 
const VertexRef_M< V > Vertices (const std::string &_name) const
 The collection of all vertices in the graph with name == _name. More...
 

Protected Attributes

VertexId nextEdgeId = 0u
 The next edge Id to be assigned to a new edge. More...
 
VertexId nextVertexId = 0u
 The next vertex Id to be assigned to a new vertex. More...
 

Friends

template<typename VV , typename EE , typename EEdgeType >
std::ostreamoperator<< (std::ostream &_out, const Graph< VV, EE, EEdgeType > &_g)
 Stream insertion operator. The output uses DOT graph description language. More...
 

Detailed Description

template<typename V, typename E, typename EdgeType>
class ignition::math::graph::Graph< V, E, EdgeType >

A generic graph class. Both vertices and edges can store user information. A vertex could be created passing a custom Id if needed, otherwise it will be choosen internally. The vertices also have a name that could be reused among other vertices if needed. This class supports the use of different edge types (e.g. directed or undirected edges).

Example directed graph

// Create a directed graph that is capable of storing integer data in the
// vertices and double data on the edges.
graph::DirectedGraph<int, double> graph(
// Create the vertices, with default data and vertex ids.
{
{"vertex1"}, {"vertex2"}, {"vertex3"}
},
// Create the edges, with default data and weight values.
{
// Edge from vertex 0 to vertex 1. Each number refers to a vertex id.
// Vertex ids start from zero.
{{0, 1}}, {{1, 2}}
});
// You can assign data to vertices.
graph::DirectedGraph<int, double> graph2(
// Create the vertices, with custom data and default vertex ids.
{
{"vertex1", 1}, {"vertex2", 2}, {"vertex3", 10}
},
// Create the edges, with default data and weight values.
{
// Edge from vertex 0 to vertex 1. Each number refers to a vertex id
// specified above.
{{0, 2}}, {{1, 2}}
});
// It's also possible to specify vertex ids.
graph::DirectedGraph<int, double> graph3(
// Create the vertices with custom data and vertex ids.
{
{"vertex1", 1, 2}, {"vertex2", 2, 3}, {"vertex3", 10, 4}
},
// Create the edges, with custom data and default weight values.
{
{{2, 3}, 6.3}, {{3, 4}, 4.2}
});
// Finally, you can also assign weights to the edges.
graph::DirectedGraph<int, double> graph4(
// Create the vertices with custom data and vertex ids.
{
{"vertex1", 1, 2}, {"vertex2", 2, 3}, {"vertex3", 10, 4}
},
// Create the edges, with custom data and default weight values
{
{{2, 3}, 6.3, 1.1}, {{3, 4}, 4.2, 2.3}
});

Constructor & Destructor Documentation

◆ Graph() [1/2]

Graph ( )
default

Default constructor.

◆ Graph() [2/2]

Graph ( const std::vector< Vertex< V >> &  _vertices,
const std::vector< EdgeInitializer< E >> &  _edges 
)
inline

Constructor.

Parameters
[in]_verticesCollection of vertices.
[in]_edgesCollection of edges.

References Graph< V, E, EdgeType >::AddEdge(), Graph< V, E, EdgeType >::AddVertex(), and std::endl().

Member Function Documentation

◆ AddEdge()

EdgeType& AddEdge ( const VertexId_P _vertices,
const E &  _data,
const double  _weight = 1.0 
)
inline

Add a new edge to the graph.

Parameters
[in]_verticesThe set of Ids of the two vertices.
[in]_dataUser data.
[in]_weightEdge weight.
Returns
Reference to the new edge created or NullEdge if the edge was not created (e.g. incorrect vertices).

References std::endl(), ignition::math::graph::kNullId, Graph< V, E, EdgeType >::LinkEdge(), and std::move().

Referenced by ignition::math::graph::BreadthFirstSort(), ignition::math::graph::DepthFirstSort(), and Graph< V, E, EdgeType >::Graph().

◆ AddVertex()

Vertex<V>& AddVertex ( const std::string _name,
const V &  _data,
const VertexId _id = kNullId 
)
inline

Add a new vertex to the graph.

Parameters
[in]_nameName of the vertex. It doesn't have to be unique.
[in]_dataData to be stored in the vertex.
[in]_idOptional Id to be used for this vertex. This Id must be unique.
Returns
A reference to the new vertex.

References std::endl(), multimap< K, T >::insert(), ignition::math::graph::kNullId, and std::make_pair().

Referenced by ignition::math::graph::BreadthFirstSort(), ignition::math::graph::DepthFirstSort(), and Graph< V, E, EdgeType >::Graph().

◆ AdjacentsFrom() [1/2]

VertexRef_M<V> AdjacentsFrom ( const VertexId _vertex) const
inline

Get all vertices that are directly connected with one edge from a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex). E.g. j is adjacent from i (the given vertex) if there is an edge (i->j).

In an undirected graph, the result of this function will match the result provided by AdjacentsTo.

Parameters
[in]_vertexThe Id of the vertex from which adjacent vertices will be returned.
Returns
A map of vertices, where keys are Ids and values are references to the vertices. This is the set of adjacent vertices. An empty map will be returned when the _vertex is not found in the graph.

References std::cref(), Graph< V, E, EdgeType >::EdgeFromId(), map< K, T >::emplace(), ignition::math::graph::kNullId, std::make_pair(), and Graph< V, E, EdgeType >::VertexFromId().

Referenced by Graph< V, E, EdgeType >::AdjacentsFrom(), ignition::math::graph::BreadthFirstSort(), and ignition::math::graph::DepthFirstSort().

◆ AdjacentsFrom() [2/2]

VertexRef_M<V> AdjacentsFrom ( const Vertex< V > &  _vertex) const
inline

Get all vertices that are directly connected with one edge from a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex). E.g. j is adjacent from i (the given vertex) if there is an edge (i->j).

In an undirected graph, the result of this function will match the result provided by AdjacentsTo.

Parameters
[in]_vertexThe Id of the vertex from which adjacent vertices will be returned.
Returns
A map of vertices, where keys are Ids and values are references to the vertices. This is the set of adjacent vertices. An empty map will be returned when the _vertex is not found in the graph.

References Graph< V, E, EdgeType >::AdjacentsFrom(), and Vertex< V >::Id().

◆ AdjacentsTo() [1/2]

VertexRef_M<V> AdjacentsTo ( const VertexId _vertex) const
inline

Get all vertices that are directly connected with one edge to a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex).

In an undirected graph, the result of this function will match the result provided by AdjacentsFrom.

E.g. i is adjacent to j (the given vertex) if there is an edge (i->j).

Parameters
[in]_vertexThe Id of the vertex to check adjacentsTo.
Returns
A map of vertices, where keys are Ids and values are references to the vertices. An empty map is returned if the _vertex is not present in this graph, or when there are no adjacent vertices.

References std::cref(), Graph< V, E, EdgeType >::EdgeFromId(), map< K, T >::emplace(), Graph< V, E, EdgeType >::IncidentsTo(), std::make_pair(), and Graph< V, E, EdgeType >::VertexFromId().

Referenced by Graph< V, E, EdgeType >::AdjacentsTo().

◆ AdjacentsTo() [2/2]

VertexRef_M<V> AdjacentsTo ( const Vertex< V > &  _vertex) const
inline

Get all vertices that are directly connected with one edge to a given vertex. In other words, this function will return child vertices of the given vertex (all vertices from the given vertex).

In an undirected graph, the result of this function will match the result provided by AdjacentsFrom.

E.g. i is adjacent to j (the given vertex) if there is an edge (i->j).

Parameters
[in]_vertexThe vertex to check adjacentsTo.
Returns
A map of vertices, where keys are Ids and values are references to the vertices. An empty map is returned if the _vertex is not present in this graph, or when there are no adjacent vertices.

References Graph< V, E, EdgeType >::AdjacentsTo(), and Vertex< V >::Id().

◆ EdgeFromId()

const EdgeType& EdgeFromId ( const EdgeId _id) const
inline

◆ EdgeFromVertices()

const EdgeType& EdgeFromVertices ( const VertexId  _sourceId,
const VertexId  _destId 
) const
inline

Get a reference to an edge based on two vertices. A NullEdge object reference is returned if an edge with the two vertices is not found. If there are multiple edges that match the provided vertices, then first is returned.

Parameters
[in]_sourceIdSource vertex Id.
[in]_destIdDestination vertex Id.
Returns
A reference to the first edge found, or NullEdge if not found.

References map< K, T >::begin(), map< K, T >::end(), and map< K, T >::find().

◆ Edges()

const EdgeRef_M<EdgeType> Edges ( ) const
inline

The collection of all edges in the graph.

Returns
A map of edges, where keys are Ids and values are references to the edges.

References std::cref(), map< K, T >::emplace(), and std::make_pair().

Referenced by ignition::math::graph::BreadthFirstSort(), ignition::math::graph::ConnectedComponents(), ignition::math::graph::DepthFirstSort(), and ignition::math::graph::ToUndirectedGraph().

◆ Empty()

bool Empty ( ) const
inline

Get whether the graph is empty.

Returns
True when there are no vertices in the graph or false otherwise.

◆ IncidentsFrom() [1/2]

const EdgeRef_M<EdgeType> IncidentsFrom ( const VertexId _vertex) const
inline

Get the set of outgoing edges from a given vertex.

Parameters
[in]_vertexId of the vertex.
Returns
A map of edges, where keys are Ids and values are references to the edges. An empty map is returned when the provided vertex does not exist, or when there are no outgoing edges.

References std::cref(), Graph< V, E, EdgeType >::EdgeFromId(), map< K, T >::emplace(), ignition::math::graph::kNullId, and std::make_pair().

Referenced by ignition::math::graph::Dijkstra(), Graph< V, E, EdgeType >::IncidentsFrom(), Graph< V, E, EdgeType >::OutDegree(), and Graph< V, E, EdgeType >::RemoveVertex().

◆ IncidentsFrom() [2/2]

const EdgeRef_M<EdgeType> IncidentsFrom ( const Vertex< V > &  _vertex) const
inline

Get the set of outgoing edges from a given vertex.

Parameters
[in]_vertexThe vertex.
Returns
A map of edges, where keys are Ids and values are references to the edges. An empty map is returned when the provided vertex does not exist, or when there are no outgoing edges.

References Vertex< V >::Id(), and Graph< V, E, EdgeType >::IncidentsFrom().

◆ IncidentsTo() [1/2]

const EdgeRef_M<EdgeType> IncidentsTo ( const VertexId _vertex) const
inline

Get the set of incoming edges to a given vertex.

Parameters
[in]_vertexId of the vertex.
Returns
A map of edges, where keys are Ids and values are references to the edges. An empty map is returned when the provided vertex does not exist, or when there are no incoming edges.

References std::cref(), Graph< V, E, EdgeType >::EdgeFromId(), map< K, T >::emplace(), ignition::math::graph::kNullId, and std::make_pair().

Referenced by Graph< V, E, EdgeType >::AdjacentsTo(), Graph< V, E, EdgeType >::IncidentsTo(), Graph< V, E, EdgeType >::InDegree(), and Graph< V, E, EdgeType >::RemoveVertex().

◆ IncidentsTo() [2/2]

const EdgeRef_M<EdgeType> IncidentsTo ( const Vertex< V > &  _vertex) const
inline

Get the set of incoming edges to a given vertex.

Parameters
[in]_vertexThe vertex.
Returns
A map of edges, where keys are Ids and values are references to the edges. An empty map is returned when the provided vertex does not exist, or when there are no incoming edges.

References Vertex< V >::Id(), and Graph< V, E, EdgeType >::IncidentsTo().

◆ InDegree() [1/2]

size_t InDegree ( const VertexId _vertex) const
inline

Get the number of edges incident to a vertex.

Parameters
[in]_vertexThe vertex Id.
Returns
The number of edges incidents to a vertex.

References Graph< V, E, EdgeType >::IncidentsTo().

◆ InDegree() [2/2]

size_t InDegree ( const Vertex< V > &  _vertex) const
inline

Get the number of edges incident to a vertex.

Parameters
[in]_vertexThe vertex.
Returns
The number of edges incidents to a vertex.

References Vertex< V >::Id(), Graph< V, E, EdgeType >::IncidentsTo(), and Graph< V, E, EdgeType >::VertexFromId().

◆ LinkEdge()

EdgeType& LinkEdge ( const EdgeType &  _edge)
inline

Links an edge to the graph. This function verifies that the edge's two vertices exist in the graph, copies the edge into the graph's internal data structure, and returns a reference to this new edge.

Parameters
[in]_edgeAn edge to copy into the graph.
Returns
A reference to the new edge.

References map< K, T >::insert(), ignition::math::graph::kNullId, and std::make_pair().

Referenced by Graph< V, E, EdgeType >::AddEdge().

◆ OutDegree() [1/2]

size_t OutDegree ( const VertexId _vertex) const
inline

Get the number of edges incident from a vertex.

Parameters
[in]_vertexThe vertex Id.
Returns
The number of edges incidents from a vertex.

References Graph< V, E, EdgeType >::IncidentsFrom().

◆ OutDegree() [2/2]

size_t OutDegree ( const Vertex< V > &  _vertex) const
inline

Get the number of edges incident from a vertex.

Parameters
[in]_vertexThe vertex.
Returns
The number of edges incidents from a vertex.

References Vertex< V >::Id(), Graph< V, E, EdgeType >::IncidentsFrom(), and Graph< V, E, EdgeType >::VertexFromId().

◆ RemoveEdge() [1/2]

bool RemoveEdge ( const EdgeId _edge)
inline

Remove an existing edge from the graph. After the removal, it won't be possible to reach any of the vertices from the edge, unless there are other edges that connect the to vertices.

Parameters
[in]_edgeId of the edge to be removed.
Returns
True when the edge was removed or false otherwise.

References map< K, T >::end(), map< K, T >::erase(), map< K, T >::find(), and ignition::math::graph::kNullId.

Referenced by Graph< V, E, EdgeType >::RemoveEdge(), and Graph< V, E, EdgeType >::RemoveVertex().

◆ RemoveEdge() [2/2]

bool RemoveEdge ( EdgeType &  _edge)
inline

Remove an existing edge from the graph. After the removal, it won't be possible to reach any of the vertices from the edge, unless there are other edges that connect the to vertices.

Parameters
[in]_edgeThe edge to be removed.
Returns
True when the edge was removed or false otherwise.

References Graph< V, E, EdgeType >::RemoveEdge().

◆ RemoveVertex() [1/2]

bool RemoveVertex ( const VertexId _vertex)
inline

Remove an existing vertex from the graph.

Parameters
[in]_vertexId of the vertex to be removed.
Returns
True when the vertex was removed or false otherwise.

References multimap< K, T >::equal_range(), multimap< K, T >::erase(), Graph< V, E, EdgeType >::IncidentsFrom(), Graph< V, E, EdgeType >::IncidentsTo(), and Graph< V, E, EdgeType >::RemoveEdge().

Referenced by Graph< V, E, EdgeType >::RemoveVertex(), and Graph< V, E, EdgeType >::RemoveVertices().

◆ RemoveVertex() [2/2]

bool RemoveVertex ( Vertex< V > &  _vertex)
inline

Remove an existing vertex from the graph.

Parameters
[in]_vertexThe vertex to be removed.
Returns
True when the vertex was removed or false otherwise.

References Vertex< V >::Id(), and Graph< V, E, EdgeType >::RemoveVertex().

◆ RemoveVertices()

size_t RemoveVertices ( const std::string _name)
inline

Remove all vertices with name == _name.

Parameters
[in]_nameName of the vertices to be removed.
Returns
The number of vertices removed.

References multimap< K, T >::count(), multimap< K, T >::find(), and Graph< V, E, EdgeType >::RemoveVertex().

◆ VertexFromId() [1/2]

const Vertex<V>& VertexFromId ( const VertexId _id) const
inline

Get a reference to a vertex using its Id.

Parameters
[in]_idThe Id of the vertex.
Returns
A reference to the vertex with Id = _id or NullVertex if not found.

Referenced by Graph< V, E, EdgeType >::AdjacentsFrom(), Graph< V, E, EdgeType >::AdjacentsTo(), ignition::math::graph::BreadthFirstSort(), ignition::math::graph::DepthFirstSort(), Graph< V, E, EdgeType >::InDegree(), and Graph< V, E, EdgeType >::OutDegree().

◆ VertexFromId() [2/2]

Vertex<V>& VertexFromId ( const VertexId _id)
inline

Get a mutable reference to a vertex using its Id.

Parameters
[in]_idThe Id of the vertex.
Returns
A mutable reference to the vertex with Id = _id or NullVertex if not found.

◆ Vertices() [1/2]

const VertexRef_M<V> Vertices ( ) const
inline

The collection of all vertices in the graph.

Returns
A map of vertices, where keys are Ids and values are references to the vertices.

References std::cref(), map< K, T >::emplace(), and std::make_pair().

Referenced by ignition::math::graph::BreadthFirstSort(), ignition::math::graph::ConnectedComponents(), ignition::math::graph::DepthFirstSort(), ignition::math::graph::Dijkstra(), and ignition::math::graph::ToUndirectedGraph().

◆ Vertices() [2/2]

const VertexRef_M<V> Vertices ( const std::string _name) const
inline

The collection of all vertices in the graph with name == _name.

Returns
A map of vertices, where keys are Ids and values are references to the vertices.

References std::cref(), map< K, T >::emplace(), and std::make_pair().

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<< ( std::ostream _out,
const Graph< VV, EE, EEdgeType > &  _g 
)
friend

Stream insertion operator. The output uses DOT graph description language.

Parameters
[out]_outThe output stream.
[in]_gGraph to write to the stream.
See also
https://en.wikipedia.org/wiki/DOT_(graph_description_language).

Referenced by Graph< V, E, EdgeType >::EdgeFromId().

Member Data Documentation

◆ nextEdgeId

VertexId nextEdgeId = 0u
protected

The next edge Id to be assigned to a new edge.

Referenced by Graph< V, E, EdgeType >::EdgeFromId().

◆ nextVertexId

VertexId nextVertexId = 0u
protected

The next vertex Id to be assigned to a new vertex.

Referenced by Graph< V, E, EdgeType >::EdgeFromId().


The documentation for this class was generated from the following file: