Ancillary functions about bases¶
The methods for the class FinitelyGeneratedSubgroup use a number of ancillary functions. These are the functions which deal with bases: determining one, parsing a word along a given basis.
A word is a string of characters from either a numerical or an alphabetical set
of letters: alphabet_type='123' or 'abc'.
alphabet_type='123': The positive letters form an interval \([1,r]\). Their inverses (aka
negative letters) are the corresponding negative integers. The symmetrized
alphabet is the union of positive and negative letters (zero is NOT a letter).
The \(\textit{rank}\) of a word is the maximal absolute value of a letter occurring in the word.
When represented in a (say LaTeX) file (.tex, .pdf), the letters are written
\(a_i\).
alphabet_type='abc': positive letters are lower case (at most 26 letters, \(a\):\(z\))
and their inverses are the corresponding upper case letters (\(A\):\(Z\)).
Automata are objects of class DiGraph whose edge labels are positive letters (always numerical).
When automata are visualized, the value of alphabet_type determines how these edge labels will appear. In most cases, the vertex set of a DiGraph is a set of integers, usually of the form \([0..n]\).
We have functions to:
- compute a spanning tree
- compute a basis specified by a spanning tree
- express a Word in a basis specified by a spanning tree
EXAMPLES:
sage: from stallings_graphs.about_words import random_reduced_word
sage: L = ['aBABBaaaab', 'BBAbbABABA', 'bbAbAbaabb']
sage: from stallings_graphs.about_automata import bouquet
sage: G = bouquet(L, alphabet_type='abc')
sage: from stallings_graphs.about_folding import NT_fold
sage: GG = NT_fold(G)
sage: GG
Looped multi-digraph on 23 vertices
AUTHOR:
- Pascal WEIL (2018-06-09): initial version CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>
-
stallings_graphs.about_bases.basis_from_spanning_tree(G, T, D, root=0, alphabet_type='abc')[source]¶ Return the basis (of the space of loops of
G``at the ``rootvertex) specified by the spanning treeT.Gis expected to be a foldedDiGraphwith numerical edge labels.T(also aDiGraph) is expected to be a spanning tree ofG.Dis expected to be a dictionary associating with each vertex \(v\) ofG(andT) the word labeling the geodesic path inTfromrootto \(v\). The output basis is a list of objects of classWordon a numerical alphabet, one for each edge ofGthat is not inT.INPUT:
G–DiGraphT–DiGraphD– dictionary (the keys are the vertices ofGand the values are of classWord)root– a vertex ofG
OUTPUT:
- a list of objects of class
Word(in numerical or alphabetic form)
EXAMPLES:
sage: from stallings_graphs.about_automata import bouquet sage: from stallings_graphs.about_bases import spanning_tree_and_paths, basis_from_spanning_tree sage: from stallings_graphs.about_folding import NT_fold sage: generators = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]] sage: G = NT_fold(bouquet(generators)) sage: T,L,D = spanning_tree_and_paths(G) sage: basis_from_spanning_tree(G,T,D,alphabet_type='123') [word: -3,1,2,-1,-3, word: -2,-1,2,1,-2,-1, word: -1,3,3,-2,-1]
sage: basis_from_spanning_tree(T,T,D) []
-
stallings_graphs.about_bases.basis_interpreter(L, C, alphabet_type='abc', check=False)[source]¶ Returns the translations of a list of words into words (in numerical form) on basis
C.L``and ``Care expected to be lists of words in the same format, alphabetic or numerical, specified byalphabet_type''. Each word in ``Lis expected to be in the subgroup generated byC. This is verified ifcheckis set toTrue.INPUT:
L– list of objects of typeWordC– list of objects of typeWordalphabet_type– string, which can be either'abc'or'123'check– boolean
OUTPUT:
- list of objects of type
Word(in numerical form)
EXAMPLES:
sage: from stallings_graphs.finitely_generated_subgroup import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_bases import basis_interpreter sage: generators = ['abbC','aabCa','aaCBA','cBa'] sage: w = Word('abcbCbCabcAA') sage: basis_interpreter([Word([])], generators, alphabet_type = 'abc', check = False) [word: ]
sage: basis_interpreter([w], generators, alphabet_type = 'abc', check = False) [word: -3,2,-4,-3]
sage: ww = Word('abcbCcBabcAA') sage: basis_interpreter([w,Word([])], generators, alphabet_type = 'abc', check = False) [word: -3,2,-4,-3, word: ]
-
stallings_graphs.about_bases.spanning_tree_and_paths(G, root=0)[source]¶ Return a spanning tree \(T\) of this
DiGraph, a list of the leaves of \(T\), and shortest paths in \(T\), from the root to each vertex.Gis expected to be aDiGraphwith numerical edge labels. Computes a spanning tree \(T\) (also aDiGraph) by \(\textit{breadth first search}\) starting at vertexroot–, along with a list of the non-root leaves of \(T\), and a dictionary associating with each vertex \(v\) the word labeling the geodesic path in \(T\) fromrootto \(v\).INPUT:
G–DiGraphroot– a vertex ofG
OUTPUT:
- a triple consisting of a
DiGraph, a list and a dictionary
EXAMPLES:
sage: from stallings_graphs import FinitelyGeneratedSubgroup sage: from stallings_graphs.about_bases import spanning_tree_and_paths sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]] sage: H = FinitelyGeneratedSubgroup.from_generators(L) sage: G = H.stallings_graph() sage: T,list_of_leaves,path_in_tree = spanning_tree_and_paths(G) sage: T Multi-digraph on 12 vertices
sage: list_of_leaves [2, 10, 3, 6, 5]
sage: path_in_tree {0: word: , 1: word: 3, 2: word: 31, 3: word: -3,1, 4: word: -3, 5: word: 1,2,-1, 6: word: -2,-1, 7: word: -2, 8: word: 1, 9: word: 12, 10: word: -1,3, 11: word: -1}
-
stallings_graphs.about_bases.tree_based_interpreter(w, G, T, root=0, alphabet_type='abc')[source]¶ Return the expression of the Word
win the basis (of the space of loops ofG``at the ``rootvertex) specified by the spanning treeT.wis expected to be a Word in alphabetic or numerical form, depending onalphabet_type''. In addition, ``w``is expected to label a loop at vertex ``rootin the foldedDiGraphG(with numerical edge labels).T(also aDiGraph) is expected to be a spanning tree ofG. The output is a numerical Word which is the translation ofwin the alphabet of the basis defined byT.INPUT:
G–DiGraphT–DiGraphw–Wordroot– a vertex ofGalphabet_type– string, which can be either'abc'or'123'
OUTPUT:
Word(in numerical form)
EXAMPLES:
sage: from stallings_graphs.about_automata import bouquet sage: from stallings_graphs.about_bases import spanning_tree_and_paths, basis_from_spanning_tree, tree_based_interpreter sage: from stallings_graphs.about_folding import NT_fold sage: generators = ['abaa','ababb','ababab'] sage: G = NT_fold(bouquet(generators,alphabet_type = 'abc')) sage: T,L,D = spanning_tree_and_paths(G) sage: basis_from_spanning_tree(G,T,D) [word: abaa, word: Abb, word: Bab]
sage: w = Word('AbaabAABABab') sage: tree_based_interpreter(w,G,T) word: 2,3,3,-1,3