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.

	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. 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).

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).

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).

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).

EdgeType &	EdgeFromId (const EdgeId &_id)
	Get a mutable reference to an edge using its Id.

const EdgeType &	EdgeFromId (const EdgeId &_id) const
	Get a reference to an edge using its Id.

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.

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. 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.

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. 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.

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.

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 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

// 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]

template<typename V , typename E , typename EdgeType >

Graph ( )

default

Default constructor.

◆ Graph() [2/2]

template<typename V , typename E , typename EdgeType >

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

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()

template<typename V , typename E , typename EdgeType >

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

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 Graph< V, E, EdgeType >::Graph().

◆ AddVertex()

template<typename V , typename E , typename EdgeType >

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

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 Graph< V, E, EdgeType >::Graph().

◆ AdjacentsFrom() [1/2]

template<typename V , typename E , typename EdgeType >

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] _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().

◆ AdjacentsFrom() [2/2]

template<typename V , typename E , typename EdgeType >

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] _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(), gz::math::graph::kNullId, std::make_pair(), and Graph< V, E, EdgeType >::VertexFromId().

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

◆ AdjacentsTo() [1/2]

template<typename V , typename E , typename EdgeType >

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] _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().

◆ AdjacentsTo() [2/2]

template<typename V , typename E , typename EdgeType >

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] _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(), Graph< V, E, EdgeType >::IncidentsTo(), std::make_pair(), and Graph< V, E, EdgeType >::VertexFromId().

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

◆ EdgeFromId() [1/2]

template<typename V , typename E , typename EdgeType >

EdgeType & EdgeFromId ( const EdgeId & _id )

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]

template<typename V , typename E , typename EdgeType >

const EdgeType & EdgeFromId ( const EdgeId & _id ) const

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()

template<typename V , typename E , typename EdgeType >

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]	_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 >::end(), and map< K, T >::find().

◆ Edges()

template<typename V , typename E , typename EdgeType >

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(), and std::make_pair().

◆ Empty()

template<typename V , typename E , typename EdgeType >

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]

template<typename V , typename E , typename EdgeType >

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

inline

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 Graph< V, E, EdgeType >::IncidentsFrom().

◆ IncidentsFrom() [2/2]

template<typename V , typename E , typename EdgeType >

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

inline

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(), gz::math::graph::kNullId, and std::make_pair().

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

◆ IncidentsTo() [1/2]

template<typename V , typename E , typename EdgeType >

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

inline

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 Graph< V, E, EdgeType >::IncidentsTo().

◆ IncidentsTo() [2/2]

template<typename V , typename E , typename EdgeType >

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

inline

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(), 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(), Graph< V, E, EdgeType >::InDegree(), and Graph< V, E, EdgeType >::RemoveVertex().

◆ InDegree() [1/2]

template<typename V , typename E , typename EdgeType >

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

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 Graph< V, E, EdgeType >::IncidentsTo(), and Graph< V, E, EdgeType >::VertexFromId().

◆ InDegree() [2/2]

template<typename V , typename E , typename EdgeType >

size_t InDegree ( const VertexId & _vertex ) const

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()

template<typename V , typename E , typename EdgeType >

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] _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]

template<typename V , typename E , typename EdgeType >

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

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 Graph< V, E, EdgeType >::IncidentsFrom(), and Graph< V, E, EdgeType >::VertexFromId().

◆ OutDegree() [2/2]

template<typename V , typename E , typename EdgeType >

size_t OutDegree ( const VertexId & _vertex ) const

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]

template<typename V , typename E , typename EdgeType >

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] _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]

template<typename V , typename E , typename EdgeType >

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] _edge The edge to be removed.