Main MRPT website > C++ reference for MRPT 1.5.7
CDirectedTree.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-2017, 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_DIRECTED_TREE_H
10 #define MRPT_DIRECTED_TREE_H
11 
12 #include <mrpt/utils/utils_defs.h>
13 #include <list>
14 
15 namespace mrpt
16 {
17  namespace graphs
18  {
19  using mrpt::utils::TNodeID; //!< Make available this typedef in this namespace too
20 
21  /** A special kind of graph in the form of a tree with directed edges and optional edge annotations of templatized type "TYPE_EDGES".
22  * The tree is represented by means of:
23  * - \a root: The ID of the root node.
24  * - \a edges_to_children: A map from node ID to all the edges to its children.
25  *
26  * Note that nodes are *not* explicitly listed anywhere: their existence is only inferred from their ID numbers in the list
27  * of edges in the \a edges_to_children data structure. If you want to include information for each node, derive from this class
28  * and create a separate container for that data.
29  *
30  * This class is less general than CDirectedGraph but more efficient to traverse (see \a visitDepthFirst and \a visitBreadthFirst).
31  *
32  * If annotations in edges are not required, you can leave TYPE_EDGES to its default type "uint8_t".
33  *
34  * Example of insertion of a new edge:
35  * \code
36  * typedef CDirectedTree<edge_t> my_tree_t;
37  * my_tree_t tree;
38  * TNodeID id_root = XXX;
39  * TNodeID id_child = XXX;
40  * my_tree_t::TListEdges & edges_of_root = tree.edges_to_children[id_root];
41  * edges_of_root.push_back( my_tree_t::TEdgeInfo(id_child,false, edge_t(...) ) );
42  * \endcode
43  *
44  * \sa CDirectedGraph, CDijkstra, mrpt::graphs::CNetworkOfPoses
45  * \ingroup mrpt_graphs_grp
46  */
47  template <class TYPE_EDGES = uint8_t>
49  {
50  public:
51  struct TEdgeInfo
52  {
53  TNodeID id; //!< The ID of the child node.
54  bool reverse; //!< True if edge direction is child->parent, false if it's parent->child.
55  TYPE_EDGES data; //!< User data for this edge.
56 
57  /** Edge constructor from data */
58  TEdgeInfo(TNodeID child_id_, bool direction_child_to_parent=false, const TYPE_EDGES & edge_data = TYPE_EDGES() ) : id(child_id_), reverse(direction_child_to_parent), data(edge_data) { }
59  };
60 
61  typedef std::list<TEdgeInfo> TListEdges;
62  typedef std::map<TNodeID,TListEdges> TMapNode2ListEdges;
63 
64  /** @name Data
65  @{ */
66  TNodeID root; //!< The root of the tree
67  TMapNode2ListEdges edges_to_children; //!< The edges of each node
68  /** @} */
69 
70  /** @name Utilities
71  @{ */
72 
73  /** Empty all edge data and set "root" to INVALID_NODEID */
74  void clear() { edges_to_children.clear(); root = INVALID_NODEID; }
75 
76  /** Virtual base class for user-defined visitors */
77  struct Visitor
78  {
80 
81  /** Virtual method to be implemented by the user and which will be called during the visit to a graph with visitDepthFirst or visitBreadthFirst
82  * Specifically, the method will be called once for each <b>edge</b> in the tree.
83  * \param parent [IN] The ID of the parent node.
84  * \param edge_to_child [IN] The edge information from the parent to "edge_to_child.id"
85  * \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.).
86  */
87  virtual void OnVisitNode( const TNodeID parent, const typename tree_t::TEdgeInfo &edge_to_child, const size_t depth_level ) = 0;
88  };
89 
90  /** 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 */
91  void visitDepthFirst( const TNodeID root, Visitor & user_visitor, const size_t root_depth_level =0 ) const
92  {
93  const size_t next_depth_level = root_depth_level+1;
94  typename TMapNode2ListEdges::const_iterator itChildren = edges_to_children.find(root);
95  if (itChildren==edges_to_children.end()) return; // No children
96  const TListEdges &children = itChildren->second;
97  for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
98  {
99  user_visitor.OnVisitNode(root,*itEdge,next_depth_level);
100  visitDepthFirst(itEdge->id,user_visitor, next_depth_level); // Recursive depth-first call.
101  }
102  }
103 
104  /** 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 */
105  void visitBreadthFirst( const TNodeID root, Visitor & user_visitor, const size_t root_depth_level =0 ) const
106  {
107  const size_t next_depth_level = root_depth_level+1;
108  typename TMapNode2ListEdges::const_iterator itChildren = edges_to_children.find(root);
109  if (itChildren==edges_to_children.end()) return; // No children
110  const TListEdges &children = itChildren->second;
111  for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
112  user_visitor.OnVisitNode(root,*itEdge,next_depth_level);
113  for (typename TListEdges::const_iterator itEdge=children.begin();itEdge!=children.end();++itEdge)
114  visitDepthFirst(itEdge->id,user_visitor,next_depth_level); // Recursive breath-first call.
115  }
116 
117  /** Return a text representation of the tree spanned in a depth-first view, as in this example:
118  * \code
119  * 0
120  * -> 1
121  * -> 2
122  * -> 4
123  * -> 5
124  * -> 3
125  * \endcode
126  */
128  {
129  std::ostringstream s;
130  struct CMyVisitor : public mrpt::graphs::CDirectedTree<TYPE_EDGES>::Visitor
131  {
132  std::ostringstream &m_s;
133  CMyVisitor(std::ostringstream &s) : m_s(s) { }
134  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 ) MRPT_OVERRIDE {
135  m_s << std::string(depth_level*5, ' ') << (edge_to_child.reverse ? "<-" : "->" ) //;
136  << edge_to_child.id << std::endl;
137  }
138  };
139  CMyVisitor myVisitor(s);
140  s << root << std::endl;
141  visitDepthFirst( root, myVisitor );
142  return s.str();
143  }
144 
145  };
146 
147  /** @} */
148  } // End of namespace
149 } // End of namespace
150 #endif
TMapNode2ListEdges edges_to_children
The edges of each node.
Definition: CDirectedTree.h:67
< Make available this typedef in this namespace too
Definition: CDirectedTree.h:48
#define MRPT_OVERRIDE
C++11 "override" for virtuals:
std::list< TEdgeInfo > TListEdges
Definition: CDirectedTree.h:61
#define INVALID_NODEID
const Scalar * const_iterator
Definition: eigen_plugins.h:24
CDirectedTree< TYPE_EDGES > tree_t
Definition: CDirectedTree.h:79
GLdouble s
Definition: glext.h:3602
Virtual base class for user-defined visitors.
Definition: CDirectedTree.h:77
void visitDepthFirst(const TNodeID root, Visitor &user_visitor, const size_t root_depth_level=0) const
Depth-first visit of all children nodes of a given root (itself excluded from the visit)...
Definition: CDirectedTree.h:91
bool reverse
True if edge direction is child->parent, false if it&#39;s parent->child.
Definition: CDirectedTree.h:54
uint64_t TNodeID
The type for node IDs in graphs of different types.
virtual void OnVisitNode(const TNodeID parent, const typename tree_t::TEdgeInfo &edge_to_child, const size_t depth_level)=0
Virtual method to be implemented by the user and which will be called during the visit to a graph wit...
uint64_t TNodeID
The type for node IDs in graphs of different types.
Definition: types_simple.h:45
TNodeID root
The root of the tree.
Definition: CDirectedTree.h:66
TNodeID id
The ID of the child node.
Definition: CDirectedTree.h:53
GLsizei const GLchar ** string
Definition: glext.h:3919
void visitBreadthFirst(const TNodeID root, Visitor &user_visitor, const size_t root_depth_level=0) const
Breadth-first visit of all children nodes of a given root (itself excluded from the visit)...
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
TEdgeInfo(TNodeID child_id_, bool direction_child_to_parent=false, const TYPE_EDGES &edge_data=TYPE_EDGES())
Edge constructor from data.
Definition: CDirectedTree.h:58
GLuint id
Definition: glext.h:3770
TYPE_EDGES data
User data for this edge.
Definition: CDirectedTree.h:55
std::map< TNodeID, TListEdges > TMapNode2ListEdges
Definition: CDirectedTree.h:62
void clear()
Empty all edge data and set "root" to INVALID_NODEID.
Definition: CDirectedTree.h:74
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: glext.h:3520
std::string getAsTextDescription() const
Return a text representation of the tree spanned in a depth-first view, as in this example: ...



Page generated by Doxygen 1.8.14 for MRPT 1.5.7 Git: 8277875f6 Mon Jun 11 02:47:32 2018 +0200 at lun oct 28 01:50:49 CET 2019