Dynamic TreesThe data type dynamic_trees represents a set of dynamically changing rooted trees. Each edge is directed towards the root and has a weight. Additional user defined information of arbitrary type can be stored at each vertex and each edge.This data type has probably no direct use in application programs. It can be used as a building block for other data types. ExampleThe following program shows how dynamic_trees can be used in a program.#include <LEDA/core/dynamic_trees.h> using namespace leda; int main() { dynamic_trees D; //generate 6 trees containing a single vertex vertex v1=D.make();vertex v2=D.make();vertex v3=D.make(); vertex v4=D.make();vertex v5=D.make();vertex v6=D.make(); D.link(v1,v2,1); //combine the trees v1 and v2: // v2 // 1/ // v1 D.link(v3,v4,2); //combine the trees v3 and v4: // v4 // 2/ // v3 D.link(v4,v2,3); //combine the trees of v4 and v2: // v2 // 1/ \3 // v1 v4 // \2 // v3 D.link(v6,v2,4); //combine the trees of v6 and v2: // v2 // 1/ |3\4 // v1 v4 v6 // |2 // v3 D.cut(v4); //cut subtree with root v4: // v2 // 1/ \4 // v1 v6 v4 // |2 // v3 D.link(v4,v6,1); //combine the trees of v4 and v6: // v2 // 1/ \4 // v1 v6 // |1 // v4 // |2 // v3 //compute functions on D std::cout << "Cost of edge (v3,v4) is " << D.cost(v3) << std::endl; std::cout << "mincost(v3)=" << D.cost(D.mincost(v3)) << std::endl; return 0; } |
See also:Manual Entries: |