vpar.gp
This is some functions for Pari/GP making calculations on labelled oriented trees (graph theory trees) as "vpar" vector of parent vertex numbers. Functions include
- Height, depths, eccentricity, diameter, centre, centroid, weights, Wiener index and terminal Wiener.
- Min/max ancestor or descendant, row widths.
- Matrix adjacency, skew adjacency, path lengths, Laplacian.
- Independent sets, matchings, dominating sets, minimal dominating sets, total dominating sets, independent dominating sets.
- Relabelling, re-rooting, isomorphism (rooted or free).
- Subdivide, join, delete, contract, branch reduce, root above.
- Prime code.
- Sequences pre/post, rows, up queue, subtree height, subtree sizes, blob.
- Make some specific trees, including random trees.
- Counts of various trees and forests.
- Least child monk, hereditary least single.
Vertices are numbered 1 to n. A tree is a vector where vpar[v]
is parent of v, or 0 if no parent. Such a
representation is oriented in that there is a distinguished root (or roots for
a forest) and labelled in that each vertex has a particular number. There are
no other attributes etc.
The main use is to calculate or verify properties of specific trees of interest. Various functions like diameter are the same for any root or labelling so effectively act as on a "free" tree. Most functions are linear in the number of vertices so can be used on large trees.
vpar.gp is
free software (free
as in freedom), published under the terms of the
GNU
General Public License (v3 or higher). Download version
3 here,
vpar.gp(247k, and sig)
vpar-4.tar.gz(264k, and sig)
Just vpar.gp is enough to run. The tar file
includes some self-tests and some work-in-progress extras (most of which work
but may change wildly). The sig files are Gnu
PG ascii armoured signatures generated from my
key.