The folding algorithm¶
The methods for the class FinitelyGeneratedSubgroup
use a number of ancillary functions. These are the functions which deal with the crucial operation of folding a DiGraph
.
The algorithm used here is based on Nicholas Touikan’s article [T2006] and it ought to
have time complexity \(O(n\ \log^*n)\) – that is: very efficient. It uses in a crucial way the
Union-Find algorithm, implemented in the DisjointSet
class.
The DiGraph
to be folded is expected to have numerical edge labels and to have a
vertex set of the form \([0..n]\).
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, CNRS, Univ. Bordeaux, LaBRI <pascal.weil@cnrs.fr>: initial version (2018-06-09)
-
stallings_graphs.about_folding.
NT_data_structures_initialization
(digr)[source]¶ Return the necessary data to initiate the folding of a labeled
DiGraph
.digr
is expected to be a labeledDiGraph
, with vertex set of the form \([0..n]\) and edges labeled by integers in \([1..r]\). In this preliminary step of the folding algorithm, the edges ofdigr
are organized in a dictionary of dictionaries and the vertices ofdigr
are organized in aDisjointSet
structure (to later use the union-find algorithm). The dictionary of dictionaries is a variant of the data structure used by Nicholas Touikan in [T2006].INPUT:
digr
–DiGraph
OUTPUT:
- A tuple consisting of a dictionary of dictionaries and a
DisjointSet
object
EXAMPLES
sage: from stallings_graphs.about_automata import bouquet sage: from stallings_graphs.about_folding import NT_data_structures_initialization sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]] sage: G = bouquet(L) sage: NT_data_structures_initialization(G) ({{0}, {10}, {11}, {12}, {13}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}}, {1: {0: [{13}, {5, 10}], 1: [set(), {2}], 2: [{1}, set()], 3: [{4}, set()], 4: [set(), {3}], 5: [{0}, set()], 6: [{7}, set()], 7: [set(), {6}], 8: [set(), {9}], 9: [{8}, set()], 10: [{0}, set()], 11: [set(), set()], 12: [set(), set()], 13: [set(), {0}]}, 2: {0: [{9}, set()], 1: [set(), set()], 2: [{3}, set()], 3: [set(), {2}], 4: [set(), set()], 5: [set(), {6}], 6: [{5}, set()], 7: [{8}, set()], 8: [set(), {7}], 9: [set(), {0}], 10: [set(), {11}], 11: [{10}, set()], 12: [set(), set()], 13: [set(), set()]}, 3: {0: [{4}, {1}], 1: [{0}, set()], 2: [set(), set()], 3: [set(), set()], 4: [set(), {0}], 5: [set(), set()], 6: [set(), set()], 7: [set(), set()], 8: [set(), set()], 9: [set(), set()], 10: [set(), set()], 11: [{12}, set()], 12: [{13}, {11}], 13: [set(), {12}]}})
-
stallings_graphs.about_folding.
NT_fold
(digr)[source]¶ Returns the folded version of this
DiGraph
(with base vertex 0).digr
is expected to be aDiGraph
with vertex set of the form \([0..n]\). The base vertex after folding is still called 0. The set of vertices of the outputDiGraph
is of the form \([0..m]\): this is not reflecting the name of vertices in the originalDiGraph
– except for the base vertex \(0\).INPUT:
digr
–DiGraph
OUTPUT:
DiGraph
EXAMPLE
sage: from stallings_graphs.about_words import translate_alphabetic_Word_to_numeric sage: from stallings_graphs.about_automata import show_rooted_graph, bouquet sage: from stallings_graphs.about_folding import NT_fold sage: L1 = ['bABcac','abcBA','baaCB','abABcaCA'] sage: L2 = [translate_alphabetic_Word_to_numeric(w) for w in L1] sage: G = bouquet(L2) sage: GG = NT_fold(G) sage: show_rooted_graph(GG, base_vertex=0) Graphics object consisting of 62 graphics primitives
-
stallings_graphs.about_folding.
NT_fold_edge
(NT_vertices, NT_edge_structure, NT_unfolded, u, v1, v2)[source]¶ Performs the crucial step of folding two edges.
NT_vertices
,NT_edge_structure
are expected to be the data structures (seeNT_data_structures_initialization
) associated with aDiGraph
.NT_unfolded
is the current set of unfolded vertices,u
sits in that set,v1
andv2
are distinct vertices such that, for some letter \(a\) (a key inNT_edge_structure
),v1
andv2
are both inNT_edge_structure[a][u][0]
(outgoing edges) or both inNT_edge_structure[a][u][1]
(incoming edges). The method returns updated versions ofNT_vertices
,NT_edge_structure
,NT_unfolded
after the \(a\)-labeled edges out ofu
and intov1
andv2
(resp. intou
out ofv1
andv2
) are merged.INPUT:
NT_vertices
–DisjointSet
NT_edge_structure
– dictionary of dictionariesNT_unfolded
– setu
– elementv1
– elementv2
– element
OUTPUT:
- the input objects
NT_vertices
,NT_edge_structure
andNT_unfolded
are modified in place
EXAMPLES
sage: from stallings_graphs.about_automata import bouquet sage: from stallings_graphs.about_folding import NT_data_structures_initialization, NT_initially_unfolded_construction, NT_fold_edge sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]] sage: G = bouquet(L) sage: NT_vertices,NT_edge_structure = NT_data_structures_initialization(G) sage: NT_unfolded = set([0]) sage: NT_fold_edge(NT_vertices,NT_edge_structure,NT_unfolded,0,5,10)
-
stallings_graphs.about_folding.
NT_initially_unfolded_construction
(digr, NT_vertices, NT_edge_structure)[source]¶ Returns the set of unfolded vertices in this
DiGraph
at the beginning of the folding algorithm.digr
is expected to be aDiGraph
,NT_vertices
is aDisjointSet
structure based on the vertices ofdigr
andNT_edge_structure
is a dictionary based on the edges ofdigr
. This method is meant to be used once, when the input defining a subgroup is an NFA with one initial-final state.INPUT:
digr
–DiGraph
NT_vertices
–DisjointSet
NT_edge_structure
– dictionary of dictionaries
OUTPUT:
- set
EXAMPLES
sage: from stallings_graphs.about_automata import bouquet sage: from stallings_graphs.about_folding import NT_data_structures_initialization, NT_initially_unfolded_construction sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]] sage: G = bouquet(L) sage: NT_vertices,NT_edge_structure = NT_data_structures_initialization(G) sage: NT_initially_unfolded_construction(G,NT_vertices,NT_edge_structure) {0}
-
stallings_graphs.about_folding.
NT_is_vertex_unfolded
(v, NT_vertices, NT_edge_structure)[source]¶ Return whether this vertex is unfolded in the given
DisjointSet
structure.v
is expected to be an element of the vertex set \(V\) of a graph,NT_vertices
is aDisjointSet
object based on \(V\) andNT_edge_structure
is a dictionary of dictionaries. The method detects whether the root of \(v\) inNT_vertices
is unfolded, that is, whether for some letter \(i\),NT_edge_structure[i][w][0]
orNT_edge_structure[i][w][1]
has at least 2 elements — after updating these sets using theNT_vertices.find
operator.INPUT:
digr
–DiGraph
NT_vertices
–DisjointSet
NT_edge_structure
– dictionary of dictionaries
OUTPUT:
- boolean
EXAMPLES
sage: from stallings_graphs.about_automata import bouquet sage: from stallings_graphs.about_folding import NT_data_structures_initialization, NT_is_vertex_unfolded sage: L = [[3,1,-2,-1,3],[1,2,-1,-2,1,2],[1,2,-3,-3,1]] sage: G = bouquet(L) sage: NT_vertices,NT_edge_structure = NT_data_structures_initialization(G) sage: NT_is_vertex_unfolded(0,NT_vertices,NT_edge_structure) True
sage: NT_is_vertex_unfolded(2,NT_vertices,NT_edge_structure) False