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
15#include <set>
16#include <map>
17#include <fstream>
18
19namespace 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
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::const_iterator const_iterator;
71
72 /** The public member with the directed edges in the graph */
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
#define MRPT_DECLARE_TTYPENAME(_TYPE)
Definition: TTypeName.h:60
A directed graph with the argument of the template specifying the type of the annotations in the edge...
bool saveAsDot(const std::string &fileName, const TGraphvizExportParams &p=TGraphvizExportParams()) const
This is an overloaded member function, provided for convenience. It differs from the above function o...
edges_map_t::iterator iterator
edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
Return a reference to the content of a given edge.
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...
CDirectedGraph()
Default constructor.
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.
const_iterator end() const
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.
const_iterator begin() const
void getAllNodes(std::set< TNodeID > &lstNode_IDs) const
Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list...
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.
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...
edges_map_t edges
The public member with the directed 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)
edges_map_t::const_iterator const_iterator
size_t edgeCount() const
The number of edges in the graph.
mrpt::aligned_containers< TPairNodeIDs, edge_t >::multimap_t edges_map_t
The type of the member edges.
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< 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.
std::set< TNodeID > getAllNodes() const
Less efficient way to get all nodes that returns a copy of the set object.
void clearEdges()
Erase all edges.
size_t countDifferentNodesInEdges() const
Count how many different node IDs appear in the graph edges.
CDirectedGraph(const edges_map_t &obj)
Copy constructor from a multimap<pair< >, >
const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
Return a reference to the content of a given edge.
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.
Definition: types_simple.h:45
std::pair< TNodeID, TNodeID > TPairNodeIDs
A pair of node IDs.
Definition: types_simple.h:46
#define MRPT_ALIGN16
Definition: mrpt_macros.h:92
#define THROW_EXCEPTION(msg)
Definition: mrpt_macros.h:110
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
std::string BASE_IMPEXP format(const char *fmt,...) MRPT_printf_format_check(1
A std::string version of C sprintf.
std::multimap< TYPE1, TYPE2, std::less< TYPE1 >, Eigen::aligned_allocator< std::pair< const TYPE1, TYPE2 > > > multimap_t
The type of each global pose in nodes: an extension of the TYPE_EDGES pose with any optional user-def...
edge_t(const ARG1 &a1, const ARG2 &a2)
Used in mrpt::graphs export functions to .dot files.
bool mark_edges_as_not_constraint
If true (default=false), an "[constraint=false]" will be added to all edges (see Graphviz docs).
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...
std::map< TNodeID, std::string > node_props
If provided, an extra line will be added setting Graphviz properties for each node,...



Page generated by Doxygen 1.9.5 for MRPT 1.4.0 SVN: at Sun Nov 27 02:56:26 UTC 2022