TREEPACK
Computations using Tree Graphs
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:
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 FORTRAN90 version and
a MATLAB version.
Related Data and Programs:
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:
-
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:
Examples and Tests:
List of Routines:
-
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.