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:
    // typedefs

    typedef std::function<void(const TNodeID parent, const TEdgeInfo&edgeToChild, const size_t depthLevel)> visitor_t;

    // structs

    struct TEdgeInfo;
    struct Visitor;

    //
fields

    TNodeID root;
    TMapNode2ListEdges edges_to_children;

    //
methods

    void clear();
    void visitDepthFirst(const TNodeID vroot, const visitor_t& user_visitor, const size_t root_depth_level = 0) const;
    void visitDepthFirst(const TNodeID vroot, Visitor& user_visitor, const size_t root_depth_level = 0) const;
    void visitBreadthFirst(const TNodeID vroot, const visitor_t& 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;

Typedefs

typedef std::function<void(const TNodeID parent, const TEdgeInfo&edgeToChild, const size_t depthLevel)> visitor_t

Virtual method to be implemented by the user and which will be called during the visit to a graph with visitDepthFirst or visitBreadthFirst Specifically, the method will be called once for each edge in the tree.

Parameters:

parent	[IN] The ID of the parent node.
edge_to_child	[IN] The edge information from the parent to “edge_to_child.id”
depth_level	[IN] The “depth level” of the child node “edge_to_child.id” (root node is at 0, its children are at 1, etc.).

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,
    const visitor_t& 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.