17 #ifndef GZ_MATH_GRAPH_GRAPHALGORITHMS_HH_
18 #define GZ_MATH_GRAPH_GRAPHALGORITHMS_HH_
28 #include <gz/math/config.hh>
35 inline namespace GZ_MATH_VERSION_NAMESPACE {
49 template<
typename V,
typename E,
typename EdgeType>
58 for (
auto const &v : _graph.
Vertices())
59 visitorGraph.
AddVertex(
"",
false, v.first);
62 for (
auto const &e : _graph.
Edges())
63 visitorGraph.
AddEdge(e.second.get().Vertices(), E());
68 while (!pending.
empty())
70 auto vId = pending.
front();
83 for (
auto const &adj : adjacents)
86 auto &v = adj.second.get();
101 template<
typename V,
typename E,
typename EdgeType>
110 for (
auto const &v : _graph.
Vertices())
111 visitorGraph.
AddVertex(
"",
false, v.first);
114 for (
auto const &e : _graph.
Edges())
115 visitorGraph.
AddEdge(e.second.get().Vertices(), E());
120 while (!pending.empty())
122 auto vId = pending.
top();
131 vertex.Data() =
true;
135 for (
auto const &adj : adjacents)
138 auto &v = adj.second.get();
210 template<
typename V,
typename E,
typename EdgeType>
215 auto allVertices = _graph.
Vertices();
218 if (allVertices.find(_from) == allVertices.end())
226 allVertices.find(_to) == allVertices.end())
239 for (
auto const &v : allVertices)
255 if (_to !=
kNullId && _to == u)
262 const auto &edge = edgePair.second.get();
263 const auto &v = edge.From(u);
264 double weight = edge.Weight();
267 if (dist[v].first > dist[u].first + weight)
287 template<
typename V,
typename E>
292 unsigned int componentCount = 0;
294 for (
auto const &v : _graph.
Vertices())
296 if (visited.
find(v.first) == visited.
end())
299 for (
auto const &vId : component)
300 visited[vId] = componentCount;
308 for (
auto const &vPair : _graph.
Vertices())
310 const auto &v = vPair.second.get();
311 const auto &componentId = visited[v.Id()];
312 res[componentId].AddVertex(v.Name(), v.Data(), v.Id());
316 for (
auto const &ePair : _graph.
Edges())
318 const auto &e = ePair.second.get();
319 const auto &vertices = e.Vertices();
320 const auto &componentId = visited[vertices.first];
321 res[componentId].AddEdge(vertices, e.Data(), e.Weight());
332 template<
typename V,
typename E>
339 for (
auto const &vPair : _graph.
Vertices())
346 for (
auto const &ePair : _graph.
Edges())
348 auto const &e = ePair.second.get();
349 edges.
push_back({e.Vertices(), e.Data(), e.Weight()});