17 #ifndef IGNITION_MATH_GRAPH_GRAPH_HH_ 18 #define IGNITION_MATH_GRAPH_GRAPH_HH_ 26 #include <ignition/math/config.hh> 35 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())
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)
210 const double _weight = 1.0)
212 auto id = this->NextEdgeId();
217 std::cerr <<
"[Graph::AddEdge()] The limit of edges has been reached. " 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());
257 return ret.first->second;
266 for (
auto const &edge : this->edges)
294 auto vertexIt = this->adjList.
find(_vertex);
295 if (vertexIt == this->adjList.end())
298 for (
auto const &edgeId : vertexIt->second)
300 const auto &edge = this->EdgeFromId(edgeId);
301 auto neighborVertexId = edge.From(_vertex);
302 if (neighborVertexId !=
kNullId)
304 const auto &neighborVertex = this->VertexFromId(neighborVertexId);
330 return this->AdjacentsFrom(_vertex.
Id());
350 auto incidentEdges = this->IncidentsTo(_vertex);
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);
383 return this->AdjacentsTo(_vertex.
Id());
391 return this->IncidentsTo(_vertex).size();
399 return this->IncidentsTo(this->VertexFromId(_vertex.
Id())).size();
407 return this->IncidentsFrom(_vertex).size();
415 return this->IncidentsFrom(this->VertexFromId(_vertex.
Id())).size();
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)
435 const auto &edge = this->EdgeFromId(edgeId);
436 if (edge.From(_vertex) !=
kNullId)
451 return this->IncidentsFrom(_vertex.
Id());
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)
471 const auto &edge = this->EdgeFromId(edgeId);
472 if (edge.To(_vertex) !=
kNullId)
487 return this->IncidentsTo(_vertex.
Id());
495 return this->vertices.empty();
503 auto vIt = this->vertices.find(_vertex);
504 if (vIt == this->vertices.end())
510 auto incidents = this->IncidentsTo(_vertex);
511 for (
auto edgePair : incidents)
512 this->RemoveEdge(edgePair.first);
515 incidents = this->IncidentsFrom(_vertex);
516 for (
auto edgePair : incidents)
517 this->RemoveEdge(edgePair.first);
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);
544 return this->RemoveVertex(_vertex.
Id());
552 size_t numVertices = this->names.count(_name);
554 for (
size_t i = 0; i < numVertices; ++i)
556 auto iter = this->names.find(_name);
557 if (this->RemoveVertex(iter->second))
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);
600 return this->RemoveEdge(_edge.Id());
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>
655 while (this->vertices.find(this->nextVertexId) != this->vertices.end()
658 ++this->nextVertexId;
661 return this->nextVertexId;
668 while (this->edges.find(this->nextEdgeId) != this->edges.end() &&
674 return this->nextEdgeId;
702 template<
typename VV,
typename EE>
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();
729 template<
typename VV,
typename EE>
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();
756 template<
typename V,
typename E>
761 template<
typename V,
typename E>
std::ostream & operator<<(std::ostream &_out, const Graph< VV, EE, DirectedEdge< EE >> &_g)
Partial template specification for directed edges.
Definition: Graph.hh:730
uint64_t EdgeId
Definition: Edge.hh:40
const EdgeRef_M< EdgeType > IncidentsFrom(const VertexId &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition: Graph.hh:423
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
A generic graph class. Both vertices and edges can store user information. A vertex could be created ...
Definition: Graph.hh:100
VertexRef_M< V > AdjacentsTo(const Vertex< V > &_vertex) const
Get all vertices that are directly connected with one edge to a given vertex. In other words...
Definition: Graph.hh:381
A vertex of a graph. It stores user information, an optional name, and keeps an internal unique Id...
Definition: Vertex.hh:54
static const uint64_t MAX_UI64
64bit unsigned integer maximum value
Definition: Helpers.hh:329
const Vertex< V > & VertexFromId(const VertexId &_id) const
Get a reference to a vertex using its Id.
Definition: Graph.hh:607
bool Empty() const
Get whether the graph is empty.
Definition: Graph.hh:493
const EdgeType & EdgeFromId(const EdgeId &_id) const
Get a reference to an edge using its Id.
Definition: Graph.hh:633
bool RemoveVertex(Vertex< V > &_vertex)
Remove an existing vertex from the graph.
Definition: Graph.hh:542
const EdgeRef_M< EdgeType > IncidentsTo(const Vertex< V > &_vertex) const
Get the set of incoming edges to a given vertex.
Definition: Graph.hh:484
EdgeType & LinkEdge(const EdgeType &_edge)
Links an edge to the graph. This function verifies that the edge's two vertices exist in the graph...
Definition: Graph.hh:232
std::set< EdgeId > EdgeId_S
Definition: Edge.hh:192
bool RemoveEdge(EdgeType &_edge)
Remove an existing edge from the graph. After the removal, it won't be possible to reach any of the v...
Definition: Graph.hh:598
VertexRef_M< V > AdjacentsFrom(const Vertex< V > &_vertex) const
Get all vertices that are directly connected with one edge from a given vertex. In other words...
Definition: Graph.hh:328
An undirected edge represents a connection between two vertices. The connection is bidirectional...
Definition: Edge.hh:204
size_t OutDegree(const VertexId &_vertex) const
Get the number of edges incident from a vertex.
Definition: Graph.hh:405
VertexRef_M< V > AdjacentsTo(const VertexId &_vertex) const
Get all vertices that are directly connected with one edge to a given vertex. In other words...
Definition: Graph.hh:348
static const VertexId kNullId
Represents an invalid Id.
Definition: Vertex.hh:48
const EdgeRef_M< EdgeType > IncidentsTo(const VertexId &_vertex) const
Get the set of incoming edges to a given vertex.
Definition: Graph.hh:459
size_t OutDegree(const Vertex< V > &_vertex) const
Get the number of edges incident from a vertex.
Definition: Graph.hh:413
const EdgeRef_M< EdgeType > IncidentsFrom(const Vertex< V > &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition: Graph.hh:448
const VertexRef_M< V > Vertices() const
The collection of all vertices in the graph.
Definition: Graph.hh:179
bool RemoveEdge(const EdgeId &_edge)
Remove an existing edge from the graph. After the removal, it won't be possible to reach any of the v...
Definition: Graph.hh:569
Vertex< V > & VertexFromId(const VertexId &_id)
Get a mutable reference to a vertex using its Id.
Definition: Graph.hh:620
size_t InDegree(const VertexId &_vertex) const
Get the number of edges incident to a vertex.
Definition: Graph.hh:389
Used in the Graph constructors for uniform initialization.
Definition: Edge.hh:44
VertexRef_M< V > AdjacentsFrom(const VertexId &_vertex) const
Get all vertices that are directly connected with one edge from a given vertex. In other words...
Definition: Graph.hh:289
Graph(const std::vector< Vertex< V >> &_vertices, const std::vector< EdgeInitializer< E >> &_edges)
Constructor.
Definition: Graph.hh:108
const VertexRef_M< V > Vertices(const std::string &_name) const
The collection of all vertices in the graph with name == _name.
Definition: Graph.hh:191
VertexId Id() const
Get the vertex Id.
Definition: Vertex.hh:88
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
size_t RemoveVertices(const std::string &_name)
Remove all vertices with name == _name.
Definition: Graph.hh:550
uint64_t VertexId
Definition: Vertex.hh:41
bool RemoveVertex(const VertexId &_vertex)
Remove an existing vertex from the graph.
Definition: Graph.hh:501
size_t InDegree(const Vertex< V > &_vertex) const
Get the number of edges incident to a vertex.
Definition: Graph.hh:397
const EdgeRef_M< EdgeType > Edges() const
The collection of all edges in the graph.
Definition: Graph.hh:263
A directed edge represents a connection between two vertices. The connection is unidirectional, it's only possible to traverse the edge in one direction (from the tail to the head).
Definition: Edge.hh:267