MRPT  1.9.9
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-2018, 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 <list>
13 #include <mrpt/graphs/TNodeID.h>
14 #include <sstream>
15 
16 namespace mrpt::graphs
17 {
18 /** A special kind of graph in the form of a tree with directed edges and
19  *optional edge annotations of templatized type "TYPE_EDGES".
20  * The tree is represented by means of:
21  * - \a root: The ID of the root node.
22  * - \a edges_to_children: A map from node ID to all the edges to its
23  *children.
24  *
25  * Note that nodes are *not* explicitly listed anywhere: their existence is
26  *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
28  *information for each node, derive from this class
29  * and create a separate container for that data.
30  *
31  * This class is less general than CDirectedGraph but more efficient to
32  *traverse (see \a visitDepthFirst and \a visitBreadthFirst).
33  *
34  * If annotations in edges are not required, you can leave TYPE_EDGES to its
35  *default type "uint8_t".
36  *
37  * Example of insertion of a new edge:
38  * \code
39  * using my_tree_t = CDirectedTree<edge_t> ;
40  * my_tree_t tree;
41  * TNodeID id_root = XXX;
42  * TNodeID id_child = XXX;
43  * my_tree_t::TListEdges & edges_of_root = tree.edges_to_children[id_root];
44  * edges_of_root.push_back( my_tree_t::TEdgeInfo(id_child,false, edge_t(...) )
45  *);
46  * \endcode
47  *
48  * \sa CDirectedGraph, CDijkstra, mrpt::graphs::CNetworkOfPoses
49  * \ingroup mrpt_graphs_grp
50  */
51 template <class TYPE_EDGES = uint8_t>
53 {
54  public:
55  struct TEdgeInfo
56  {
57  /** The ID of the child node. */
59  /** True if edge direction is child->parent, false if it's
60  * parent->child. */
61  bool reverse;
62  /** User data for this edge. */
63  TYPE_EDGES data;
64 
65  /** Edge constructor from data */
67  TNodeID child_id_, bool direction_child_to_parent = false,
68  const TYPE_EDGES& edge_data = TYPE_EDGES())
69  : id(child_id_), reverse(direction_child_to_parent), data(edge_data)
70  {
71  }
72  };
73 
74  using TListEdges = std::list<TEdgeInfo>;
75  using TMapNode2ListEdges = std::map<TNodeID, TListEdges>;
76 
77  /** @name Data
78  @{ */
79  /** The root of the tree */
81  /** The edges of each node */
83  /** @} */
84 
85  /** @name Utilities
86  @{ */
87 
88  /** Empty all edge data and set "root" to INVALID_NODEID */
89  void clear()
90  {
91  edges_to_children.clear();
93  }
94 
95  /** Virtual base class for user-defined visitors */
96  struct Visitor
97  {
99 
100  /** Virtual method to be implemented by the user and which will be
101  * called during the visit to a graph with visitDepthFirst or
102  * visitBreadthFirst
103  * Specifically, the method will be called once for each <b>edge</b>
104  * in the tree.
105  * \param parent [IN] The ID of the parent node.
106  * \param edge_to_child [IN] The edge information from the parent to
107  * "edge_to_child.id"
108  * \param depth_level [IN] The "depth level" of the child node
109  * "edge_to_child.id" (root node is at 0, its children are at 1, etc.).
110  */
111  virtual void OnVisitNode(
112  const TNodeID parent,
113  const typename tree_t::TEdgeInfo& edge_to_child,
114  const size_t depth_level) = 0;
115  };
116 
117  /** Depth-first visit of all children nodes of a given root (itself excluded
118  * from the visit), invoking a user-provided function for each node/edge.
119  * \sa visitBreadthFirst */
121  const TNodeID vroot, Visitor& user_visitor,
122  const size_t root_depth_level = 0) const
123  {
124  const size_t next_depth_level = root_depth_level + 1;
125  typename TMapNode2ListEdges::const_iterator itChildren =
126  edges_to_children.find(vroot);
127  if (itChildren == edges_to_children.end()) return; // No children
128  const TListEdges& children = itChildren->second;
129  for (typename TListEdges::const_iterator itEdge = children.begin();
130  itEdge != children.end(); ++itEdge)
131  {
132  user_visitor.OnVisitNode(vroot, *itEdge, next_depth_level);
134  itEdge->id, user_visitor,
135  next_depth_level); // Recursive depth-first call.
136  }
137  }
138 
139  /** Breadth-first visit of all children nodes of a given root (itself
140  * excluded from the visit), invoking a user-provided function for each
141  * node/edge. \sa visitDepthFirst */
143  const TNodeID vroot, Visitor& user_visitor,
144  const size_t root_depth_level = 0) const
145  {
146  const size_t next_depth_level = root_depth_level + 1;
147  typename TMapNode2ListEdges::const_iterator itChildren =
148  edges_to_children.find(vroot);
149  if (itChildren == edges_to_children.end()) return; // No children
150  const TListEdges& children = itChildren->second;
151  for (typename TListEdges::const_iterator itEdge = children.begin();
152  itEdge != children.end(); ++itEdge)
153  user_visitor.OnVisitNode(vroot, *itEdge, next_depth_level);
154  for (typename TListEdges::const_iterator itEdge = children.begin();
155  itEdge != children.end(); ++itEdge)
157  itEdge->id, user_visitor,
158  next_depth_level); // Recursive breath-first call.
159  }
160 
161  /** Return a text representation of the tree spanned in a depth-first view,
162  * as in this example:
163  * \code
164  * 0
165  * -> 1
166  * -> 2
167  * -> 4
168  * -> 5
169  * -> 3
170  * \endcode
171  */
173  {
174  std::stringstream s;
175  struct CMyVisitor
176  : public mrpt::graphs::CDirectedTree<TYPE_EDGES>::Visitor
177  {
178  std::stringstream& m_s;
179  CMyVisitor(std::stringstream& s) : m_s(s) {}
180  virtual void OnVisitNode(
181  const TNodeID parent,
182  const typename mrpt::graphs::CDirectedTree<
183  TYPE_EDGES>::Visitor::tree_t::TEdgeInfo& edge_to_child,
184  const size_t depth_level) override
185  {
186  m_s << std::string(depth_level * 5, ' ')
187  << (edge_to_child.reverse ? "<-" : "->") //;
188  << edge_to_child.id << std::endl;
189  }
190  };
191  CMyVisitor myVisitor(s);
192  s << root << std::endl;
193  visitDepthFirst(root, myVisitor);
194  return s.str();
195  }
196 };
197 
198 /** @} */
199 }
200 #endif
201 
202 
std::map< TNodeID, TListEdges > TMapNode2ListEdges
Definition: CDirectedTree.h:75
TMapNode2ListEdges edges_to_children
The edges of each node.
Definition: CDirectedTree.h:82
A special kind of graph in the form of a tree with directed edges and optional edge annotations of te...
Definition: CDirectedTree.h:52
Abstract graph and tree data structures, plus generic graph algorithms.
GLdouble s
Definition: glext.h:3676
Virtual base class for user-defined visitors.
Definition: CDirectedTree.h:96
bool reverse
True if edge direction is child->parent, false if it&#39;s parent->child.
Definition: CDirectedTree.h:61
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...
void visitDepthFirst(const TNodeID vroot, 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)...
TNodeID root
The root of the tree.
Definition: CDirectedTree.h:80
TNodeID id
The ID of the child node.
Definition: CDirectedTree.h:58
GLsizei const GLchar ** string
Definition: glext.h:4101
TEdgeInfo(TNodeID child_id_, bool direction_child_to_parent=false, const TYPE_EDGES &edge_data=TYPE_EDGES())
Edge constructor from data.
Definition: CDirectedTree.h:66
GLuint id
Definition: glext.h:3909
TYPE_EDGES data
User data for this edge.
Definition: CDirectedTree.h:63
uint64_t TNodeID
A generic numeric type for unique IDs of nodes or entities.
Definition: TNodeID.h:16
#define INVALID_NODEID
Definition: TNodeID.h:19
void clear()
Empty all edge data and set "root" to INVALID_NODEID.
Definition: CDirectedTree.h:89
GLsizei GLsizei GLenum GLenum const GLvoid * data
Definition: glext.h:3546
std::string getAsTextDescription() const
Return a text representation of the tree spanned in a depth-first view, as in this example: ...
const Scalar * const_iterator
Definition: eigen_plugins.h:27
void visitBreadthFirst(const TNodeID vroot, 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)...



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: 7d5e6d718 Fri Aug 24 01:51:28 2018 +0200 at lun nov 2 08:35:50 CET 2020