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:

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 labeled DiGraph, 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 of digr are organized in a dictionary of dictionaries and the vertices of digr are organized in a DisjointSet 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:

  • digrDiGraph

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 a DiGraph with vertex set of the form \([0..n]\). The base vertex after folding is still called 0. The set of vertices of the output DiGraph is of the form \([0..m]\): this is not reflecting the name of vertices in the original DiGraph – except for the base vertex \(0\).

INPUT:

  • digrDiGraph

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 (see NT_data_structures_initialization) associated with a DiGraph. NT_unfolded is the current set of unfolded vertices, u sits in that set, v1 and v2 are distinct vertices such that, for some letter \(a\) (a key in NT_edge_structure), v1 and v2 are both in NT_edge_structure[a][u][0] (outgoing edges) or both in NT_edge_structure[a][u][1] (incoming edges). The method returns updated versions of NT_vertices, NT_edge_structure, NT_unfolded after the \(a\)-labeled edges out of u and into v1 and v2 (resp. into u out of v1 and v2) are merged.

INPUT:

  • NT_verticesDisjointSet
  • NT_edge_structure – dictionary of dictionaries
  • NT_unfolded – set
  • u – element
  • v1 – element
  • v2 – element

OUTPUT:

  • the input objects NT_vertices, NT_edge_structure and NT_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 a DiGraph, NT_vertices is a DisjointSet structure based on the vertices of digr and NT_edge_structure is a dictionary based on the edges of digr. This method is meant to be used once, when the input defining a subgroup is an NFA with one initial-final state.

INPUT:

  • digrDiGraph
  • NT_verticesDisjointSet
  • 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 a DisjointSet object based on \(V\) and NT_edge_structure is a dictionary of dictionaries. The method detects whether the root of \(v\) in NT_vertices is unfolded, that is, whether for some letter \(i\), NT_edge_structure[i][w][0] or NT_edge_structure[i][w][1] has at least 2 elements — after updating these sets using the NT_vertices.find operator.

INPUT:

  • digrDiGraph
  • NT_verticesDisjointSet
  • 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