c.reconstruccion()

c.relaciones()

Sucesion([7,5,5,4,3,3,3,3,3,2,2]).reconstruccion()

c = Sucesion([4,3,2,2,1,1,1])

c.es_grafica()

c.relaciones()

c.reconstruccion()

"""
Explanation: Si intentamos dibujarla sin ser sucesión gráfica nos da un error
End of explanation
"""


from prufer import Prufer

"""
Explanation: Árboles
End of explanation
"""


p = Prufer( (4,4,3,1,7) )

p.construir()

p1 = Prufer( (5,5,1,3,3) )

p1.construir()

"""
Explanation: Podemos tanto dato un código construir el árbol
End of explanation
"""


p2 = Prufer({5:[4,2], 1:[5,3], 3:[6,7]})

p2.codigo()

p3 = Prufer( {4:[5,2], 3:[4], 1:[3], 7:[1], 6:[7]} )

p3.codigo()

"""
Explanation: Como dado el árbol en forma de diccionario obtener su código
End of explanation
"""


a = (("AD",5), ("CE",5), ("DF", 6), ("AB",7), ("BE", 7), ("BC", 8),  ("EF", 8), ("DB", 9), ("EG",9), ("FG", 11),("DE", 15))


def Kruskal(grafo):
    
    final = {}
    
    def tiene_ciclos(lado):
        v1, v2 = lado[0], lado[1]
        dict.fromkeys(final, False)
        return ciclo_entre(v1, v2, dict(final))
    
    def ciclo_entre(v1, v2, lados):
        adyacentes = {k:v for (k,v) in lados.items() if v1 in k }
        if len(adyacentes) == 0:
            return False
        
        #No explorados
        validos = [k for (k,v) in adyacentes.items() if v == False]

        
        if len(validos) == 0:
            return False
        
        for lado in sorted(validos):
            lados[lado] = True
            if lado[0] == v1:
                otro_nodo = lado[1]
            else:
                otro_nodo = lado[0]

            if otro_nodo == v2 or ciclo_entre(otro_nodo, v2, lados):
                    return True 
    
    grafo_sorted = sorted(grafo, key = lambda t: t[1])
    
    
    for lado in grafo_sorted:
        vertices = lado[0]
        if not tiene_ciclos(vertices):
            final[vertices] = False
    return sorted([x for x in a if x[0] in final], key=lambda t: t[1])
    

Kruskal(a)

"""
Explanation: El algoritmo de Kruskal nos permite encontrar un árbol recubridor mínimo en un grafo conexo y ponderado.
Le podemos dar un grafo ponderado de la siguiente forma:
Una tupla de tuplas, cada tupla lleva como primera componente las letras de los nodos y la segunda componente es el valor del lado que los une.
End of explanation
"""


