Main MRPT website > C++ reference for MRPT 1.9.9
CDirectedGraph.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | http://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2018, Individual contributors, see AUTHORS file |
6  | See: http://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See details in http://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #ifndef MRPT_DIRECTEDGRAPH_H
10 #define MRPT_DIRECTEDGRAPH_H
11 
15 #include <mrpt/core/exceptions.h>
16 #include <mrpt/graphs/TNodeID.h>
17 #include <set>
18 #include <map>
19 #include <fstream>
20 
21 namespace mrpt
22 {
23 namespace graphs
24 {
25 /** \addtogroup mrpt_graphs_grp
26  @{ */
27 
28 /** Used in mrpt::graphs export functions to .dot files \sa
29  * mrpt::graphs::CDirectedGraph::saveAsDot */
31 {
32  /** If true (default=false), an "[constraint=false]" will be added to all
33  * edges (see Graphviz docs). */
35  /** If provided, these textual names will be used for naming the nodes
36  * instead of their numeric IDs given in the edges. */
37  std::map<TNodeID, std::string> node_names;
38  /** If provided, an extra line will be added setting Graphviz properties for
39  * each node, e.g. to set a node position, use the string "pos = \"x,y\"" */
40  std::map<TNodeID, std::string> node_props;
41 
43 };
44 
45 namespace detail
46 {
47 /** An empty structure */
49 {
51 };
52 } // namespace detail
53 
54 /** A directed graph with the argument of the template specifying the type of
55  * the annotations in the edges.
56  * This class only keeps a list of edges (in the member \a edges), so there is
57  * no information stored for each node but its existence referred by a node_ID.
58  *
59  * Note that edges are stored as a std::multimap<> to allow <b>multiple
60  * edges</b> between the same pair of nodes.
61  *
62  * \sa mrpt::graphs::CDijkstra, mrpt::graphs::CNetworkOfPoses,
63  * mrpt::graphs::CDirectedTree
64  * \ingroup mrpt_graphs_grp
65  */
66 template <class TYPE_EDGES,
67  class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
69 {
70  public:
71  /** The type of each global pose in \a nodes: an extension of the \a
72  * TYPE_EDGES pose with any optional user-defined data */
73  struct edge_t : public TYPE_EDGES, public EDGE_ANNOTATIONS
74  {
75  // Replicate possible constructors:
76  inline edge_t() : TYPE_EDGES() {}
77  template <typename... Args>
78  inline edge_t(Args&&... a) : TYPE_EDGES(std::forward<Args>(a)...)
79  {
80  }
81  constexpr static auto getClassName()
82  {
83  using namespace mrpt::typemeta;
84  return literal("edge_t<") + TTypeName<TYPE_EDGES>::get() +
86  literal(">");
87  }
88  };
89 
90  /** The type of the member \a edges */
92  using iterator = typename edges_map_t::iterator;
93  using reverse_iterator = typename edges_map_t::reverse_iterator;
95  using const_reverse_iterator = typename edges_map_t::const_reverse_iterator;
96  /**\brief Handy self type */
98 
99  /** The public member with the directed edges in the graph */
101 
102  /** Copy constructor from a multimap<pair< >, > */
103  inline CDirectedGraph(const edges_map_t& obj) : edges(obj) {}
104  /** Default constructor */
105  inline CDirectedGraph() : edges() {}
106  inline iterator begin() { return edges.begin(); }
107  inline iterator rbegin() { return edges.rbegin(); }
108  inline iterator end() { return edges.end(); }
109  inline iterator rend() { return edges.rend(); }
110  inline const_iterator begin() const { return edges.begin(); }
111  inline const_iterator rbegin() const { return edges.rbegin(); }
112  inline const_iterator end() const { return edges.end(); }
113  inline const_iterator rend() const { return edges.rend(); }
114  /** @name Edges/nodes utility methods
115  @{ */
116 
117  /** The number of edges in the graph */
118  inline size_t edgeCount() const { return edges.size(); }
119  /** Erase all edges */
120  inline void clearEdges() { edges.clear(); }
121  /** Insert an edge (from -> to) with the given edge value. \sa
122  * insertEdgeAtEnd */
123  inline void insertEdge(
124  TNodeID from_nodeID, TNodeID to_nodeID, const edge_t& edge_value)
125  {
126  alignas(MRPT_MAX_ALIGN_BYTES) 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_ALIGN_BYTES) typename edges_map_t::value_type entry(
138  std::make_pair(from_nodeID, to_nodeID), edge_value);
139  edges.insert(edges.end(), entry);
140  }
141 
142  /** Test if the given directed edge exists. */
143  inline bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const
144  {
145  return edges.find(std::make_pair(from_nodeID, to_nodeID)) !=
146  edges.end();
147  }
148 
149  /** Return a reference to the content of a given edge.
150  * If several edges exist between the given nodes, the first one is
151  * returned.
152  * \exception std::exception if the given edge does not exist
153  * \sa getEdges
154  */
155  edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
156  {
157  iterator it = edges.find(std::make_pair(from_nodeID, to_nodeID));
158  if (it == edges.end())
159  {
161  "Edge %u->%u does not exist", (unsigned)from_nodeID,
162  (unsigned)to_nodeID);
163  }
164  else
165  return it->second;
166  }
167 
168  /** Return a reference to the content of a given edge.
169  * If several edges exist between the given nodes, the first one is
170  * returned.
171  * \exception std::exception if the given edge does not exist
172  * \sa getEdges
173  */
174  const edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
175  {
176  const_iterator it = edges.find(std::make_pair(from_nodeID, to_nodeID));
177  if (it == edges.end())
178  {
180  "Edge %u->%u does not exist", (unsigned)from_nodeID,
181  (unsigned)to_nodeID);
182  }
183  else
184  return it->second;
185  }
186 
187  /** Return a pair<first,last> of iterators to the range of edges between two
188  * given nodes. \sa getEdge */
189  std::pair<iterator, iterator> getEdges(
190  TNodeID from_nodeID, TNodeID to_nodeID)
191  {
192  return edges.equal_range(std::make_pair(from_nodeID, to_nodeID));
193  }
194  /** Return a pair<first,last> of const iterators to the range of edges
195  * between two given nodes. \sa getEdge */
196  std::pair<const_iterator, const_iterator> getEdges(
197  TNodeID from_nodeID, TNodeID to_nodeID) const
198  {
199  return edges.equal_range(std::make_pair(from_nodeID, to_nodeID));
200  }
201 
202  /** Erase all edges between the given nodes (it has no effect if no edge
203  * existed)
204  */
205  inline void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID)
206  {
207  edges.erase(std::make_pair(from_nodeID, to_nodeID));
208  }
209 
210  /** Return a list of all the node_ID's of the graph, generated from all the
211  * nodes that appear in the list of edges
212  */
213  void getAllNodes(std::set<TNodeID>& lstNode_IDs) const
214  {
215  lstNode_IDs.clear();
216  for (typename edges_map_t::const_iterator it = edges.begin();
217  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::utils::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 (typename edges_map_t::const_iterator it = edges.begin();
285  it != edges.end(); ++it)
286  {
287  outAdjacency[it->first.first].insert(it->first.second);
288  outAdjacency[it->first.second].insert(it->first.first);
289  }
290  }
291 
292  /** Just like \a getAdjacencyMatrix but return only the adjacency for those
293  * node_ids in the set \a onlyForTheseNodes
294  * (both endings nodes of an edge must be within the set for it to be
295  * returned) */
296  template <class MAP_NODEID_SET_NODEIDS, class SET_NODEIDS>
298  MAP_NODEID_SET_NODEIDS& outAdjacency,
299  const SET_NODEIDS& onlyForTheseNodes) const
300  {
301  outAdjacency.clear();
302  const typename SET_NODEIDS::const_iterator setEnd =
303  onlyForTheseNodes.end();
304  for (typename edges_map_t::const_iterator it = edges.begin();
305  it != edges.end(); ++it)
306  {
307  if (onlyForTheseNodes.find(it->first.first) == setEnd ||
308  onlyForTheseNodes.find(it->first.second) == setEnd)
309  continue;
310  outAdjacency[it->first.first].insert(it->first.second);
311  outAdjacency[it->first.second].insert(it->first.first);
312  }
313  }
314 
315  /** @} */ // end of edge/nodes utilities
316 
317  /** @name I/O utilities
318  @{ */
319 
320  /** Save the graph in a Graphviz (.dot files) text format; useful for
321  * quickly rendering the graph with "dot"
322  * \return false on any error */
323  bool saveAsDot(
324  std::ostream& o,
326  {
327  o << "digraph G {\n";
328  for (const_iterator it = begin(); it != end(); ++it)
329  {
330  const TNodeID id1 = it->first.first;
331  const TNodeID id2 = it->first.second;
332  std::string s1, s2;
333  if (!p.node_names.empty())
334  {
336  p.node_names.find(id1);
337  if (itNam1 != p.node_names.end()) s1 = itNam1->second;
339  p.node_names.find(id2);
340  if (itNam2 != p.node_names.end()) s2 = itNam2->second;
341  }
342  if (s1.empty()) s1 = std::to_string(id1);
343  if (s2.empty()) s2 = std::to_string(id2);
344  if (p.node_props.empty())
345  {
347  p.node_props.find(id1);
348  if (itP1 != p.node_props.end())
349  o << "\"" << s1 << "\""
350  << " [" << itP1->second << "];\n";
352  p.node_props.find(id2);
353  if (itP2 != p.node_props.end())
354  o << "\"" << s2 << "\""
355  << " [" << itP2->second << "];\n";
356  }
357  o << " \"" << s1 << "\" -> \"" << s2 << "\"";
358  if (p.mark_edges_as_not_constraint) o << " [constraint=false]";
359  o << ";\n";
360  }
361  return !((o << "}\n").fail());
362  }
363 
364  /** \overload */
365  bool saveAsDot(
366  const std::string& fileName,
368  {
369  std::ofstream f(fileName.c_str());
370  if (!f.is_open()) return false;
371  return saveAsDot(f, p);
372  }
373  /** @} */
374 
375 }; // end class CDirectedGraph
376 
377 /** @} */
378 } // namespace graphs
379 } // namespace mrpt
380 #endif
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...
Scalar * iterator
Definition: eigen_plugins.h:26
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.
#define MRPT_MAX_ALIGN_BYTES
mrpt::aligned_std_multimap< TPairNodeIDs, edge_t > edges_map_t
The type of the member edges.
const_iterator rbegin() const
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.
GLsizei GLsizei GLuint * obj
Definition: glext.h:4070
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:65
std::multimap< KEY, VALUE, std::less< KEY >, mrpt::aligned_allocator_cpp11< std::pair< const KEY, VALUE > >> aligned_std_multimap
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:43
const_iterator rend() const
#define DECLARE_TTYPENAME_CLASSNAME(_CLASSNAME)
Like DECLARE_CUSTOM_TTYPENAME(), but for use within the class declaration body.
Definition: TTypeName.h:100
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
GLsizei const GLchar ** string
Definition: glext.h:4101
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)...
uint64_t TNodeID
A generic numeric type for unique IDs of nodes or entities.
Definition: TNodeID.h:17
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:43
GLubyte GLubyte GLubyte a
Definition: glext.h:6279
GLfloat GLfloat p
Definition: glext.h:6305
const Scalar * const_iterator
Definition: eigen_plugins.h:27
std::string std::string to_string(T v)
Just like std::to_string(), but with an overloaded version for std::string arguments.
Definition: format.h:27
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 1.9.9 Git: ad3a9d8ae Tue May 1 23:10:22 2018 -0700 at lun oct 28 00:14:14 CET 2019