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 ``root
vertex) specified by the spanning treeT
.G
is expected to be a foldedDiGraph
with numerical edge labels.T
(also aDiGraph
) is expected to be a spanning tree ofG
.D
is expected to be a dictionary associating with each vertex \(v\) ofG
(andT
) the word labeling the geodesic path inT
fromroot
to \(v\). The output basis is a list of objects of classWord
on a numerical alphabet, one for each edge ofG
that is not inT
.INPUT:
G
–DiGraph
T
–DiGraph
D
– dictionary (the keys are the vertices ofG
and 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 ``C
are expected to be lists of words in the same format, alphabetic or numerical, specified byalphabet_type''. Each word in ``L
is expected to be in the subgroup generated byC
. This is verified ifcheck
is set toTrue
.INPUT:
L
– list of objects of typeWord
C
– list of objects of typeWord
alphabet_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.G
is expected to be aDiGraph
with 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\) fromroot
to \(v\).INPUT:
G
–DiGraph
root
– 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
w
in the basis (of the space of loops ofG``at the ``root
vertex) specified by the spanning treeT
.w
is expected to be a Word in alphabetic or numerical form, depending onalphabet_type''. In addition, ``w``is expected to label a loop at vertex ``root
in the foldedDiGraph
G
(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 ofw
in the alphabet of the basis defined byT
.INPUT:
G
–DiGraph
T
–DiGraph
w
–Word
root
– a vertex ofG
alphabet_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