template class mrpt::graphs::CDirectedTree
A special kind of graph in the form of a tree with directed edges and optional edge annotations of templatized type “TYPE_EDGES”.
The tree is represented by means of:
root: The ID of the root node.
edges_to_children: A map from node ID to all the edges to its children.
Note that nodes are not explicitly listed anywhere: their existence is only inferred from their ID numbers in the list of edges in the edges_to_children data structure. If you want to include information for each node, derive from this class and create a separate container for that data.
This class is less general than CDirectedGraph but more efficient to traverse (see visitDepthFirst and visitBreadthFirst).
If annotations in edges are not required, you can leave TYPE_EDGES to its default type “uint8_t”.
Example of insertion of a new edge:
using my_tree_t = CDirectedTree<edge_t> ; my_tree_t tree; TNodeID id_root = XXX; TNodeID id_child = XXX; my_tree_t::TListEdges & edges_of_root = tree.edges_to_children[id_root]; edges_of_root.push_back( my_tree_t::TEdgeInfo(id_child,false, edge_t(...) ) );
See also:
CDirectedGraph, CDijkstra, mrpt::graphs::CNetworkOfPoses
#include <mrpt/graphs/CDirectedTree.h> template <class TYPE_EDGES = uint8_t> class CDirectedTree { public: // typedefs typedef std::function<void(TNodeID const parent, const TEdgeInfo&edgeToChild, size_t depthLevel)> visitor_t; // structs struct TEdgeInfo; struct Visitor; // fields TNodeID root; TMapNode2ListEdges edges_to_children; // methods void clear(); void visitDepthFirst(TNodeID const vroot, const visitor_t& user_visitor, size_t root_depth_level = 0) const; void visitBreadthFirst(TNodeID const vroot, const visitor_t& user_visitor, size_t root_depth_level = 0) const; std::string getAsTextDescription() const; }; // direct descendants template < class NODE_TYPE_DATA, class EDGE_TYPE, class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector > class TMoveTree;
Typedefs
typedef std::function<void(TNodeID const parent, const TEdgeInfo&edgeToChild, size_t depthLevel)> visitor_t
Virtual method to be implemented by the user and which will be called during the visit to a graph with visitDepthFirst or visitBreadthFirst Specifically, the method will be called once for each edge in the tree.
Parameters:
parent |
[IN] The ID of the parent node. |
edge_to_child |
[IN] The edge information from the parent to “edge_to_child.id” |
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.). |
Fields
TNodeID root
The root of the tree.
TMapNode2ListEdges edges_to_children
The edges of each node.
Methods
void clear()
Empty all edge data and set “root” to INVALID_NODEID.
void visitDepthFirst( TNodeID const vroot, const visitor_t& user_visitor, size_t root_depth_level = 0 ) const
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.
See also:
void visitBreadthFirst( TNodeID const vroot, const visitor_t& user_visitor, size_t root_depth_level = 0 ) const
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.
See also:
std::string getAsTextDescription() const
Return a text representation of the tree spanned in a depth-first view, as in this example:
0 -> 1 -> 2 -> 4 -> 5 -> 3