Main MRPT website > C++ reference for MRPT 1.5.7
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-2017, 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 
12 #include <mrpt/utils/utils_defs.h>
13 #include <mrpt/utils/TTypeName.h>
15 #include <set>
16 #include <map>
17 #include <fstream>
18 
19 namespace mrpt
20 {
21  namespace graphs
22  {
23  using mrpt::utils::TNodeID; //!< Make available this typedef in this namespace too
24  using mrpt::utils::TPairNodeIDs; //!< Make available this typedef in this namespace too
25 
26  /** \addtogroup mrpt_graphs_grp
27  @{ */
28 
29  /** Used in mrpt::graphs export functions to .dot files \sa mrpt::graphs::CDirectedGraph::saveAsDot */
31  {
32  bool mark_edges_as_not_constraint; //!< If true (default=false), an "[constraint=false]" will be added to all edges (see Graphviz docs).
33  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 in the edges.
34  std::map<TNodeID,std::string> node_props; //!< If provided, an extra line will be added setting Graphviz properties for each node, e.g. to set a node position, use the string "pos = \"x,y\""
35 
37  {}
38  };
39 
40  namespace detail
41  {
42  /** An empty structure */
44  }
45 
46  /** A directed graph with the argument of the template specifying the type of the annotations in the edges.
47  * This class only keeps a list of edges (in the member \a edges), so there is no information stored for each node but its existence referred by a node_ID.
48  *
49  * Note that edges are stored as a std::multimap<> to allow <b>multiple edges</b> between the same pair of nodes.
50  *
51  * \sa mrpt::graphs::CDijkstra, mrpt::graphs::CNetworkOfPoses, mrpt::graphs::CDirectedTree
52  * \ingroup mrpt_graphs_grp
53  */
54  template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
56  {
57  public:
58  /** The type of each global pose in \a nodes: an extension of the \a TYPE_EDGES pose with any optional user-defined data */
59  struct edge_t : public TYPE_EDGES, public EDGE_ANNOTATIONS
60  {
61  // Replicate possible constructors:
62  inline edge_t () : TYPE_EDGES() { }
63  template <typename ARG1> inline edge_t (const ARG1 &a1) : TYPE_EDGES(a1) { }
64  template <typename ARG1,typename ARG2> inline edge_t (const ARG1 &a1,const ARG2 &a2) : TYPE_EDGES(a1,a2) { }
65  };
66  typedef TYPE_EDGES edge_underlying_t;
67 
68  typedef typename mrpt::aligned_containers<TPairNodeIDs,edge_t>::multimap_t edges_map_t; //!< The type of the member \a edges
69  typedef typename edges_map_t::iterator iterator;
70  typedef typename edges_map_t::reverse_iterator reverse_iterator;
72  typedef typename edges_map_t::const_reverse_iterator const_reverse_iterator;
73  /**\brief Handy self type */
75 
76  /** The public member with the directed edges in the graph */
78 
79 
80  inline CDirectedGraph(const edges_map_t &obj) : edges(obj) { } //!< Copy constructor from a multimap<pair< >, >
81  inline CDirectedGraph() : edges() {} //!< Default constructor
82 
83  inline iterator begin() { return edges.begin(); }
84  inline iterator rbegin() { return edges.rbegin(); }
85  inline iterator end() { return edges.end(); }
86  inline iterator rend() { return edges.rend(); }
87  inline const_iterator begin() const { return edges.begin(); }
88  inline const_iterator rbegin() const { return edges.rbegin(); }
89  inline const_iterator end() const { return edges.end(); }
90  inline const_iterator rend() const { return edges.rend(); }
91 
92  /** @name Edges/nodes utility methods
93  @{ */
94 
95  inline size_t edgeCount() const { return edges.size(); } //!< The number of edges in the graph
96  inline void clearEdges() { edges.clear(); } //!< Erase all edges
97 
98 
99  /** Insert an edge (from -> to) with the given edge value. \sa insertEdgeAtEnd */
100  inline void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID,const edge_t &edge_value )
101  {
102  MRPT_ALIGN16 typename edges_map_t::value_type entry(
103  std::make_pair(from_nodeID,to_nodeID),
104  edge_value);
105  edges.insert(entry);
106  }
107 
108  /** Insert an edge (from -> to) with the given edge value (more efficient version to be called if you know that the end will go at the end of the sorted std::multimap). \sa insertEdge */
109  inline void insertEdgeAtEnd(TNodeID from_nodeID, TNodeID to_nodeID,const edge_t &edge_value )
110  {
111  MRPT_ALIGN16 typename edges_map_t::value_type entry(
112  std::make_pair(from_nodeID,to_nodeID),
113  edge_value);
114  edges.insert(edges.end(), entry);
115  }
116 
117  /** Test if the given directed edge exists. */
118  inline bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const {
119  return edges.find(std::make_pair(from_nodeID,to_nodeID))!=edges.end();
120  }
121 
122  /** Return a reference to the content of a given edge.
123  * If several edges exist between the given nodes, the first one is returned.
124  * \exception std::exception if the given edge does not exist
125  * \sa getEdges
126  */
127  edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
128  {
129  iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
130  if (it==edges.end())
131  THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
132  else return it->second;
133  }
134 
135  /** Return a reference to the content of a given edge.
136  * If several edges exist between the given nodes, the first one is returned.
137  * \exception std::exception if the given edge does not exist
138  * \sa getEdges
139  */
140  const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
141  {
142  const_iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
143  if (it==edges.end())
144  THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
145  else return it->second;
146  }
147 
148  /** Return a pair<first,last> of iterators to the range of edges between two given nodes. \sa getEdge */
149  std::pair<iterator,iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) {
150  return edges.equal_range(std::make_pair(from_nodeID,to_nodeID));
151  }
152  /** Return a pair<first,last> of const iterators to the range of edges between two given nodes. \sa getEdge */
153  std::pair<const_iterator,const_iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) const {
154  return edges.equal_range(std::make_pair(from_nodeID,to_nodeID));
155  }
156 
157  /** Erase all edges between the given nodes (it has no effect if no edge existed)
158  */
159  inline void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID) {
160  edges.erase(std::make_pair(from_nodeID,to_nodeID));
161  }
162 
163  /** Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges
164  */
165  void getAllNodes( std::set<TNodeID> &lstNode_IDs) const
166  {
167  lstNode_IDs.clear();
168  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
169  {
170  lstNode_IDs.insert(it->first.first);
171  lstNode_IDs.insert(it->first.second);
172  }
173  }
174 
175  /** Less efficient way to get all nodes that returns a copy of the set object \sa getAllNodes( std::set<TNodeID> &lstNode_IDs) */
176  inline std::set<TNodeID> getAllNodes() const { std::set<TNodeID> lst; getAllNodes(lst); return lst; }
177 
178  /** Count how many different node IDs appear in the graph edges.
179  */
181  {
182  std::set<TNodeID> aux;
183  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
184  {
185  aux.insert(it->first.first);
186  aux.insert(it->first.second);
187  }
188  return aux.size();
189  }
190 
191  /** Return the list of all neighbors of "nodeID", by creating a list of their node IDs. \sa getAdjacencyMatrix */
192  void getNeighborsOf(const TNodeID nodeID, std::set<TNodeID> &neighborIDs) const
193  {
194  neighborIDs.clear();
195  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
196  {
197  if (it->first.first==nodeID)
198  neighborIDs.insert(it->first.second);
199  else if (it->first.second==nodeID)
200  neighborIDs.insert(it->first.first);
201  }
202  }
203  /** Return the list of all neighbors of "nodeID", by creating a list of their node IDs. \sa getAdjacencyMatrix */
204  std::set<TNodeID> getNeighborsOf(const TNodeID nodeID) const {
205  std::set<TNodeID> neighborIDs;
206  this->getNeighborsOf(nodeID, neighborIDs);
207  return neighborIDs;
208  }
209 
210  /** Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction)
211  * This is a much more efficient method than calling getNeighborsOf() for each node in the graph.
212  * Possible values for the template argument MAP_NODEID_SET_NODEIDS are:
213  * - std::map<TNodeID, std::set<TNodeID> >
214  * - mrpt::utils::map_as_vector<TNodeID, std::set<TNodeID> >
215  * \sa getNeighborsOf
216  */
217  template <class MAP_NODEID_SET_NODEIDS>
218  void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS &outAdjacency ) const
219  {
220  outAdjacency.clear();
221  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
222  {
223  outAdjacency[it->first.first].insert(it->first.second);
224  outAdjacency[it->first.second].insert(it->first.first);
225  }
226  }
227 
228  /** Just like \a getAdjacencyMatrix but return only the adjacency for those node_ids in the set \a onlyForTheseNodes
229  * (both endings nodes of an edge must be within the set for it to be returned) */
230  template <class MAP_NODEID_SET_NODEIDS,class SET_NODEIDS>
231  void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS &outAdjacency, const SET_NODEIDS &onlyForTheseNodes ) const
232  {
233  outAdjacency.clear();
234  const typename SET_NODEIDS::const_iterator setEnd = onlyForTheseNodes.end();
235  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
236  {
237  if (onlyForTheseNodes.find(it->first.first)==setEnd || onlyForTheseNodes.find(it->first.second)==setEnd)
238  continue;
239  outAdjacency[it->first.first].insert(it->first.second);
240  outAdjacency[it->first.second].insert(it->first.first);
241  }
242  }
243 
244  /** @} */ // end of edge/nodes utilities
245 
246 
247  /** @name I/O utilities
248  @{ */
249 
250  /** Save the graph in a Graphviz (.dot files) text format; useful for quickly rendering the graph with "dot"
251  * \return false on any error */
252  bool saveAsDot(std::ostream &o, const TGraphvizExportParams &p = TGraphvizExportParams() ) const
253  {
254  o << "digraph G {\n";
255  for (const_iterator it=begin();it!=end();++it)
256  {
257  const TNodeID id1 = it->first.first;
258  const TNodeID id2 = it->first.second;
259  std::string s1,s2;
260  if (!p.node_names.empty())
261  {
262  std::map<TNodeID,std::string>::const_iterator itNam1=p.node_names.find(id1);
263  if (itNam1!=p.node_names.end()) s1 =itNam1->second;
264  std::map<TNodeID,std::string>::const_iterator itNam2=p.node_names.find(id2);
265  if (itNam2!=p.node_names.end()) s2 =itNam2->second;
266  }
267  if (s1.empty()) s1 = mrpt::format("%u",static_cast<unsigned int>(id1));
268  if (s2.empty()) s2 = mrpt::format("%u",static_cast<unsigned int>(id2));
269  if (p.node_props.empty())
270  {
271  std::map<TNodeID,std::string>::const_iterator itP1=p.node_props.find(id1);
272  if (itP1!=p.node_props.end()) o << "\""<<s1<<"\""<< " [" << itP1->second << "];\n";
273  std::map<TNodeID,std::string>::const_iterator itP2=p.node_props.find(id2);
274  if (itP2!=p.node_props.end()) o << "\""<<s2<<"\""<< " [" << itP2->second << "];\n";
275  }
276  o << " \"" << s1 << "\" -> \"" << s2 << "\"";
277  if (p.mark_edges_as_not_constraint) o << " [constraint=false]";
278  o << ";\n";
279  }
280  return !((o << "}\n").fail());
281  }
282 
283  /** \overload */
284  bool saveAsDot(const std::string &fileName, const TGraphvizExportParams &p = TGraphvizExportParams() ) const
285  {
286  std::ofstream f(fileName.c_str());
287  if (!f.is_open()) return false;
288  return saveAsDot(f,p);
289  }
290  /** @} */
291 
292  }; // end class CDirectedGraph
293 
294  /** @} */
295  } // End of namespace
296 
297  // Specialization of TTypeName must occur in the same namespace:
298  namespace utils
299  {
301  }
302 
303 } // End of namespace
304 #endif
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
edges_map_t edges
The public member with the directed edges in the graph.
#define THROW_EXCEPTION(msg)
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.
Scalar * iterator
Definition: eigen_plugins.h:23
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::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...
std::set< TNodeID > getAllNodes() const
Less efficient way to get all nodes that returns a copy of the set object.
const_iterator end() const
std::map< TNodeID, std::string > node_props
If provided, an extra line will be added setting Graphviz properties for each node, e.g. to set a node position, use the string "pos = \"x,y"".
const Scalar * const_iterator
Definition: eigen_plugins.h:24
GLsizei GLsizei GLuint * obj
Definition: glext.h:3902
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
CDirectedGraph(const edges_map_t &obj)
Copy constructor from a multimap<pair< >, >
edges_map_t::iterator iterator
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...
uint64_t TNodeID
The type for node IDs in graphs of different types.
const_iterator rend() const
edges_map_t::const_reverse_iterator const_reverse_iterator
void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
Insert an edge (from -> to) with the given edge value.
CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS > self_t
Handy self type.
std::string BASE_IMPEXP format(const char *fmt,...) MRPT_printf_format_check(1
A std::string version of C sprintf.
Definition: format.cpp:21
std::pair< TNodeID, TNodeID > TPairNodeIDs
A pair of node IDs.
bool saveAsDot(const std::string &fileName, const TGraphvizExportParams &p=TGraphvizExportParams()) const
uint64_t TNodeID
The type for node IDs in graphs of different types.
Definition: types_simple.h:45
edge_t(const ARG1 &a1, const ARG2 &a2)
std::string BASE_IMPEXP format(const char *fmt,...) MRPT_printf_format_check(1
A std::string version of C sprintf.
GLsizei const GLchar ** string
Definition: glext.h:3919
mrpt::aligned_containers< TPairNodeIDs, edge_t >::multimap_t edges_map_t
The type of the member edges.
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.
edges_map_t::reverse_iterator reverse_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< TYPE1, TYPE2, std::less< TYPE1 >, Eigen::aligned_allocator< std::pair< const TYPE1, TYPE2 > > > multimap_t
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...
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.
GLfloat GLfloat p
Definition: glext.h:5587
#define MRPT_ALIGN16
edges_map_t::const_iterator const_iterator
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...
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...
#define MRPT_DECLARE_TTYPENAME(_TYPE)
Definition: TTypeName.h:60



Page generated by Doxygen 1.8.14 for MRPT 1.5.7 Git: 5902e14cc Wed Apr 24 15:04:01 2019 +0200 at lun oct 28 01:39:17 CET 2019