template class mrpt::graphs::CDirectedTree¶

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(...) )
);

#include <mrpt/graphs/CDirectedTree.h>

template <class TYPE_EDGES = uint8_t>
class CDirectedTree
{
public:
    // structs

    struct TEdgeInfo;
    struct Visitor;

    //
fields

    TNodeID root;
    TMapNode2ListEdges edges_to_children;

    //
methods

    void clear();
    void visitDepthFirst(const TNodeID vroot, Visitor& user_visitor, const size_t root_depth_level = 0) const;
    void visitBreadthFirst(const TNodeID vroot, Visitor& user_visitor, const size_t root_depth_level = 0) const;
    std::string getAsTextDescription() const;
};

// direct descendants

template <
    class NODE_TYPE_DATA,
    class EDGE_TYPE,
    class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_map_as_vector
    >
class TMoveTree;

Fields¶

TNodeID root

The root of the tree.

TMapNode2ListEdges edges_to_children

The edges of each node.

Methods¶

void clear()

Empty all edge data and set “root” to INVALID_NODEID.

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.