Template Class CDirectedTree

Defined in File CDirectedTree.h

Nested Relationships

Nested Types

Class Documentation

template<class TYPE_EDGES = uint8_t> class 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(...) )
);

See also

visitDepthFirst

inline void visitBreadthFirst(TNodeID const vroot, Visitor &user_visitor, size_t root_depth_level = 0) const

inline std::string getAsTextDescription() const

Return a text representation of the tree spanned in a depth-first view, as in this example:

0
 -> 1
 -> 2
     -> 4
     -> 5
 -> 3

Data

TNodeID root: The root of the tree

TMapNode2ListEdges edges_to_children: The edges of each node

Public Types

using TListEdges = std::list<TEdgeInfo>

using TMapNode2ListEdges = std::map<TNodeID, TListEdges>

struct TEdgeInfo

Public Functions

inline TEdgeInfo(TNodeID child_id_, bool direction_child_to_parent = false, const TYPE_EDGES &edge_data = TYPE_EDGES()): Edge constructor from data

Public Members

TNodeID id: The ID of the child node.

bool reverse: True if edge direction is child->parent, false if it’s parent->child.

TYPE_EDGES data: User data for this edge.

struct Visitor

Virtual base class for user-defined visitors. Obsolete: Prefer C++11 visitor_t

Public Types

using tree_t = CDirectedTree<TYPE_EDGES>

Public Functions

virtual void OnVisitNode(TNodeID const parent, const typename tree_t::TEdgeInfo &edge_to_child, size_t depth_level) = 0

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