TREEPACK
Computations using Tree Graphs
TREEPACK
is a FORTRAN90 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.
Note that a tree using N nodes will have exactly N1 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 N2 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 Ith 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 FORTRAN90 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 FORTRAN90 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:

Alan Gibbons,
Algorithmic Graph Theory,
Cambridge University Press, 1985,
ISBN: 0521288819,
LC: QA166.G53.

Hang Tong Lau,
Combinatorial Heuristic Algorithms with FORTRAN,
Springer, 1986,
ISBN: 3540171614,
LC: QA402.5.L37.

Albert Nijenhuis, Herbert Wilf,
Combinatorial Algorithms for Computers and Calculators,
Second Edition,
Academic Press, 1978,
ISBN: 0125192606,
LC: QA164.N54.

Robert Sedgewick,
Algorithms in C,
AddisonWesley, 1990,
ISBN: 0201514257,
LC: QA76.73.C15S43.

Dennis Stanton, Dennis White,
Constructive Combinatorics,
Springer, 1986,
ISBN: 0387963472,
LC: QA164.S79.

Krishnaiyan Thulasiraman, M Swamy,
Graphs: Theory and Algorithms,
John Wiley, 1992,
ISBN: 0471513563,
LC: QA166.T58.
Source Code:
Examples and Tests:
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 Nvectors of integers modulo a given base.

VEC_RANDOM selects a random Nvector of integers modulo a given base.
You can go up one level to
the FORTRAN90 source codes.
Last revised on 24 June 2013.