jburkardt

TREEPACK\ Computations using Tree Graphs {#treepack-computations-using-tree-graphs align=”center”} ==============================

TREEPACK is a C++ 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 N-1 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 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: {#licensing align=”center”}

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages: {#languages align=”center”}

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

COMBO, a C++ 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

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

Reference: {#reference align=”center”}

Alan Gibbons,\ Algorithmic Graph Theory,\ Cambridge University Press, 1985,\ ISBN: 0-5212-8881-9,\ 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: 0-12-519260-6,\ LC: QA164.N54.
Robert Sedgewick,\ Algorithms in C,\ Addison-Wesley, 1990,\ ISBN: 0-201-51425-7,\ 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: {#source-code align=”center”}

treepack.cpp, the source code;
treepack.hpp, the include file.

Examples and Tests: {#examples-and-tests align=”center”}

treepack_prb.cpp, the calling program;
treepack_prb_output.txt, the output file.

List of Routines: {#list-of-routines align=”center”}

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 C++ source codes.

Last revised on 05 August 2013.