17 #ifndef IGNITION_MATH_GRAPH_GRAPH_HH_ 18 #define IGNITION_MATH_GRAPH_GRAPH_HH_ 28 #include <ignition/math/config.hh> 37 inline namespace IGNITION_MATH_VERSION_NAMESPACE {
101 template<
typename V,
typename E,
typename EdgeType>
105 public:
Graph() =
default;
114 for (
auto const &v : _vertices)
116 if (!this->AddVertex(v.Name(), v.Data(), v.Id()).Valid())
118 std::cerr <<
"Invalid vertex with Id [" << v.Id() <<
"]. Ignoring." 124 for (
auto const &e : _edges)
126 if (!this->AddEdge(e.vertices, e.data, e.weight).Valid())
146 id = this->NextVertexId();
151 std::cerr <<
"[Graph::AddVertex()] The limit of vertices has been " 152 <<
"reached. Ignoring vertex." <<
std::endl;
158 auto ret = this->vertices.insert(
164 std::cerr <<
"[Graph::AddVertex()] Repeated vertex [" <<
id <<
"]" 175 return ret.first->second;
184 for (
auto const &v : this->vertices)
196 for (
auto const &vertex : this->vertices)
198 if (vertex.second.Name() == _name)
213 const double _weight = 1.0)
215 auto id = this->NextEdgeId();
220 std::cerr <<
"[Graph::AddEdge()] The limit of edges has been reached. " 222 return EdgeType::NullEdge;
225 EdgeType newEdge(_vertices, _data, _weight,
id);
226 return this->LinkEdge(
std::move(newEdge));
237 auto edgeVertices = _edge.Vertices();
240 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
242 if (this->vertices.find(v) == this->vertices.end())
243 return EdgeType::NullEdge;
247 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
251 auto vertexIt = this->adjList.find(v);
252 assert(vertexIt != this->adjList.end());
253 vertexIt->second.insert(_edge.Id());
260 return ret.first->second;
269 for (
auto const &edge : this->edges)
297 auto vertexIt = this->adjList.
find(_vertex);
298 if (vertexIt == this->adjList.end())
301 for (
auto const &edgeId : vertexIt->second)
303 const auto &edge = this->EdgeFromId(edgeId);
304 auto neighborVertexId = edge.From(_vertex);
305 if (neighborVertexId !=
kNullId)
307 const auto &neighborVertex = this->VertexFromId(neighborVertexId);
333 return this->AdjacentsFrom(_vertex.
Id());
353 auto incidentEdges = this->IncidentsTo(_vertex);
356 for (
auto const &incidentEdgeRef : incidentEdges)
358 const auto &incidentEdgeId = incidentEdgeRef.first;
359 const auto &incidentEdge = this->EdgeFromId(incidentEdgeId);
360 const auto &neighborVertexId = incidentEdge.To(_vertex);
361 const auto &neighborVertex = this->VertexFromId(neighborVertexId);
386 return this->AdjacentsTo(_vertex.
Id());
394 return this->IncidentsTo(_vertex).size();
402 return this->IncidentsTo(this->VertexFromId(_vertex.
Id())).size();
410 return this->IncidentsFrom(_vertex).size();
418 return this->IncidentsFrom(this->VertexFromId(_vertex.
Id())).size();
431 const auto &adjIt = this->adjList.
find(_vertex);
432 if (adjIt == this->adjList.end())
435 const auto &edgeIds = adjIt->second;
436 for (
auto const &edgeId : edgeIds)
438 const auto &edge = this->EdgeFromId(edgeId);
439 if (edge.From(_vertex) !=
kNullId)
454 return this->IncidentsFrom(_vertex.
Id());
467 const auto &adjIt = this->adjList.
find(_vertex);
468 if (adjIt == this->adjList.end())
471 const auto &edgeIds = adjIt->second;
472 for (
auto const &edgeId : edgeIds)
474 const auto &edge = this->EdgeFromId(edgeId);
475 if (edge.To(_vertex) !=
kNullId)
490 return this->IncidentsTo(_vertex.
Id());
498 return this->vertices.empty();
506 auto vIt = this->vertices.find(_vertex);
507 if (vIt == this->vertices.end())
513 auto incidents = this->IncidentsTo(_vertex);
514 for (
auto edgePair : incidents)
515 this->RemoveEdge(edgePair.first);
518 incidents = this->IncidentsFrom(_vertex);
519 for (
auto edgePair : incidents)
520 this->RemoveEdge(edgePair.first);
523 this->adjList.erase(_vertex);
526 this->vertices.erase(_vertex);
529 auto iterPair = this->names.equal_range(name);
530 for (
auto it = iterPair.first; it != iterPair.second; ++it)
532 if (it->second == _vertex)
534 this->names.erase(it);
547 return this->RemoveVertex(_vertex.
Id());
555 size_t numVertices = this->names.count(_name);
557 for (
size_t i = 0; i < numVertices; ++i)
559 auto iter = this->names.find(_name);
560 if (this->RemoveVertex(iter->second))
574 auto edgeIt = this->edges.find(_edge);
575 if (edgeIt == this->edges.end())
578 auto edgeVertices = edgeIt->second.Vertices();
581 for (
auto const &v : {edgeVertices.first, edgeVertices.second})
583 if (edgeIt->second.From(v) !=
kNullId)
585 auto vertex = this->adjList.find(v);
586 assert(vertex != this->adjList.end());
587 vertex->second.erase(_edge);
591 this->edges.erase(_edge);
603 return this->RemoveEdge(_edge.Id());
612 auto iter = this->vertices.find(_id);
613 if (iter == this->vertices.end())
625 auto iter = this->vertices.find(_id);
626 if (iter == this->vertices.end())
645 this->adjList.
find(_sourceId);
648 if (adjIt == this->adjList.
end())
649 return EdgeType::NullEdge;
653 edgIt != adjIt->second.
end(); ++edgIt)
657 this->edges.
find(*edgIt);
660 if (edgeIter != this->edges.
end() &&
661 edgeIter->second.From(_sourceId) == _destId)
663 assert(edgeIter->second.To(_destId) == _sourceId);
664 return edgeIter->second;
668 return EdgeType::NullEdge;
677 auto iter = this->edges.find(_id);
678 if (iter == this->edges.end())
679 return EdgeType::NullEdge;
689 public:
template<
typename VV,
typename EE,
typename EEdgeType>
697 while (this->vertices.find(this->nextVertexId) != this->vertices.end()
700 ++this->nextVertexId;
703 return this->nextVertexId;
710 while (this->edges.find(this->nextEdgeId) != this->edges.end() &&
716 return this->nextEdgeId;
744 template<
typename VV,
typename EE>
751 for (
auto const &vertexMap : _g.Vertices())
753 auto vertex = vertexMap.second.get();
758 for (
auto const &edgeMap : _g.Edges())
760 auto edge = edgeMap.second.get();
771 template<
typename VV,
typename EE>
778 for (
auto const &vertexMap : _g.Vertices())
780 auto vertex = vertexMap.second.get();
785 for (
auto const &edgeMap : _g.Edges())
787 auto edge = edgeMap.second.get();
798 template<
typename V,
typename E>
803 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:772
const EdgeRef_M< EdgeType > IncidentsFrom(const VertexId &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition: Graph.hh:426
Vertex< V > & AddVertex(const std::string &_name, const V &_data, const VertexId &_id=kNullId)
Add a new vertex to the graph.
Definition: Graph.hh:137
A generic graph class. Both vertices and edges can store user information. A vertex could be created ...
Definition: Graph.hh:102
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:384
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:336
const Vertex< V > & VertexFromId(const VertexId &_id) const
Get a reference to a vertex using its Id.
Definition: Graph.hh:610
bool Empty() const
Get whether the graph is empty.
Definition: Graph.hh:496
const EdgeType & EdgeFromId(const EdgeId &_id) const
Get a reference to an edge using its Id.
Definition: Graph.hh:675
bool RemoveVertex(Vertex< V > &_vertex)
Remove an existing vertex from the graph.
Definition: Graph.hh:545
const EdgeRef_M< EdgeType > IncidentsTo(const Vertex< V > &_vertex) const
Get the set of incoming edges to a given vertex.
Definition: Graph.hh:487
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:235
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:601
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:331
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:408
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:351
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:462
size_t OutDegree(const Vertex< V > &_vertex) const
Get the number of edges incident from a vertex.
Definition: Graph.hh:416
const EdgeType & EdgeFromVertices(const VertexId _sourceId, const VertexId _destId) const
Get a reference to an edge based on two vertices. A NullEdge object reference is returned if an edge ...
Definition: Graph.hh:640
uint64_t EdgeId
The unique Id for an edge.
Definition: Edge.hh:40
const EdgeRef_M< EdgeType > IncidentsFrom(const Vertex< V > &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition: Graph.hh:451
const VertexRef_M< V > Vertices() const
The collection of all vertices in the graph.
Definition: Graph.hh:181
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:572
Vertex< V > & VertexFromId(const VertexId &_id)
Get a mutable reference to a vertex using its Id.
Definition: Graph.hh:623
size_t InDegree(const VertexId &_vertex) const
Get the number of edges incident to a vertex.
Definition: Graph.hh:392
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:292
Graph(const std::vector< Vertex< V >> &_vertices, const std::vector< EdgeInitializer< E >> &_edges)
Constructor.
Definition: Graph.hh:110
const VertexRef_M< V > Vertices(const std::string &_name) const
The collection of all vertices in the graph with name == _name.
Definition: Graph.hh:193
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:211
uint64_t VertexId
The unique Id of each vertex.
Definition: Vertex.hh:41
size_t RemoveVertices(const std::string &_name)
Remove all vertices with name == _name.
Definition: Graph.hh:553
bool RemoveVertex(const VertexId &_vertex)
Remove an existing vertex from the graph.
Definition: Graph.hh:504
size_t InDegree(const Vertex< V > &_vertex) const
Get the number of edges incident to a vertex.
Definition: Graph.hh:400
const EdgeRef_M< EdgeType > Edges() const
The collection of all edges in the graph.
Definition: Graph.hh:266
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