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. | |
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
|
default |
Default constructor.
|
inline |
Constructor.
[in] | _vertices | Collection of vertices. |
[in] | _edges | Collection of edges. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddEdge(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddVertex().
|
inline |
Add a new edge to the graph.
[in] | _vertices | The set of Ids of the two vertices. |
[in] | _data | User data. |
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().
|
inline |
Add a new vertex to the graph.
[in] | _name | Name of the vertex. It doesn't have to be unique. |
[in] | _data | Data to be stored in the vertex. |
[in] | _id | Optional Id to be used for this vertex. This Id must be unique. |
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().
|
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.
[in] | _vertex | The Id of the vertex from which adjacent vertices will be returned. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id().
|
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.
[in] | _vertex | The Id of the vertex from which adjacent vertices will be returned. |
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().
|
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).
[in] | _vertex | The vertex to check adjacentsTo. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsTo(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id().
|
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).
[in] | _vertex | The Id of the vertex to check adjacentsTo. |
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().
|
inline |
Get a reference to an edge using its Id.
[in] | _id | The Id of the edge. |
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsTo(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo().
|
inline |
The collection of all edges in the graph.
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().
|
inline |
Get whether the graph is empty.
|
inline |
Get the set of outgoing edges from a given vertex.
[in] | _vertex | The vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom().
|
inline |
Get the set of outgoing edges from a given vertex.
[in] | _vertex | Id of the vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::EdgeFromId(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId.
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Dijkstra(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::OutDegree(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::OutDegree(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex().
|
inline |
Get the set of incoming edges to a given vertex.
[in] | _vertex | The vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo().
|
inline |
Get the set of incoming edges to a given vertex.
[in] | _vertex | Id of the vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::EdgeFromId(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId.
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsTo(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::InDegree(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::InDegree(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex().
|
inline |
Get the number of edges incident to a vertex.
[in] | _vertex | The vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), 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().
|
inline |
Get the number of edges incident to a vertex.
[in] | _vertex | The vertex Id. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo().
|
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.
[in] | _edge | An edge to copy into the graph. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::kNullId.
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddEdge().
|
inline |
Get the number of edges incident from a vertex.
[in] | _vertex | The vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::VertexFromId().
|
inline |
Get the number of edges incident from a vertex.
[in] | _vertex | The vertex Id. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom().
|
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.
[in] | _edge | Id of the edge to be removed. |
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().
|
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.
[in] | _edge | The edge to be removed. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveEdge().
|
inline |
Remove an existing vertex from the graph.
[in] | _vertex | Id of the vertex to be removed. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveEdge().
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertices().
|
inline |
Remove an existing vertex from the graph.
[in] | _vertex | The vertex to be removed. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Id(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex().
|
inline |
Remove all vertices with name == _name.
[in] | _name | Name of the vertices to be removed. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveVertex().
|
inline |
Get a mutable reference to a vertex using its Id.
[in] | _id | The Id of the vertex. |
|
inline |
Get a reference to a vertex using its Id.
[in] | _id | The Id of the vertex. |
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsTo(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::BreadthFirstSort(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::DepthFirstSort(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::InDegree(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::OutDegree().
|
inline |
The collection of all vertices in the graph.
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::BreadthFirstSort(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::ConnectedComponents(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::DepthFirstSort(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Dijkstra().
|
inline |
The collection of all vertices in the graph with name == _name.
|
protected |
The next edge Id to be assigned to a new edge.
|
protected |
The next vertex Id to be assigned to a new vertex.