TREEPACK
Computations using Tree Graphs
TREEPACK
is a MATLAB 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 MATLAB 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 MATLAB library which
reads and writes GRF files.
SUBSET,
a MATLAB library which
generates, ranks and unranks various combinatorial objects.
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:

catalan.m,
computes the Catalan numbers, from C(0) to C(N).

graph_adj_edge_count.m,
counts the number of edges in a graph.

graph_adj_is_node_connected.m,
determines if a graph is nodewise connected.

graph_adj_is_tree.m,
determines whether a graph is a tree.

graph_arc_degree.m,
determines the degree of the nodes of a graph.

graph_arc_is_tree.m,
determines whether a graph is a tree.

graph_arc_node_count.m,
counts the number of nodes in a graph.

graph_arc_print.m,
prints out a graph from an edge list.

graph_arc_to_graph_adj.m,
converts an arc list graph to an adjacency graph.

i4_uniform_ab.m,
returns a scaled pseudorandom I4 between A and B.

i4vec_heap_d.m,
reorders an I4VEC into an descending heap.

i4vec_indicator.m,
sets an I4VEC to the indicator vector.

i4vec_print.m,
prints an I4VEC.

i4vec_sort_heap_a.m,
ascending sorts an I4VEC using heap sort.

i4vec_sorted_unique_count.m,
counts the unique elements in a sorted I4VEC.

pruefer_to_tree_arc.m,
is given a Pruefer code, and computes the tree.

pruefer_to_tree_2.m,
produces the edge list of a tree from its Pruefer code.

r8_uniform_01.m,
returns a unit pseudorandom R8.

timestamp.m,
prints the current YMDHMS date as a time stamp.

tree_arc_center.m,
computes the center, eccentricity, and parity of a tree.

tree_arc_diam.m,
computes the "diameter" of a tree.

tree_arc_random.m,
selects a random labeled tree and its Pruefer code.

tree_arc_to_pruefer.m,
is given a labeled tree, and computes its Pruefer code.

tree_enum.m,
enumerates the labeled trees on NNODE nodes.

tree_parent_next.m,
generates, one at a time, all labeled trees.

tree_parent_to_arc.m,
converts a tree from parent to arc representation.

tree_rb_enum.m,
returns the number of rooted binary trees with N nodes.

tree_rb_lex_next.m,
generates rooted binary trees in lexicographic order.

tree_rb_to_parent.m,
converts rooted binary tree to parent node representation.

tree_rb_yule.m,
adds two nodes to a rooted binary tree using the Yule model.

tree_rooted_code.m,
returns the code of a rooted tree.

tree_rooted_code_compare.m,
compares a portion of the code for two rooted trees.

tree_rooted_depth.m,
returns the depth of a rooted tree.

tree_rooted_enum.m,
counts the number of unlabeled rooted trees.

tree_rooted_random.m,
selects a random unlabeled rooted tree.

vec_next.m,
generates all Nvectors of integers modulo a given base.

vec_random.m,
selects a random Nvector of integers modulo a given base.
Examples and Tests:

treepack_test.m,
calls all the tests.

treepack_test_output.txt,
the output file.

treepack_test005.m,
tests CATALAN and CATALAN_VALUES.

treepack_test006.m,
tests CBT_TRAVERSE.

treepack_test01.m,
tests PRUEFER_TO_TREE_ARC.

treepack_test025.m,
tests PRUEFER_TO_TREE_2.

treepack_test02.m,
tests PRUEFER_TO_TREE_2.

treepack_test03.m,
tests TREE_ARC_TO_PRUEFER.

treepack_test04.m,
tests TREE_ARC_CENTER.

treepack_test05.m,
tests TREE_ARC_CENTER.

treepack_test06.m,
tests TREE_ARC_CENTER.

treepack_test07.m,
tests TREE_ARC_DIAM.

treepack_test08.m,
tests TREE_ARC_RANDOM.

treepack_test09.m,
tests TREE_ENUM.

treepack_test10.m,
tests TREE_PARENT_NEXT.

treepack_test11.m,
tests TREE_RB_ENUM.

treepack_test12.m,
tests TREE_RB_LEX_NEXT.

treepack_test13.m,
tests TREE_RB_LEX_NEXT, TREE_RB_TO_PARENT.

treepack_test14.m,
tests TREE_RB_YULE.

treepack_test15.m,
tests TREE_ROOTED_CODE.

treepack_test16.m,
tests TREE_ROOTED_DEPTH.

treepack_test17.m,
tests TREE_ROOTED_ENUM.

treepack_test18.m,
tests TREE_ROOTED_RANDOM.
You can go up one level to
the MATLAB source codes.
Last revised on 28 June 2013.