17 #ifndef GZ_MATH_GRAPH_GRAPH_HH_
18 #define GZ_MATH_GRAPH_GRAPH_HH_
28 #include <gz/math/config.hh>
35 inline namespace GZ_MATH_VERSION_NAMESPACE {
99 template<
typename V,
typename E,
typename EdgeType>
112 for (
auto const &v : _vertices)
114 if (!this->AddVertex(v.Name(), v.Data(), v.Id()).Valid())
116 std::cerr <<
"Invalid vertex with Id [" << v.Id() <<
"]. Ignoring."
122 for (
auto const &e : _edges)
124 if (!this->AddEdge(e.vertices, e.data, e.weight).Valid())
144 id = this->NextVertexId();
149 std::cerr <<
"[Graph::AddVertex()] The limit of vertices has been "
150 <<
"reached. Ignoring vertex." <<
std::endl;
156 auto ret = this->vertices.insert(
162 std::cerr <<
"[Graph::AddVertex()] Repeated vertex [" <<
id <<
"]"
173 return ret.first->second;
182 for (
auto const &v : this->vertices)
194 for (
auto const &vertex : this->vertices)
196 if (vertex.second.Name() == _name)
211 const double _weight = 1.0)
213 auto id = this->NextEdgeId();
218 std::cerr <<
"[Graph::AddEdge()] The limit of edges has been reached. "
220 return EdgeType::NullEdge;
223 EdgeType newEdge(_vertices, _data, _weight,
id);
224 return this->LinkEdge(
std::move(newEdge));
235 auto edgeVertices = _edge.Vertices();
238 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
240 if (this->vertices.find(v) == this->vertices.end())
241 return EdgeType::NullEdge;
245 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
249 auto vertexIt = this->adjList.find(v);
250 assert(vertexIt != this->adjList.end());
251 vertexIt->second.insert(_edge.Id());
258 return ret.first->second;
267 for (
auto const &edge : this->edges)
295 auto vertexIt = this->adjList.
find(_vertex);
296 if (vertexIt == this->adjList.end())
299 for (
auto const &edgeId : vertexIt->second)
301 const auto &edge = this->EdgeFromId(edgeId);
302 auto neighborVertexId = edge.From(_vertex);
303 if (neighborVertexId !=
kNullId)
305 const auto &neighborVertex = this->VertexFromId(neighborVertexId);
331 return this->AdjacentsFrom(_vertex.
Id());
351 auto incidentEdges = this->IncidentsTo(_vertex);
354 for (
auto const &incidentEdgeRef : incidentEdges)
356 const auto &incidentEdgeId = incidentEdgeRef.first;
357 const auto &incidentEdge = this->EdgeFromId(incidentEdgeId);
358 const auto &neighborVertexId = incidentEdge.To(_vertex);
359 const auto &neighborVertex = this->VertexFromId(neighborVertexId);
384 return this->AdjacentsTo(_vertex.
Id());
392 return this->IncidentsTo(_vertex).size();
400 return this->IncidentsTo(this->VertexFromId(_vertex.
Id())).size();
408 return this->IncidentsFrom(_vertex).size();
416 return this->IncidentsFrom(this->VertexFromId(_vertex.
Id())).size();
429 const auto &adjIt = this->adjList.
find(_vertex);
430 if (adjIt == this->adjList.end())
433 const auto &edgeIds = adjIt->second;
434 for (
auto const &edgeId : edgeIds)
436 const auto &edge = this->EdgeFromId(edgeId);
437 if (edge.From(_vertex) !=
kNullId)
452 return this->IncidentsFrom(_vertex.
Id());
465 const auto &adjIt = this->adjList.
find(_vertex);
466 if (adjIt == this->adjList.end())
469 const auto &edgeIds = adjIt->second;
470 for (
auto const &edgeId : edgeIds)
472 const auto &edge = this->EdgeFromId(edgeId);
473 if (edge.To(_vertex) !=
kNullId)
488 return this->IncidentsTo(_vertex.
Id());
496 return this->vertices.empty();
504 auto vIt = this->vertices.find(_vertex);
505 if (vIt == this->vertices.end())
511 auto incidents = this->IncidentsTo(_vertex);
512 for (
auto edgePair : incidents)
513 this->RemoveEdge(edgePair.first);
516 incidents = this->IncidentsFrom(_vertex);
517 for (
auto edgePair : incidents)
518 this->RemoveEdge(edgePair.first);
521 this->adjList.erase(_vertex);
524 this->vertices.erase(_vertex);
527 auto iterPair = this->names.equal_range(name);
528 for (
auto it = iterPair.first; it != iterPair.second; ++it)
530 if (it->second == _vertex)
532 this->names.erase(it);
545 return this->RemoveVertex(_vertex.
Id());
553 size_t numVertices = this->names.count(_name);
555 for (
size_t i = 0; i < numVertices; ++i)
557 auto iter = this->names.find(_name);
558 if (this->RemoveVertex(iter->second))
572 auto edgeIt = this->edges.find(_edge);
573 if (edgeIt == this->edges.end())
576 auto edgeVertices = edgeIt->second.Vertices();
579 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
581 if (edgeIt->second.From(v) !=
kNullId)
583 auto vertex = this->adjList.find(v);
584 assert(vertex != this->adjList.end());
585 vertex->second.erase(_edge);
589 this->edges.erase(_edge);
601 return this->RemoveEdge(_edge.Id());
610 auto iter = this->vertices.find(_id);
611 if (iter == this->vertices.end())
623 auto iter = this->vertices.find(_id);
624 if (iter == this->vertices.end())
643 this->adjList.
find(_sourceId);
646 if (adjIt == this->adjList.
end())
647 return EdgeType::NullEdge;
651 edgIt != adjIt->second.
end(); ++edgIt)
655 this->edges.
find(*edgIt);
658 if (edgeIter != this->edges.
end() &&
659 edgeIter->second.From(_sourceId) == _destId)
661 assert(edgeIter->second.To(_destId) == _sourceId);
662 return edgeIter->second;
666 return EdgeType::NullEdge;
675 auto iter = this->edges.find(_id);
676 if (iter == this->edges.end())
677 return EdgeType::NullEdge;
688 auto iter = this->edges.find(_id);
689 if (iter == this->edges.end())
690 return EdgeType::NullEdge;
700 public:
template<
typename VV,
typename EE,
typename EEdgeType>
708 while (this->vertices.find(this->nextVertexId) != this->vertices.end()
711 ++this->nextVertexId;
714 return this->nextVertexId;
721 while (this->edges.find(this->nextEdgeId) != this->edges.end() &&
727 return this->nextEdgeId;
755 template<
typename VV,
typename EE>
762 for (
auto const &vertexMap : _g.Vertices())
764 auto vertex = vertexMap.second.get();
769 for (
auto const &edgeMap : _g.Edges())
771 auto edge = edgeMap.second.get();
782 template<
typename VV,
typename EE>
789 for (
auto const &vertexMap : _g.Vertices())
791 auto vertex = vertexMap.second.get();
796 for (
auto const &edgeMap : _g.Edges())
798 auto edge = edgeMap.second.get();
809 template<
typename V,
typename E>
814 template<
typename V,
typename E>