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. Various things treat as unlabelled and/or free too. Functions include
Vertices are numbered 1 to n. A tree is a vector "
vpar[v] is parent of
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.
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 define the structure. 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(746k, and sig), or compressed
vpar-21.tar.gz(1226k, and sig)
vpar.gp is enough to run. Comments at the start give an
introduction and overview, then each function has an
tar file includes some example scripts, self-tests, and
work-in-progress extras (
vpar-wip.gp). These extras mostly work
but may change wildly. The sig files are Gnu
PG ascii armoured signatures generated from my
The examples include bits of
vpar_to_free() in version 19 and earlier had a bug where it did
not give the intended free-primary form (per
iteration). See note in
vpar.gp for some details. The wrong
form was still canonical (fine for unduplicating up to isomorphism etc), but
was not the free-primary canonical form.
gentreeg in the
Nauty tools which can generate
free trees in vertex parent form, and other forms, and can be used from the
command line or in C code.
for some other graph (and tree) creation, in Perl.
See my Nautyextra for some C code.
This page Copyright 2017, 2018, 2019, 2020, 2021, 2022 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).