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:
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.