treepack


treepack, a C++ code which defines, analyzes, and manipulates trees, a simple kind of graph with no circuits. Special cases include rooted and binary trees. Representations include adjacency, arc, Pruefer code, and parent. Operations include center, diameter, eccentricity, enumeration, generation one at a time, random selection, traversal.

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 02 May 2020.