`vpar.gp`

This is some functions for Pari/GP making calculations on labelled oriented trees and forests (graph theory trees) as "vpar" vector of parent vertex numbers. Functions include

- Height, depth, eccentricity, radius, diameter, centre, centroid, weights, Wiener index and terminal Wiener.
- Children, neighbours, siblings, childless, leaves, singletons, rows, min/max ancestor, min/max descendant.
- Matrix adjacency, incidence, path lengths, reachability, Laplacian. Characteristic polynomial of adjacency, Laplacian.
- Independent sets, matchings, maximal matchings, equimatchable, stable equimatchable, almost equimatchable.
- Dominating sets, minimal dominating sets, independent dominating sets, total dominating sets, semi-total domination number, perfect dominating sets, disjoint domination number.
- Relabelling, re-rooting, upwards/downwards.
- Isomorphism as unlabelled, free, ordered. Canonical unlabelled, free, ordered, unrooted, lexmin.
- Automorphisms, orbits, asymmetric, rooted or free.
- Iterate labelled, unlabelled, free, preorder. I'th preorder, downwards.
- Prime code, balanced binary, graph6, sparse6, digraph6.
- Subdivide, join, delete, contract, branch reduce, root above, forest components.
- Sequences pre-order, post-order, rows, up ascend (Prüfer), up queue, down queue, subtree height, subtree sizes, blob, successive paths, childless paths.
- Make some specific trees. Random labelled, preorder, downwards.
- Counts of various trees, forests, or properties.
- Least child monk, hereditary least single, strongly monotone, equaldepths.

Vertices are numbered 1 to n. A tree is a vector "`vpar`

" 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.

3 ^ ^ tree, root=3 / \ 1 5 vpar=[3,1,0,1,3] ^ ^ / \ 2 4

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 and the vertex numbers just for tree creation. Most functions are linear in the number of vertices so can be used on large trees.

Connections to Pari/GP specifics include polynomials for roots (spectra),
matrices for some linear algebra, `Set()`

s for independent sets,
permutations in relabelling and automorphisms, and then general compactness of
GP for experimenting etc.

`vpar.gp`

is
free software (free
as in freedom), published under the terms of the
GNU
General Public License (v3 or higher). Download version
16 here,

`vpar.gp`

(692k, and sig), or compressed`vpar.gp.gz`

(183k)

`vpar-16.tar.gz`

(896k, and sig)

Just `vpar.gp`

is enough to run. Comments at the start give an
introduction and overview, then each function has an `addhelp()`

.
The `tar`

file includes some example scripts, self-tests, and
work-in-progress extras. The extras mostly work but may change wildly. The
sig files are Gnu PG ascii armoured
signatures generated from my key.

The examples include bits of

- Bulgarian solitaire.
- Count preorder forests by footprint exercise from Knuth.
- Cospectrals per Mowshowitz.
- Equal01 towards balanced by several authors, realizing the Chung-Feller theorem.
- Equimatchable tree counts and generating functions.
- Integral trees (integer adjacency spectrum) by diameter per Csikvari.
- Isomorphic halves trees.
- Maximal asymmetric subtrees per Nesetril.
- Most maximum matchings per Heuberger and Wagner.
- Parking function to labelled forest per de Oliveira, and las Vergnas.
- Path lengths determinants per Graham and Pollak, and Bapat and Sivasubramanian.
- Perm to upwards per Dennis Walsh.
- Random decorated binary tree per Jean-Luc Rémy.

See also `gentreeg`

in the
Nauty tools which can generate
free trees in vertex parent form, and other forms, and can be used command
line or C.

See my
`Graph-Maker-Other`

for other graph (and tree) creation in Perl.

This page Copyright 2017, 2018, 2019 Kevin Ryde, except for the GPLv3 logo which is Copyright Free Software Foundation and used here in accordance with its terms.

(Back to the sitemap, or the Pari/GP section there).