17 #ifndef IGNITION_MATH_GRAPH_GRAPH_HH_
18 #define IGNITION_MATH_GRAPH_GRAPH_HH_
26 #include <ignition/math/config.hh>
34 inline namespace IGNITION_MATH_VERSION_NAMESPACE
99 template<
typename V,
typename E,
typename EdgeType>
103 public:
Graph() =
default;
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())
125 std::cerr <<
"Ignoring edge" << std::endl;
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(
157 std::make_pair(
id,
Vertex<V>(_name, _data,
id)));
162 std::cerr <<
"[Graph::AddVertex()] Repeated vertex [" <<
id <<
"]"
171 this->names.insert(std::make_pair(_name,
id));
173 return ret.first->second;
182 for (
auto const &v : this->vertices)
183 res.emplace(std::make_pair(v.first, std::cref(v.second)));
185 return std::move(res);
194 for (
auto const &vertex : this->vertices)
196 if (vertex.second.Name() == _name)
197 res.emplace(std::make_pair(vertex.first, std::cref(vertex.second)));
200 return std::move(res);
210 const double _weight = 1.0)
212 auto id = this->NextEdgeId();
217 std::cerr <<
"[Graph::AddEdge()] The limit of edges has been reached. "
218 <<
"Ignoring edge." << std::endl;
219 return EdgeType::NullEdge;
222 EdgeType newEdge(_vertices, _data, _weight,
id);
223 return this->
LinkEdge(std::move(newEdge));
234 auto edgeVertices = _edge.Vertices();
237 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
239 if (this->vertices.find(v) == this->vertices.end())
240 return EdgeType::NullEdge;
244 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
248 auto vertexIt = this->adjList.find(v);
249 assert(vertexIt != this->adjList.end());
250 vertexIt->second.insert(_edge.Id());
254 auto ret = this->edges.insert(std::make_pair(_edge.Id(), _edge));
257 return ret.first->second;
266 for (
auto const &edge : this->edges)
268 res.emplace(std::make_pair(edge.first, std::cref(edge.second)));
271 return std::move(res);
294 auto vertexIt = this->adjList.find(_vertex);
295 if (vertexIt == this->adjList.end())
298 for (
auto const &edgeId : vertexIt->second)
301 auto neighborVertexId = edge.From(_vertex);
302 if (neighborVertexId !=
kNullId)
304 const auto &neighborVertex = this->
VertexFromId(neighborVertexId);
306 std::make_pair(neighborVertexId, std::cref(neighborVertex)));
353 for (
auto const &incidentEdgeRef : incidentEdges)
355 const auto &incidentEdgeId = incidentEdgeRef.first;
356 const auto &incidentEdge = this->
EdgeFromId(incidentEdgeId);
357 const auto &neighborVertexId = incidentEdge.To(_vertex);
358 const auto &neighborVertex = this->
VertexFromId(neighborVertexId);
360 std::make_pair(neighborVertexId, std::cref(neighborVertex)));
428 const auto &adjIt = this->adjList.find(_vertex);
429 if (adjIt == this->adjList.end())
432 const auto &edgeIds = adjIt->second;
433 for (
auto const &edgeId : edgeIds)
436 if (edge.From(_vertex) !=
kNullId)
437 res.emplace(std::make_pair(edge.Id(), std::cref(edge)));
440 return std::move(res);
464 const auto &adjIt = this->adjList.find(_vertex);
465 if (adjIt == this->adjList.end())
468 const auto &edgeIds = adjIt->second;
469 for (
auto const &edgeId : edgeIds)
472 if (edge.To(_vertex) !=
kNullId)
473 res.emplace(std::make_pair(edge.Id(), std::cref(edge)));
476 return std::move(res);
495 return this->vertices.empty();
503 auto vIt = this->vertices.find(_vertex);
504 if (vIt == this->vertices.end())
507 std::string name = vIt->second.Name();
511 for (
auto edgePair : incidents)
516 for (
auto edgePair : incidents)
520 this->adjList.erase(_vertex);
523 this->vertices.erase(_vertex);
526 auto iterPair = this->names.equal_range(name);
527 for (
auto it = iterPair.first; it != iterPair.second; ++it)
529 if (it->second == _vertex)
531 this->names.erase(it);
552 size_t numVertices = this->names.count(_name);
554 for (
size_t i = 0; i < numVertices; ++i)
556 auto iter = this->names.find(_name);
571 auto edgeIt = this->edges.find(_edge);
572 if (edgeIt == this->edges.end())
575 auto edgeVertices = edgeIt->second.Vertices();
578 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
580 if (edgeIt->second.From(v) !=
kNullId)
582 auto vertex = this->adjList.find(v);
583 assert(vertex != this->adjList.end());
584 vertex->second.erase(_edge);
588 this->edges.erase(_edge);
609 auto iter = this->vertices.find(_id);
610 if (iter == this->vertices.end())
622 auto iter = this->vertices.find(_id);
623 if (iter == this->vertices.end())
635 auto iter = this->edges.find(_id);
636 if (iter == this->edges.end())
637 return EdgeType::NullEdge;
647 public:
template<
typename VV,
typename EE,
typename EEdgeType>
648 friend std::ostream &
operator<<(std::ostream &_out,
655 while (this->vertices.find(this->nextVertexId) != this->vertices.end()
668 while (this->edges.find(this->nextEdgeId) != this->edges.end() &&
684 private: std::map<VertexId, Vertex<V>> vertices;
687 private: std::map<EdgeId, EdgeType> edges;
694 private: std::map<VertexId, EdgeId_S> adjList;
697 private: std::multimap<std::string, VertexId> names;
702 template<
typename VV,
typename EE>
706 _out <<
"graph {" << std::endl;
709 for (
auto const &vertexMap : _g.Vertices())
711 auto vertex = vertexMap.second.get();
716 for (
auto const &edgeMap : _g.Edges())
718 auto edge = edgeMap.second.get();
722 _out <<
"}" << std::endl;
729 template<
typename VV,
typename EE>
733 _out <<
"digraph {" << std::endl;
736 for (
auto const &vertexMap : _g.Vertices())
738 auto vertex = vertexMap.second.get();
743 for (
auto const &edgeMap : _g.Edges())
745 auto edge = edgeMap.second.get();
749 _out <<
"}" << std::endl;
756 template<
typename V,
typename E>
761 template<
typename V,
typename E>