mrpt::math::CDirectedTree< TYPE_EDGES > Class Template Reference

---

Detailed Description

template<class TYPE_EDGES = uint8_t>
class mrpt::math::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.

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".

See also:

CDirectedGraph, CDijkstra, mrpt::poses::CNetworkOfPoses,

Definition at line 220 of file graphs.h.

#include <mrpt/math/graphs.h>

List of all members.

Classes
struct	TEdgeInfo
struct	Visitor
	Virtual base class for user-defined visitors. More...
Public Types
typedef std::list< TEdgeInfo >	TListEdges
typedef std::map< TNodeID, TListEdges >	TMapNode2ListEdges
Public Member Functions
Utilities
void	clear ()
	Empty all edge data and set "root" to INVALID_NODEID.
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), invoking a user-provided function for each node/edge.
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), invoking a user-provided function for each node/edge.
std::string	getAsTextDescription () const
	Return a text representation of the tree spanned in a depth-first view, as in this example:
Public Attributes
Data
TNodeID	root
	The root of the tree.
TMapNode2ListEdges	edges_to_children
	The edges of each node.

---

Member Typedef Documentation

template<class TYPE_EDGES = uint8_t>

typedef std::list<TEdgeInfo> mrpt::math::CDirectedTree< TYPE_EDGES >::TListEdges

Definition at line 229 of file graphs.h.

template<class TYPE_EDGES = uint8_t>

typedef std::map<TNodeID,TListEdges> mrpt::math::CDirectedTree< TYPE_EDGES >::TMapNode2ListEdges

Definition at line 230 of file graphs.h.

---

Member Function Documentation

template<class TYPE_EDGES = uint8_t>

void mrpt::math::CDirectedTree< TYPE_EDGES >::clear

(

)

[inline]

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

Definition at line 242 of file graphs.h.

References mrpt::math::CDirectedTree< TYPE_EDGES >::edges_to_children, INVALID_NODEID, and mrpt::math::CDirectedTree< TYPE_EDGES >::root.

Referenced by mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::getTreeGraph().

template<class TYPE_EDGES = uint8_t>

std::string mrpt::math::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 295 of file graphs.h.

References mrpt::math::CDirectedTree< TYPE_EDGES >::TEdgeInfo::id, mrpt::math::CDirectedTree< TYPE_EDGES >::TEdgeInfo::reverse, mrpt::math::CDirectedTree< TYPE_EDGES >::root, and mrpt::math::CDirectedTree< TYPE_EDGES >::visitDepthFirst().

template<class TYPE_EDGES = uint8_t>

void mrpt::math::CDirectedTree< TYPE_EDGES >::visitBreadthFirst	(	const TNodeID	root,
		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 273 of file graphs.h.

References mrpt::math::CDirectedTree< TYPE_EDGES >::edges_to_children, mrpt::math::CDirectedTree< TYPE_EDGES >::Visitor::OnVisitNode(), and mrpt::math::CDirectedTree< TYPE_EDGES >::visitDepthFirst().

template<class TYPE_EDGES = uint8_t>

void mrpt::math::CDirectedTree< TYPE_EDGES >::visitDepthFirst	(	const TNodeID	root,
		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 259 of file graphs.h.

References mrpt::math::CDirectedTree< TYPE_EDGES >::edges_to_children, and mrpt::math::CDirectedTree< TYPE_EDGES >::Visitor::OnVisitNode().

Referenced by mrpt::math::CDirectedTree< TYPE_EDGES >::getAsTextDescription(), and mrpt::math::CDirectedTree< TYPE_EDGES >::visitBreadthFirst().

---

Member Data Documentation

template<class TYPE_EDGES = uint8_t>

TMapNode2ListEdges mrpt::math::CDirectedTree< TYPE_EDGES >::edges_to_children

The edges of each node.

Definition at line 235 of file graphs.h.

Referenced by mrpt::math::CDirectedTree< TYPE_EDGES >::clear(), mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::getTreeGraph(), mrpt::math::CDirectedTree< TYPE_EDGES >::visitBreadthFirst(), and mrpt::math::CDirectedTree< TYPE_EDGES >::visitDepthFirst().

template<class TYPE_EDGES = uint8_t>

TNodeID mrpt::math::CDirectedTree< TYPE_EDGES >::root

The root of the tree.

Definition at line 234 of file graphs.h.

Referenced by mrpt::math::CDirectedTree< TYPE_EDGES >::clear(), mrpt::math::CDirectedTree< TYPE_EDGES >::getAsTextDescription(), and mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::getTreeGraph().