--Obtain the formula representation of the graph, expand the formula representation and enumerate it. ――For example, if each side is a, b, c in a triangle graph, the expression expression will be ** set ** (abc), and if this is expanded, it will be ab / ac / bc. --The formula representation of the graph is calculated as follows. --Give one letter of the alphabet as the first expression of the edge. --Graphs can remove edges or edges and points while preserving the expression representation. --The formula expression is required when the graph reaches one point. --The expression representation of graph G (Expr (G)) can be transformed as follows by selecting any one side E. (Standard rule) --Expr (G) = ** sum ** (** product ** (** set ** (Expr (E)), Expr (remove E from G)), ** product ** (Expr (E)) , Expr (reduced from G to E [^ 1])))

[^ 1]: Shrinking an edge is an operation that makes the edge 0 in length and changes the points at both ends to one.

There are the following types of expression expressions.

-** Sum ** (A, B): The union of the elements of A and B. -** Product ** (A, B): An intersection of A and B elements (combined letters). -** Pair ** (A): Erases and expands one character for each element of A. For example, ** pairs ** (abc) are expanded into three, ab, ac, and bc.

You can do it with just the standard rule, but to reduce the amount of calculation, add a rule for a specific case. (Derived from standard rules)

--If edge E is a self-loop: Expr (G) = ** Product ** (** Pair ** (Expr (E)), Expr (remove E from G)) --If the order of one end of side E (number of connected sides) = 1: Expr (G) = ** Product ** (Expr (E), Expr (reducing E from G)) --When side E and side F are connected by point V and the order of point V = 2: Expr (E) = ** Product ** (Expr (E), Expr (F)) Find the graph after contraction.

Define the class.

python3

from itertools import combinations, product
from collections import namedtuple
Union = namedtuple('Union', 'l r') #sum
Produ = namedtuple('Produ', 'l r') #product
Combi = namedtuple('Combi', 'e') #set
class Edge:
    def __init__(self, u, v, e):
        self.u = u
        self.v = v
        self.e = e
    def __repr__(self):
        return '<%s %s %s>'%(self.u, self.v, self.e)
class Graph:
    def __init__(self, num_nodes, edges):
        self.nodes = [[] for _ in range(num_nodes)]
        self.edges = []
        for i, (u, v) in enumerate(edges):
            self.edges.append(Edge(u, v, chr(97 + i)))
            self.nodes[u].append(i)
            self.nodes[v].append(i)
    def __repr__(self):
        return str(self.edges)
    def spanning_tree(self):
        res = Graph._reduct(self.nodes.copy(), self.edges.copy())
        return sorted(Graph._expand(res))
    @staticmethod
    def _reduct(nodes, edges):
        if not edges:
            return '' if len(nodes) == 1 else None
        for i, e in enumerate(edges): #Self loop
            if e.u == e.v:
                Graph._erase(nodes, edges, i)
                return Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges))
        for con in nodes: #Degree=1
            if len(con) == 1:
                e = edges[con[0]]
                Graph._erase(nodes, edges, con[0])
                return Produ(l=e.e, r=Graph._reduct(nodes, edges))
        for con in nodes: #Degree=2
            if len(con) == 2:
                e = edges[con[0]]
                edges[con[0]] = Edge(e.u, e.v, Produ(l=edges[con[0]].e,
                                                     r=edges[con[1]].e))
                Graph._shrink(nodes, edges, con[1])
                return Graph._reduct(nodes, edges)
        e = edges[0]
        nodes2, edges2 = nodes.copy(), edges.copy()
        Graph._erase(nodes, edges, 0)
        Graph._shrink(nodes2, edges2, 0)
        return Union(l=Produ(l=Combi(e=e.e), r=Graph._reduct(nodes, edges)),
                     r=Produ(l=e.e, r=Graph._reduct(nodes2, edges2)))
    @staticmethod
    def _erase(nodes, edges, k):
        for a, con in enumerate(nodes):
            nodes[a] = [b if b < k else b-1 for b in con if b != k]
        del edges[k]
    @staticmethod
    def _shrink(nodes, edges, k):
        e = edges[k]
        dn = max(e.u, e.v)
        sn = e.u+e.v-dn
        nodes[sn] = nodes[sn] + nodes[dn]
        for a, con in enumerate(nodes):
            nodes[a] = [b if b < k else b-1 for b in con if b != k]
        for a, ed in enumerate(edges):
            u = sn if ed.u == dn else ed.u if ed.u < dn else ed.u-1
            v = sn if ed.v == dn else ed.v if ed.v < dn else ed.v-1
            edges[a] = Edge(u, v, ed.e)
        del edges[k]
        del nodes[dn]
    @staticmethod
    def _expand(ex):
        if ex is None:
            return set()
        elif isinstance(ex, str):
            return set(ex) if ex else {''}
        elif isinstance(ex, Combi):
            exe = Graph._expand(ex.e)
            return set.union(*(set(''.join(s) for s in
                combinations(e, len(e)-1)) for e in exe))
        exl = Graph._expand(ex.l)
        exr = Graph._expand(ex.r)
        if isinstance(ex, Union):
            return exl.union(exr)
        return {''.join(sorted((i+j))) for i, j in product(exl, exr)}

Try it with a ternary plot.

python3

g = Graph(3, [(0,1), (1,2), (2,0)])
print(g.spanning_tree())
>>>
['ab', 'ac', 'bc']

I will try it with a complete graph of 4 points.

python3

g = Graph(4, [(0,1), (1,2), (2,3), (3,0), (0,2), (1,3)])
print(g.spanning_tree())
>>>
['abc', 'abd', 'abf', 'acd', 'ace', 'acf', 'ade', 'aef',
 'bcd', 'bce', 'bde', 'bdf', 'bef', 'cdf', 'cef', 'def']

By the way, this Python has 85 lines, but it was 500 lines when written in C and about 330 lines when written in C #.

that's all