Loading...
Searching...
No Matches
ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType > Class Template Reference

A generic graph class. More...

#include <Graph.hh>

Public Member Functions

 Graph ()=default
 Default constructor.
 
 Graph (const std::vector< Vertex< V > > &_vertices, const std::vector< EdgeInitializer< E > > &_edges)
 Constructor.
 
EdgeType & AddEdge (const VertexId_P &_vertices, const E &_data, const double _weight=1.0)
 Add a new edge to the graph.
 
Vertex< V > & AddVertex (const std::string &_name, const V &_data, const VertexId &_id=kNullId)
 Add a new vertex to the graph.
 
VertexRef_M< V > AdjacentsFrom (const Vertex< V > &_vertex) const
 Get all vertices that are directly connected with one edge from a given vertex.
 
VertexRef_M< V > AdjacentsFrom (const VertexId &_vertex) const
 Get all vertices that are directly connected with one edge from a given vertex.
 
VertexRef_M< V > AdjacentsTo (const Vertex< V > &_vertex) const
 Get all vertices that are directly connected with one edge to a given vertex.
 
VertexRef_M< V > AdjacentsTo (const VertexId &_vertex) const
 Get all vertices that are directly connected with one edge to a given vertex.
 
const EdgeType & EdgeFromId (const EdgeId &_id) const
 Get a reference to an edge using its Id.
 
const EdgeRef_M< EdgeType > Edges () const
 The collection of all edges in the graph.
 
bool Empty () const
 Get whether the graph is empty.
 
const EdgeRef_M< EdgeType > IncidentsFrom (const Vertex< V > &_vertex) const
 Get the set of outgoing edges from a given vertex.
 
const EdgeRef_M< EdgeType > IncidentsFrom (const VertexId &_vertex) const
 Get the set of outgoing edges from a given vertex.
 
const EdgeRef_M< EdgeType > IncidentsTo (const Vertex< V > &_vertex) const
 Get the set of incoming edges to a given vertex.
 
const EdgeRef_M< EdgeType > IncidentsTo (const VertexId &_vertex) const
 Get the set of incoming edges to a given vertex.
 
size_t InDegree (const Vertex< V > &_vertex) const
 Get the number of edges incident to a vertex.
 
size_t InDegree (const VertexId &_vertex) const
 Get the number of edges incident to a vertex.
 
EdgeType & LinkEdge (const EdgeType &_edge)
 Links an edge to the graph.
 
size_t OutDegree (const Vertex< V > &_vertex) const
 Get the number of edges incident from a vertex.
 
size_t OutDegree (const VertexId &_vertex) const
 Get the number of edges incident from a vertex.
 
bool RemoveEdge (const EdgeId &_edge)
 Remove an existing edge from the graph.
 
bool RemoveEdge (EdgeType &_edge)
 Remove an existing edge from the graph.
 
bool RemoveVertex (const VertexId &_vertex)
 Remove an existing vertex from the graph.
 
bool RemoveVertex (Vertex< V > &_vertex)
 Remove an existing vertex from the graph.
 
size_t RemoveVertices (const std::string &_name)
 Remove all vertices with name == _name.
 
Vertex< V > & VertexFromId (const VertexId &_id)
 Get a mutable reference to a vertex using its Id.
 
const Vertex< V > & VertexFromId (const VertexId &_id) const
 Get a reference to a vertex using its Id.
 
const VertexRef_M< V > Vertices () const
 The collection of all vertices in the graph.
 
const VertexRef_M< V > Vertices (const std::string &_name) const
 The collection of all vertices in the graph with name == _name.
 

Protected Attributes

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

Detailed Description

template<typename V, typename E, typename EdgeType>
class ignition::math::IGNITION_MATH_VERSION_NAMESPACE::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.
ignition::math::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.
ignition::math::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.
ignition::math::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.
ignition::math::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]

template<typename V , typename E , typename EdgeType >
ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Graph ( )
default

Default constructor.

◆ Graph() [2/2]

template<typename V , typename E , typename EdgeType >
ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Graph ( const std::vector< Vertex< V > > & _vertices,
const std::vector< EdgeInitializer< E > > & _edges )
inline

Member Function Documentation

◆ AddEdge()

template<typename V , typename E , typename EdgeType >
EdgeType & ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, 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.
Returns
Reference to the new edge created or NullEdge if the edge was not created (e.g. incorrect vertices).

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

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

◆ AddVertex()

template<typename V , typename E , typename EdgeType >
Vertex< V > & ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId.

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

◆ AdjacentsFrom() [1/2]

template<typename V , typename E , typename EdgeType >
VertexRef_M< V > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id().

◆ AdjacentsFrom() [2/2]

template<typename V , typename E , typename EdgeType >
VertexRef_M< V > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::EdgeFromId(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId, and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::VertexFromId().

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

◆ AdjacentsTo() [1/2]

template<typename V , typename E , typename EdgeType >
VertexRef_M< V > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsTo(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id().

◆ AdjacentsTo() [2/2]

template<typename V , typename E , typename EdgeType >
VertexRef_M< V > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::EdgeFromId(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::VertexFromId().

Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsTo().

◆ EdgeFromId()

template<typename V , typename E , typename EdgeType >
const EdgeType & ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::EdgeFromId ( const EdgeId & _id) const
inline

◆ Edges()

template<typename V , typename E , typename EdgeType >
const EdgeRef_M< EdgeType > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, 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.

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

◆ Empty()

template<typename V , typename E , typename EdgeType >
bool ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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]

template<typename V , typename E , typename EdgeType >
const EdgeRef_M< EdgeType > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, 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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom().

◆ IncidentsFrom() [2/2]

template<typename V , typename E , typename EdgeType >
const EdgeRef_M< EdgeType > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom ( const VertexId & _vertex) const
inline

◆ IncidentsTo() [1/2]

template<typename V , typename E , typename EdgeType >
const EdgeRef_M< EdgeType > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, 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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo().

◆ IncidentsTo() [2/2]

◆ InDegree() [1/2]

template<typename V , typename E , typename EdgeType >
size_t ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::InDegree ( const Vertex< V > & _vertex) const
inline

◆ InDegree() [2/2]

template<typename V , typename E , typename EdgeType >
size_t ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo().

◆ LinkEdge()

template<typename V , typename E , typename EdgeType >
EdgeType & ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, 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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId.

Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddEdge().

◆ OutDegree() [1/2]

template<typename V , typename E , typename EdgeType >
size_t ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::OutDegree ( const Vertex< V > & _vertex) const
inline

◆ OutDegree() [2/2]

template<typename V , typename E , typename EdgeType >
size_t ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom().

◆ RemoveEdge() [1/2]

template<typename V , typename E , typename EdgeType >
bool ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId.

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

◆ RemoveEdge() [2/2]

template<typename V , typename E , typename EdgeType >
bool ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveEdge().

◆ RemoveVertex() [1/2]

◆ RemoveVertex() [2/2]

template<typename V , typename E , typename EdgeType >
bool ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex().

◆ RemoveVertices()

template<typename V , typename E , typename EdgeType >
size_t ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex().

◆ VertexFromId() [1/2]

template<typename V , typename E , typename EdgeType >
Vertex< V > & ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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.

◆ VertexFromId() [2/2]

◆ Vertices() [1/2]

template<typename V , typename E , typename EdgeType >
const VertexRef_M< V > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Vertices ( ) const
inline

◆ Vertices() [2/2]

template<typename V , typename E , typename EdgeType >
const VertexRef_M< V > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::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.

Member Data Documentation

◆ nextEdgeId

template<typename V , typename E , typename EdgeType >
VertexId ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::nextEdgeId = 0u
protected

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

◆ nextVertexId

template<typename V , typename E , typename EdgeType >
VertexId ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::nextVertexId = 0u
protected

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


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