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 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 > | 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 > | 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... | |
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... | |
EdgeType & | EdgeFromId (const EdgeId &_id) |
Get a mutable reference to an edge using its Id. 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 Vertex< V > &_vertex) const |
Get the set of outgoing edges from a given vertex. 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 > | IncidentsTo (const Vertex< V > &_vertex) const |
Get the set of incoming edges to a given vertex. More... | |
const EdgeRef_M< EdgeType > | IncidentsTo (const VertexId &_vertex) const |
Get the set of incoming edges to a given vertex. More... | |
size_t | InDegree (const Vertex< V > &_vertex) const |
Get the number of edges incident to a vertex. More... | |
size_t | InDegree (const VertexId &_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 Vertex< V > &_vertex) const |
Get the number of edges incident from a vertex. More... | |
size_t | OutDegree (const VertexId &_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... | |
Vertex< V > & | VertexFromId (const VertexId &_id) |
Get a mutable reference to a vertex using its Id. More... | |
const Vertex< V > & | VertexFromId (const VertexId &_id) const |
Get a 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... | |
Detailed Description
template<typename V, typename E, typename EdgeType>
class gz::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
Constructor & Destructor Documentation
◆ Graph() [1/2]
|
default |
Default constructor.
◆ Graph() [2/2]
|
inline |
Constructor.
- Parameters
-
[in] _vertices Collection of vertices. [in] _edges Collection of edges.
References Graph< V, E, EdgeType >::AddEdge(), Graph< V, E, EdgeType >::AddVertex(), and std::endl().
Member Function Documentation
◆ AddEdge()
|
inline |
Add a new edge to the graph.
- Parameters
-
[in] _vertices The set of Ids of the two vertices. [in] _data User data. [in] _weight Edge weight.
- Returns
- Reference to the new edge created or NullEdge if the edge was not created (e.g. incorrect vertices).
References std::endl(), gz::math::graph::kNullId, Graph< V, E, EdgeType >::LinkEdge(), and std::move().
Referenced by gz::math::graph::BreadthFirstSort(), gz::math::graph::DepthFirstSort(), and Graph< V, E, EdgeType >::Graph().
◆ AddVertex()
|
inline |
Add a new vertex to the graph.
- Parameters
-
[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.
- Returns
- A reference to the new vertex.
References std::endl(), multimap< K, T >::insert(), gz::math::graph::kNullId, and std::make_pair().
Referenced by gz::math::graph::BreadthFirstSort(), gz::math::graph::DepthFirstSort(), and Graph< V, E, EdgeType >::Graph().
◆ AdjacentsFrom() [1/2]
|
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] _vertex The 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().
◆ AdjacentsFrom() [2/2]
|
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] _vertex The 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(), gz::math::graph::kNullId, std::make_pair(), and Graph< V, E, EdgeType >::VertexFromId().
Referenced by Graph< V, E, EdgeType >::AdjacentsFrom(), gz::math::graph::BreadthFirstSort(), and gz::math::graph::DepthFirstSort().
◆ AdjacentsTo() [1/2]
|
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] _vertex 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 Graph< V, E, EdgeType >::AdjacentsTo(), and Vertex< V >::Id().
◆ AdjacentsTo() [2/2]
|
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] _vertex The 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().
◆ EdgeFromId() [1/2]
|
inline |
Get a mutable reference to an edge using its Id.
- Parameters
-
[in] _id The Id of the edge.
- Returns
- A mutable reference to the edge with Id = _id or NullEdge if not found.
References map< K, T >::end(), and map< K, T >::find().
◆ EdgeFromId() [2/2]
|
inline |
Get a reference to an edge using its Id.
- Parameters
-
[in] _id The Id of the edge.
- Returns
- A reference to the edge with Id = _id or NullEdge if not found.
References map< K, T >::end(), and map< K, T >::find().
Referenced by Graph< V, E, EdgeType >::AdjacentsFrom(), Graph< V, E, EdgeType >::AdjacentsTo(), Graph< V, E, EdgeType >::IncidentsFrom(), and Graph< V, E, EdgeType >::IncidentsTo().
◆ EdgeFromVertices()
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] _sourceId Source vertex Id. [in] _destId Destination 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()
|
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 gz::math::graph::BreadthFirstSort(), gz::math::graph::ConnectedComponents(), gz::math::graph::DepthFirstSort(), and gz::math::graph::ToUndirectedGraph().
◆ Empty()
|
inline |
Get whether the graph is empty.
- Returns
- True when there are no vertices in the graph or false otherwise.
◆ IncidentsFrom() [1/2]
Get the set of outgoing edges from a given vertex.
- Parameters
-
[in] _vertex 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 Vertex< V >::Id(), and Graph< V, E, EdgeType >::IncidentsFrom().
◆ IncidentsFrom() [2/2]
Get the set of outgoing edges from a given vertex.
- Parameters
-
[in] _vertex Id 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(), gz::math::graph::kNullId, and std::make_pair().
Referenced by gz::math::graph::Dijkstra(), Graph< V, E, EdgeType >::IncidentsFrom(), Graph< V, E, EdgeType >::OutDegree(), and Graph< V, E, EdgeType >::RemoveVertex().
◆ IncidentsTo() [1/2]
Get the set of incoming edges to a given vertex.
- Parameters
-
[in] _vertex 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 Vertex< V >::Id(), and Graph< V, E, EdgeType >::IncidentsTo().
◆ IncidentsTo() [2/2]
Get the set of incoming edges to a given vertex.
- Parameters
-
[in] _vertex Id 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(), gz::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().
◆ InDegree() [1/2]
|
inline |
Get the number of edges incident to a vertex.
- Parameters
-
[in] _vertex The 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().
◆ InDegree() [2/2]
|
inline |
Get the number of edges incident to a vertex.
- Parameters
-
[in] _vertex The vertex Id.
- Returns
- The number of edges incidents to a vertex.
References Graph< V, E, EdgeType >::IncidentsTo().
◆ LinkEdge()
|
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] _edge An edge to copy into the graph.
- Returns
- A reference to the new edge.
References map< K, T >::insert(), gz::math::graph::kNullId, and std::make_pair().
Referenced by Graph< V, E, EdgeType >::AddEdge().
◆ OutDegree() [1/2]
|
inline |
Get the number of edges incident from a vertex.
- Parameters
-
[in] _vertex The 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().
◆ OutDegree() [2/2]
|
inline |
Get the number of edges incident from a vertex.
- Parameters
-
[in] _vertex The vertex Id.
- Returns
- The number of edges incidents from a vertex.
References Graph< V, E, EdgeType >::IncidentsFrom().
◆ RemoveEdge() [1/2]
|
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] _edge Id 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 gz::math::graph::kNullId.
Referenced by Graph< V, E, EdgeType >::RemoveEdge(), and Graph< V, E, EdgeType >::RemoveVertex().
◆ RemoveEdge() [2/2]
|
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] _edge The edge to be removed.
- Returns
- True when the edge was removed or false otherwise.
References Graph< V, E, EdgeType >::RemoveEdge().
◆ RemoveVertex() [1/2]
|
inline |
Remove an existing vertex from the graph.
- Parameters
-
[in] _vertex Id 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]
|
inline |
Remove an existing vertex from the graph.
- Parameters
-
[in] _vertex The 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()
|
inline |
Remove all vertices with name == _name.
- Parameters
-
[in] _name Name 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]
Get a mutable reference to a vertex using its Id.
- Parameters
-
[in] _id The Id of the vertex.
- Returns
- A mutable reference to the vertex with Id = _id or NullVertex if not found.
◆ VertexFromId() [2/2]
Get a reference to a vertex using its Id.
- Parameters
-
[in] _id The 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(), gz::math::graph::BreadthFirstSort(), gz::math::graph::DepthFirstSort(), Graph< V, E, EdgeType >::InDegree(), and Graph< V, E, EdgeType >::OutDegree().
◆ Vertices() [1/2]
|
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 gz::math::graph::BreadthFirstSort(), gz::math::graph::ConnectedComponents(), gz::math::graph::DepthFirstSort(), gz::math::graph::Dijkstra(), and gz::math::graph::ToUndirectedGraph().
◆ Vertices() [2/2]
|
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().
Member Data Documentation
◆ nextEdgeId
|
protected |
The next edge Id to be assigned to a new edge.
◆ nextVertexId
|
protected |
The next vertex Id to be assigned to a new vertex.
The documentation for this class was generated from the following file: