Main MRPT website > C++ reference
MRPT logo

graphs.h

Go to the documentation of this file.
00001 /* +---------------------------------------------------------------------------+
00002    |          The Mobile Robot Programming Toolkit (MRPT) C++ library          |
00003    |                                                                           |
00004    |                   http://mrpt.sourceforge.net/                            |
00005    |                                                                           |
00006    |   Copyright (C) 2005-2011  University of Malaga                           |
00007    |                                                                           |
00008    |    This software was written by the Machine Perception and Intelligent    |
00009    |      Robotics Lab, University of Malaga (Spain).                          |
00010    |    Contact: Jose-Luis Blanco  <jlblanco@ctima.uma.es>                     |
00011    |                                                                           |
00012    |  This file is part of the MRPT project.                                   |
00013    |                                                                           |
00014    |     MRPT is free software: you can redistribute it and/or modify          |
00015    |     it under the terms of the GNU General Public License as published by  |
00016    |     the Free Software Foundation, either version 3 of the License, or     |
00017    |     (at your option) any later version.                                   |
00018    |                                                                           |
00019    |   MRPT is distributed in the hope that it will be useful,                 |
00020    |     but WITHOUT ANY WARRANTY; without even the implied warranty of        |
00021    |     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         |
00022    |     GNU General Public License for more details.                          |
00023    |                                                                           |
00024    |     You should have received a copy of the GNU General Public License     |
00025    |     along with MRPT.  If not, see <http://www.gnu.org/licenses/>.         |
00026    |                                                                           |
00027    +---------------------------------------------------------------------------+ */
00028 #ifndef  MRPT_GRAPHS_H
00029 #define  MRPT_GRAPHS_H
00030 
00031 #include <mrpt/math/utils.h>
00032 #include <set>
00033 
00034 /*---------------------------------------------------------------
00035         Class
00036   ---------------------------------------------------------------*/
00037 namespace mrpt
00038 {
00039         namespace math
00040         {
00041                 using mrpt::utils::TNodeID;
00042 
00043                 /** @name Graph-related classes
00044                     @{ */
00045 
00046                 /** A directed graph with the argument of the template specifying the type of the annotations in the edges.
00047                   *  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.
00048                   *
00049                   *  Note that edges are stored as a std::multimap<> to allow <b>multiple edges</b> between the same pair of nodes.
00050                   *
00051                   * \sa mrpt::math::CDijkstra, mrpt::poses::CNetworkOfPoses, mrpt::math::CDirectedTree
00052                   */
00053                 template<class TYPE_EDGES>
00054                 class CDirectedGraph
00055                 {
00056                 public:
00057                         typedef TYPE_EDGES                             edge_t;  //!< The type of the graph edges
00058                         typedef typename mrpt::aligned_containers<TPairNodeIDs,edge_t>::multimap_t      edges_map_t;  //!< The type of the member \a edges
00059                         typedef typename edges_map_t::iterator         iterator;
00060                         typedef typename edges_map_t::const_iterator   const_iterator;
00061 
00062                         /** The public member with the directed edges in the graph */
00063                         edges_map_t   edges;
00064 
00065 
00066                         inline CDirectedGraph(const edges_map_t &obj) : edges(obj) { }  //!< Copy constructor from a multimap<pair< >, >
00067                         inline CDirectedGraph() : edges() {}  //!< Default constructor
00068 
00069                         inline iterator begin() { return edges.begin(); }
00070                         inline iterator end() { return edges.end(); }
00071                         inline const_iterator begin() const { return edges.begin(); }
00072                         inline const_iterator end() const { return edges.end(); }
00073 
00074 
00075                         /** @name Edges/nodes utility methods
00076                                 @{ */
00077 
00078                         inline size_t edgeCount() const { return edges.size(); }  //!< The number of edges in the graph
00079                         inline void clearEdges() { edges.clear(); } //!< Erase all edges
00080 
00081 
00082                         /** Insert an edge (from -> to) with the given edge value. \sa insertEdgeAtEnd */
00083                         inline void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID,const edge_t &edge_value )
00084                         {
00085                                 EIGEN_ALIGN16 typename edges_map_t::value_type entry(
00086                                         std::make_pair(from_nodeID,to_nodeID),
00087                                         edge_value);
00088                                 edges.insert(entry);
00089                         }
00090 
00091                         /** 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 */
00092                         inline void insertEdgeAtEnd(TNodeID from_nodeID, TNodeID to_nodeID,const edge_t &edge_value )
00093                         {
00094                                 EIGEN_ALIGN16 typename edges_map_t::value_type entry(
00095                                         std::make_pair(from_nodeID,to_nodeID),
00096                                         edge_value);
00097                                 edges.insert(edges.end(), entry);
00098                         }
00099 
00100                         /** Test is the given directed edge exists. */
00101                         inline bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const
00102                         { return edges.find(std::make_pair(from_nodeID,to_nodeID))!=edges.end(); }
00103 
00104                         /** Return a reference to the content of a given edge.
00105                           *  If several edges exist between the given nodes, the first one is returned.
00106                           * \exception std::exception if the given edge does not exist
00107                           * \sa getEdges
00108                           */
00109                         edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID)
00110                         {
00111                                 iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
00112                                 if (it==edges.end())
00113                                         THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
00114                                 else return it->second;
00115                         }
00116 
00117                         /** Return a reference to the content of a given edge.
00118                           *  If several edges exist between the given nodes, the first one is returned.
00119                           * \exception std::exception if the given edge does not exist
00120                           * \sa getEdges
00121                           */
00122                         const edge_t & getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const
00123                         {
00124                                 const_iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
00125                                 if (it==edges.end())
00126                                         THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
00127                                 else return it->second;
00128                         }
00129 
00130                         /** Return a pair<first,last> of iterators to the range of edges between two given nodes. \sa getEdge  */
00131                         std::pair<iterator,iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) {
00132                                 return edges.equal_range( std::make_pair(from_nodeID,to_nodeID) );
00133                         }
00134                         /** Return a pair<first,last> of const iterators to the range of edges between two given nodes.  \sa getEdge */
00135                         std::pair<const_iterator,const_iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) const {
00136                                 return edges.equal_range( std::make_pair(from_nodeID,to_nodeID) );
00137                         }
00138 
00139                         /** Erase all edges between the given nodes (it has no effect if no edge existed)
00140                           */
00141                         inline void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID) {
00142                                 edges.erase(std::make_pair(from_nodeID,to_nodeID));
00143                         }
00144 
00145                         /** Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges
00146                           */
00147                         void getAllNodes( std::set<TNodeID> &lstNode_IDs) const
00148                         {
00149                                 lstNode_IDs.clear();
00150                                 for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
00151                                 {
00152                                         lstNode_IDs.insert(it->first.first);
00153                                         lstNode_IDs.insert(it->first.second);
00154                                 }
00155                         }
00156 
00157                         /** Less efficient way to get all nodes that returns a copy of the set object \sa getAllNodes( std::set<TNodeID> &lstNode_IDs) */
00158                         inline std::set<TNodeID> getAllNodes() const { std::set<TNodeID> lst; getAllNodes(lst); return lst; }
00159 
00160                         /** Count how many different node IDs appear in the graph edges.
00161                           */
00162                         size_t countDifferentNodesInEdges() const
00163                         {
00164                                 std::set<TNodeID> aux;
00165                                 for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
00166                                 {
00167                                         aux.insert(it->first.first);
00168                                         aux.insert(it->first.second);
00169                                 }
00170                                 return aux.size();
00171                         }
00172 
00173                         /** Return the list of all neighbors of "nodeID", by creating a list of their node IDs. \sa getAdjacencyMatrix */
00174                         void getNeighborsOf(const TNodeID nodeID, std::set<TNodeID> &neighborIDs) const
00175                         {
00176                                 neighborIDs.clear();
00177                                 for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
00178                                 {
00179                                         if (it->first.first==nodeID)
00180                                                 neighborIDs.insert(it->first.second);
00181                                         else if (it->first.second==nodeID)
00182                                                 neighborIDs.insert(it->first.first);
00183                                 }
00184                         }
00185 
00186                         /** Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction)
00187                           *  This is a much more efficient method than calling getNeighborsOf() for each node in the graph.
00188                           *  Possible values for the template argument MAP_NODEID_SET_NODEIDS are:
00189                           *    - std::map<TNodeID, std::set<TNodeID> >
00190                           *    - mrpt::utils::map_as_vector<TNodeID, std::set<TNodeID> >
00191                           * \sa getNeighborsOf
00192                           */
00193                         template <class MAP_NODEID_SET_NODEIDS>
00194                         void getAdjacencyMatrix( MAP_NODEID_SET_NODEIDS  &outAdjacency ) const
00195                         {
00196                                 outAdjacency.clear();
00197                                 for (typename edges_map_t::const_iterator it=edges.begin();it!=edges.end();++it)
00198                                 {
00199                                         outAdjacency[it->first.first].insert(it->first.second);
00200                                         outAdjacency[it->first.second].insert(it->first.first);
00201                                 }
00202                         }
00203 
00204                         /** @} */  // end of edge/nodes utilities
00205 
00206                 }; // end class CDirectedGraph
00207 
00208 
00209                 /** A special kind of graph in the form of a tree with directed edges and optional edge annotations of templatized type "TYPE_EDGES".
00210                   *  The tree is represented by means of:
00211                   *             - \a root: The ID of the root node.
00212                   *             - \a edges_to_children: A map from node ID to all the edges to its children.
00213                   *
00214                   *  This class is less general than CDirectedGraph but more efficient to traverse (see \a visitDepthFirst and \a visitBreadthFirst).
00215                   *
00216                   *  If annotations in edges are not required, you can leave TYPE_EDGES to its default type "uint8_t".
00217                   *  \sa CDirectedGraph, CDijkstra, mrpt::poses::CNetworkOfPoses,
00218                   */
00219                 template <class TYPE_EDGES = uint8_t>
00220                 class CDirectedTree
00221                 {
00222                 public:
00223                         struct TEdgeInfo
00224                         {
00225                                 TNodeID    id;      //!< The ID of the child node.
00226                                 bool       reverse; //!< True if edge direction is child->parent, false if it's parent->child.
00227                                 TYPE_EDGES data;    //!< User data for this edge.
00228                         };
00229                         typedef std::list<TEdgeInfo>          TListEdges;
00230                         typedef std::map<TNodeID,TListEdges>  TMapNode2ListEdges;
00231 
00232                         /** @name Data
00233                             @{ */
00234                         TNodeID            root;               //!< The root of the tree
00235                         TMapNode2ListEdges edges_to_children;  //!< The edges of each node
00236                         /** @} */
00237 
00238                         /** @name Utilities
00239                             @{ */
00240 
00241                         /** Empty all edge data and set "root" to INVALID_NODEID */
00242                         void clear() { edges_to_children.clear(); root = INVALID_NODEID; }
00243 
00244                         /** Virtual base class for user-defined visitors */
00245                         struct Visitor
00246                         {
00247                                 typedef CDirectedTree<TYPE_EDGES> tree_t;
00248 
00249                                 /** Virtual method to be implemented by the user and which will be called during the visit to a graph with visitDepthFirst or visitBreadthFirst
00250                                   *  Specifically, the method will be called once for each <b>edge</b> in the tree.
00251                                   * \param parent [IN] The ID of the parent node.
00252                                   * \param edge_to_child [IN] The edge information from the parent to "edge_to_child.id"
00253                                   * \param depth_level [IN] The "depth level" of the child node "edge_to_child.id" (root node is at 0, its children are at 1, etc.).
00254                                   */
00255                                 virtual void OnVisitNode( const TNodeID parent, const typename tree_t::TEdgeInfo &edge_to_child, const size_t depth_level ) = 0;
00256                         };
00257 
00258                         /** Depth-first visit of all children nodes of a given root (itself excluded from the visit), invoking a user-provided function for each node/edge. \sa visitBreadthFirst */
00259                         void visitDepthFirst( const TNodeID root, Visitor & user_visitor, const size_t root_depth_level =0 ) const
00260                         {
00261                                 const size_t next_depth_level = root_depth_level+1;
00262                                 typename TMapNode2ListEdges::const_iterator itChildren = edges_to_children.find(root);
00263                                 if (itChildren==edges_to_children.end()) return; // No children
00264                                 const TListEdges &children = itChildren->second;
00265                                 for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
00266                                 {
00267                                         user_visitor.OnVisitNode(root,*itEdge,next_depth_level);
00268                                         visitDepthFirst(itEdge->id,user_visitor, next_depth_level); // Recursive depth-first call.
00269                                 }
00270                         }
00271 
00272                         /** Breadth-first visit of all children nodes of a given root (itself excluded from the visit), invoking a user-provided function for each node/edge. \sa visitDepthFirst */
00273                         void visitBreadthFirst( const TNodeID root, Visitor & user_visitor, const size_t root_depth_level =0  ) const
00274                         {
00275                                 const size_t next_depth_level = root_depth_level+1;
00276                                 typename TMapNode2ListEdges::const_iterator itChildren = edges_to_children.find(root);
00277                                 if (itChildren==edges_to_children.end()) return; // No children
00278                                 const TListEdges &children = itChildren->second;
00279                                 for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
00280                                         user_visitor.OnVisitNode(root,*itEdge,next_depth_level);
00281                                 for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
00282                                         visitDepthFirst(itEdge->id,user_visitor,next_depth_level); // Recursive breath-first call.
00283                         }
00284 
00285                         /** Return a text representation of the tree spanned in a depth-first view, as in this example:
00286                           *  \code
00287                           *    0
00288                           *     -> 1
00289                           *     -> 2
00290                           *         -> 4
00291                           *         -> 5
00292                           *     -> 3
00293                           *  \endcode
00294                           */
00295                         std::string getAsTextDescription() const
00296                         {
00297                                 std::ostringstream s;
00298                                 struct CMyVisitor : public mrpt::math::CDirectedTree<TYPE_EDGES>::Visitor
00299                                 {
00300                                         std::ostringstream  &m_s;
00301                                         CMyVisitor(std::ostringstream &s) : m_s(s) { }
00302                                         virtual void OnVisitNode( const TNodeID parent, const typename mrpt::math::CDirectedTree<TYPE_EDGES>::Visitor::tree_t::TEdgeInfo &edge_to_child, const size_t depth_level ) {
00303                                                 m_s << std::string(depth_level*5, ' ') << (edge_to_child.reverse ? "<-" : "->" ) //;
00304                                                         << std::setw(3) << edge_to_child.id << std::endl;
00305                                         }
00306                                 };
00307                                 CMyVisitor myVisitor(s);
00308                                 s << std::setw(3) << root << std::endl;
00309                                 visitDepthFirst( root, myVisitor );
00310                                 return s.str();
00311                         }
00312 
00313                         /** @} */
00314 
00315                 };
00316 
00317                 /** @} */
00318         } // End of namespace
00319 } // End of namespace
00320 #endif



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:40:17 UTC 2011