[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]
![]() |
BinaryForest Class Reference | ![]() |
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. | |
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.
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.
© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de) |
html generated using doxygen and Python
|