17#ifndef IGNITION_MATH_GRAPH_GRAPH_HH_
18#define IGNITION_MATH_GRAPH_GRAPH_HH_
26#include <ignition/math/config.hh>
34inline namespace IGNITION_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())
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>
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>
A directed edge represents a connection between two vertices.
Definition Edge.hh:268
A generic graph class.
Definition Graph.hh:101
VertexRef_M< V > AdjacentsFrom(const Vertex< V > &_vertex) const
Get all vertices that are directly connected with one edge from a given vertex.
Definition Graph.hh:328
Graph()=default
Default constructor.
const EdgeRef_M< EdgeType > IncidentsFrom(const Vertex< V > &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition Graph.hh:448
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
Vertex< V > & VertexFromId(const VertexId &_id)
Get a mutable reference to a vertex using its Id.
Definition Graph.hh:620
bool RemoveEdge(EdgeType &_edge)
Remove an existing edge from the graph.
Definition Graph.hh:598
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
const EdgeType & EdgeFromId(const EdgeId &_id) const
Get a reference to an edge using its Id.
Definition Graph.hh:633
bool Empty() const
Get whether the graph is empty.
Definition Graph.hh:493
VertexRef_M< V > AdjacentsTo(const Vertex< V > &_vertex) const
Get all vertices that are directly connected with one edge to a given vertex.
Definition Graph.hh:381
VertexId nextEdgeId
The next edge Id to be assigned to a new edge.
Definition Graph.hh:681
const Vertex< V > & VertexFromId(const VertexId &_id) const
Get a reference to a vertex using its Id.
Definition Graph.hh:607
const EdgeRef_M< EdgeType > IncidentsTo(const Vertex< V > &_vertex) const
Get the set of incoming edges to a given vertex.
Definition Graph.hh:484
size_t InDegree(const Vertex< V > &_vertex) const
Get the number of edges incident to a vertex.
Definition Graph.hh:397
bool RemoveVertex(const VertexId &_vertex)
Remove an existing vertex from the graph.
Definition Graph.hh:501
const VertexRef_M< V > Vertices() const
The collection of all vertices in the graph.
Definition Graph.hh:179
VertexId nextVertexId
The next vertex Id to be assigned to a new vertex.
Definition Graph.hh:678
const EdgeRef_M< EdgeType > IncidentsFrom(const VertexId &_vertex) const
Get the set of outgoing edges from a given vertex.
Definition Graph.hh:423
const EdgeRef_M< EdgeType > Edges() const
The collection of all edges in the graph.
Definition Graph.hh:263
EdgeType & LinkEdge(const EdgeType &_edge)
Links an edge to the graph.
Definition Graph.hh:232
Graph(const std::vector< Vertex< V > > &_vertices, const std::vector< EdgeInitializer< E > > &_edges)
Constructor.
Definition Graph.hh:108
bool RemoveEdge(const EdgeId &_edge)
Remove an existing edge from the graph.
Definition Graph.hh:569
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 RemoveVertices(const std::string &_name)
Remove all vertices with name == _name.
Definition Graph.hh:550
size_t OutDegree(const Vertex< V > &_vertex) const
Get the number of edges incident from a vertex.
Definition Graph.hh:413
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
friend std::ostream & operator<<(std::ostream &_out, const Graph< VV, EE, EEdgeType > &_g)
Stream insertion operator.
VertexRef_M< V > AdjacentsTo(const VertexId &_vertex) const
Get all vertices that are directly connected with one edge to a given vertex.
Definition Graph.hh:348
bool RemoveVertex(Vertex< V > &_vertex)
Remove an existing vertex from the graph.
Definition Graph.hh:542
size_t InDegree(const VertexId &_vertex) const
Get the number of edges incident to a vertex.
Definition Graph.hh:389
size_t OutDegree(const VertexId &_vertex) const
Get the number of edges incident from a vertex.
Definition Graph.hh:405
VertexRef_M< V > AdjacentsFrom(const VertexId &_vertex) const
Get all vertices that are directly connected with one edge from a given vertex.
Definition Graph.hh:289
An undirected edge represents a connection between two vertices.
Definition Edge.hh:205
A vertex of a graph.
Definition Vertex.hh:55
VertexId Id() const
Get the vertex Id.
Definition Vertex.hh:88
std::pair< VertexId, VertexId > VertexId_P
Definition Vertex.hh:45
std::map< EdgeId, std::reference_wrapper< const EdgeType > > EdgeRef_M
Definition Edge.hh:198
std::ostream & operator<<(std::ostream &_out, const Graph< VV, EE, UndirectedEdge< EE > > &_g)
Partial template specification for undirected edges.
Definition Graph.hh:703
static const VertexId kNullId
Represents an invalid Id.
Definition Vertex.hh:48
uint64_t VertexId
Definition Vertex.hh:41
std::set< EdgeId > EdgeId_S
Definition Edge.hh:192
std::map< VertexId, std::reference_wrapper< const Vertex< V > > > VertexRef_M
Definition Vertex.hh:138
uint64_t EdgeId
Definition Edge.hh:40
static const uint64_t MAX_UI64
64bit unsigned integer maximum value
Definition Helpers.hh:328
Used in the Graph constructors for uniform initialization.
Definition Edge.hh:45