17#ifndef IGNITION_MATH_GRAPH_GRAPHALGORITHMS_HH_
18#define IGNITION_MATH_GRAPH_GRAPHALGORITHMS_HH_
28#include <ignition/math/config.hh>
36inline namespace IGNITION_MATH_VERSION_NAMESPACE
51 template<
typename V,
typename E,
typename EdgeType>
64 for (
auto const &
e :
_graph.Edges())
88 auto &
v =
adj.second.get();
103 template<
typename V,
typename E,
typename EdgeType>
116 for (
auto const &
e :
_graph.Edges())
140 auto &
v =
adj.second.get();
207 template<
typename V,
typename E,
typename EdgeType>
217 std::cerr <<
"Vertex [" <<
_from <<
"] Not found" << std::endl;
225 std::cerr <<
"Vertex [" <<
_from <<
"] Not found" << std::endl;
231 std::vector<CostInfo>, std::greater<CostInfo>>
pq;
235 std::map<VertexId, CostInfo>
dist;
243 pq.push(std::make_pair(0.0,
_from));
284 template<
typename V,
typename E>
288 std::map<VertexId, unsigned int>
visited;
307 const auto &
v =
vPair.second.get();
315 const auto &
e =
ePair.second.get();
const E & Data() const
Get a non-mutable reference to the user data stored in the edge.
Definition Edge.hh:110
VertexId_P Vertices() const
Get the two vertices contained in the edge.
Definition Edge.hh:100
double Weight() const
The cost of traversing the _from end to the other end of the edge.
Definition Edge.hh:125
EdgeId Id() const
Get the edge Id.
Definition Edge.hh:93
An undirected edge represents a connection between two vertices.
Definition Edge.hh:205
VertexId From(const VertexId &_from) const override
Get the destination end that is reachable from a source end of an edge.
Definition Edge.hh:223
std::vector< UndirectedGraph< V, E > > ConnectedComponents(const UndirectedGraph< V, E > &_graph)
Calculate the connected components of an undirected graph.
Definition GraphAlgorithms.hh:285
std::vector< VertexId > DepthFirstSort(const Graph< V, E, EdgeType > &_graph, const VertexId &_from)
Depth first sort (DFS).
Definition GraphAlgorithms.hh:104
static const VertexId kNullId
Represents an invalid Id.
Definition Vertex.hh:48
std::map< VertexId, CostInfo > Dijkstra(const Graph< V, E, EdgeType > &_graph, const VertexId &_from, const VertexId &_to=kNullId)
Dijkstra algorithm.
Definition GraphAlgorithms.hh:208
std::pair< double, VertexId > CostInfo
Definition GraphAlgorithms.hh:43
std::vector< VertexId > BreadthFirstSort(const Graph< V, E, EdgeType > &_graph, const VertexId &_from)
Breadth first sort (BFS).
Definition GraphAlgorithms.hh:52
uint64_t VertexId
Definition Vertex.hh:41
static const double MAX_D
Double maximum value. This value will be similar to 1.79769e+308.
Definition Helpers.hh:246