treepack

treepack, a MATLAB 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:

• 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 information on this web page is distributed under the MIT 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 and an Octave version.

Related Data and Programs:

treepack_test

combo, a MATLAB 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

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

grf_io, a MATLAB code which reads and writes GRF files.

subset, a MATLAB code which generates, ranks and unranks various combinatorial objects.

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:

• 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.
• 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 N-vectors of integers modulo a given base.
• vec_random.m, selects a random N-vector of integers modulo a given base.