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:

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

Definition at line 52 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 74 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 75 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 89 of file CDirectedTree.h.

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

◆ 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 172 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 142 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