Classes
class	DirectedEdge
	A directed edge represents a connection between two vertices. The connection is unidirectional, it's only possible to traverse the edge in one direction (from the tail to the head). More...

class	Edge
	Generic edge class. An edge has two ends and some constraint between them. For example, a directed edge only allows traversing the edge in one direction. More...

struct	EdgeInitializer
	Used in the Graph constructors for uniform initialization. More...

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

class	UndirectedEdge
	An undirected edge represents a connection between two vertices. The connection is bidirectional, it's possible to traverse the edge in both directions. More...

class	Vertex
	A vertex of a graph. It stores user information, an optional name, and keeps an internal unique Id. This class does not enforce to choose a unique name. More...

Typedefs
using	CostInfo = std::pair< double, VertexId >
	Used in Dijkstra. For a given source vertex, this pair represents the cost (first element) to reach a destination vertex (second element). More...

template<typename V , typename E >
using	DirectedGraph = Graph< V, E, DirectedEdge< E > >

using	EdgeId = uint64_t
	The unique Id for an edge. More...

using	EdgeId_S = std::set< EdgeId >

template<typename EdgeType >
using	EdgeRef_M = std::map< EdgeId, std::reference_wrapper< const EdgeType > >

template<typename V , typename E >
using	UndirectedGraph = Graph< V, E, UndirectedEdge< E > >

using	VertexId = uint64_t
	The unique Id of each vertex. More...

using	VertexId_P = std::pair< VertexId, VertexId >

template<typename V >
using	VertexRef_M = std::map< VertexId, std::reference_wrapper< const Vertex< V > >>

Functions
template<typename V , typename E , typename EdgeType >
std::pair< std::vector< VertexId >, bool >	Ancestors (const Graph< V, E, EdgeType > &_graph, const VertexId &_vertex)
	Walk parent edges from `_vertex` up to a root and return the chain of ancestors in walk order (immediate parent first, root last) together with a flag indicating whether the walk terminated cleanly at a root (no parent) or was aborted by the cycle guard. In a tree this returns the unique parent chain; in a more general directed graph it follows the first incoming edge at each step (deterministic via the adjacency-list ordering) and aborts on cycles. More...

template<typename V , typename E , typename EdgeType >
std::vector< VertexId >	BreadthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from)
	Breadth first sort (BFS). Starting from the vertex == _from, it traverses the graph exploring the neighbors first, before moving to the next level neighbors. More...

template<typename V , typename E >
std::vector< UndirectedGraph< V, E > >	ConnectedComponents (const UndirectedGraph< V, E > &_graph)
	Calculate the connected components of an undirected graph. A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. More...

template<typename V , typename E , typename EdgeType >
std::vector< VertexId >	DepthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from)
	Depth first sort (DFS). Starting from the vertex == _from, it visits the graph as far as possible along each branch before backtracking. More...

template<typename V , typename E , typename EdgeType >
std::unordered_set< VertexId >	DescendantsSet (const Graph< V, E, EdgeType > &_graph, const VertexId &_vertex)
	Set of all descendants of `_vertex` (including `_vertex` itself). Equivalent to BreadthFirstSort + insert-into-set, but avoids the intermediate vector copy. Matches the return shape downstream consumers (gz-sim's EntityComponentManager::Descendants) use. More...

template<typename V , typename E , typename EdgeType >
std::map< VertexId, CostInfo >	Dijkstra (const Graph< V, E, EdgeType > &_graph, const VertexId &_from, const VertexId &_to=kNullId)
	Dijkstra algorithm. Find the shortest path between the vertices in a graph. If only a graph and a source vertex is provided, the algorithm will find shortest paths from the source vertex to all other vertices in the graph. If an additional destination vertex is provided, the algorithm will stop when the shortest path is found between the source and destination vertex. More...

template<typename V , typename E , typename EdgeType >
bool	IsAncestor (const Graph< V, E, EdgeType > &_graph, const VertexId &_ancestor, const VertexId &_descendant)
	Test whether `_ancestor` lies on the parent chain above `_descendant`. O(depth) – walks `_descendant` up via Ancestors() and stops as soon as a match is found. Returns false for `_a == _d` (consistent with the strict ancestor relation). More...

template<typename V , typename E , typename EdgeType >
VertexId	LowestCommonAncestor (const Graph< V, E, EdgeType > &_graph, const VertexId &_a, const VertexId &_b)
	Lowest common ancestor of two vertices in a directed forest. Walks `_a` up to root collecting ancestors, then walks `_b` up until hitting one of those ancestors. O(depth_a + depth_b). More...

template<typename VV , typename EE >
std::ostream &	operator<< (std::ostream &_out, const Graph< VV, EE, DirectedEdge< EE >> &_g)
	Partial template specification for directed edges. More...

template<typename VV , typename EE >
std::ostream &	operator<< (std::ostream &_out, const Graph< VV, EE, UndirectedEdge< EE >> &_g)
	Partial template specification for undirected edges. More...

template<typename V , typename E , typename EdgeType >
Graph< V, E, EdgeType >	Subgraph (const Graph< V, E, EdgeType > &_graph, const VertexId &_root)
	Extract the subgraph induced by `_root` and all descendants reachable from it. Vertices and edges are copied (preserving ids, names, data, weights). All edges whose endpoints both lie in the reachable set are kept, including back-edges – so if the source graph contains cycles within the reachable region, the cycles are preserved in the result. Equivalent to "save just this entity and everything beneath it" – the shape of operation gz-sim and sdformat would invoke when serializing a single model out of a world. More...

template<typename V , typename E >
UndirectedGraph< V, E >	ToUndirectedGraph (const DirectedGraph< V, E > &_graph)
	Copy a DirectedGraph to an UndirectedGraph with the same vertices and edges. More...

Variables
static const VertexId	kNullId = MAX_UI64
	Represents an invalid Id. More...

Typedef Documentation

◆ CostInfo

CostInfo

Used in Dijkstra. For a given source vertex, this pair represents the cost (first element) to reach a destination vertex (second element).

◆ DirectedGraph

using DirectedGraph = Graph<V, E, DirectedEdge<E> >

◆ EdgeId

EdgeId

The unique Id for an edge.

◆ EdgeId_S

using EdgeId_S = std::set<EdgeId>

◆ EdgeRef_M

using EdgeRef_M = std::map<EdgeId, std::reference_wrapper<const EdgeType> >

◆ UndirectedGraph

using UndirectedGraph = Graph<V, E, UndirectedEdge<E> >

◆ VertexId

VertexId

The unique Id of each vertex.

◆ VertexId_P

using VertexId_P = std::pair<VertexId, VertexId>

◆ VertexRef_M

using VertexRef_M = std::map<VertexId, std::reference_wrapper<const Vertex<V> >>

Function Documentation

◆ Ancestors()

std::pair<std::vector<VertexId>, bool> ignition::math::graph::Ancestors	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_vertex
	)

Walk parent edges from _vertex up to a root and return the chain of ancestors in walk order (immediate parent first, root last) together with a flag indicating whether the walk terminated cleanly at a root (no parent) or was aborted by the cycle guard. In a tree this returns the unique parent chain; in a more general directed graph it follows the first incoming edge at each step (deterministic via the adjacency-list ordering) and aborts on cycles.

This subsumes the hand-coded "walk to root" loops widely seen in downstream code (e.g. gz-sim's worldPose / worldEntity / scopedName, sdformat's FrameSemantics::FindSourceVertex).

Parameters

[in]	_graph	Any graph (typically a directed forest/tree).
[in]	_vertex	Starting vertex.

Returns

A pair (chain, reachedRoot):

chain: vertex ids in walk order (parent, grandparent, ..., root). Empty if _vertex is invalid or has no parent.
reachedRoot: true if the walk terminated at a root (parent chain is complete). False if _vertex was invalid, or the walk was aborted because a previously visited vertex was reached again (cycle), in which case chain holds the partial path traversed up to the revisit.

References Graph< V, E, EdgeType >::AdjacentsTo(), unordered_set< K >::insert(), vector< T >::push_back(), and Graph< V, E, EdgeType >::VertexFromId().

Referenced by LowestCommonAncestor().

◆ BreadthFirstSort()

std::vector<VertexId> ignition::math::graph::BreadthFirstSort	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_from
	)

Breadth first sort (BFS). Starting from the vertex == _from, it traverses the graph exploring the neighbors first, before moving to the next level neighbors.

Parameters

[in]	_graph	A graph.
[in]	_from	The starting vertex.

Returns: The vector of vertices Ids traversed in a breadth first manner. An empty vector if _from is not a vertex of the graph.

References Graph< V, E, EdgeType >::AdjacentsFrom(), queue< T >::empty(), queue< T >::front(), unordered_set< K >::insert(), queue< T >::pop(), queue< T >::push(), vector< T >::push_back(), and Graph< V, E, EdgeType >::VertexFromId().

Referenced by ConnectedComponents(), and Subgraph().

◆ ConnectedComponents()

std::vector<UndirectedGraph<V, E> > ignition::math::graph::ConnectedComponents ( const UndirectedGraph< V, E > & _graph )

Calculate the connected components of an undirected graph. A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

See also: https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

Parameters

[in] _graph A graph.

Returns: A vector of graphs. Each element of the graph is a component (subgraph) of the original graph.

References BreadthFirstSort(), Graph< V, E, EdgeType >::Edges(), map< K, T >::end(), map< K, T >::find(), and Graph< V, E, EdgeType >::Vertices().

◆ DepthFirstSort()

std::vector<VertexId> ignition::math::graph::DepthFirstSort	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_from
	)

Depth first sort (DFS). Starting from the vertex == _from, it visits the graph as far as possible along each branch before backtracking.

Parameters

[in]	_graph	A graph.
[in]	_from	The starting vertex.

Returns: The vector of vertices Ids visited in a depth first manner. An empty vector if _from is not a vertex of the graph.

References Graph< V, E, EdgeType >::AdjacentsFrom(), unordered_set< K >::count(), stack< T >::empty(), unordered_set< K >::insert(), stack< T >::pop(), stack< T >::push(), vector< T >::push_back(), stack< T >::top(), and Graph< V, E, EdgeType >::VertexFromId().

◆ DescendantsSet()

std::unordered_set<VertexId> ignition::math::graph::DescendantsSet	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_vertex
	)

Set of all descendants of _vertex (including _vertex itself). Equivalent to BreadthFirstSort + insert-into-set, but avoids the intermediate vector copy. Matches the return shape downstream consumers (gz-sim's EntityComponentManager::Descendants) use.

Parameters

[in]	_graph	Source graph.
[in]	_vertex	Root vertex.

Returns: Set of vertex ids reachable from _vertex.

References Graph< V, E, EdgeType >::AdjacentsFrom(), queue< T >::empty(), queue< T >::front(), unordered_set< K >::insert(), queue< T >::pop(), queue< T >::push(), and Graph< V, E, EdgeType >::VertexFromId().

◆ Dijkstra()

std::map<VertexId, CostInfo> ignition::math::graph::Dijkstra	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_from,
		const VertexId &	_to = `kNullId`
	)

Dijkstra algorithm. Find the shortest path between the vertices in a graph. If only a graph and a source vertex is provided, the algorithm will find shortest paths from the source vertex to all other vertices in the graph. If an additional destination vertex is provided, the algorithm will stop when the shortest path is found between the source and destination vertex.

Parameters

[in]	_graph	A graph.
[in]	_from	The starting vertex.
[in]	_to	Optional destination vertex.

Returns: A map where the keys are the destination vertices. For each destination, the value is another pair, where the key is the shortest cost from the origin vertex. The value is the previous neighbor Id in the shortest path. Note: In the case of providing a destination vertex, only the entry in the map with key = _to should be used. The rest of the map may contain incomplete information. If you want all shortest paths to all other vertices, please remove the destination vertex. If the source or destination vertex don't exist, the function will return an empty map.

E.g.: Given the following undirected graph, g, with five vertices:

         (6)                |
      0-------1             |
      |      /|\            |
      |     / | \‍(5)        |
      | (2)/  |  \          |
      |   /   |   2         |
   (1)|  / (2)|  /          |
      | /     | /(5)        |
      |/      |/            |
      3-------4             |
         (1)                |

This is the resut of Dijkstra(g, 0):

================================
| Dst | Cost | Previous vertex |
================================
|  0  |  0   |        0        |
|  1  |  3   |        3        |
|  2  |  7   |        4        |
|  3  |  1   |        0        |
|  4  |  2   |        3        |
================================

This is the result of Dijkstra(g, 0, 3):

================================
| Dst | Cost | Previous vertex |
================================
|  0  |  0   |        0        |
|  1  |ignore|     ignore      |
|  2  |ignore|     ignore      |
|  3  |  1   |        0        |
|  4  |ignore|     ignore      |
================================

References std::endl(), Graph< V, E, EdgeType >::IncidentsFrom(), kNullId, std::make_pair(), ignition::math::MAX_D, and Graph< V, E, EdgeType >::Vertices().

◆ IsAncestor()

bool ignition::math::graph::IsAncestor	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_ancestor,
		const VertexId &	_descendant
	)

Test whether _ancestor lies on the parent chain above _descendant. O(depth) – walks _descendant up via Ancestors() and stops as soon as a match is found. Returns false for _a == _d (consistent with the strict ancestor relation).

Parameters

[in]	_graph	Any graph.
[in]	_ancestor	Candidate ancestor vertex id.
[in]	_descendant	Candidate descendant vertex id.

Returns: True if _ancestor is on the parent chain of _descendant.

References Graph< V, E, EdgeType >::AdjacentsTo(), unordered_set< K >::insert(), and Graph< V, E, EdgeType >::VertexFromId().

◆ LowestCommonAncestor()

VertexId ignition::math::graph::LowestCommonAncestor	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_a,
		const VertexId &	_b
	)

Lowest common ancestor of two vertices in a directed forest. Walks _a up to root collecting ancestors, then walks _b up until hitting one of those ancestors. O(depth_a + depth_b).

Useful for relative-frame computation: if two entities live in the same world tree, the LCA is the deepest shared frame, and a relative pose can be composed by chaining transforms a->LCA and LCA->b.

Parameters

[in]	_graph	A directed graph (expected to be a forest).
[in]	_a	One vertex.
[in]	_b	Another vertex.

Returns: The LCA vertex id, or kNullId if the two vertices share no common ancestor (different trees) or either is invalid. If _a == _b, returns _a.

References Ancestors(), unordered_set< K >::count(), unordered_set< K >::insert(), kNullId, and Graph< V, E, EdgeType >::VertexFromId().

◆ operator<<() [1/2]

std::ostream& ignition::math::graph::operator<<	(	std::ostream &	_out,
		const Graph< VV, EE, DirectedEdge< EE >> &	_g
	)

Partial template specification for directed edges.

References std::endl().

◆ operator<<() [2/2]

std::ostream& ignition::math::graph::operator<<	(	std::ostream &	_out,
		const Graph< VV, EE, UndirectedEdge< EE >> &	_g
	)

Partial template specification for undirected edges.

References std::endl().

◆ Subgraph()

Graph<V, E, EdgeType> ignition::math::graph::Subgraph	(	const Graph< V, E, EdgeType > &	_graph,
		const VertexId &	_root
	)

Extract the subgraph induced by _root and all descendants reachable from it. Vertices and edges are copied (preserving ids, names, data, weights). All edges whose endpoints both lie in the reachable set are kept, including back-edges – so if the source graph contains cycles within the reachable region, the cycles are preserved in the result. Equivalent to "save just this entity and everything beneath it" – the shape of operation gz-sim and sdformat would invoke when serializing a single model out of a world.

Parameters

[in]	_graph	Source graph.
[in]	_root	Root vertex of the subgraph.

Returns: A new graph containing _root and all descendants reachable from it, plus the edges between them. Empty graph if _root is invalid.

References Graph< V, E, EdgeType >::AddEdge(), Graph< V, E, EdgeType >::AddVertex(), BreadthFirstSort(), unordered_set< K >::count(), Graph< V, E, EdgeType >::Edges(), and Graph< V, E, EdgeType >::VertexFromId().

◆ ToUndirectedGraph()

UndirectedGraph<V, E> ignition::math::graph::ToUndirectedGraph ( const DirectedGraph< V, E > & _graph )

Copy a DirectedGraph to an UndirectedGraph with the same vertices and edges.

Parameters

[in] _graph A directed graph.

Returns: An undirected graph with the same vertices and edges as the original graph.

References Graph< V, E, EdgeType >::Edges(), vector< T >::push_back(), and Graph< V, E, EdgeType >::Vertices().

Variable Documentation

◆ kNullId

const VertexId kNullId = MAX_UI64

static

Represents an invalid Id.

Referenced by Graph< V, E, EdgeType >::AddEdge(), Graph< V, E, EdgeType >::AddVertex(), Graph< V, E, EdgeType >::AdjacentsFrom(), Dijkstra(), UndirectedEdge< E >::From(), DirectedEdge< E >::From(), Graph< V, E, EdgeType >::IncidentsFrom(), Graph< V, E, EdgeType >::IncidentsTo(), Graph< V, E, EdgeType >::LinkEdge(), LowestCommonAncestor(), Graph< V, E, EdgeType >::RemoveEdge(), DirectedEdge< E >::To(), Edge< E >::Valid(), Vertex< V >::Valid(), and Edge< E >::Vertices().

Gazebo Math

API Reference

Classes

Typedefs

Functions

Variables

Typedef Documentation

◆ CostInfo

◆ DirectedGraph

◆ EdgeId

◆ EdgeId_S

◆ EdgeRef_M

◆ UndirectedGraph

◆ VertexId

◆ VertexId_P

◆ VertexRef_M

Function Documentation

◆ Ancestors()

◆ BreadthFirstSort()

◆ ConnectedComponents()

◆ DepthFirstSort()

◆ DescendantsSet()

◆ Dijkstra()

◆ IsAncestor()

◆ LowestCommonAncestor()

◆ operator<<() [1/2]

◆ operator<<() [2/2]

◆ Subgraph()

◆ ToUndirectedGraph()

Variable Documentation

◆ kNullId