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:
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.
The computer code and data files described and made available on this web page are distributed under the MIT license
treepack is available in a C version and a C++ version and a FORTRAN90 version and a MATLAB version.
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.