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>
116 std::cerr <<
"Invalid vertex with Id [" <<
v.
Id() <<
"]. Ignoring."
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(
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)
200 return std::move(
res);
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;
239 if (this->vertices.find(
v) == this->vertices.end())
240 return EdgeType::NullEdge;
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);
295 if (
vertexIt == this->adjList.end())
429 if (
adjIt == this->adjList.end())
440 return std::move(
res);
465 if (
adjIt == this->adjList.end())
476 return std::move(
res);
495 return this->vertices.empty();
504 if (
vIt == this->vertices.end())
507 std::string name =
vIt->second.Name();
526 auto iterPair = this->names.equal_range(name);
531 this->names.erase(
it);
572 if (
edgeIt == this->edges.end())
582 auto vertex = this->adjList.find(
v);
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;
722 _out <<
"}" << std::endl;
729 template<
typename VV,
typename EE>
733 _out <<
"digraph {" << std::endl;
749 _out <<
"}" << std::endl;
756 template<
typename V,
typename E>
761 template<
typename V,
typename E>
bool Valid() const
An edge is considered valid when its id is not kNullId.
Definition Edge.hh:171
const E & Data() const
Get a non-mutable reference to the user data stored in the edge.
Definition Edge.hh:110
VertexId_P Vertices() const
Get the two vertices contained in the edge.
Definition Edge.hh:100
EdgeId Id() const
Get the edge Id.
Definition Edge.hh:93
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
VertexId To(const VertexId &_to) const override
Get the source end that can reach the destination end of an edge.
Definition Edge.hh:238
VertexId From(const VertexId &_from) const override
Get the destination end that is reachable from a source end of an edge.
Definition Edge.hh:223
A vertex of a graph.
Definition Vertex.hh:55
std::pair< VertexId, VertexId > VertexId_P
Definition Vertex.hh:45
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
uint64_t EdgeId
Definition Edge.hh:40
static const uint64_t MAX_UI64
64bit unsigned integer maximum value
Definition Helpers.hh:328