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< VertexId > | BreadthFirstSort (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< VertexId > | DepthFirstSort (const Graph< V, E, EdgeType > &_graph, const VertexId &_from) |
Depth first sort (DFS). | |
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. | |
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. | |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::CostInfo = std::pair<double, VertexId> |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::DirectedGraph = Graph<V, E, DirectedEdge<E>> |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::EdgeId = uint64_t |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::EdgeId_S = std::set<EdgeId> |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::EdgeRef_M = std::map<EdgeId, std::reference_wrapper<const EdgeType>> |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::UndirectedGraph = Graph<V, E, UndirectedEdge<E>> |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::VertexId = uint64_t |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::VertexId_P = std::pair<VertexId, VertexId> |
using ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::VertexRef_M |
std::vector< VertexId > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::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.
[in] | _graph | A graph. |
[in] | _from | The starting vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddEdge(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddVertex(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Edges(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::VertexFromId(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Vertices().
Referenced by ConnectedComponents().
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)
[in] | _graph | A 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().
std::vector< VertexId > ignition::math::IGNITION_MATH_VERSION_NAMESPACE::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.
[in] | _graph | A graph. |
[in] | _from | The starting vertex. |
References ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddEdge(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddVertex(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Edges(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::VertexFromId(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::Vertices().
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.
[in] | _graph | A graph. |
[in] | _from | The starting vertex. |
[in] | _to | Optional destination vertex. |
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):
| 0 | 0 | 0 | | 1 | 3 | 3 | | 2 | 7 | 4 | | 3 | 1 | 0 |
This is the result of Dijkstra(g, 0, 3):
| 0 | 0 | 0 | | 1 |ignore| ignore | | 2 |ignore| ignore | | 3 | 1 | 0 |
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().
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.
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.
Represents an invalid Id.
Referenced by ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddEdge(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AddVertex(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::AdjacentsFrom(), Dijkstra(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::DirectedEdge< E >::From(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::UndirectedEdge< E >::From(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsFrom(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::IncidentsTo(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::LinkEdge(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Graph< V, E, EdgeType >::RemoveEdge(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::DirectedEdge< E >::To(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Edge< E >::Valid(), ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Vertex< V >::Valid(), and ignition::math::IGNITION_MATH_VERSION_NAMESPACE::graph::Edge< E >::Vertices().