• Obtenez la représentation de formule du graphique, développez la représentation de formule et énumérez-la. Par exemple, si chaque côté est a, b, c dans un graphe triangulaire, l'expression d'expression sera ** set ** (abc), et si elle est développée, ce sera ab / ac / bc. --La représentation de formule du graphique est calculée comme suit.
• Comme première expression du côté, ayez une lettre de l'alphabet.
• Les graphiques peuvent supprimer des côtés ou des côtés et des points tout en préservant la représentation de l'expression.
• L'expression est requise lorsque le graphique atteint un point. --La représentation d'expression du graphe G (Expr (G)) peut être transformée comme suit en sélectionnant n'importe quel côté E. (Règle standard) --Expr (G) = ** somme ** (** produit ** (** set ** (Expr (E)), Expr (supprimer E de G)), ** produit ** (Expr (E)) , Expr (réduit de G à E [^ 1])))

[^ 1]: La réduction d'un côté est une opération qui rend le côté 0 de longueur et change les points aux deux extrémités en un.

Il existe les types d'expressions d'expression suivants.

• ** Sum ** (A, B): La somme des éléments A et B.
• ** Produit ** (A, B): Un ensemble de produits d'éléments A et B (caractères combinés et arrangés).
• ** Paire ** (A): efface et développe un caractère pour chaque élément de A. Par exemple, ** paires ** (abc) sont développées en trois, ab, ac et bc.

Vous pouvez le faire avec uniquement les règles standard ci-dessus, mais pour réduire la quantité de calcul, ajoutez des règles pour des cas spécifiques. (Dérivé de règles standard)

--Si le côté E est en boucle automatique: Expr (G) = ** produit ** (** paire ** (Expr (E)), Expr (retirer E de G)) --Si l'ordre d'une extrémité du côté E (nombre de côtés connectés) = 1: Expr (G) = ** produit ** (Expr (E), Expr (réduisant E de G)) --Lorsque le côté E et le côté F sont reliés par le point V et l'ordre du point V = 2: Expr (E) = ** produit ** (Expr (E), Expr (F)) Trouvez le graphique après la contraction.

Définissez la classe.

python3

from itertools import combinations, product
from collections import namedtuple
Union = namedtuple('Union', 'l r') #somme
Produ = namedtuple('Produ', 'l r') #produit
Combi = namedtuple('Combi', 'e') #ensemble
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): #Boucle auto
            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: #Commande=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: #Commande=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)}

Essayez-le avec un graphique en triangle.

python3

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

Je vais l'essayer avec un graphique complet de 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']

Au fait, ce Python a 85 lignes, mais c'était 500 lignes lorsqu'il était écrit en C et environ 330 lignes lorsqu'il était écrit en C #.

c'est tout