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:

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”}

  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: {#source-code align=”center”}

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

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

You can go up one level to the C++ source codes.


Last revised on 05 August 2013.