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>
60 for (
auto const &v : _graph.
Vertices())
61 visitorGraph.
AddVertex(
"",
false, v.first);
64 for (
auto const &e : _graph.
Edges())
65 visitorGraph.
AddEdge(e.second.get().Vertices(), E());
67 std::vector<VertexId> visited;
68 std::list<VertexId> pending = {_from};
70 while (!pending.empty())
72 auto vId = pending.front();
80 visited.push_back(vId);
85 for (
auto const &adj : adjacents)
88 auto &v = adj.second.get();
90 pending.push_back(vId);
103 template<
typename V,
typename E,
typename EdgeType>
112 for (
auto const &v : _graph.
Vertices())
113 visitorGraph.
AddVertex(
"",
false, v.first);
116 for (
auto const &e : _graph.
Edges())
117 visitorGraph.
AddEdge(e.second.get().Vertices(), E());
119 std::vector<VertexId> visited;
120 std::stack<VertexId> pending({_from});
122 while (!pending.empty())
124 auto vId = pending.top();
132 visited.push_back(vId);
133 vertex.Data() =
true;
137 for (
auto const &adj : adjacents)
140 auto &v = adj.second.get();
207 template<
typename V,
typename E,
typename EdgeType>
212 auto allVertices = _graph.
Vertices();
215 if (allVertices.find(_from) == allVertices.end())
217 std::cerr <<
"Vertex [" << _from <<
"] Not found" << std::endl;
223 allVertices.find(_to) == allVertices.end())
225 std::cerr <<
"Vertex [" << _from <<
"] Not found" << std::endl;
231 std::vector<CostInfo>, std::greater<CostInfo>> pq;
235 std::map<VertexId, CostInfo> dist;
236 for (
auto const &v : allVertices)
243 pq.push(std::make_pair(0.0, _from));
244 dist[_from] = std::make_pair(0.0, _from);
252 if (_to !=
kNullId && _to == u)
259 const auto &edge = edgePair.second.get();
260 const auto &v = edge.From(u);
261 double weight = edge.Weight();
264 if (dist[v].first > dist[u].first + weight)
267 dist[v] = std::make_pair(dist[u].first + weight, u);
268 pq.push(std::make_pair(dist[v].first, v));
284 template<
typename V,
typename E>
288 std::map<VertexId, unsigned int> visited;
289 unsigned int componentCount = 0;
291 for (
auto const &v : _graph.
Vertices())
293 if (visited.find(v.first) == visited.end())
296 for (
auto const &vId : component)
297 visited[vId] = componentCount;
302 std::vector<UndirectedGraph<V, E>> res(componentCount);
305 for (
auto const &vPair : _graph.
Vertices())
307 const auto &v = vPair.second.get();
308 const auto &componentId = visited[v.Id()];
309 res[componentId].AddVertex(v.Name(), v.Data(), v.Id());
313 for (
auto const &ePair : _graph.
Edges())
315 const auto &e = ePair.second.get();
316 const auto &vertices = e.Vertices();
317 const auto &componentId = visited[vertices.first];
318 res[componentId].AddEdge(vertices, e.Data(), e.Weight());
A generic graph class.
Definition Graph.hh:101
EdgeType & AddEdge(const VertexId_P &_vertices, const E &_data, const double _weight=1.0)
Add a new edge to the graph.
Definition Graph.hh:208
const Vertex< V > & VertexFromId(const VertexId &_id) const
Get a reference to a vertex using its Id.
Definition Graph.hh:607
const VertexRef_M< V > Vertices() const
The collection of all vertices in the graph.
Definition Graph.hh:179
const EdgeRef_M< EdgeType > IncidentsFrom(const VertexId &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition Graph.hh:423
const EdgeRef_M< EdgeType > Edges() const
The collection of all edges in the graph.
Definition Graph.hh:263
Vertex< V > & AddVertex(const std::string &_name, const V &_data, const VertexId &_id=kNullId)
Add a new vertex to the graph.
Definition Graph.hh:135
VertexRef_M< V > AdjacentsFrom(const VertexId &_vertex) const
Get all vertices that are directly connected with one edge from a given vertex.
Definition Graph.hh:289
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