Dynamic Collection of Trees

The data type tree_collection represents a collection of vertex disjoint rooted trees. Each vertex has a double valued cost and contains information of an arbitrary type I.

This data type has probably no direct use in application programs. It can be used as a building block for other data types.

Example

The following program shows how tree_collection can be used in a program.

#include <LEDA/core/tree_collection.h>

using namespace leda;

int main()
{
  tree_collection<int> D;

  //generate 6 trees containing a single vertex
  d_vertex dv1=D.maketree(1);d_vertex dv2=D.maketree(2);
  d_vertex dv3=D.maketree(3);d_vertex dv4=D.maketree(4);
  d_vertex dv5=D.maketree(5);d_vertex dv6=D.maketree(6);
  
  D.link(dv1,dv2); //combine the trees dv1 and dv2:
                   //       dv2
                   //       /
                   //    dv1

  D.link(dv3,dv4); //combine the trees dv3 and dv4:
                   //       dv4
                   //       /
                   //    dv3

  D.link(dv4,dv2); //combine the trees of dv4 and dv2:
                   //     dv2
                   //     / \
                   //  dv1   dv4
                   //          \
                   //           dv3

  D.link(dv6,dv2); //combine the trees of dv6 and dv2:
                   //      dv2
                   //     / | \
                   //  dv1 dv4 dv6
                   //       |
                   //      dv3

  D.cut(dv4);      //cut subtree with root dv4:
                   //      dv2
                   //     /   \
                   //  dv1    dv6       dv4
                   //                    |
                   //                   dv3 

  D.link(dv4,dv6); //combine the trees of dv4 and dv6:
                   //      dv2
                   //     /   \
                   //  dv1    dv6       
                   //          |         
                   //         dv4    
                   //          |
                   //         dv3 

  //compute different functions on D
  std::cout << "Parent of " << D.inf(dv3) 
       << " is " << D.inf(D.parent(dv3))  << std::endl;  
  std::cout << "Root of " << D.inf(dv3) 
       << " is " << D.inf(D.findroot(dv3))  << std::endl;
  double x;
  std::cout << "Findcost(" << D.inf(dv4) << ")=" 
       << D.inf(D.findcost(dv4,x))  << std::endl;

  return 0;
}	  

See also:

Dynamic Trees

Manual Page Dynamic Collection of Trees

User Defined Parameter Types