Rake-Compress Trees (RC-Trees)
A library for maintaining Dynamic Trees

Copyright (c) 2004
Guy Blelloch, Umut Acar, Jorge Vittes
School of Computer Science
Carnegie Mellon University
5000 Forbes Avenue
Pittsburgh, Pennsylvania  15213-3891
Please send bugs and comments to blelloch@cs.cmu.edu

Created as part of the Aladdin Center, supported in part by NSF Grant
CCR-0122581.  There is no warranty whatsoever.  Use at your own risk.
These programs may be freely redistributed under the condition that the
copyright notices in each file.

This library is designed to support many interfaces for dynamic trees.
All interfaces support link (adding an edge) and cut (deleting an
edge) operations, but they can support different types of queries and
data updates on the tree.  The user can specialize it to their own
operations, or can use one of the several supplied interfaces.  The
ideas behind the library are described in a paper:

  An Experimental Analysis of Change Propagation in Dynamic Trees
  Umut A. Acar, Guy E. Blelloch, Jorge L. Vittes
  CMU Technical Report #???

The paper can be found as part of the release in RCtrees.ps.

The release consists of the following directories:

rcTrees: This contains the main library that supports all the
  different interfaces for dynamic trees, and implements the link and
  cut operations.  It allows abstract data to be stored at each node
  of the support tree.  The particular interface needs to define what
  this data is and how it is manipulated.

All the following interfaces assume that edges are weighted and that
the tree is not rooted.  It is easy to add information that can root a
tree.  The distance between two vertices in the same tree is
defined as the sum of the weights of edges on the path and is denoted
as d(u,v).

center: This supports finding the center of a tree.  The center is the
  vertex v that maximizes Max{v' in V} d(v,v').

closest: This supports finding for a vertex v the closest marked
  vertex in a forest.  Each vertex can be dynamically marked or unmarked.

diameter: This supports finding the diameter of a tree.  The diameter
  is Max{u,v in V} d(u,v).

median: This supports finding the median of a tree.  The median is the
  vertex v that minimized Sum{v' in V} d(v,v').

path: Finds the maximum weight edge on a path between any two vertices.

subtree: Find the maximum weight edge on any subtree.

------------------------------------------------------------------------------

To compile go to any of the interface subdirectories and run make.
In addition to making the library for that interface it will compile
Example.c which is an example of how to use it.