Loading...
Searching...
No Matches
ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph Namespace Reference

Classes

class  DirectedEdge
 A directed edge represents a connection between two vertices. More...
 
class  Edge
 Generic edge class. More...
 
struct  EdgeInitializer
 Used in the Graph constructors for uniform initialization. More...
 
class  Graph
 A generic graph class. More...
 
class  UndirectedEdge
 An undirected edge represents a connection between two vertices. More...
 
class  Vertex
 A vertex of a graph. More...
 

Typedefs

using CostInfo = std::pair<double, VertexId>
 
template<typename V , typename E >
using DirectedGraph = Graph<V, E, DirectedEdge<E>>
 
using EdgeId = uint64_t
 
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
 
using VertexId_P = std::pair<VertexId, VertexId>
 
template<typename V >
using VertexRef_M
 

Functions

template<typename V , typename E , typename EdgeType >
std::vector< VertexIdBreadthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from)
 Breadth first sort (BFS).
 
template<typename V , typename E >
std::vector< UndirectedGraph< V, E > > ConnectedComponents (const UndirectedGraph< V, E > &_graph)
 Calculate the connected components of an undirected graph.
 
template<typename V , typename E , typename EdgeType >
std::vector< VertexIdDepthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from)
 Depth first sort (DFS).
 
template<typename V , typename E , typename EdgeType >
std::map< VertexId, CostInfoDijkstra (const Graph< V, E, EdgeType > &_graph, const VertexId &_from, const VertexId &_to=kNullId)
 Dijkstra algorithm.
 
template<typename VV , typename EE >
std::ostream & operator<< (std::ostream &_out, const Graph< VV, EE, DirectedEdge< EE > > &_g)
 Partial template specification for directed edges.
 
template<typename VV , typename EE >
std::ostream & operator<< (std::ostream &_out, const Graph< VV, EE, UndirectedEdge< EE > > &_g)
 Partial template specification for undirected edges.
 

Variables

static const VertexId kNullId = MAX_UI64
 Represents an invalid Id.
 

Typedef Documentation

◆ CostInfo

◆ DirectedGraph

◆ EdgeId

◆ EdgeId_S

◆ EdgeRef_M

template<typename EdgeType >
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::EdgeRef_M = std::map<EdgeId, std::reference_wrapper<const EdgeType>>

◆ UndirectedGraph

◆ VertexId

◆ VertexId_P

◆ VertexRef_M

Initial value:
std::map<VertexId, std::reference_wrapper<const Vertex<V>>>

Function Documentation

◆ BreadthFirstSort()

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

◆ ConnectedComponents()

template<typename V , typename E >
std::vector< UndirectedGraph< V, E > > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::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. https://en.wikipedia.org/wiki/Connected_component_(graph_theory)

Parameters
[in]_graphA graph.
Returns
A vector of graphs. Each element of the graph is a component (subgraph) of the original graph.

References BreadthFirstSort(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Edges(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Vertices().

◆ DepthFirstSort()

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

◆ Dijkstra()

template<typename V , typename E , typename EdgeType >
std::map< VertexId, CostInfo > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::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]_graphA graph.
[in]_fromThe starting vertex.
[in]_toOptional 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 ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom(), kNullId, ignition::math::IGNITION_MATH_VERSION_NAMESPACE::MAX_D, and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Vertices().

◆ operator<<() [1/2]

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

Partial template specification for directed edges.

◆ operator<<() [2/2]

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

Partial template specification for undirected edges.

Variable Documentation

◆ kNullId