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:
Definition at line 56 of file CDirectedTree.h.
#include <mrpt/graphs/CDirectedTree.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. More... | |
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. More... | |
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. 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... | |
typedef std::list<TEdgeInfo> mrpt::graphs::CDirectedTree< TYPE_EDGES >::TListEdges |
Definition at line 78 of file CDirectedTree.h.
typedef std::map<TNodeID, TListEdges> mrpt::graphs::CDirectedTree< TYPE_EDGES >::TMapNode2ListEdges |
Definition at line 79 of file CDirectedTree.h.
|
inline |
Empty all edge data and set "root" to INVALID_NODEID.
Definition at line 93 of file CDirectedTree.h.
Referenced by mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph().
|
inline |
Return a text representation of the tree spanned in a depth-first view, as in this example:
Definition at line 176 of file CDirectedTree.h.
|
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 146 of file CDirectedTree.h.
|
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 124 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().
TMapNode2ListEdges mrpt::graphs::CDirectedTree< TYPE_EDGES >::edges_to_children |
The edges of each node.
Definition at line 86 of file CDirectedTree.h.
Referenced by mrpt::graphs::CDirectedTree< EDGE_TYPE >::clear(), mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph(), mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitBreadthFirst(), and mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitDepthFirst().
TNodeID mrpt::graphs::CDirectedTree< TYPE_EDGES >::root |
The root of the tree.
Definition at line 84 of file CDirectedTree.h.
Referenced by mrpt::graphs::CDirectedTree< EDGE_TYPE >::clear(), mrpt::graphs::CDirectedTree< EDGE_TYPE >::getAsTextDescription(), mrpt::graphs::CDijkstra< TYPE_GRAPH, MAPS_IMPLEMENTATION >::getTreeGraph(), mrpt::nav::PlannerRRT_SE2_TPS::solve(), mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitBreadthFirst(), and mrpt::graphs::CDirectedTree< EDGE_TYPE >::visitDepthFirst().
Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: ae4571287 Thu Nov 23 00:06:53 2017 +0100 at dom oct 27 23:51:55 CET 2019 |