TREEPACK
Computations using Tree Graphs

TREEPACK is a FORTRAN77 library 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.

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 GNU LGPL license.

Languages:

TREEPACK is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

COMBO, a F77 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

GRF, a data directory which contains a description of the GRF format and some examples.

GRF_IO, a FORTRAN90 library which reads and writes GRF files.

GRF_TO_EPS, a FORTRAN90 library which can make an Encapsulated PostScript (EPS) image of a GRF file.

SUBSET, a FORTRAN77 library which generates, ranks and unranks various combinatorial objects.

TABLE_GRAPH_CODE, a FORTRAN90 program which reads a TABLE file describing a graph, and computes its graph code.

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:

• treepack.f, the source code;
• treepack.sh, commands to compile the source code;

Examples and Tests:

• treepack_prb.f, the calling program;
• treepack_prb.sh, commands to compile, link and run the calling program;
• treepack_prb_output.txt, the output file.

List of Routines:

• CATALAN computes the Catalan numbers, from C(0) to C(N).
• GRAPH_ADJ_EDGE_COUNT counts the number of edges in a graph.
• GRAPH_ADJ_IS_NODE_CONNECTED determines if a graph is nodewise connected.
• GRAPH_ADJ_IS_TREE determines whether a graph is a tree.
• GRAPH_ARC_DEGREE determines the degree of the nodes of a graph.
• GRAPH_ADJ_IS_TREE determines whether a graph is a tree.
• GRAPH_ARC_NODE_COUNT counts the number of nodes in a graph.
• GRAPH_ARC_PRINT prints out a graph from an edge list.
• GRAPH_ARC_TO_GRAPH_ADJ converts an arc list graph to an adjacency graph.
• I4_UNIFORM_AB returns a scaled pseudorandom I4 between A and B.
• I4VEC_HEAP_D reorders an I4VEC into an descending heap.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector.
• I4VEC_PRINT prints an I4VEC.
• I4VEC_SORT_HEAP_A ascending sorts an I4VEC using heap sort.
• I4VEC_SORTED_UNIQUE_COUNT counts the unique elements in a sorted I4VEC.
• PRUEFER_TO_TREE_ARC is given a Pruefer code, and computes the tree.
• PRUEFER_TO_TREE_2 produces the edge list of a tree from its Pruefer code.
• R8_UNIFORM_01 returns a unit pseudorandom R8.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TREE_ARC_CENTER computes the center, eccentricity, and parity of a tree.
• TREE_ARC_DIAM computes the "diameter" of a tree.
• TREE_ARC_RANDOM selects a random labeled tree and its Pruefer code.
• TREE_ARC_TO_PRUEFER is given a labeled tree, and computes its Pruefer code.
• TREE_ENUM enumerates the labeled trees on NNODE nodes.
• TREE_PARENT_NEXT generates, one at a time, all labeled trees.
• TREE_PARENT_TO_ARC converts a tree from parent to arc representation.
• TREE_RB_ENUM returns the number of rooted binary trees with N nodes.
• TREE_RB_LEX_NEXT generates rooted binary trees in lexicographic order.
• TREE_RB_TO_PARENT converts rooted binary tree to parent node representation.
• TREE_RB_YULE adds two nodes to a rooted binary tree using the Yule model.
• TREE_ROOTED_CODE returns the code of a rooted tree.
• TREE_ROOTED_CODE_COMPARE compares a portion of the code for two rooted trees.
• TREE_ROOTED_DEPTH returns the depth of a rooted tree.
• TREE_ROOTED_ENUM counts the number of unlabeled rooted trees.
• TREE_ROOTED_RANDOM selects a random unlabeled rooted tree.
• VEC_NEXT generates all N-vectors of integers modulo a given base.
• VEC_RANDOM selects a random N-vector of integers modulo a given base.

You can go up one level to the FORTRAN77 source codes.