[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

details BinaryForest Class Reference VIGRA

BinaryForest stores a collection of rooted binary trees. More...

#include <vigra/binary_forest.hxx>

Public Types

typedef detail::ArcDescriptor
< index_type > 
Arc
 Arc descriptor type of the present graph.
 
typedef detail::NodeDescriptor
< index_type > 
Node
 Node descriptor type of the present graph.
 

Public Member Functions

Arc addArc (Node const &u, Node const &v)
 Add a new arc from node u to node v. The arc ID is 2*id(u) if v is the left child of u, 2*id(u)+1 otherwise.
 
Node addNode ()
 Add a new node (its node ID will be selected automatically).
 
Arc arcFromId (index_type const &id) const
 Get arc descriptor for id.
 
 BinaryForest ()
 Create an empty forest.
 
Node getChild (Node const &node, size_t i=0) const
 Get child number i of node. Returns the left child if i=0, the right child if i=1, and lemon::INVALID for other values of i or when the respective is undefined.
 
Node getNode (size_t i) const
 Create node cescriptor for ID i, or lemon::INVALID if i is not a valid ID.
 
Node getParent (Node const &node, size_t i=0) const
 Get the parent node descriptor of node, or lemon::INVALID if node is a root or i is non-zero.
 
Node getRoot (size_t i=0) const
 Get the root node descriptor of tree i in the forest, or lemon::INVALID if i is invalid.
 
index_type id (Node const &node) const
 Get ID for node descriptor node.
 
index_type id (Arc const &arc) const
 Get ID for arc descriptor arc.
 
size_t inDegree (Node const &node) const
 Return the number of incoming edges of node. 0 for a root node, 1 otherwise.
 
index_type maxArcId () const
 Return the highest possible arc ID (equivalent to 2*maxNodeId() + 1).
 
index_type maxNodeId () const
 Return the highest existing node ID.
 
size_t merge (BinaryForest const &other)
 Merge two forests and increase the IDs of other to avoid ID clashes. The function returns the offset that has been added to these IDs.
 
Node nodeFromId (index_type const &id) const
 Get node descriptor for id.
 
size_t numArcs () const
 Return the number of arcs. Always less than maxArcId() because not all arcs actually exist.
 
size_t numChildren (Node const &node) const
 Return the number of children of node (equivalent to outDegree()).
 
size_t numNodes () const
 Return the number of nodes (equivalent to maxNodeId()+1).
 
size_t numParents (Node const &node) const
 Return the number of parents of node (equivalent to inDegree()).
 
size_t numRoots () const
 Return the number of trees in the forest.
 
size_t outDegree (Node const &node) const
 Return the number of outgoing edges of node. 0 for a leaf node, 1 or 2 otherwise.
 
Node source (Arc const &arc) const
 Find start node of arc.
 
Node target (Arc const &arc) const
 Find end node of arc.
 
bool valid (Node const &node) const
 Check if node exists.
 
bool valid (Arc const &arc) const
 Check if arc exists.
 

Detailed Description

BinaryForest stores a collection of rooted binary trees.

Each connected component of the BinaryForest is thus a tree, and all edges are directed away from the root node of the corresponding tree.

Note
If there is an arc from node u to node v, then the arc ID is 2*id(u) when v is the left child and 2*id(u)+1 when v is the right child.

The documentation for this class was generated from the following file:

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.11.0 (Fri May 19 2017)