Main MRPT website > C++ reference for MRPT 1.4.0
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-2016, 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 
36  TGraphvizExportParams() : mark_edges_as_not_constraint(false)
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 
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;
71 
72  /** The public member with the directed edges in the graph */
73  edges_map_t edges;
74 
75 
76  inline CDirectedGraph(const edges_map_t &obj) : edges(obj) { } //!< Copy constructor from a multimap<pair< >, >
77  inline CDirectedGraph() : edges() {} //!< Default constructor
78 
79  inline iterator begin() { return edges.begin(); }
80  inline iterator end() { return edges.end(); }
81  inline const_iterator begin() const { return edges.begin(); }
82  inline const_iterator end() const { return edges.end(); }
83 
84  /** @name Edges/nodes utility methods
85  @{ */
86 
87  inline size_t edgeCount() const { return edges.size(); } //!< The number of edges in the graph
88  inline void clearEdges() { edges.clear(); } //!< Erase all edges
89 
90 
91  /** Insert an edge (from -> to) with the given edge value. \sa insertEdgeAtEnd */
92  inline void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID,const edge_t &edge_value )
93  {
94  MRPT_ALIGN16 typename edges_map_t::value_type entry(
95  std::make_pair(from_nodeID,to_nodeID),
96  edge_value);
97  edges.insert(entry);
98  }
99 
100  /** 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 */
101  inline void insertEdgeAtEnd(TNodeID from_nodeID, TNodeID to_nodeID,const edge_t &edge_value )
102  {
103  MRPT_ALIGN16 typename edges_map_t::value_type entry(
104  std::make_pair(from_nodeID,to_nodeID),
105  edge_value);
106  edges.insert(edges.end(), entry);
107  }
108 
109  /** Test is the given directed edge exists. */
110  inline bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const
111  { return edges.find(std::make_pair(from_nodeID,to_nodeID))!=edges.end(); }
112 
113  /** Return a reference to the content of a given edge.
114  * If several edges exist between the given nodes, the first one is returned.
115  * \exception std::exception if the given edge does not exist
116  * \sa getEdges
117  */
118  edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
119  {
120  iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
121  if (it==edges.end())
122  THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
123  else return it->second;
124  }
125 
126  /** Return a reference to the content of a given edge.
127  * If several edges exist between the given nodes, the first one is returned.
128  * \exception std::exception if the given edge does not exist
129  * \sa getEdges
130  */
131  const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
132  {
133  const_iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
134  if (it==edges.end())
135  THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
136  else return it->second;
137  }
138 
139  /** Return a pair<first,last> of iterators to the range of edges between two given nodes. \sa getEdge */
140  std::pair<iterator,iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) {
141  return edges.equal_range( std::make_pair(from_nodeID,to_nodeID) );
142  }
143  /** Return a pair<first,last> of const iterators to the range of edges between two given nodes. \sa getEdge */
144  std::pair<const_iterator,const_iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) const {
145  return edges.equal_range( std::make_pair(from_nodeID,to_nodeID) );
146  }
147 
148  /** Erase all edges between the given nodes (it has no effect if no edge existed)
149  */
150  inline void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID) {
151  edges.erase(std::make_pair(from_nodeID,to_nodeID));
152  }
153 
154  /** Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges
155  */
156  void getAllNodes( std::set<TNodeID> &lstNode_IDs) const
157  {
158  lstNode_IDs.clear();
159  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
160  {
161  lstNode_IDs.insert(it->first.first);
162  lstNode_IDs.insert(it->first.second);
163  }
164  }
165 
166  /** Less efficient way to get all nodes that returns a copy of the set object \sa getAllNodes( std::set<TNodeID> &lstNode_IDs) */
167  inline std::set<TNodeID> getAllNodes() const { std::set<TNodeID> lst; getAllNodes(lst); return lst; }
168 
169  /** Count how many different node IDs appear in the graph edges.
170  */
172  {
173  std::set<TNodeID> aux;
174  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
175  {
176  aux.insert(it->first.first);
177  aux.insert(it->first.second);
178  }
179  return aux.size();
180  }
181 
182  /** Return the list of all neighbors of "nodeID", by creating a list of their node IDs. \sa getAdjacencyMatrix */
183  void getNeighborsOf(const TNodeID nodeID, std::set<TNodeID> &neighborIDs) const
184  {
185  neighborIDs.clear();
186  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
187  {
188  if (it->first.first==nodeID)
189  neighborIDs.insert(it->first.second);
190  else if (it->first.second==nodeID)
191  neighborIDs.insert(it->first.first);
192  }
193  }
194 
195  /** Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction)
196  * This is a much more efficient method than calling getNeighborsOf() for each node in the graph.
197  * Possible values for the template argument MAP_NODEID_SET_NODEIDS are:
198  * - std::map<TNodeID, std::set<TNodeID> >
199  * - mrpt::utils::map_as_vector<TNodeID, std::set<TNodeID> >
200  * \sa getNeighborsOf
201  */
202  template <class MAP_NODEID_SET_NODEIDS>
203  void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS &outAdjacency ) const
204  {
205  outAdjacency.clear();
206  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
207  {
208  outAdjacency[it->first.first].insert(it->first.second);
209  outAdjacency[it->first.second].insert(it->first.first);
210  }
211  }
212 
213  /** Just like \a getAdjacencyMatrix but return only the adjacency for those node_ids in the set \a onlyForTheseNodes
214  * (both endings nodes of an edge must be within the set for it to be returned) */
215  template <class MAP_NODEID_SET_NODEIDS,class SET_NODEIDS>
216  void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS &outAdjacency, const SET_NODEIDS &onlyForTheseNodes ) const
217  {
218  outAdjacency.clear();
219  const typename SET_NODEIDS::const_iterator setEnd = onlyForTheseNodes.end();
220  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
221  {
222  if (onlyForTheseNodes.find(it->first.first)==setEnd || onlyForTheseNodes.find(it->first.second)==setEnd)
223  continue;
224  outAdjacency[it->first.first].insert(it->first.second);
225  outAdjacency[it->first.second].insert(it->first.first);
226  }
227  }
228 
229  /** @} */ // end of edge/nodes utilities
230 
231 
232  /** @name I/O utilities
233  @{ */
234 
235  /** Save the graph in a Graphviz (.dot files) text format; useful for quickly rendering the graph with "dot"
236  * \return false on any error */
237  bool saveAsDot(std::ostream &o, const TGraphvizExportParams &p = TGraphvizExportParams() ) const
238  {
239  o << "digraph G {\n";
240  for (const_iterator it=begin();it!=end();++it)
241  {
242  const TNodeID id1 = it->first.first;
243  const TNodeID id2 = it->first.second;
244  std::string s1,s2;
245  if (!p.node_names.empty())
246  {
247  std::map<TNodeID,std::string>::const_iterator itNam1=p.node_names.find(id1);
248  if (itNam1!=p.node_names.end()) s1 =itNam1->second;
249  std::map<TNodeID,std::string>::const_iterator itNam2=p.node_names.find(id2);
250  if (itNam2!=p.node_names.end()) s2 =itNam2->second;
251  }
252  if (s1.empty()) s1 = mrpt::format("%u",static_cast<unsigned int>(id1));
253  if (s2.empty()) s2 = mrpt::format("%u",static_cast<unsigned int>(id2));
254  if (p.node_props.empty())
255  {
256  std::map<TNodeID,std::string>::const_iterator itP1=p.node_props.find(id1);
257  if (itP1!=p.node_props.end()) o << "\""<<s1<<"\""<< " [" << itP1->second << "];\n";
258  std::map<TNodeID,std::string>::const_iterator itP2=p.node_props.find(id2);
259  if (itP2!=p.node_props.end()) o << "\""<<s2<<"\""<< " [" << itP2->second << "];\n";
260  }
261  o << " \"" << s1 << "\" -> \"" << s2 << "\"";
262  if (p.mark_edges_as_not_constraint) o << " [constraint=false]";
263  o << ";\n";
264  }
265  return !((o << "}\n").fail());
266  }
267 
268  /** \overload */
269  bool saveAsDot(const std::string &fileName, const TGraphvizExportParams &p = TGraphvizExportParams() ) const
270  {
271  std::ofstream f(fileName.c_str());
272  if (!f.is_open()) return false;
273  return saveAsDot(f,p);
274  }
275  /** @} */
276 
277  }; // end class CDirectedGraph
278 
279  /** @} */
280  } // End of namespace
281 
282  // Specialization of TTypeName must occur in the same namespace:
283  namespace utils
284  {
286  }
287 
288 } // End of namespace
289 #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...
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...
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.
EIGEN_STRONG_INLINE iterator end()
Definition: eigen_plugins.h:27
bool saveAsDot(const std::string &fileName, const TGraphvizExportParams &p=TGraphvizExportParams()) const
std::set< TNodeID > getAllNodes() const
Less efficient way to get all nodes that returns a copy of the set object.
edges_map_t edges
The public member with the directed edges in the graph.
std::string BASE_IMPEXP format(const char *fmt,...) MRPT_printf_format_check(1
A std::string version of C sprintf.
#define THROW_EXCEPTION(msg)
Scalar * iterator
Definition: eigen_plugins.h:23
EIGEN_STRONG_INLINE iterator begin()
Definition: eigen_plugins.h:26
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"".
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...
const Scalar * const_iterator
Definition: eigen_plugins.h:24
size_t countDifferentNodesInEdges() const
Count how many different node IDs appear in the graph edges.
void clearEdges()
Erase all edges.
const_iterator end() const
CDirectedGraph(const edges_map_t &obj)
Copy constructor from a multimap<pair< >, >
edges_map_t::iterator iterator
CDirectedGraph()
Default constructor.
uint64_t TNodeID
The type for node IDs in graphs of different types.
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...
void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
Insert an edge (from -> to) with the given edge value.
std::pair< TNodeID, TNodeID > TPairNodeIDs
A pair of node IDs.
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)
size_t edgeCount() const
The number of edges in the graph.
std::string BASE_IMPEXP format(const char *fmt,...) MRPT_printf_format_check(1
A std::string version of C sprintf.
mrpt::aligned_containers< TPairNodeIDs, edge_t >::multimap_t edges_map_t
The type of the member edges.
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...
const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
Return a reference to the content of a given edge.
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
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.
const_iterator begin() const
bool mark_edges_as_not_constraint
If true (default=false), an "[constraint=false]" will be added to all edges (see Graphviz docs)...
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...
bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const
Test is the given directed edge exists.
std::multimap< TYPE1, TYPE2, std::less< TYPE1 >, Eigen::aligned_allocator< std::pair< const TYPE1, TYPE2 > > > multimap_t
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.
#define MRPT_ALIGN16
edges_map_t::const_iterator const_iterator
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.11 for MRPT 1.4.0 SVN: at Mon Aug 15 11:50:21 UTC 2016