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:
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".
#include <mrpt/math/graphs.h>
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. |
typedef std::list<TEdgeInfo> mrpt::math::CDirectedTree< TYPE_EDGES >::TListEdges |
typedef std::map<TNodeID,TListEdges> mrpt::math::CDirectedTree< TYPE_EDGES >::TMapNode2ListEdges |
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().
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().
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.
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().
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.
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().
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().
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().
Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN:exported at Tue Jan 25 21:56:31 UTC 2011 |