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”}
Examples and Tests: {#examples-and-tests align=”center”}
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.