Main MRPT website > C++ reference for MRPT 1.4.0
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-2016, 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
13#include <list>
14
15/*---------------------------------------------------------------
16 Class
17 ---------------------------------------------------------------*/
18namespace mrpt
19{
20 namespace graphs
21 {
22 using mrpt::utils::TNodeID; //!< Make available this typedef in this namespace too
23
24 /** A special kind of graph in the form of a tree with directed edges and optional edge annotations of templatized type "TYPE_EDGES".
25 * The tree is represented by means of:
26 * - \a root: The ID of the root node.
27 * - \a edges_to_children: A map from node ID to all the edges to its children.
28 *
29 * Note that nodes are *not* explicitly listed anywhere: their existence is only inferred from their ID numbers in the list
30 * of edges in the \a edges_to_children data structure. If you want to include information for each node, derive from this class
31 * and create a separte container for that data.
32 *
33 * This class is less general than CDirectedGraph but more efficient to traverse (see \a visitDepthFirst and \a visitBreadthFirst).
34 *
35 * If annotations in edges are not required, you can leave TYPE_EDGES to its default type "uint8_t".
36 *
37 * Example of insertion of a new edge:
38 * \code
39 * typedef CDirectedTree<edge_t> my_tree_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 * \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 TNodeID id; //!< The ID of the child node.
57 bool reverse; //!< True if edge direction is child->parent, false if it's parent->child.
58 TYPE_EDGES data; //!< User data for this edge.
59
60 /** Edge constructor from data */
61 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) { }
62 };
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 */
78
79 /** Virtual base class for user-defined visitors */
80 struct Visitor
81 {
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 ) MRPT_OVERRIDE {
138 m_s << std::string(depth_level*5, ' ') << (edge_to_child.reverse ? "<-" : "->" ) //;
139 << edge_to_child.id << std::endl;
140 }
141 };
142 CMyVisitor myVisitor(s);
143 s << 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
< Make available this typedef in this namespace too
Definition: CDirectedTree.h:52
void clear()
Empty all edge data and set "root" to INVALID_NODEID.
Definition: CDirectedTree.h:77
std::map< TNodeID, TListEdges > TMapNode2ListEdges
Definition: CDirectedTree.h:65
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:94
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),...
std::string getAsTextDescription() const
Return a text representation of the tree spanned in a depth-first view, as in this example:
TNodeID root
The root of the tree.
Definition: CDirectedTree.h:69
std::list< TEdgeInfo > TListEdges
Definition: CDirectedTree.h:64
TMapNode2ListEdges edges_to_children
The edges of each node.
Definition: CDirectedTree.h:70
uint64_t TNodeID
The type for node IDs in graphs of different types.
Definition: types_simple.h:45
#define INVALID_NODEID
Definition: types_simple.h:47
#define MRPT_OVERRIDE
C++11 "override" for virtuals:
Definition: mrpt_macros.h:28
This is the global namespace for all Mobile Robot Programming Toolkit (MRPT) libraries.
TNodeID id
The ID of the child node.
Definition: CDirectedTree.h:56
TYPE_EDGES data
User data for this edge.
Definition: CDirectedTree.h:58
TEdgeInfo(TNodeID child_id_, bool direction_child_to_parent=false, const TYPE_EDGES &edge_data=TYPE_EDGES())
Edge constructor from data.
Definition: CDirectedTree.h:61
bool reverse
True if edge direction is child->parent, false if it's parent->child.
Definition: CDirectedTree.h:57
Virtual base class for user-defined visitors.
Definition: CDirectedTree.h:81
CDirectedTree< TYPE_EDGES > tree_t
Definition: CDirectedTree.h:82
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...



Page generated by Doxygen 1.9.6 for MRPT 1.4.0 SVN: at Thu Mar 23 03:22:58 UTC 2023