Main MRPT website > C++ reference
MRPT logo
CDirectedTree.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_DIRECTED_TREE_H
29 #define MRPT_DIRECTED_TREE_H
30 
31 //#include <mrpt/math/utils.h>
32 #include <mrpt/utils/utils_defs.h>
33 
34 /*---------------------------------------------------------------
35  Class
36  ---------------------------------------------------------------*/
37 namespace mrpt
38 {
39  namespace graphs
40  {
41  using mrpt::utils::TNodeID;
42 
43  /** A special kind of graph in the form of a tree with directed edges and optional edge annotations of templatized type "TYPE_EDGES".
44  * The tree is represented by means of:
45  * - \a root: The ID of the root node.
46  * - \a edges_to_children: A map from node ID to all the edges to its children.
47  *
48  * This class is less general than CDirectedGraph but more efficient to traverse (see \a visitDepthFirst and \a visitBreadthFirst).
49  *
50  * If annotations in edges are not required, you can leave TYPE_EDGES to its default type "uint8_t".
51  * \sa CDirectedGraph, CDijkstra, mrpt::graphs::CNetworkOfPoses,
52  * \ingroup mrpt_graphs_grp
53  */
54  template <class TYPE_EDGES = uint8_t>
55  class CDirectedTree
56  {
57  public:
58  struct TEdgeInfo
59  {
60  TNodeID id; //!< The ID of the child node.
61  bool reverse; //!< True if edge direction is child->parent, false if it's parent->child.
62  TYPE_EDGES data; //!< User data for this edge.
63  };
64  typedef std::list<TEdgeInfo> TListEdges;
65  typedef std::map<TNodeID,TListEdges> TMapNode2ListEdges;
66 
67  /** @name Data
68  @{ */
69  TNodeID root; //!< The root of the tree
70  TMapNode2ListEdges edges_to_children; //!< The edges of each node
71  /** @} */
72 
73  /** @name Utilities
74  @{ */
75 
76  /** Empty all edge data and set "root" to INVALID_NODEID */
77  void clear() { edges_to_children.clear(); root = INVALID_NODEID; }
78 
79  /** Virtual base class for user-defined visitors */
80  struct Visitor
81  {
82  typedef CDirectedTree<TYPE_EDGES> tree_t;
83 
84  /** Virtual method to be implemented by the user and which will be called during the visit to a graph with visitDepthFirst or visitBreadthFirst
85  * Specifically, the method will be called once for each <b>edge</b> in the tree.
86  * \param parent [IN] The ID of the parent node.
87  * \param edge_to_child [IN] The edge information from the parent to "edge_to_child.id"
88  * \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.).
89  */
90  virtual void OnVisitNode( const TNodeID parent, const typename tree_t::TEdgeInfo &edge_to_child, const size_t depth_level ) = 0;
91  };
92 
93  /** 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 */
94  void visitDepthFirst( const TNodeID root, Visitor & user_visitor, const size_t root_depth_level =0 ) const
95  {
96  const size_t next_depth_level = root_depth_level+1;
97  typename TMapNode2ListEdges::const_iterator itChildren = edges_to_children.find(root);
98  if (itChildren==edges_to_children.end()) return; // No children
99  const TListEdges &children = itChildren->second;
100  for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
101  {
102  user_visitor.OnVisitNode(root,*itEdge,next_depth_level);
103  visitDepthFirst(itEdge->id,user_visitor, next_depth_level); // Recursive depth-first call.
104  }
105  }
106 
107  /** 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 */
108  void visitBreadthFirst( const TNodeID root, Visitor & user_visitor, const size_t root_depth_level =0 ) const
109  {
110  const size_t next_depth_level = root_depth_level+1;
111  typename TMapNode2ListEdges::const_iterator itChildren = edges_to_children.find(root);
112  if (itChildren==edges_to_children.end()) return; // No children
113  const TListEdges &children = itChildren->second;
114  for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
115  user_visitor.OnVisitNode(root,*itEdge,next_depth_level);
116  for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
117  visitDepthFirst(itEdge->id,user_visitor,next_depth_level); // Recursive breath-first call.
118  }
119 
120  /** Return a text representation of the tree spanned in a depth-first view, as in this example:
121  * \code
122  * 0
123  * -> 1
124  * -> 2
125  * -> 4
126  * -> 5
127  * -> 3
128  * \endcode
129  */
130  std::string getAsTextDescription() const
131  {
132  std::ostringstream s;
133  struct CMyVisitor : public mrpt::graphs::CDirectedTree<TYPE_EDGES>::Visitor
134  {
135  std::ostringstream &m_s;
136  CMyVisitor(std::ostringstream &s) : m_s(s) { }
137  virtual void OnVisitNode( const TNodeID parent, const typename mrpt::graphs::CDirectedTree<TYPE_EDGES>::Visitor::tree_t::TEdgeInfo &edge_to_child, const size_t depth_level ) {
138  m_s << std::string(depth_level*5, ' ') << (edge_to_child.reverse ? "<-" : "->" ) //;
139  << std::setw(3) << edge_to_child.id << std::endl;
140  }
141  };
142  CMyVisitor myVisitor(s);
143  s << std::setw(3) << root << std::endl;
144  visitDepthFirst( root, myVisitor );
145  return s.str();
146  }
147 
148  };
149 
150  /** @} */
151  } // End of namespace
152 } // End of namespace
153 #endif


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