MRPT  2.0.1
CDirectedGraph.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
12 #include <mrpt/core/exceptions.h>
13 #include <mrpt/graphs/TNodeID.h>
15 #include <fstream>
16 #include <map>
17 #include <set>
18 
19 namespace mrpt
20 {
21 namespace graphs
22 {
23 /** \addtogroup mrpt_graphs_grp
24  @{ */
25 
26 /** Used in mrpt::graphs export functions to .dot files \sa
27  * mrpt::graphs::CDirectedGraph::saveAsDot */
29 {
30  /** If true (default=false), an "[constraint=false]" will be added to all
31  * edges (see Graphviz docs). */
33  /** If provided, these textual names will be used for naming the nodes
34  * instead of their numeric IDs given in the edges. */
35  std::map<TNodeID, std::string> node_names;
36  /** If provided, an extra line will be added setting Graphviz properties for
37  * each node, e.g. to set a node position, use the string "pos = \"x,y\"" */
38  std::map<TNodeID, std::string> node_props;
39 
40  TGraphvizExportParams() = default;
41 };
42 
43 namespace detail
44 {
45 /** An empty structure */
47 {
49 };
50 } // namespace detail
51 
52 /** A directed graph with the argument of the template specifying the type of
53  * the annotations in the edges.
54  * This class only keeps a list of edges (in the member \a edges), so there is
55  * no information stored for each node but its existence referred by a node_ID.
56  *
57  * Note that edges are stored as a std::multimap<> to allow <b>multiple
58  * edges</b> between the same pair of nodes.
59  *
60  * \sa mrpt::graphs::CDijkstra, mrpt::graphs::CNetworkOfPoses,
61  * mrpt::graphs::CDirectedTree
62  * \ingroup mrpt_graphs_grp
63  */
64 template <
65  class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
67 {
68  public:
69  /** The type of each global pose in \a nodes: an extension of the \a
70  * TYPE_EDGES pose with any optional user-defined data */
71  struct edge_t : public TYPE_EDGES, public EDGE_ANNOTATIONS
72  {
73  // Replicate possible constructors:
74  inline edge_t() : TYPE_EDGES() {}
75  template <typename... Args>
76  inline edge_t(Args&&... a) : TYPE_EDGES(std::forward<Args>(a)...)
77  {
78  }
79  constexpr static auto getClassName()
80  {
81  using namespace mrpt::typemeta;
82  return literal("edge_t<") + TTypeName<TYPE_EDGES>::get() +
84  literal(">");
85  }
86  };
87  /** Underlying type for edge_t = TYPE_EDGES + annotations */
88  using edge_underlying_t = TYPE_EDGES;
89  /** The type of the member \a edges */
90  using edges_map_t = std::multimap<TPairNodeIDs, edge_t>;
91  using iterator = typename edges_map_t::iterator;
92  using reverse_iterator = typename edges_map_t::reverse_iterator;
93  using const_iterator = typename edges_map_t::const_iterator;
94  using const_reverse_iterator = typename edges_map_t::const_reverse_iterator;
95  /**\brief Handy self type */
97 
98  /** The public member with the directed edges in the graph */
100 
101  /** Copy constructor from a multimap<pair< >, > */
102  inline CDirectedGraph(const edges_map_t& obj) : edges(obj) {}
103  /** Default constructor */
104  inline CDirectedGraph() : edges() {}
105  inline iterator begin() { return edges.begin(); }
106  inline iterator rbegin() { return edges.rbegin(); }
107  inline iterator end() { return edges.end(); }
108  inline iterator rend() { return edges.rend(); }
109  inline const_iterator begin() const { return edges.begin(); }
110  inline const_iterator rbegin() const { return edges.rbegin(); }
111  inline const_iterator end() const { return edges.end(); }
112  inline const_iterator rend() const { return edges.rend(); }
113  /** @name Edges/nodes utility methods
114  @{ */
115 
116  /** The number of edges in the graph */
117  inline size_t edgeCount() const { return edges.size(); }
118  /** Erase all edges */
119  inline void clearEdges() { edges.clear(); }
120  /** Insert an edge (from -> to) with the given edge value. \sa
121  * insertEdgeAtEnd */
122  inline void insertEdge(
123  TNodeID from_nodeID, TNodeID to_nodeID, const edge_t& edge_value)
124  {
125  alignas(MRPT_MAX_STATIC_ALIGN_BYTES)
126  typename edges_map_t::value_type entry(
127  std::make_pair(from_nodeID, to_nodeID), edge_value);
128  edges.insert(entry);
129  }
130 
131  /** Insert an edge (from -> to) with the given edge value (more efficient
132  * version to be called if you know that the end will go at the end of the
133  * sorted std::multimap). \sa insertEdge */
134  inline void insertEdgeAtEnd(
135  TNodeID from_nodeID, TNodeID to_nodeID, const edge_t& edge_value)
136  {
137  alignas(MRPT_MAX_STATIC_ALIGN_BYTES)
138  typename edges_map_t::value_type entry(
139  std::make_pair(from_nodeID, to_nodeID), edge_value);
140  edges.insert(edges.end(), entry);
141  }
142 
143  /** Test if the given directed edge exists. */
144  inline bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const
145  {
146  return edges.find(std::make_pair(from_nodeID, to_nodeID)) !=
147  edges.end();
148  }
149 
150  /** Return a reference to the content of a given edge.
151  * If several edges exist between the given nodes, the first one is
152  * returned.
153  * \exception std::exception if the given edge does not exist
154  * \sa getEdges
155  */
156  edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
157  {
158  iterator it = edges.find(std::make_pair(from_nodeID, to_nodeID));
159  if (it == edges.end())
160  {
162  "Edge %u->%u does not exist", (unsigned)from_nodeID,
163  (unsigned)to_nodeID);
164  }
165  else
166  return it->second;
167  }
168 
169  /** Return a reference to the content of a given edge.
170  * If several edges exist between the given nodes, the first one is
171  * returned.
172  * \exception std::exception if the given edge does not exist
173  * \sa getEdges
174  */
175  const edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
176  {
177  const_iterator it = edges.find(std::make_pair(from_nodeID, to_nodeID));
178  if (it == edges.end())
179  {
181  "Edge %u->%u does not exist", (unsigned)from_nodeID,
182  (unsigned)to_nodeID);
183  }
184  else
185  return it->second;
186  }
187 
188  /** Return a pair<first,last> of iterators to the range of edges between two
189  * given nodes. \sa getEdge */
190  std::pair<iterator, iterator> getEdges(
191  TNodeID from_nodeID, TNodeID to_nodeID)
192  {
193  return edges.equal_range(std::make_pair(from_nodeID, to_nodeID));
194  }
195  /** Return a pair<first,last> of const iterators to the range of edges
196  * between two given nodes. \sa getEdge */
197  std::pair<const_iterator, const_iterator> getEdges(
198  TNodeID from_nodeID, TNodeID to_nodeID) const
199  {
200  return edges.equal_range(std::make_pair(from_nodeID, to_nodeID));
201  }
202 
203  /** Erase all edges between the given nodes (it has no effect if no edge
204  * existed)
205  */
206  inline void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID)
207  {
208  edges.erase(std::make_pair(from_nodeID, to_nodeID));
209  }
210 
211  /** Return a list of all the node_ID's of the graph, generated from all the
212  * nodes that appear in the list of edges
213  */
214  void getAllNodes(std::set<TNodeID>& lstNode_IDs) const
215  {
216  lstNode_IDs.clear();
217  for (auto it = edges.begin(); it != edges.end(); ++it)
218  {
219  lstNode_IDs.insert(it->first.first);
220  lstNode_IDs.insert(it->first.second);
221  }
222  }
223 
224  /** Less efficient way to get all nodes that returns a copy of the set
225  * object \sa getAllNodes( std::set<TNodeID> &lstNode_IDs) */
226  inline std::set<TNodeID> getAllNodes() const
227  {
228  std::set<TNodeID> lst;
229  getAllNodes(lst);
230  return lst;
231  }
232 
233  /** Count how many different node IDs appear in the graph edges.
234  */
236  {
237  std::set<TNodeID> aux;
238  for (typename edges_map_t::const_iterator it = edges.begin();
239  it != edges.end(); ++it)
240  {
241  aux.insert(it->first.first);
242  aux.insert(it->first.second);
243  }
244  return aux.size();
245  }
246 
247  /** Return the list of all neighbors of "nodeID", by creating a list of
248  * their node IDs. \sa getAdjacencyMatrix */
250  const TNodeID nodeID, std::set<TNodeID>& neighborIDs) const
251  {
252  neighborIDs.clear();
253  for (typename edges_map_t::const_iterator it = edges.begin();
254  it != edges.end(); ++it)
255  {
256  if (it->first.first == nodeID)
257  neighborIDs.insert(it->first.second);
258  else if (it->first.second == nodeID)
259  neighborIDs.insert(it->first.first);
260  }
261  }
262  /** Return the list of all neighbors of "nodeID", by creating a list of
263  * their node IDs. \sa getAdjacencyMatrix */
264  std::set<TNodeID> getNeighborsOf(const TNodeID nodeID) const
265  {
266  std::set<TNodeID> neighborIDs;
267  this->getNeighborsOf(nodeID, neighborIDs);
268  return neighborIDs;
269  }
270 
271  /** Return a map from node IDs to all its neighbors (that is, connected
272  * nodes, regardless of the edge direction)
273  * This is a much more efficient method than calling getNeighborsOf() for
274  * each node in the graph.
275  * Possible values for the template argument MAP_NODEID_SET_NODEIDS are:
276  * - std::map<TNodeID, std::set<TNodeID> >
277  * - mrpt::containers::map_as_vector<TNodeID, std::set<TNodeID> >
278  * \sa getNeighborsOf
279  */
280  template <class MAP_NODEID_SET_NODEIDS>
281  void getAdjacencyMatrix(MAP_NODEID_SET_NODEIDS& outAdjacency) const
282  {
283  outAdjacency.clear();
284  for (auto it = edges.begin(); it != edges.end(); ++it)
285  {
286  outAdjacency[it->first.first].insert(it->first.second);
287  outAdjacency[it->first.second].insert(it->first.first);
288  }
289  }
290 
291  /** Just like \a getAdjacencyMatrix but return only the adjacency for those
292  * node_ids in the set \a onlyForTheseNodes
293  * (both endings nodes of an edge must be within the set for it to be
294  * returned) */
295  template <class MAP_NODEID_SET_NODEIDS, class SET_NODEIDS>
297  MAP_NODEID_SET_NODEIDS& outAdjacency,
298  const SET_NODEIDS& onlyForTheseNodes) const
299  {
300  outAdjacency.clear();
301  const typename SET_NODEIDS::const_iterator setEnd =
302  onlyForTheseNodes.end();
303  for (typename edges_map_t::const_iterator it = edges.begin();
304  it != edges.end(); ++it)
305  {
306  if (onlyForTheseNodes.find(it->first.first) == setEnd ||
307  onlyForTheseNodes.find(it->first.second) == setEnd)
308  continue;
309  outAdjacency[it->first.first].insert(it->first.second);
310  outAdjacency[it->first.second].insert(it->first.first);
311  }
312  }
313 
314  /** @} */ // end of edge/nodes utilities
315 
316  /** @name I/O utilities
317  @{ */
318 
319  /** Save the graph in a Graphviz (.dot files) text format; useful for
320  * quickly rendering the graph with "dot"
321  * \return false on any error */
322  bool saveAsDot(
323  std::ostream& o,
324  const TGraphvizExportParams& p = TGraphvizExportParams()) const
325  {
326  o << "digraph G {\n";
327  for (const_iterator it = begin(); it != end(); ++it)
328  {
329  const TNodeID id1 = it->first.first;
330  const TNodeID id2 = it->first.second;
331  std::string s1, s2;
332  if (!p.node_names.empty())
333  {
334  auto itNam1 = p.node_names.find(id1);
335  if (itNam1 != p.node_names.end()) s1 = itNam1->second;
336  auto itNam2 = p.node_names.find(id2);
337  if (itNam2 != p.node_names.end()) s2 = itNam2->second;
338  }
339  if (s1.empty()) s1 = std::to_string(id1);
340  if (s2.empty()) s2 = std::to_string(id2);
341  if (p.node_props.empty())
342  {
343  auto itP1 = p.node_props.find(id1);
344  if (itP1 != p.node_props.end())
345  o << "\"" << s1 << "\""
346  << " [" << itP1->second << "];\n";
347  auto itP2 = p.node_props.find(id2);
348  if (itP2 != p.node_props.end())
349  o << "\"" << s2 << "\""
350  << " [" << itP2->second << "];\n";
351  }
352  o << " \"" << s1 << "\" -> \"" << s2 << "\"";
353  if (p.mark_edges_as_not_constraint) o << " [constraint=false]";
354  o << ";\n";
355  }
356  return !((o << "}\n").fail());
357  }
358 
359  /** \overload */
360  bool saveAsDot(
361  const std::string& fileName,
362  const TGraphvizExportParams& p = TGraphvizExportParams()) const
363  {
364  std::ofstream f(fileName.c_str());
365  if (!f.is_open()) return false;
366  return saveAsDot(f, p);
367  }
368  /** @} */
369 
370 }; // end class CDirectedGraph
371 
372 /** @} */
373 } // namespace graphs
374 } // namespace mrpt
std::pair< const_iterator, const_iterator > getEdges(TNodeID from_nodeID, TNodeID to_nodeID) const
Return a pair<first,last> of const iterators to the range of edges between two given nodes...
A directed graph with the argument of the template specifying the type of the annotations in the edge...
The type of each global pose in nodes: an extension of the TYPE_EDGES pose with any optional user-def...
const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
Return a reference to the content of a given edge.
const_iterator rbegin() const
std::string to_string(T v)
Just like std::to_string(), but with an overloaded version for std::string arguments.
Definition: format.h:36
std::map< TNodeID, std::string > node_names
If provided, these textual names will be used for naming the nodes instead of their numeric IDs given...
edges_map_t edges
The public member with the directed edges in the graph.
void getNeighborsOf(const TNodeID nodeID, std::set< TNodeID > &neighborIDs) const
Return the list of all neighbors of "nodeID", by creating a list of their node IDs.
typename edges_map_t::const_reverse_iterator const_reverse_iterator
void getAdjacencyMatrix(MAP_NODEID_SET_NODEIDS &outAdjacency, const SET_NODEIDS &onlyForTheseNodes) const
Just like getAdjacencyMatrix but return only the adjacency for those node_ids in the set onlyForThese...
std::set< TNodeID > getAllNodes() const
Less efficient way to get all nodes that returns a copy of the set object.
std::map< TNodeID, std::string > node_props
If provided, an extra line will be added setting Graphviz properties for each node, e.g.
const_iterator end() const
STL namespace.
std::pair< iterator, iterator > getEdges(TNodeID from_nodeID, TNodeID to_nodeID)
Return a pair<first,last> of iterators to the range of edges between two given nodes.
void clearEdges()
Erase all edges.
bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const
Test if the given directed edge exists.
const_iterator begin() const
A template to obtain the type of its argument as a string at compile time.
Definition: TTypeName.h:69
CDirectedGraph(const edges_map_t &obj)
Copy constructor from a multimap<pair< >, >
static constexpr auto getClassName()
CDirectedGraph()
Default constructor.
void getAdjacencyMatrix(MAP_NODEID_SET_NODEIDS &outAdjacency) const
Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge dir...
constexpr auto literal(const char(&lit)[N_PLUS_1]) -> string_literal< N_PLUS_1 - 1 >
Definition: static_string.h:46
const_iterator rend() const
#define DECLARE_TTYPENAME_CLASSNAME(_CLASSNAME)
Like DECLARE_CUSTOM_TTYPENAME(), but for use within the class declaration body.
Definition: TTypeName.h:104
void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
Insert an edge (from -> to) with the given edge value.
bool saveAsDot(const std::string &fileName, const TGraphvizExportParams &p=TGraphvizExportParams()) const
CPOSE edge_underlying_t
Underlying type for edge_t = TYPE_EDGES + annotations.
typename edges_map_t::reverse_iterator reverse_iterator
size_t countDifferentNodesInEdges() const
Count how many different node IDs appear in the graph edges.
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
void getAllNodes(std::set< TNodeID > &lstNode_IDs) const
Return a list of all the node_ID&#39;s of the graph, generated from all the nodes that appear in the list...
Used in mrpt::graphs export functions to .dot files.
edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
Return a reference to the content of a given edge.
typename edges_map_t::const_iterator const_iterator
bool mark_edges_as_not_constraint
If true (default=false), an "[constraint=false]" will be added to all edges (see Graphviz docs)...
std::multimap< TPairNodeIDs, edge_t > edges_map_t
The type of the member edges.
uint64_t TNodeID
A generic numeric type for unique IDs of nodes or entities.
Definition: TNodeID.h:16
size_t edgeCount() const
The number of edges in the graph.
void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID)
Erase all edges between the given nodes (it has no effect if no edge existed)
void insertEdgeAtEnd(TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
Insert an edge (from -> to) with the given edge value (more efficient version to be called if you kno...
#define THROW_EXCEPTION_FMT(_FORMAT_STRING,...)
Definition: exceptions.h:69
std::set< TNodeID > getNeighborsOf(const TNodeID nodeID) const
Return the list of all neighbors of "nodeID", by creating a list of their node IDs.
bool saveAsDot(std::ostream &o, const TGraphvizExportParams &p=TGraphvizExportParams()) const
Save the graph in a Graphviz (.dot files) text format; useful for quickly rendering the graph with "d...



Page generated by Doxygen 1.8.14 for MRPT 2.0.1 Git: 0fef1a6d7 Fri Apr 3 23:00:21 2020 +0200 at vie abr 3 23:20:28 CEST 2020