Main MRPT website > C++ reference
MRPT logo
CDirectedGraph.h
Go to the documentation of this file.
1 /* +---------------------------------------------------------------------------+
2  | The Mobile Robot Programming Toolkit (MRPT) C++ library |
3  | |
4  | http://www.mrpt.org/ |
5  | |
6  | Copyright (C) 2005-2012 University of Malaga |
7  | |
8  | This software was written by the Machine Perception and Intelligent |
9  | Robotics Lab, University of Malaga (Spain). |
10  | Contact: Jose-Luis Blanco <jlblanco@ctima.uma.es> |
11  | |
12  | This file is part of the MRPT project. |
13  | |
14  | MRPT is free software: you can redistribute it and/or modify |
15  | it under the terms of the GNU General Public License as published by |
16  | the Free Software Foundation, either version 3 of the License, or |
17  | (at your option) any later version. |
18  | |
19  | MRPT is distributed in the hope that it will be useful, |
20  | but WITHOUT ANY WARRANTY; without even the implied warranty of |
21  | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22  | GNU General Public License for more details. |
23  | |
24  | You should have received a copy of the GNU General Public License |
25  | along with MRPT. If not, see <http://www.gnu.org/licenses/>. |
26  | |
27  +---------------------------------------------------------------------------+ */
28 #ifndef MRPT_DIRECTEDGRAPH_H
29 #define MRPT_DIRECTEDGRAPH_H
30 
31 #include <mrpt/utils/utils_defs.h>
32 //#include <mrpt/math/utils.h>
33 
34 /*---------------------------------------------------------------
35  Class
36  ---------------------------------------------------------------*/
37 namespace mrpt
38 {
39  namespace graphs
40  {
41  using mrpt::utils::TNodeID;
42  using mrpt::utils::TPairNodeIDs;
43 
44  /** \addtogroup mrpt_graphs_grp
45  @{ */
46 
47  namespace detail
48  {
49  /** An empty structure */
50  struct edge_annotations_empty { };
51  }
52 
53  /** A directed graph with the argument of the template specifying the type of the annotations in the edges.
54  * 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.
55  *
56  * Note that edges are stored as a std::multimap<> to allow <b>multiple edges</b> between the same pair of nodes.
57  *
58  * \sa mrpt::math::CDijkstra, mrpt::graphs::CNetworkOfPoses, mrpt::graphs::CDirectedTree
59  * \ingroup mrpt_graphs_grp
60  */
61  template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
62  class CDirectedGraph
63  {
64  public:
65  /** The type of each global pose in \a nodes: an extension of the \a TYPE_EDGES pose with any optional user-defined data */
66  struct edge_t : public TYPE_EDGES, public EDGE_ANNOTATIONS
67  {
68  // Replicate possible constructors:
69  inline edge_t () : TYPE_EDGES() { }
70  template <typename ARG1> inline edge_t (const ARG1 &a1) : TYPE_EDGES(a1) { }
71  template <typename ARG1,typename ARG2> inline edge_t (const ARG1 &a1,const ARG2 &a2) : TYPE_EDGES(a1,a2) { }
72  };
73 
74 
75  typedef typename mrpt::aligned_containers<TPairNodeIDs,edge_t>::multimap_t edges_map_t; //!< The type of the member \a edges
76  typedef typename edges_map_t::iterator iterator;
77  typedef typename edges_map_t::const_iterator const_iterator;
78 
79  /** The public member with the directed edges in the graph */
80  edges_map_t edges;
81 
82 
83  inline CDirectedGraph(const edges_map_t &obj) : edges(obj) { } //!< Copy constructor from a multimap<pair< >, >
84  inline CDirectedGraph() : edges() {} //!< Default constructor
85 
86  inline iterator begin() { return edges.begin(); }
87  inline iterator end() { return edges.end(); }
88  inline const_iterator begin() const { return edges.begin(); }
89  inline const_iterator end() const { return edges.end(); }
90 
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  EIGEN_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  EIGEN_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 is 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  /** Return a reference to the content of a given edge.
122  * If several edges exist between the given nodes, the first one is returned.
123  * \exception std::exception if the given edge does not exist
124  * \sa getEdges
125  */
126  edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
127  {
128  iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
129  if (it==edges.end())
130  THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
131  else return it->second;
132  }
133 
134  /** Return a reference to the content of a given edge.
135  * If several edges exist between the given nodes, the first one is returned.
136  * \exception std::exception if the given edge does not exist
137  * \sa getEdges
138  */
139  const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
140  {
141  const_iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
142  if (it==edges.end())
143  THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
144  else return it->second;
145  }
146 
147  /** Return a pair<first,last> of iterators to the range of edges between two given nodes. \sa getEdge */
148  std::pair<iterator,iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) {
149  return edges.equal_range( std::make_pair(from_nodeID,to_nodeID) );
150  }
151  /** Return a pair<first,last> of const iterators to the range of edges between two given nodes. \sa getEdge */
152  std::pair<const_iterator,const_iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) const {
153  return edges.equal_range( std::make_pair(from_nodeID,to_nodeID) );
154  }
155 
156  /** Erase all edges between the given nodes (it has no effect if no edge existed)
157  */
158  inline void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID) {
159  edges.erase(std::make_pair(from_nodeID,to_nodeID));
160  }
161 
162  /** Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges
163  */
164  void getAllNodes( std::set<TNodeID> &lstNode_IDs) const
165  {
166  lstNode_IDs.clear();
167  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
168  {
169  lstNode_IDs.insert(it->first.first);
170  lstNode_IDs.insert(it->first.second);
171  }
172  }
173 
174  /** Less efficient way to get all nodes that returns a copy of the set object \sa getAllNodes( std::set<TNodeID> &lstNode_IDs) */
175  inline std::set<TNodeID> getAllNodes() const { std::set<TNodeID> lst; getAllNodes(lst); return lst; }
176 
177  /** Count how many different node IDs appear in the graph edges.
178  */
179  size_t countDifferentNodesInEdges() const
180  {
181  std::set<TNodeID> aux;
182  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
183  {
184  aux.insert(it->first.first);
185  aux.insert(it->first.second);
186  }
187  return aux.size();
188  }
189 
190  /** Return the list of all neighbors of "nodeID", by creating a list of their node IDs. \sa getAdjacencyMatrix */
191  void getNeighborsOf(const TNodeID nodeID, std::set<TNodeID> &neighborIDs) const
192  {
193  neighborIDs.clear();
194  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
195  {
196  if (it->first.first==nodeID)
197  neighborIDs.insert(it->first.second);
198  else if (it->first.second==nodeID)
199  neighborIDs.insert(it->first.first);
200  }
201  }
202 
203  /** Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction)
204  * This is a much more efficient method than calling getNeighborsOf() for each node in the graph.
205  * Possible values for the template argument MAP_NODEID_SET_NODEIDS are:
206  * - std::map<TNodeID, std::set<TNodeID> >
207  * - mrpt::utils::map_as_vector<TNodeID, std::set<TNodeID> >
208  * \sa getNeighborsOf
209  */
210  template <class MAP_NODEID_SET_NODEIDS>
211  void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS &outAdjacency ) const
212  {
213  outAdjacency.clear();
214  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
215  {
216  outAdjacency[it->first.first].insert(it->first.second);
217  outAdjacency[it->first.second].insert(it->first.first);
218  }
219  }
220 
221  /** Just like \a getAdjacencyMatrix but return only the adjacency for those node_ids in the set \a onlyForTheseNodes
222  * (both endings nodes of an edge must be within the set for it to be returned) */
223  template <class MAP_NODEID_SET_NODEIDS,class SET_NODEIDS>
224  void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS &outAdjacency, const SET_NODEIDS &onlyForTheseNodes ) const
225  {
226  outAdjacency.clear();
227  const typename SET_NODEIDS::const_iterator setEnd = onlyForTheseNodes.end();
228  for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
229  {
230  if (onlyForTheseNodes.find(it->first.first)==setEnd || onlyForTheseNodes.find(it->first.second)==setEnd)
231  continue;
232  outAdjacency[it->first.first].insert(it->first.second);
233  outAdjacency[it->first.second].insert(it->first.first);
234  }
235  }
236 
237  /** @} */ // end of edge/nodes utilities
238 
239  }; // end class CDirectedGraph
240 
241  /** @} */
242  } // End of namespace
243 } // End of namespace
244 #endif


Page generated by Doxygen 1.8.3 for MRPT 0.9.6 SVN: at Fri Feb 15 22:05:02 EST 2013