treepack


treepack, a C code which performs common calculations involving a special kind of graph known as a tree.

A graph is a collection of objects or "nodes", such that any (unordered) pair of nodes is connected or not connected. If a pair of nodes i and j are connected, we say there is an "edge" between them, and we may describe the edge as (i,j). A graph can be represented by a drawing of dots with lines connecting some of the dots.

A tree is a minimally connected graph; more precisely, it is a graph with two additional properties:

Note that a tree using N nodes will have exactly N-1 edges.

There are several ways to represent a graph on the computer.

For the TREE_ARC representation, we simply store a list of the edges of the tree, that is, pairs of nodes.

For the TREE_PRUEFER representation, a tree of N nodes is represented by a sequence of N-2 integers known as the Pruefer code.

For the TREE_PARENT representation, a tree of N nodes is represented by a list of nodes PARENT, such that, for I = 1 to N - 1, the I-th edge of the tree connects node I to node PARENT(I).

For the TREE_ROOTED representation, a tree is assumed to have the additional property that one node has been designated as the "root".

For the TREE_RB representation, a tree is assumed to have the additional properties that one node has been designated as the "root", and that every node has exactly 1 or 2 edges.

Licensing:

The computer code and data files described and made available on this web page are distributed under the MIT license

Languages:

treepack is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

COMBO, a C code which includes routines for ranking, unranking, enumerating and randomly selecting balanced sequences, cycles, graphs, Gray codes, subsets, partitions, permutations, restricted growth functions, Pruefer codes and trees.

GRAPH_REPRESENTATION, a data directory which contains examples of ways of representing abstract mathematical graphs

SUBSET, a C code which generates, ranks and unranks various combinatorial objects.

treepack_test

Reference:

  1. Alan Gibbons,
    Algorithmic Graph Theory,
    Cambridge University Press, 1985,
    ISBN: 0-5212-8881-9,
    LC: QA166.G53.
  2. Hang Tong Lau,
    Combinatorial Heuristic Algorithms with FORTRAN,
    Springer, 1986,
    ISBN: 3540171614,
    LC: QA402.5.L37.
  3. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms for Computers and Calculators,
    Second Edition,
    Academic Press, 1978,
    ISBN: 0-12-519260-6,
    LC: QA164.N54.
  4. Robert Sedgewick,
    Algorithms in C,
    Addison-Wesley, 1990,
    ISBN: 0-201-51425-7,
    LC: QA76.73.C15S43.
  5. Dennis Stanton, Dennis White,
    Constructive Combinatorics,
    Springer, 1986,
    ISBN: 0387963472,
    LC: QA164.S79.
  6. Krishnaiyan Thulasiraman, M Swamy,
    Graphs: Theory and Algorithms,
    John Wiley, 1992,
    ISBN: 0471513563,
    LC: QA166.T58.

Source Code:


Last revised on 20 August 2019.