Implementation of Stalling's Foldings on Free Groups

[Albert Yao]

Over the last few months, I have been learning about Abstract Algebra and Group Theory. Recently, I came across the concept of foldings. I created a method that takes in free group elements, shows the resulting graph, and folds it. Is it possible to implement this into SageMath?

def assign_colors(g):
    labelList = []
    edge_colors = {}
   
    for (u, v, label) in g.edges(labels = True):
        if abs(label) == 1:
            edge_colors.setdefault('red', []).append((u, v, label))
        elif abs(label) == 2:
            edge_colors.setdefault('orange', []).append((u, v, label))
        elif abs(label) == 3:
            edge_colors.setdefault('yellow', []).append((u, v, label))
        elif abs(label) == 4:
            edge_colors.setdefault('green', []).append((u, v, label))
        elif abs(label) == 5:
            edge_colors.setdefault('blue', []).append((u, v, label))  
        elif abs(label) == 6:
            edge_colors.setdefault('purple', []).append((u, v, label))    
           
    return edge_colors

def word_to_element(word, F):
    gens = F.gens_dict()
    el = F.one()
    for c in word:
        if c.isupper():    
            el *= gens[c.lower()]^-1
        else:
            el *= gens[c]
    return el

def freeGroupFolding(subsetList):  # Takes in a string of elements from freegroup
   
    allElements = []
   
    for element in subsetList:
        for i in range (len(element)):
            if(element[i].lower() not in allElements):
                allElements.append(element[i])
               

    g = DiGraph({0: []})
   
    F = FreeGroup(allElements)
   
    vertexNumber = 0

    for i in range(len(subsetList)):
       
        thing = word_to_element(subsetList[i], F)
        tietzeList = thing.Tietze()

        for j in range (len(tietzeList)):
            if(j == len(tietzeList)-1):
                if(tietzeList[j] > 0):
                    g.add_edge(vertexNumber, 0, tietzeList[j])
                else:
                    g.add_edge(0, vertexNumber, tietzeList[j])      
                break

            vertexNumber += 1
            if(j == 0):
                if(tietzeList[j] > 0):
                    g.add_edge(0, vertexNumber, tietzeList[j])
                else:
                    g.add_edge(vertexNumber, 0, tietzeList[j])  


            else:
                if(tietzeList[j] > 0):
                    g.add_edge(vertexNumber-1, vertexNumber, tietzeList[j])
                else:
                    g.add_edge(vertexNumber, vertexNumber-1, tietzeList[j])



    edge_colors = assign_colors(g)
    print(edge_colors)

    g.show(graph_border = True, edge_labels = False, edge_colors = edge_colors, vertex_labels = True, vertex_size = 300, figsize = 5)

    existsFolding = True
    while existsFolding:
        existsFolding = False  

        edges_dict = {}

        for (u, v, label) in g.edges(labels=True):
            edges_dict.setdefault((u, label), []).append((u, v, label))

        for edge_list in edges_dict.values():
            if len(edge_list) > 1:
                existsFolding = True

                e1 = edge_list[0]
                e2 = edge_list[1]

                g.add_edge(e1[1], e2[1])
                g.contract_edge((e1[1], e2[1]))

                edge_colors = assign_colors(g)

                g.show(graph_border = True, edge_colors = edge_colors, figsize = 6)

   
freeGroupFolding(["axyyzXY", "aXZyxZ", "axyzY", "azYxyz"])            

[Dima Pasechnik]

On Thu, Sep 4, 2025 at 1:48 AM Albert Yao <albert...@gmail.com> wrote:
>
> Over the last few months, I have been learning about Abstract Algebra and Group Theory. Recently, I came across the concept of foldings. I created a method that takes in free group elements, shows the resulting graph, and folds it. Is it possible to implement this into SageMath?

There is (or there used to be, I am not sure if it works now) a package
https://plmlab.math.cnrs.fr/pascalweil/stallings_graphs

Not sure whether it's helpful for you, but just in case.

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/9b677e82-e831-476a-85a2-feafca024a07n%40googlegroups.com.

[Vincent Delecroix]

Stallings foldings (and more) are implemented in

https://plmlab.math.cnrs.fr/pascalweil/stallings_graphs

> To view this discussion visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq1VQ%2B4rd1O_RtvdnEOhRyeWXEE6GAjb93ujWCkL__LssA%40mail.gmail.com.