MRPT  2.0.4
List of all members | Classes | Public Types
mrpt::graphs::CDirectedTree< TYPE_EDGES > Class Template Reference

Detailed Description

template<class TYPE_EDGES = uint8_t>
class mrpt::graphs::CDirectedTree< TYPE_EDGES >

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:

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

Definition at line 51 of file CDirectedTree.h.

#include <mrpt/graphs/CDirectedTree.h>

Inheritance diagram for mrpt::graphs::CDirectedTree< TYPE_EDGES >:

Classes

struct  TEdgeInfo
 
struct  Visitor
 Virtual base class for user-defined visitors. More...
 

Public Types

using TListEdges = std::list< TEdgeInfo >
 
using TMapNode2ListEdges = std::map< TNodeID, TListEdges >
 

Public Member Functions

Utilities
void clear ()
 Empty all edge data and set "root" to INVALID_NODEID. More...
 
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), invoking a user-provided function for each node/edge. More...
 
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), invoking a user-provided function for each node/edge. More...
 
std::string getAsTextDescription () const
 Return a text representation of the tree spanned in a depth-first view, as in this example: More...
 

Public Attributes

Data
TNodeID root
 The root of the tree. More...
 
TMapNode2ListEdges edges_to_children
 The edges of each node. More...
 

Member Typedef Documentation

◆ TListEdges

template<class TYPE_EDGES = uint8_t>
using mrpt::graphs::CDirectedTree< TYPE_EDGES >::TListEdges = std::list<TEdgeInfo>

Definition at line 73 of file CDirectedTree.h.

◆ TMapNode2ListEdges

template<class TYPE_EDGES = uint8_t>
using mrpt::graphs::CDirectedTree< TYPE_EDGES >::TMapNode2ListEdges = std::map<TNodeID, TListEdges>

Definition at line 74 of file CDirectedTree.h.

Member Function Documentation

◆ clear()

template<class TYPE_EDGES = uint8_t>
void mrpt::graphs::CDirectedTree< TYPE_EDGES >::clear ( )
inline

Empty all edge data and set "root" to INVALID_NODEID.

Definition at line 88 of file CDirectedTree.h.

Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph().

Here is the caller graph for this function:

◆ getAsTextDescription()

template<class TYPE_EDGES = uint8_t>
std::string mrpt::graphs::CDirectedTree< TYPE_EDGES >::getAsTextDescription ( ) const
inline

Return a text representation of the tree spanned in a depth-first view, as in this example:

0
-> 1
-> 2
-> 4
-> 5
-> 3

Definition at line 166 of file CDirectedTree.h.

◆ visitBreadthFirst()

template<class TYPE_EDGES = uint8_t>
void mrpt::graphs::CDirectedTree< TYPE_EDGES >::visitBreadthFirst ( const TNodeID  vroot,
Visitor user_visitor,
const size_t  root_depth_level = 0 
) const
inline

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
visitDepthFirst

Definition at line 139 of file CDirectedTree.h.

◆ visitDepthFirst()

template<class TYPE_EDGES = uint8_t>
void mrpt::graphs::CDirectedTree< TYPE_EDGES >::visitDepthFirst ( const TNodeID  vroot,
Visitor user_visitor,
const size_t  root_depth_level = 0 
) const
inline

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
visitBreadthFirst

Definition at line 119 of file CDirectedTree.h.

Referenced by mrpt::graphs::CDirectedTree< EDGE_TYPE >::getAsTextDescription(), mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitBreadthFirst(), and mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitDepthFirst().

Here is the caller graph for this function:

Member Data Documentation

◆ edges_to_children

template<class TYPE_EDGES = uint8_t>
TMapNode2ListEdges mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children

◆ root

template<class TYPE_EDGES = uint8_t>
TNodeID mrpt::graphs::CDirectedTree< TYPE_EDGES >::root



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