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.digris 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 ofdigrare organized in a dictionary of dictionaries and the vertices ofdigrare organized in aDisjointSetstructure (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
DisjointSetobject
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).digris expected to be aDiGraphwith vertex set of the form \([0..n]\). The base vertex after folding is still called 0. The set of vertices of the outputDiGraphis 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_structureare expected to be the data structures (seeNT_data_structures_initialization) associated with aDiGraph.NT_unfoldedis the current set of unfolded vertices,usits in that set,v1andv2are distinct vertices such that, for some letter \(a\) (a key inNT_edge_structure),v1andv2are 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_unfoldedafter the \(a\)-labeled edges out ofuand intov1andv2(resp. intouout ofv1andv2) are merged.INPUT:
NT_vertices–DisjointSetNT_edge_structure– dictionary of dictionariesNT_unfolded– setu– elementv1– elementv2– element
OUTPUT:
- the input objects
NT_vertices,NT_edge_structureandNT_unfoldedare 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
DiGraphat the beginning of the folding algorithm.digris expected to be aDiGraph,NT_verticesis aDisjointSetstructure based on the vertices ofdigrandNT_edge_structureis 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–DiGraphNT_vertices–DisjointSetNT_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
DisjointSetstructure.vis expected to be an element of the vertex set \(V\) of a graph,NT_verticesis aDisjointSetobject based on \(V\) andNT_edge_structureis a dictionary of dictionaries. The method detects whether the root of \(v\) inNT_verticesis 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.findoperator.INPUT:
digr–DiGraphNT_vertices–DisjointSetNT_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