tcsliblua

• Index

Contents

• Class Graph
• Class Rook
• Class CaleyZnZm
• Class BipCompl
• Class Match
• Class Path
• Class Cycle
• Class Tree

Modules

• graphs
• matrix
• moddec
• indref
• rationals
• wl
• genref
• graph6
• oo

Module graphs

graphs (as known form graph theory)

Class Graph

Class Rook

Class CaleyZnZm

Class BipCompl

Class Match

Class Path

Class Cycle

Class Tree

Class Graph

Graph.new (V, E, nocopy, P)

the constructor. constructs the Graph

Parameters:

• V any[] the vertex set (required) for graphs with computed edges this is a number.
• E any[] the edge set (required).
• nocopy boolean default: false; if true V,E and P are not copied.
• P any[] a tuple of pebbles (optional) Pebbles are vertices that must be mapped onto each other (in order) by any isomorphism (a single pebble can be considered a root).

Graph.fromAdjacencyMatrixString (s)

creates a Graph from an adjacency matrix given as a string.

Parameters:

• s string String containing the matrix.

Returns:

Graph 'created graph'

Graph.fromAdjacencyMatrixStringMulti (s)

creates a list of Graphs from multiple adjacency matrix given as a string.

Parameters:

• s string String containing the matrices separated by \n\n.

Returns:

Graph[] 'list of graphs'

Graph.n (G)

number of vertices.

Parameters:

• G Graph

Returns:

integer 'number of vertices'.

Graph.m (G)

number of edges.

Parameters:

• G Graph

Returns:

integer 'number of edges'.

Graph.spec (G)

a descriotiuon used to create the graph. For subclasses such as Tree the degree or level sequence is considered its specification. Otherwise just a verbal description wit vertices and edges.

Parameters:

• G Graph

Returns:

string 'specification string'

Graph.toIntGraph (G)

converts the vertices to integers. G:vertex(i) becomes i, edges {G:vertex(i), G:vertex(j)} become {i,j}.

Parameters:

• G Graph

Returns:

Graph 'where V and E are actual sets of integers'.

Graph.addEdge (G, u, v)

adds an edge to the graph.

Parameters:

• G Graph
• u any vertex of G or entire edge
• v any|nil vertex of G or nil

Graph.removeEdge (G, u, v)

removes an edge to the graph.

Parameters:

• G Graph
• u any vertex of G or entire edge
• v any|nil vertex of G or nil

Graph.addPebbles (G, peb)

appends a peppble to the graph's list of pebbles.

Parameters:

• G Graph
• peb any[]

Graph.vertex (G, i)

returns the ith vertex. for non-computed graphs this is G.V[i]

Parameters:

• G Graph
• i integer

Returns:

any

Graph.edge (G, i)

returns the ith edge. for non-computed graphs this is G.E[i]

Parameters:

• G Graph
• i integer

Returns:

any[]|nil

Graph.pebble (G, i)

returns the ith pebble. for non-computed graphs this is G.P[i]

Parameters:

• G Graph
• i integer

Returns:

any

Graph.vertices (G)

returns an iterator over all vertices.

Parameters:

• G Graph

Returns:

function

Graph.edges (G)

returns an iterator over all edge.

Parameters:

• G Graph

Returns:

function

Graph.pebbles (G)

returns an iterator over all pebbles.

Parameters:

• G Graph

Returns:

function

Graph.hasEdge (G, u, v)

checks if {u,v} is an edge of the graph.

Parameters:

• G Graph
• u any vertex of G or entire edge
• v any|nil vertex of G or nil

Returns:

boolean

Graph.pebblesOn (G, v)

returns the index of the pebble on v or false if there is none.

Parameters:

• G Graph
• v any vertex of G

Returns:

integer|boolean

Graph.degrees (G)

returns a table of degrees indexed by vertices

Parameters:

• G Graph

Returns:

integer[]

Graph.degPart (G)

partitions vertices by degree.

Parameters:

• G Graph

Returns:

any[][]

Graph.neighbors (G, v)

returns an iterator over all neighbors of v.

Parameters:

• G Graph
• v any vertex of G

Returns:

function

Graph.neighborhood (G, v)

returns the neighborhood as a table.

Parameters:

• G Graph
• v any vertex of G

Returns:

function

Graph.areTwins (G, u, v)

checks if N(v){u} = N(u){v}, where N is the neighborhood.

Parameters:

• G Graph
• u any vertex of G
• v any vertex of G

Returns:

boolean

Graph.complement (G)

returns the graph with edge set {{u,v}\subseteq V| {u,v}\notin E}. pebbles keep their position,

Parameters:

• G Graph

Returns:

Graph

Graph.disjointUnion (G, H)

Disjoint union of graphs. Ignores pebbles.

Parameters:

• G Graph
• H Graph

Returns:

Graph

Graph.permuted (G, pi)

computes a graph G' with integer vertices first and then permutes edges and pebbles accoirding to pi. {u,v} -> {pi(u),pi(v)}.

Parameters:

• G Graph
• pi integer[] assumed to be a permutation on {1,...,G:n()}

Returns:

Graph

Graph.isIsomorphicTo (G, H)

checks if G is isomorphic to H this currently does not respect pebbles but will likely do so in the future. uses an naive implementation (no intelligent backtracking) of individualization-refinement and thus maybe costly

Parameters:

• G Graph
• H Graph

Returns:

boolean

Graph.orbits (G, vcolor, vorder)

computes the orbits accoding to Graph.isIsomorphicTo(). The colors in vcolor are respected, the order in vorder is used to sort the orbits: If vorder corresponds to u,v,x,y,z and orbit are {x,v} and {u,y,z} then they will be returned as [[u,y,z],[x,v]]. If no order is given the canonical order from canonOrderIR(G) is used.

Parameters:

• G Graph
• vcolor function|table?
• vorder integer[]?

Returns:

Graph

See also:

Graph.automFactGrp (G)

returns table of represantatives of the factor group (Sym(G.V)/Aut(G))

Parameters:

• G Graph

Returns:

integer[][]

Graph.countSub (G, F)

counts the number of subgraphs of G that are isomorphic to F devided by the size of Aut(F) this is faster than countSubIso

Parameters:

• G Graph host graph
• F Graph pattern graph

Returns:

integer

Graph.countSubIso (G, F)

counts the number of subgraphs of G that are isomorphic to F

Parameters:

• G Graph host graph
• F Graph pattern graph

Returns:

integer

Graph.pebbleInjRestr (G, F)

returns a mapping between the pebbles of F and G and its inverse.

Parameters:

• G Graph
• F Graph

Returns:

1. table|nil
2. table|nil

Graph.pebbleLast (G)

permutes the vertex set of a graph with integer vertices such that the c pebbles sit on the vertice n-c+1,...,n.

Parameters:

• G Graph intGraph

Returns:

Graph

Graph.countSubIsoPeb (G, F)

counts the number of subgraphs of G that are isomorphic to F if both F and G are pebbled. This method is automatically called by Graph.countSubIso as needed.

Parameters:

• G Graph host graph
• F Graph pattern graph

Returns:

integer

Graph.adjString (G, vorder)

computes a string representation of the adjacency matrix where columns and rows are sorted according to vorder.

Parameters:

• G Graph
• vorder integer[]

Returns:

string

Graph.colorString (G, vcolor, vorder)

computes a string representing the vertex colors in order vorder. Together with canAdjString it forms a complete invariant for colored graphs.

Parameters:

• G Graph
• vcolor table|function
• vorder integer[]

Returns:

string

Graph.canAdjString (G)

shortcut for G:adjString(canonOrderIR(G)). serves as a complete invariant for uncolored graphs.

Parameters:

• G Graph

Returns:

string

Graph.adjMatrix (G, vorder)

computes the adjacency matrix.

Parameters:

• G Graph
• vorder integer[] row and column order

Returns:

Matrix

Graph.walkMatrix (G, filter, ncol, useClosedWalks)

computes the walk matrix with ncol columns. column i is defined as e*A^(i-1) where e is the filter vector.

Parameters:

• G Graph
• filter integer[]|Matrix filter vector
• ncol integer default: G:n()
• useClosedWalks boolean column i is diagonal of A^(i-1)

Returns:

Matrix

Graph.walkMatrixSortedString (G, filter, ncol, useClosedWalks)

computes a string representation of the walk matrix. The rows are converted to strings first and then sorted lexicographically. Thus this constitutes an invariant (as opposed to the 'raw' walk matrix).

Parameters:

• G Graph
• filter integer[]|Matrix filter vector
• ncol integer default: G:n()
• useClosedWalks boolean column i is diagonal of A^(i-1)

Returns:

string

Graph.matrixPartition (G, mat, vorder)

computes a partition part of the vertices such that for each s in part: u,v \in s \iff the rows corresponding to u and v in mat are equal. The sets and vertices in the sets are sorted according to vorder, see Graph.orbits for details.

Parameters:

• G Graph
• mat Matrix nxk-Matrix for some k
• vorder integer[]

Returns:

any[][]

Graph.walkMatrixPartition (G, filter, vorder, ncol, useClosedWalks)

computes a partition part of the vertices such that for each s in part: u,v \in s \iff the rows corresponding to u and v in the walkMatrix are equal. The sets and vertices in the sets are sorted according to vorder, see Graph.orbits for details.

Parameters:

• G Graph
• filter integer[]|Matrix filter vector
• vorder integer[]
• ncol integer default: G:n()
• useClosedWalks boolean column i is diagonal of A^(i-1)

Returns:

any[][]

Graph.degereeSequenceWalks (G, length)

computes a the number of walks where each vertex has the given degree from a degree sequence for all vertices and all degree sequence of length 'length'.

Parameters:

• G Graph
• length integer

Returns:

DSW

Graph.toDot (G, name)

computes a representation in DOT format, that is used by the Graphviz family of programs. https://en.wikipedia.org/wiki/DOT%28graphdescription_language%29

Parameters:

• G Graph
• name string used after "graph" in DOT format

Returns:

string

Graph.isVCint (G, S)

For an integer graph G, checks whether S is a vertex cover of G.

Parameters:

• G Graph
• S table S[v] == true iff v \in S

Returns:

boolean

Graph.vc (G, k, S, i)

Classic FPT vertex cover algorithm, computes a superset of S with at most k vertices that is a vertex cover (if such a set exists) for the subgraph pof G consistiung of all edges starting from the (i+1)th edge.

Parameters:

• G Graph
• k integer
• S table S[v] == true iff v \in S
• i integer last edge already covered by S

Returns:

integer[]|nil

Graph.match2Flip (G, e1, e2)

Flips a 2-matching and returns two resulting graphs. Given to edges, it checks whether they form a matching and if so returns a pair of graphs, where each graph has one of the other two possible matchings between the four vertices involved.

Parameters:

• G Graph
• e1 any frist edge of matching
• e2 any second edge of matching

Returns:

1. Graph|nil
2. Graph|nil

Graph.isTree (G)

Checks wether G is a tree. Note that not all trees are of the class "Tree".

Parameters:

• G Graph

Returns:

boolean

Graph.isConnected (G)

Checks wether G is connected. Note that not all trees are of the class "Tree".

Parameters:

• G Graph

Returns:

boolean

Graph.conComp (G)

Computes connected components.

Parameters:

• G Graph

Returns:

1. any[][] components
2. table components indexed by vertices

Graph.__index (G, S)

G[S] returns the induced subgraph with vertex set S.

Parameters:

• G Graph
• S any[]

Returns:

Graph

Graph.__tostring (G)

String representation using G.spec and G.adjMatrix

Parameters:

• G Graph

Returns:

string

Class Rook

Rook.new (n)

constructs (n x n) rook's graph. has computed edges. vertex set is {1,...,n}^2 edge set is {{(a,b),(c,d)}| a=b xor c=d}

Parameters:

• n

Class CaleyZnZm

CaleyZnZm.new (n, m, gen)

constructs a Caley graph of group product Zn x Zm. has computed edges. vertex set is {0,...,n-1}x{0,...,m-1} edge set is {{(a,b),(c,d)}| (a-b,d-c) \in gen}

Parameters:

• n ensure gen is symmetric
• m
• gen

Class BipCompl

BipCompl.new (n, m)

constructs a complete bipartite graph. has computed edges. vertex set is {1,...,n+m} edge set is {{i,j}| i<= n, j> n}

Parameters:

• n
• m

Class Match

Match.new (n, P)

constucts a matching on 2n vertices has computed edges. vertex set is {1,2}x{1,...,n} edge set is {{(1,i),(2,i)}| i<= n}

Parameters:

• n
• P

Class Path

Path.new (n, P)

constructs a path with n vertices, i.e., length n-1 has computed edges. vertex set is {1,...,n} edge set is {{i,i+1}| i < n}

Parameters:

• n
• P

Class Cycle

Cycle.new (n, P)

constructs a cycle with n vertices has computed edges. vertex set is {1,...,n} edge set is {{i,(i % n)+1}| i <= n}

Parameters:

• n
• P

Class Tree

Tree.new (...)

constructor: argument is a degree sequence either as separate arguments or as a single table

Parameters:

• ...

Tree.fromLevelSequence (...)

similar to constructor, but uses a level sequence instead of a degree sequence.

Parameters:

• ...

Tree.levseq (T, r, l, ls, ord)

returns (and computes if necessary) the preorder level sequence and an ordering of the vertices to match that sequence.

Parameters:

• T
• r
• l
• ls
• ord

Tree.degseq (T, r)

returns (and computes if necessary) the BFS degree sequence and an ordering of the vertices to match that sequence.

Parameters:

• T
• r

Tree.levseqToDegseq (ls)

Turns a level sequence into a degree sequence without creating a tree first.

Parameters:

• ls integer[]

Returns:

DS

Tree.rootedCanLevSeqNaive (n)

returns an iterator over all non-isomorphic rooted trees (naive version, just for reference). according to https://doi.org/10.1137/0209055 naive implementation of the successor function that creates a new sequence for each run naive implementation takes 13s for n=20 optimized s.b. takes 1s

Parameters:

• n integer

Returns:

function

Tree.rootedCanLevSeq (n)

returns an iterator over all non-isomorphic rooted trees (implementation close to paper). according to https://doi.org/10.1137/0209055 uses that p cannot decrease by more than two and is n or n-1 if d > 1 (because "2,2" cannot appear before p) does NOT copy sequences (would be pointless)

Parameters:

• n integer

Returns:

function

Tree.pathMatrix (T, filter, maxDist)

analogous to the walk matrix, just for paths Since we consider trees, k vertices in distance d from v imply exactly k paths of length d from v.

Parameters:

• T Tree
• filter Matrix|table
• maxDist integer maximal distance to consider (default T:n()-1)

Returns:

Matrix

Tree.pathMatrixPartition (T, filter, vorder, ncol)

computes a partition part of the vertices such that for each s in part: u,v \in s \iff the rows corresponding to u and v in the pathMatrix are equal. The sets and vertices in the sets are sorted according to vorder, see Graph.orbits for details.

Parameters:

• T Tree
• filter integer[]|Matrix filter vector
• vorder integer[]
• ncol integer default: G:n()

Returns:

any[][]

Tree.layout (T, ml)

Similar to a dendrogram.

Parameters:

• T Tree named self
• ml boolean multiline

Returns:

string