17 #ifndef IGNITION_MATH_GRAPH_GRAPHALGORITHMS_HH_
18 #define IGNITION_MATH_GRAPH_GRAPHALGORITHMS_HH_
28 #include <ignition/math/config.hh>
36 inline 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());