MRPT  2.0.4
CDirectedTree.h
Go to the documentation of this file.
1 /* +------------------------------------------------------------------------+
2  | Mobile Robot Programming Toolkit (MRPT) |
3  | https://www.mrpt.org/ |
4  | |
5  | Copyright (c) 2005-2020, Individual contributors, see AUTHORS file |
6  | See: https://www.mrpt.org/Authors - All rights reserved. |
7  | Released under BSD License. See: https://www.mrpt.org/License |
8  +------------------------------------------------------------------------+ */
9 #pragma once
10 
11 #include <mrpt/graphs/TNodeID.h>
12 #include <list>
13 #include <sstream>
14 
15 namespace mrpt::graphs
16 {
17 /** A special kind of graph in the form of a tree with directed edges and
18  *optional edge annotations of templatized type "TYPE_EDGES".
19  * The tree is represented by means of:
20  * - \a root: The ID of the root node.
21  * - \a edges_to_children: A map from node ID to all the edges to its
22  *children.
23  *
24  * Note that nodes are *not* explicitly listed anywhere: their existence is
25  *only inferred from their ID numbers in the list
26  * of edges in the \a edges_to_children data structure. If you want to include
27  *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
31  *traverse (see \a visitDepthFirst and \a visitBreadthFirst).
32  *
33  * If annotations in edges are not required, you can leave TYPE_EDGES to its
34  *default type "uint8_t".
35  *
36  * Example of insertion of a new edge:
37  * \code
38  * using my_tree_t = CDirectedTree<edge_t> ;
39  * my_tree_t tree;
40  * TNodeID id_root = XXX;
41  * TNodeID id_child = XXX;
42  * my_tree_t::TListEdges & edges_of_root = tree.edges_to_children[id_root];
43  * edges_of_root.push_back( my_tree_t::TEdgeInfo(id_child,false, edge_t(...) )
44  *);
45  * \endcode
46  *
47  * \sa CDirectedGraph, CDijkstra, mrpt::graphs::CNetworkOfPoses
48  * \ingroup mrpt_graphs_grp
49  */
50 template <class TYPE_EDGES = uint8_t>
52 {
53  public:
54  struct TEdgeInfo
55  {
56  /** The ID of the child node. */
58  /** True if edge direction is child->parent, false if it's
59  * parent->child. */
60  bool reverse;
61  /** User data for this edge. */
62  TYPE_EDGES data;
63 
64  /** Edge constructor from data */
66  TNodeID child_id_, bool direction_child_to_parent = false,
67  const TYPE_EDGES& edge_data = TYPE_EDGES())
68  : id(child_id_), reverse(direction_child_to_parent), data(edge_data)
69  {
70  }
71  };
72 
73  using TListEdges = std::list<TEdgeInfo>;
74  using TMapNode2ListEdges = std::map<TNodeID, TListEdges>;
75 
76  /** @name Data
77  @{ */
78  /** The root of the tree */
80  /** The edges of each node */
82  /** @} */
83 
84  /** @name Utilities
85  @{ */
86 
87  /** Empty all edge data and set "root" to INVALID_NODEID */
88  void clear()
89  {
90  edges_to_children.clear();
92  }
93 
94  /** Virtual base class for user-defined visitors */
95  struct Visitor
96  {
98 
99  /** Virtual method to be implemented by the user and which will be
100  * called during the visit to a graph with visitDepthFirst or
101  * visitBreadthFirst
102  * Specifically, the method will be called once for each <b>edge</b>
103  * in the tree.
104  * \param parent [IN] The ID of the parent node.
105  * \param edge_to_child [IN] The edge information from the parent to
106  * "edge_to_child.id"
107  * \param depth_level [IN] The "depth level" of the child node
108  * "edge_to_child.id" (root node is at 0, its children are at 1, etc.).
109  */
110  virtual void OnVisitNode(
111  const TNodeID parent,
112  const typename tree_t::TEdgeInfo& edge_to_child,
113  const size_t depth_level) = 0;
114  };
115 
116  /** Depth-first visit of all children nodes of a given root (itself excluded
117  * from the visit), invoking a user-provided function for each node/edge.
118  * \sa visitBreadthFirst */
120  const TNodeID vroot, Visitor& user_visitor,
121  const size_t root_depth_level = 0) const
122  {
123  const size_t next_depth_level = root_depth_level + 1;
124  auto itChildren = edges_to_children.find(vroot);
125  if (itChildren == edges_to_children.end()) return; // No children
126  const TListEdges& children = itChildren->second;
127  for (auto itEdge = children.begin(); itEdge != children.end(); ++itEdge)
128  {
129  user_visitor.OnVisitNode(vroot, *itEdge, next_depth_level);
131  itEdge->id, user_visitor,
132  next_depth_level); // Recursive depth-first call.
133  }
134  }
135 
136  /** Breadth-first visit of all children nodes of a given root (itself
137  * excluded from the visit), invoking a user-provided function for each
138  * node/edge. \sa visitDepthFirst */
140  const TNodeID vroot, Visitor& user_visitor,
141  const size_t root_depth_level = 0) const
142  {
143  const size_t next_depth_level = root_depth_level + 1;
144  auto itChildren = edges_to_children.find(vroot);
145  if (itChildren == edges_to_children.end()) return; // No children
146  const TListEdges& children = itChildren->second;
147  for (auto itEdge = children.begin(); itEdge != children.end(); ++itEdge)
148  user_visitor.OnVisitNode(vroot, *itEdge, next_depth_level);
149  for (auto itEdge = children.begin(); itEdge != children.end(); ++itEdge)
151  itEdge->id, user_visitor,
152  next_depth_level); // Recursive breath-first call.
153  }
154 
155  /** Return a text representation of the tree spanned in a depth-first view,
156  * as in this example:
157  * \code
158  * 0
159  * -> 1
160  * -> 2
161  * -> 4
162  * -> 5
163  * -> 3
164  * \endcode
165  */
166  std::string getAsTextDescription() const
167  {
168  std::stringstream s;
169  struct CMyVisitor
170  : public mrpt::graphs::CDirectedTree<TYPE_EDGES>::Visitor
171  {
172  std::stringstream& m_s;
173  CMyVisitor(std::stringstream& s) : m_s(s) {}
174  void OnVisitNode(
175  const TNodeID parent,
176  const typename mrpt::graphs::CDirectedTree<
177  TYPE_EDGES>::Visitor::tree_t::TEdgeInfo& edge_to_child,
178  const size_t depth_level) override
179  {
180  m_s << std::string(depth_level * 5, ' ')
181  << (edge_to_child.reverse ? "<-" : "->") //;
182  << edge_to_child.id << std::endl;
183  }
184  };
185  CMyVisitor myVisitor(s);
186  s << root << std::endl;
187  visitDepthFirst(root, myVisitor);
188  return s.str();
189  }
190 };
191 
192 /** @} */
193 } // namespace mrpt::graphs
std::map< TNodeID, TListEdges > TMapNode2ListEdges
Definition: CDirectedTree.h:74
TMapNode2ListEdges edges_to_children
The edges of each node.
Definition: CDirectedTree.h:81
A special kind of graph in the form of a tree with directed edges and optional edge annotations of te...
Definition: CDirectedTree.h:51
Abstract graph and tree data structures, plus generic graph algorithms.
Virtual base class for user-defined visitors.
Definition: CDirectedTree.h:95
bool reverse
True if edge direction is child->parent, false if it&#39;s parent->child.
Definition: CDirectedTree.h:60
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:79
TNodeID id
The ID of the child node.
Definition: CDirectedTree.h:57
TEdgeInfo(TNodeID child_id_, bool direction_child_to_parent=false, const TYPE_EDGES &edge_data=TYPE_EDGES())
Edge constructor from data.
Definition: CDirectedTree.h:65
TYPE_EDGES data
User data for this edge.
Definition: CDirectedTree.h:62
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:88
std::string getAsTextDescription() const
Return a text representation of the tree spanned in a depth-first view, as in this example: ...
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 2.0.4 Git: 33de1d0ad Sat Jun 20 11:02:42 2020 +0200 at sáb jun 20 17:35:17 CEST 2020