# TREEPACK Computations using Tree Graphs

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:

• it is connected, that is, given any two pair of nodes i and j, there is a sequence of edges (na,nb),(nb,nc),...(nx,ny),(ny,nz) such that na=i and nz=j;
• if any edge is removed from the graph, it is no longer connected.
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.

### 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++ library 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++ library which generates, ranks and unranks various combinatorial objects.

### 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,
ISBN: 0-12-519260-6,
LC: QA164.N54.
4. Robert Sedgewick,
Algorithms in C,
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.