Algoritmos de optimización combinatoria

caminos.py

## Algoritmos de caminos más cortos

from estructuras import Cola, ColaMin
from conectividad import ordenamiento_topologico

inf = float('inf') #Tratar infinito como un numero

def recorrido_a_lo_ancho(G, s):
    dist, padre = {v:inf for v in G}, {v:v for v in G}
    dist[s] = 0
    Q = Cola([s])
    while Q:
        u = Q.desencolar()
        for v in G[u]:
            if dist[v] == inf:
                Q.encolar(v)
                dist[v], padre[v] = dist[u] + 1, u
    return dist, padre

def relajar(G, u, v, dist, padre):
    d = dist[u] + G[u][v]       #Estimar distancia de s a v pasando por u---v
    if  d < dist[v]:            #¿Es un camino mas corto?
        dist[v], padre[v] = d, u    #Actualizar distancia y camino mas corto
        return True             #Hubo cambios
    return False #No hubo cambios

def inicializar_caminos_mas_cortos(G, s):
    dist, padre = {u:inf for u in G}, {v:v for v in G}
    dist[s] = 0 #distancia de s a si mismo es 0
    return dist, padre
        
def dijkstra(G, s):
    dist, padre = inicializar_caminos_mas_cortos(G, s)
    H = ColaMin(dist)               #Crear una cola con prioridad mínima dist[.]
    while H:                        #¿Todavia hay vertices por explorar?
        u = H.extraer_min()         #Elegir el mas cercano a s 
        for v in G[u]:              #Actualizar caminos de sus vecinos
            if v in H and relajar(G, u, v, dist, padre):
                H.bajar_prioridad(v, dist[v])
    return dist, padre

def bellman_ford(G, s):
    dist, padre = inicializar_caminos_mas_cortos(G, s)
    for k in G: #Hacer |V| repeticiones
        sin_cambios = True
        for u in G:
            for v in G[u]:
                if relajar(G, u, v, dist, padre):
                    sin_cambios = False
        if sin_cambios: break
    else:
        raise ValueError('Ciclo negativo')
    return dist, padre

def caminos_mas_cortos_en_gads(G, s):
    dist, padre = inicializar_caminos_mas_cortos(G, s)
    vertices = ordenamiento_topologico(G)
    for u in vertices:
        for v in G[u]:
            relajar(G, u, v, dist, padre)
    return dist, padre


if __name__ == '__main__':
    from grafos import Grafo

    #Recorrido a lo ancho
    print('Un grafo simple:')
    G = Grafo(dirigido = False)
    G.trazar('S', 'A', 'B', 'C', 'S', 'D', 'E', 'S')
    print(G)
    print()
    
    dist, padre =  recorrido_a_lo_ancho(G, 'S')
    print('Árbol generado por el recorrido a lo ancho iniciando en S:')
    print(Grafo.arbol(padre))
    print()
    print('Distancias encontradas por el recorrido:')
    for u in dist:
        print('d({}, {}) = {}'.format('S', u, dist[u]))
    print()

    print('Un digrafo pesado con pesos positivos:')
    G = Grafo(pesado = True)
    G.trazar('A', 4, 'B', 3, 'C', 1, 'B', 2, 'D')
    G.trazar('A', 2, 'C', 4, 'D')
    G.trazar('B', 3, 'E', 1, 'D')
    G.trazar('C', 4, 'D')
    G.trazar('C', 5, 'E')
    print(G)
    print()

    dist, padre = dijkstra(G, 'A')
    print('Árbol generado por el algoritmo de Dijkstra iniciando en A:')
    print(Grafo.arbol(padre))
    print()
    print('Distancias encontradas por el algoritmo:')
    for u in dist:
        print('d({}, {}) = {}'.format('A', u, dist[u]))
    print()
    
    print('Un digrafo pesado sin ciclos negativos:')
    G = Grafo(pesado = True)
    G.trazar('S', 10, 'A', 2, 'E', -2, 'B', 1, 'A')
    G.trazar('S', 8, 'G', 1, 'F', -4, 'A')
    G.trazar('B', 1, 'C', 3, 'D', -1, 'E')
    G.trazar('F', -1, 'E')
    print(G)
    print()
    
    dist, padre = bellman_ford(G, 'S')
    print('Árbol generado por el algoritmo de Bellman-Ford iniciando en S:')
    print(Grafo.arbol(padre))
    print()
    print('Distancias encontradas por el algoritmo:')
    for u in dist:
        print('d({}, {}) = {}'.format('A', u, dist[u]))
    print()
    
    print('Un digrafo pesado sin ciclos dirigidos:')
    G = Grafo(pesado = True)
    G.trazar('S', 2, 'B', 7, 'C', 1, 'E')
    G.trazar('A', 3, 'B', 2, 'E')
    G.trazar('A', 5, 'S', 6, 'C', -1, 'D', -2, 'E')
    G.trazar('B', 4, 'D')
    print(G)
    print()
    print('Ordenamiento topologico:')
    print(', '.join(ordenamiento_topologico(G)))
    print()
    dist, padre = caminos_mas_cortos_en_gads(G, 'S')
    print('Árbol de caminos más cortos desde S calculado en orden topológico:')
    print(Grafo.arbol(padre))
    print()
    print('Distancias encontradas por el algoritmo:')
    for u in dist:
        print('d({}, {}) = {}'.format('S', u, dist[u]))
    print()

conectividad.py

## Descripción: ejemplos de implementación y aplicación
## del recorrido en profundidad en grafos.
## Autor: Mario Abarca
## Lenguaje: Python 3
## Fecha: 4 de febrero de 2015
 
def componentes_conexas(G):
    def visita(v): #subrutina
        cc[v] = componente_actual 
        for u in G[v]:
            if u not in cc: #u no visitado <=> u no tiene componente
                visita(u)
    cc = dict() #Etiqueta de componente conexa
    componente_actual = 0
    for v in G:
        if v not in cc:
            visita(v)
            componente_actual += 1
    return cc
 
def voltear(G): #Regresa un nuevo grafo con las aristas en direccion contraria
    H = {v:[] for v in G}
    for v in G:
        for u in G[v]:
            H[u].append(v)
    return H

def postorden(G):
    def visita(u): #Subrutina del recorrido en profundidad
        visitados.add(u)
        for v in G[u]:
            if v not in visitados:
                visita(v)
        lista.append(u)

    lista, visitados = [], set()
    for u in G:
        if u not in visitados:  #¿Faltan vértices por visitar?
            visita(u)           #Vistarlos

    return lista
 
def ordenamiento_topologico(G):
    lista, post = postorden(G), dict()
    for i, u in enumerate(lista):
        post[u] = i
    
    #¿El recorrido generó una arista de retroceso?
    if any(post[u] < post[v] for u in G for v in G[u]):
        raise ValueError('No existe orden topológico para este grafo.')
    
    return list(reversed(lista))
 
def componentes_fuertemente_conexas(G):
    def visita(v): #Subrutina
        cfc[v] = componente_actual
        for u in G[v]:
            if u not in cfc: #u no visitado <=> no tiene componente
                visita(u)
    V = postorden(voltear(G)) #Calcular posorden sobre el grafo volteado
    V.reverse() #Invertir el orden
    cfc = dict() #Etiqueta de comp. fuertemente conexa
    componente_actual = 0
    for v in V: #en posorden invertido sobre el grafo revertido
        if v not in cfc:
            visita(v)
            componente_actual += 1
    return cfc
 
if __name__ == '__main__':
    from grafos import Grafo
    
    ## Componentes conexas 
    print('Un grafo simple:')
    G = Grafo(dirigido = False)
    G.trazar('B', 'A', 'E', 'I', 'J')
    G.trazar('F')
    G.trazar('L', 'H', 'K', 'G', 'H', 'C', 'G')
    G.trazar('C', 'D', 'H')
    print(G)
    cc = componentes_conexas(G)
    print('Etiqueta de componentes conexas:')
    for v in cc:
        print('cc({}) = {}'.format(v, cc[v]))
    print()

    ## Ordenamiento topologico
    print('Un digrafo sin ciclos dirigidos:')
    G = Grafo()
    G.trazar('A', 'D', 'F')
    G.trazar('A', 'B', 'D', 'C', 'F')
    G.trazar('A', 'C')
    G.trazar('B', 'E', 'D')
    G.trazar('G', 'D')
    G.trazar('G', 'F')
    G.trazar('G', 'E')
    print(G)
    print()
    orden = ordenamiento_topologico(G)
    print('Lista de vertices en orden topológico:')
    print(', '.join(orden))
    print()
 
    ## Componentes fuertemente conexas
    print('Un digrafo con ciclos dirigidos:')
    G = Grafo()
    G.trazar('A', 'B', 'C', 'F', 'H', 'K', 'L', 'J', 'I', 'G', 'H')
    G.trazar('B', 'E', 'F', 'C')
    G.trazar('E', 'B', 'D')
    G.trazar('E', 'G', 'J')
    print(G)
    print()
    cfc = componentes_fuertemente_conexas(G)
    print('Componentes fuertemente conexas del digrafo:')
    for v in cfc:
        print('cfc({}) = {}'.format(v, cfc[v]))
    print()

estructuras.py

## Estructuras de datos usadas en Optimización Combinatoria

from collections.abc import Sized, Iterable, Container, Mapping

### NODOS ###
class _Nodo:
    
    __slots__ = 'valor', 'siguiente'
    
    def __init__(self, valor, siguiente = None):
        self.valor, self.siguiente = valor, siguiente


### COLAS ###

class Cola(Sized, Iterable, Container):

    __slots__ = '_frente', '_atras', '_contador'

    def __init__(self, elementos = None):
        self._frente, self._atras = None, None
        self._contador = 0
        if elementos is not None:
            for elemento in elementos:
                self.encolar(elemento)

    def encolar(self, elemento):
        nodo = _Nodo(elemento)
        if self._frente is None:
            self._atras = nodo
            self._frente = nodo
        else:
            self._atras.siguiente = nodo
            self._atras = nodo
        self._contador += 1
            
    def desencolar(self):
        if self._frente is not None:
            elemento = self._frente.valor
            self._frente = self._frente.siguiente
            self._contador -= 1
            return elemento
        else: raise IndexError('desencolar en una Cola vacía')

    def __len__(self):
        return self._contador

    def __iter__(self):
        nodo = self._frente
        while nodo is not None:
            yield nodo.valor
            nodo = nodo.siguiente

    def __contains__(self, elemento):
        for miembro in self:
            if miembro == elemento:
                return True
        return False

    def __repr__(self):
        return 'Cola({})'.format(list(self) if self else '')


### PILAS ###
    
class Pila(Sized, Iterable, Container):

    __slots__ = '_cima', '_contador'

    def __init__(self, elementos):
        self._cima = None
        self._contador = 0
        for elemento in elementos:
            self.apilar(elemento)

    def apilar(self, elemento):
        self._cima = _Nodo(elemento, self._cima)
        self._contador += 1

    def desapilar(self):
        if self._cima is not None:
            elemento = self._cima.valor
            self._cima = self._cima.siguiente
            self._contador -= 1
        else: raise IndexError('desapilar en una Pila vacía')

    def __len__(self):
        return self._contador

    def __iter__(self):
        nodo = self._cima
        while nodo is not None:
            yield nodo.valor
            nodo = nodo.siguiente

    def __contains__(self, elemento):
        for miembro in self:
            if miembro == elemento:
                return True
        return False

    def __repr__(self):
        return 'Pila({})'.format(list(self) if self else '')


### COLAS DE PRIORIDAD MINIMA ###
    
def _padre(indice): return (indice - 1)//2

def _hijo_izquierdo(indice): return 2*indice + 1

def _hijo_derecho(indice): return 2*(indice + 1)


class ColaMin(Mapping):
        
    def __init__(self, prioridades = None):
        self._elementos = [] #arreglo de elementos
        self._prioridades = [] #arreglo de prioridades
        self._asas = dict() #tabla asociativa de elementos a indices
        if prioridades is not None:
            if not isinstance(prioridades, dict):
                raise TypeError('')
            for (elemento, prioridad) in prioridades.items():
                self.introducir_con_prioridad(elemento, prioridad)

    def introducir_con_prioridad(self, elemento, prioridad):
        self._elementos.append(elemento)
        self._prioridades.append(prioridad)
        self._asas[elemento] = len(self) - 1
        self._flotar(len(self) - 1)

    def extraer_min(self):
        if not self: #¿Es vacio?
            raise IndexError('No se puede extraer de una ColaMin vacia')
        self._intercambiar(0, len(self) - 1) #Intercambiar primero con ultimo
        #Extraer el ultimo elemento:
        elemento = self._elementos.pop()
        self._prioridades.pop()
        del self._asas[elemento]
        self._hundir(0) #Recuperar la propiedad del monticulo
        return elemento

    def bajar_prioridad(self, elemento, prioridad):
        i = self._asas[elemento] #Obtener indice del elemento actual
        if self._prioridades[i] <= prioridad:
            raise ValueError('La prioridad debe ser menor que la actual')
        self._prioridades[i] = prioridad #Bajar prioridad
        self._flotar(i) #Recuperar la propiedad del monticulo

    def _intercambiar(self, i, j):
        elem_i, elem_j = self._elementos[i], self._elementos[j]
        prio_i, prio_j = self._prioridades[i], self._prioridades[j]
        self._elementos[i], self._elementos[j] = elem_j, elem_i
        self._asas[elem_i], self._asas[elem_j] = j, i
        self._prioridades[i], self._prioridades[j] = prio_j, prio_i

    def _flotar(self, i):
        while i > 0 and self._prioridades[i] < self._prioridades[_padre(i)]:
            self._intercambiar(i, _padre(i))
            i = _padre(i)

    def _hundir(self, i):
        while True:
            izq, der, hmin = _hijo_izquierdo(i), _hijo_derecho(i), i
            if izq < len(self) and \
               self._prioridades[izq] < self._prioridades[hmin]:
                hmin = izq
            if der < len(self) and \
               self._prioridades[der] < self._prioridades[hmin]:
                hmin = der
            if hmin != i:
                self._intercambiar(i, hmin)
                i = hmin
            else: break
    
    def __len__(self):
        return len(self._elementos)

    def __iter__(self):
        for elemento in self._elementos:
            yield elemento

    def __getitem__(self, elemento):
        return self._prioridades[self._asas[elemento]]

    def __repr__(self):
        if not self:
            return 'ColaMin()' #Monticulo vacio
        t = ['{!r}:{!r}'.format(x, p) for x, p in self.items()]
        return 'ColaMin({{{}}})'.format(', '.join(t))


### ESTRUCTURA PARA CONJUNTOS DISJUNTOS ###
    
class ConjuntosDisjuntos:

    __slots__ = '_padre', '_rango'

    def __init__(self):
        self._padre, self._rango = dict(), dict()

    def hacer_conjunto(self, x):
        self._padre[x] = x
        self._rango[x] = 0

    def unir(self, x, y):
        x, y = self.hallar_conjunto(x), self.hallar_conjunto(y)
        if x != y:
            if self._rango[x] > self._rango[y]:
                self._padre[y] = x
            else:
                self._padre[x] = y
                if self._rango[x] == self._rango[y]:
                    self._rango[y] += 1

    def hallar_conjunto(self, x):
        if x != self._padre[x]:
            self._padre[x] = self.hallar_conjunto(self._padre[x])
        return self._padre[x]


if __name__ == '__main__':
    pass

flujos.py

from estructuras import Cola
from grafos import Grafo
inf = float('inf')

#Subrutina de Edmonds-Karp para encontrar un camino de aumento
def aumento_en_anchura(G, H, s, t, f):
    P, Q, F = {s: None}, Cola([s]), {s: inf}    #Árbol, Cola, Flujo
    def marcar(inc):                            #Incremetar flujo?
        if v in P or inc <= 0: return           #Visitado o inalcanzable
        F[v], P[v] = min(F[u], inc), u          #¿Mayor flujo?, ¿desde dónde?
        Q.encolar(v)                            #v descubierto

    while Q:                                    #¿Hay vértices por descubrir?
        u = Q.desencolar()                      #Procesar siguiente vértice
        if u == t: return P, F[t]               #Camino encontrado
        for v in G[u]: marcar(G[u][v] - f[u,v]) #Marcar arcos salientes
        for v in H[u]: marcar(f[v,u])           #Marcar arcos entrantes
    return None, 0                              #No hay caminos de aumento

#Método de Ford-Fulkerson para encontrar flujo máximo de s a t
def ford_fulkerson(G, s, t, camino_aum = aumento_en_anchura):
    H = G.voltear()                             #Grafo al reves
    f = {(u, v):0 for u in G for v in G[u]}     #Iniciar con el flujo cero
    while True:                                 
        P, c = camino_aum(G, H, s, t, f)        #Camino de aumento y su valor
        if c == 0: return f                     #¿Sin caminos? Terminamos
        u = t                                   #Comenzar aumento
        while u != s:                           #Vuelta atrás hasta s
            u, v = P[u], u                      #Retroceder un paso
            if v in G[u]: f[u, v] += c          #¿Arista de avance? Añadir f.
            else: f[v, u] -= c                  #¿Ar. de retroceso? Cancelar f.

def emparejamiento(R):
    G, s, t = Grafo(pesado = True), object(), object() #Crear red de flujo
    for (x, y) in R: G.trazar(s, 1, x, 1, y, 1, t) #Reducir el problema
    f = ford_fulkerson(G, s, t)                 #Resolver flujo maximo
    return {(x, y) for (x, y) in R if f[x, y] > 0} #Recuperar solucion

if __name__ == '__main__':
    from random import random, randint, getrandbits
    n = 5
    G = Grafo.aleatorio(n, 1, pesos = range(1, 6), dirigido = True)
    for u in list(G):
        if random() <= 0.5: G.trazar('S', randint(1, 5), u)
        if random() <= 0.5: G.trazar(u, randint(1, 5), 'T')
    G.trazar('S')
    G.trazar('T')
    print('Una red de flujo aleatoria:')
    print(G)
    f = ford_fulkerson(G, 'S', 'T')
    print('Flujo maximo:')
    print(Grafo(E = {e: f[e] for e in f if f[e] > 0}, pesado = True))
    print()
    X = ['Alejandro', 'Bruno', 'Carlos', 'Diego']
    Y = ['Alicia', 'Beatriz', 'Carolina', 'Daniela']
    R = [(x, y) for x in X for y in Y if random() <= 4/9]
    print('Una relacion aleatoria:')
    for x, y in R:
        print(x, '──', y)
    print()
    print('Emparejamiento maximo')
    for x, y in emparejamiento(R):
        print(x, '──', y)

grafos.py

## Los grafos en Python pueden ser implementados como se describe en
## www.python.org/doc/essays/graphs/
##
## Este módulo contiene un intérprete de comandos que permite capturar dicha
## estructura de datos a partir de sucesiones de caminos (llamadas trazos) así
## como varias funciones de gran utilidad.
##
## La implementación de la clase Grafo que aparece aquí no está orientada a
## objetos; y está diseñada para funcionar como un dict con operaciones extras
## que son específicas de la creación y manipulación de grafos.
##
## Autor: Mario Abarca
## Licencia: creativecommons.org/licenses/by-nc-sa/3.0/deed.es
## Fecha: 29 de marzo de 2015

import cmd
from collections import Counter
from collections.abc import KeysView as VistaDeVertices
from collections.abc import MappingView as _MappingView
from itertools import combinations
from random import choice, getrandbits, random, shuffle
from cmath import rect
from math import pi

class VistaDeAristas(_MappingView):
    def __len__(self):
        return self._mapping._tamano

    def __contains__(self, arista):
        u, v = arista
        return u in self._mapping and v in self._mapping[u]

    def __iter__(self):
        if self._mapping.dirigido:
            for u in self._mapping:
                for v in self._mapping[u]:
                    yield (u, v)
        else:
            indice = {u:i for i, u in enumerate(self._mapping.vertices)}
            for u in self._mapping:
                for v in self._mapping[u]:
                    if indice[u] < indice[v]:
                        yield (u, v)

class Grafo(dict):
    def __init__(self, V = None, E = None, pesado = False, dirigido = True):
        self._pesado = pesado
        self._dirigido = dirigido
        self._tamano = 0
        if V:
            for u in V:
                self.trazar(u)
        if E:
            if pesado:
                for (u, v) in E:
                    self.trazar(u, E[u, v], v)
            else:
                for (u, v) in E:
                    self.trazar(u, v)
    
    @property
    def vertices(self):
        return VistaDeVertices(self)

    @property
    def aristas(self):
        return VistaDeAristas(self)

    def vecinos(self, u):
        return VistaDeVertices(self[u])

    def copia(self):
        G = Grafo()
        G.update({u:self[u].copy() for u in self})
        G._pesado = self._pesado
        G._dirigido = self._dirigido
        G._tamano = self._tamano
        return G
    
    def trazar(self, *camino):
        def agregar_vertice(u):
            if u not in self:
                self[u] = dict() if self.pesado else set()
                
        def agregar_arista(u, v, w):
            if v not in self[u]: self._tamano += 1
            if self.pesado:
                self[u][v] = w
                if not self.dirigido: self[v][u] = w
            else:
                self[u].add(v)
                if not self.dirigido: self[v].add(u)
        
        elementos, w = iter(camino), None
        u = next(elementos, None)
        if u is not None: agregar_vertice(u)
        while True:
            if self._pesado: w = next(elementos, None)
            v = next(elementos, None)
            if v is not None:
                agregar_vertice(v)
            else: break
            agregar_arista(u, v, w)
            u = v

    def borrar(self, *camino):
        def quitar_arista(u, v):
            if self.pesado:
                if v in self[u]:
                    del self[u][v]
                    if not self.dirigido: del self[v][u]
            else:
                if v in self[u]:
                    self[u].remove[v]
                    if not self.dirigido: self[v].remove[u]
        
        def quitar_vertice(u):
            if self.pesado:
                for v in self:
                    if u in self[v]:
                        del self[v][u]
            else:
                for v in self:
                    if u in self[v]:
                        self[v].remove(u)
            del self[u]

        if len(camino) == 1:
            quitar_vertice(camino[0])
        elif camino:
            for i in range(len(camino) - 1):
                quitar_arista(camino[i], camino[i + 1])

    @property
    def dirigido(self):
        return self._dirigido

    @property
    def pesado(self):
        return self._pesado

    def voltear(self):
        if not self.dirigido:
            return self.copia()
        H = Grafo(self.vertices, pesado = self.pesado, dirigido = self.dirigido)
        if self.pesado:
            for u in self:
                for v in self[u]:
                    H[v][u] = self[u][v]
        else:
            for u in self:
                for v in self[u]:
                    H[v].add(u)
        H._tamano = self._tamano
        return H

    @staticmethod
    def arbol(pred):
        '''Genera un árbol (o bosque) a partir del diccionario de predecesores
de cada vértice. Una raíz tiene como predecesor a sí mismo (pred[r] == r)'''
        T = Grafo()
        for u in pred:
            if pred[u] == u:
                T.trazar(u)
            else: T.trazar(pred[u], u) 
        return T

    @staticmethod
    def aleatorio(n, p, pesos = None, dirigido = False):
        '''Crea un Grafo con n vértices donde cada arista tiene una probabilidad
p ∈ [0, 1] de aparecer. Si se proporciona una lista de pesos, el grafo será
pesado y cada arista generada se le asignará un peso aleatorio de la lista.'''
        V = [chr(i) for i in range(ord('A'), ord('A') + n)]
        if pesos is not None: pesos = list(pesos)
        G = Grafo(dirigido = dirigido, pesado = bool(pesos))
        for u in V: G.trazar(u)
        for u, v in combinations(V, 2):
            if random() > p: continue
            if dirigido and getrandbits(1): u, v = v, u
            if pesos:
                G.trazar(u, choice(pesos), v)
            else: G.trazar(u, v)
        return G

    def __repr__(self):
        if self:
            args = [repr(set(self.vertices))]
            if self.pesado:
                args.append(repr({(u, v):self[u][v] for (u, v) in self.aristas}))
            else:
                args.append(repr(set(self.aristas)))
        else: args = []
        if self.pesado:
            args.append('pesado = True')
        if not self.dirigido:
            args.append('dirigido = False')
        return 'Grafo({})'.format(', '.join(args))

    def trazos(self):
        '''Devuelve un conjunto de trazos que representa al grafo.'''
        ## ¿El caso no dirigido se reduce a encontrar una orientaion adecuada?
        ## ¿Este algoritmo encuentra el número mínimo de trazos?
        def factorizar(u):
            c = [u]
            while G[u]:
                v = G[u].pop()
                if self.pesado: c.append(self[u][v])
                if not G.dirigido: G[v].remove(u)
                c.append(v)
                u = v
            return c

        def extender(c):
            i = 0
            s = 1 + int(bool(self.pesado))
            while True:
                while i < len(c) and not G[c[i]]:
                    i += s
                if i >= len(c): break
                c[i:i + 1] = factorizar(c[i])

        G = Grafo(self.vertices, self.aristas, dirigido = self.dirigido)
        if G.dirigido:
            H = G.voltear()
            L = [[u] for u in G if not (G[u] or H[u])]
            Q = list(Counter({u:len(G[u]) - len(H[u]) for u in G})\
                     .elements())
        else:
            L = [[u] for u in G if not G[u]]
            Q = {u for u in G if len(G[u]) % 2}
        
        while Q:
            L.append(factorizar(Q.pop()))
            if not G.dirigido: Q.remove(L[-1][-1])
        for c in L: extender(c)
        while True:
            u = next((u for u in G if G[u]), None)
            if u is None: break 
            L.append(extender(factorizar(u)))
        return set(map(tuple, L))

    def disponer(self, iteraciones = 50, temperatura = 1.0, digitos = 3):
        '''Asigna coordenadas (x, y) a cada vertice'''
        n, vert = len(self), list(self.vertices)
        shuffle(vert)
        pos = {u:rect(0.5, (2*pi)*(k/n)) for (k, u) in enumerate(vert)}
        enfriar = temperatura/iteraciones
        for i in range(iteraciones):
            desp = {v:0j for v in self}
            for u, v in combinations(self.vertices, 2):
                    dif = pos[v] - pos[u]
                    dist2 = dif.real**2 + dif.imag**2
                    if dist2 < 4:
                        vec_repulsion = dif/dist2
                        desp[v] += vec_repulsion
                        desp[u] -= vec_repulsion
                    if v in self[u] or (self.dirigido and u in self[v]):
                        vec_atraccion = abs(dif)*dif
                        desp[u] += vec_atraccion
                        desp[v] -= vec_atraccion
            for v in self:
                dist_desp = abs(desp[v])
                if dist_desp == 0.0: continue
                pos[v] += (desp[v]/dist_desp)*min(dist_desp, temperatura)
            temperatura -= enfriar
        return {u:(round(pos[u].real, digitos), round(pos[u].imag, digitos))
                for u in pos}

    def tikz(self):
        lineas = [r'\begin{tikzpicture}']
        disp = self.disponer()
        nodestr = r'    \node ({0}) at ({1[0]},{1[1]}) {{${0}$}};'
        lineas.extend(nodestr.format(u, disp[u]) for u in disp)
        drawstr = r'    \draw' + ('[->] ' if self.dirigido else ' ')
        if self.pesado:
            drawstr += '({}) to node[auto] {{${}$}} ({});'
            lineas.extend(drawstr.format(u, self[u][v], v)
                          for (u, v) in self.aristas)
        else:
            drawstr += '({}) -- ({});'
            lineas.extend(drawstr.format(u,v) for (u, v) in self.aristas)
        lineas.append(r'\end{tikzpicture}')
        return '\n'.join(lineas)
    
    def __str__(self):
        caminos = self.trazos()
        lineas = []
        cabeza = '►' if self.dirigido else '─'
        if self.pesado:
            for camino in caminos:
                abajo = [str(camino[0])]
                arriba = [' '*len(abajo[0])]
                for i in range(1, len(camino) - 1, 2):
                    w, v = camino[i], camino[i + 1]
                    arriba.append(' ' + str(w))
                    abajo.append('─'*len(arriba[-1]))
                    abajo.append(cabeza + str(v))
                    arriba.append(' '*len(abajo[-1]))
                lineas.append(''.join(arriba))
                lineas.append(''.join(abajo))
        else:
            arista = '─' + cabeza
            for camino in caminos:
                lineas.append(arista.join(camino))
        return '\n'.join(lineas)
        
    
class Programa(cmd.Cmd):
    intro = '''Bienvenido al intérprete de comandos para la creación \
de grafos en Python.
Teclea «?» para enlistar los comandos disponibles.'''
    prompt = '▷ '
    doc_header = 'Comandos documentados (escriba help <comando>):'
    misc_header = 'Topicos de ayuda misceláneos:'
    undoc_header = 'Comandos sin documentación:'
    nohelp = '* Sin ayuda para %s'
    nosintax = '* Sintaxis desconocida: {}'

    def __init__(self):
        super().__init__()
        self.rango = None
        self.G = Grafo()

    def do_trazar(self, args):
        '''SINOPSIS:
• En grafos/digrafos simples:
  trazar v₀ v₁ v₂ … vₖ — Agrega al grafo/digrafo el camino v₀─►v₁─►v₂─►…─►vₖ
    
• En grafos/digrafos pesados:
  trazar v₀ w₀ v₁ w₁ v₂ w₂ … wₖ₋₁ vₖ — Agrega al grafo/digrafo el camino pesado
                                         w₀   w₁   w₂   wₖ₋₁
                                       v₀──►v₁──►v₂──► … ──►vₖ
EJEMPLOS:
  trazar A B C D A — Agrega los vértices A, B, C, y D al grafo actual así como
                     el ciclo A─►B─►C─►D─►A'''
        camino = args.split()
        if self.rango:
            for i in range(1, len(camino), 2):
                try:
                    camino[i] = self.rango(camino[i])
                except ValueError:
                    print('Error de dominio.')
                    return None
        self.G.trazar(*camino)

    def do_borrar(self, args):
        '''SINOPSIS:
• borrar v₀ v₁ v₂ … vₖ — borra las aristas del camino v₀─►v₁─►v₂─►…─►vₖ
• borrar v — borra el vértice v, así como todas sus aristas incidentes.

EJEMPLOS:
    borrar A B C D A — borra las aristas del ciclo A─►B─►C─►D─►A, pero conserva
                       los vértices A, B, C, y D
    borrar A — borra el vértice A del grafo actual'''
        self.G.borrar(*args.split())

    def do_nuevo(self, args):
        '''SINOPSIS:
nuevo [di]grafo (simple|entero|real) — deshecha el grafo actual y lo reemplaza
                                       por un grafo/digrafo simple o pesado,
                                       con pesos enteros/reales, sin vértices
                                       ni aristas.
EJEMPLOS:
    nuevo grafo simple — crea un nuevo grafo simple
    nuevo digrafo entero — crea un digrafo vacío con pesos enteros'''
        args = args.split()
        if len(args) != 2:
            print('Se esperaban dos argumentos.')
            return None
        if args[0] == 'grafo':
            dirigido = False
        elif args[0] == 'digrafo':
            dirigido = True
        else:
            print('Se esperaba "grafo" o "digrafo".')
            return None
        if args[1] == 'simple':
            self.rango = None
        elif args[1] == 'entero':
            self.rango = int
        elif args[1] == 'real':
            self.rango = float
        else:
            print('Se esperaba "simple", "entero" o "real".')
        self.G = Grafo(dirigido = dirigido, pesado = bool(self.rango))

    def do_imprimir(self, args):
        '''SINOPSIS:
imprimir — Muestra en pantalla la representación por trazos del grafo actual.
imprimir tikz — Muestra un código de LaTeX que dibuja el grafo actual usando
                el paquete Tikz.'''
        if args == 'tikz':
            print(self.G.tikz())
        else: print(self.G)

    def do_representar(self, args):
        '''SINOPSIS:
representar [lista] — Muestra en pantalla el código en Python que representa al
                      grafo actual. Por defecto el grafo es representado en la
                      clase Grafo. El argumento opcional “lista” muestra la
                      representación estándar de Python de listas de \
adyacencia.'''
        if args == 'lista':
            print(repr(dict(self.G)))
        else: print(repr(self.G))

    def do_vecinos(self, args):
        '''SINOPSIS:
vecinos v — Muestra los vecinos del vértice v en el grafo actual.'''
        if not args: print('Se esperaba un vértice.')
        if args in self.G:
            print(', '.join(self.G[args]))
        else: print()

    def do_salir(self, args):
        return True

Programa.do_help.__doc__ = 'Muestra los comandos disponibles con "help" o \
ayuda detallada con "help cmd"'

if __name__ == '__main__':
    Programa().cmdloop()

progdinamica.py

from grafos import Grafo
from functools import lru_cache
from conectividad import postorden
inf = float('inf')

def mochila(v, w, C):                       #Valores, Pesos y Capacidad
    n = len(w)
    K = [[0]*(n+1) for i in range(C+1)]     #Matriz de valor de los subproblemas
    P = [[False]*(n+1) for i in range(C+1)] #Matriz de selección
    for j in range(1, n):                   #Usando los primeros j objetos
        i = j - 1                           #Objeto en consideración
        for c in range(1, C+1):             #Para cada capacidad positiva
            K[c][j] = K[c][i]               #Valor sin seleccionar objeto i
            if w[i] > c: continue           #¿No cabe? Ignorarlo
            tomar = K[c - w[i]][j-1] + v[i] #Valor al seleccionar objeto i
            if K[c][j] < tomar:             #¿Mejora la sol. al tomar el ob. i?
                K[c][j] = tomar             #Actualizar solución
                P[c][j] = True              #Recordar la selección
    return K, P

def conjunto_mochila(P, w):                 #Construir la selección de mochila
    c, j, S = len(P) - 1, len(P[0]) - 1, [] #Capacidad, objeto, conjunto
    while c > 0 and j > 0:
        if P[c][j]:
            S.append(j - 1)
            c -= w[j - 1]
        j -= 1
    S.reverse()
    return S

def floyd_warshall(G):
    D, P = dict(), dict()                   #Matrices de distancias y caminos
    for u in G:                             #Inicializar caminos
        for v in G:
            if v in G[u]:                   #¿v es vecino de u?
                D[u, v], P[u, v] = G[u][v], u #Distancia y camino inicial
            else: D[u, v], P[u, v] = inf, None #No hay camino inicial

    for k in G:                             #Vértice k en consideración
        for u in G:                         #Iterar sobre toda pareja de vért.
            for v in G:
                atajo = D[u, k] + D[k, v]   #Distancia de u a v pasando por k
                if atajo < D[u, v]:         #¿Pasar por k forma un atajo?
                    D[u, v] = atajo         #Actualizar distancias
                    P[u, v] = P[k, v]       #Actualizar caminos
    return D, P

def camino(P, u, v):                        #Camino u⤳v dado por Floyd-Warshall
    lista = [v]                             #El camino termina en v
    while v != u:                           #Hasta no llegar a u
        v = P[u, v]                         #…retrocedemos un paso
        lista.append(v)                     
    lista.reverse()                         #Enlistamos el recorrido en reversa
    return lista

def nietos(T, u): #Calcula el conjunto de nietos del vértice u en el árbol T
    S = []
    for v in T[u]:
        S.extend(T[v])
    return S

def wilf(T, r):                             #Conjunto independiente en árboles
    I, P = dict(), dict()                   #Soluciones parciales
    for u in postorden(T):                  #calculando de las hojas a la raíz
        con_u = 1 + sum(I[w] for w in nietos(T, u)) #Valor con u en el conjunto:
        sin_u = sum(I[h] for h in T[u])     #Valor sin u en el conjunto
        I[u] = max(con_u, sin_u)            #Seleccionar mejor valor
        P[u] = (con_u > sin_u)              #Almacenar si u pertenece a la sol.
    return I, P                             #Devolver resultados parciales

def independiete_arbol(T, r, P):            #Construye el conj. indep. de Wilf
    S = set()                               #Iniciar con conjunto vacío
    if P[r]:                                #¿r fue seleccionado?
        S.add(r)                            #Agregar r
        for w in nietos(T, r):              #…y los subconjuntos de los nietos
            S.update(independiete_arbol(T, w, P))
    else:
        for h in T[r]:                      #Agrgar subconjuntos de los hijos
            S.update(independiete_arbol(T, h, P))
    return S

if __name__ == '__main__':
    from random import randint, shuffle
    from itertools import combinations
    from estructuras import ConjuntosDisjuntos
    from caminos import recorrido_a_lo_ancho
    print('== Problema de la mochila ==')
    print('Objetos, peso y valor:')
    n = 10
    w = [randint(1, 10) for k in range(n)]
    v = [100*randint(1, 9) for k in range(n)]
    C = 30
    for i in range(n):
        print(i, ':', '█'*w[i], ' $', v[i])
    print('Capacidad:')
    print('   ', '░'*C)
    K, P = mochila(v, w, C)
    S = conjunto_mochila(P, w)
    peso = sum(w[j] for j in S)
    print('Selección de objetos:', S)
    print('Peso y valor seleccionado:')
    print('   ', '█'*peso + '░'*(C-peso), '$', K[C-1][n-1])
    print()
    print('== Problema de caminos más cortos entre todos los pares de v. ==')
    print('Un digrafo pesado aleatorio:')
    G = Grafo.aleatorio(4, 1.0, pesos = range(1, 6), dirigido = True)
    print(G)
    print('Caminos más cortos y distancias encontradas por Floyd-Warshall:')
    D, P = floyd_warshall(G)
    for u in G:
        for v in G:
            if u != v and D[u, v] < inf:
                print('─►'.join(camino(P, u, v)), ':', D[u, v])
    print()
    print('== Problema del conjunto independiente en árboles ==')
    ##Crear un arbol aleatorio usando Kruskal con aristas en orden aleatorio
    n = 20
    V = list(map(chr, range(ord('A'), ord('A') + n)))
    E = list(combinations(V, 2))
    shuffle(E)
    F = ConjuntosDisjuntos()
    T = Grafo(dirigido = False)
    for v in V: F.hacer_conjunto(v)
    for (u, v) in E:
        if F.hallar_conjunto(u) != F.hallar_conjunto(v):
            T.trazar(u, v)
            F.unir(u, v)
    print('Un árbol:')
    print(T)
    ##Enraizar el arbol en A mediante un recorrido a lo ancho
    dist, padre = recorrido_a_lo_ancho(T, 'A')
    T = Grafo.arbol(padre)
    I, P = wilf(T, 'A')
    print('Conjunto independiente:', ', '.join(independiete_arbol(T, 'A', P)))

simplex.py

## La programación lineal es el problema de maximizar o minimizar una función
## lineal en un poliedro convexo especificado por restricciones lineales de
## no-negatividad. La programación lineal se puede resolver utilizando el 
## método simplex (Dantzig, G. B. "Programming of Interdependent Activities.
## II. Mathematical Model." Econometrica 17, 200-211, 1949.) que recorre los
## bordes del poliedro para encontrar la mejor respuesta.
##
## La presente implementación del método Simplex está diseñada como herramienta
## didáctica. Para una implementación profesional refiérase a GLPK (GNU Linear
## Programming Kit) en https://www.gnu.org/software/glpk/
## 
## Autor: Mario Abarca
## Lenguaje: Python 3
## Fecha: 26 de marzo de 2015

from fractions import Fraction
from cmd import Cmd
import csv
from random import randint
inf  = float('inf')

## EL MÉTODO SIMPLEX ##

def cuadro(A, b, c, K = Fraction):          #Crea un cuadro para Simplex
    m, n = len(b), len(c)
    M = [[K(0)]*(1 + m + n) for i in range(m + 1)] #Crear matriz M de ceros
    for j in range(n): M[0][j + 1] = K(c[j]) #Función objetivo en renglón M[0]
    for i in range(m):
        M[i + 1][0] = K(b[i])               #Constantes b[i] en columna M[i][0]
        for j in range(n):                  
            M[i + 1][j + 1] = K(A[i][j])    #Copia de A en M[1..m][1..n]
        M[i + 1][n + i + 1] = K(1)          #Agregar variables de holgura
    return M, list(range(n + 1, m + n + 1)) #Devolver cuadro y base inicial

def pivotar(M, B, h, e, verboso = False):
    m, n = len(M), len(M[0])
    r = M[h][e]                             #Hacer 1 en M[h,e]
    for j in range(n): M[h][j] /= r         #…dividiendo todo M[h] entre M[h,e]
    for i in range(m):                      #Para todo renglón M[i]
        if i == h: continue                 #…excepto M[h],
        r = M[i][e]                         #hacer ceros en M[i,e]
        for j in range(n):
            M[i][j] -= M[h][j]*r            #…restando M[i,e] veces M[h] de M[i]
    B[h - 1] = e                            #Meter x[e] en la base
    if verboso:
        print('Pivoteo en renglón {}, columna {}.'.format(h, e))
        imprimir_cuadro(M, B, True)

def simplex(M, B, verboso = False):
    m, n = len(M), len(M[0])
    while True:
        e = 1                               #Buscar variable entrante x[e]
        while e < n and M[0][e] <= 0: e += 1 #elegiendo primer e con M[0][e] > 0
        if e >= n:
            if verboso: print('Solución óptima encontrada.')
            break                           #¿No hay? Terminamos
        d, h, s = inf, m, n                 #Buscar var. más apretada x[s]
        for i, j in enumerate(B, 1):        
            q = M[i][0]/M[i][e] if M[i][e] > 0 else inf #Holgura de x[j]
            if q < d or (q == d and j < s): 
                d, h, s = q, i, j           #x[s] tiene holgura e índice mínimos
        if d == inf: raise RuntimeError('Programa no acotado.')
        if verboso:
            print('Se elige ({}) para entrar a la base con plusvalia {}.'\
                  .format(e, M[0][e]))
            print('Se elige ({}) para salir de la base con holgura {}.'\
                  .format(s, d))
        pivotar(M, B, h, e, verboso)        #Pivotar en M[h][e] (sale x[s] de B)

def simplex_dos_fases(M, B, K = Fraction, verboso = False):
    if verboso:
        print('Cuadro inical:')
        imprimir_cuadro(M, B, True)
    m, n = len(M), len(M[0])
    #Fase 1: Encontrar una sol. básica factible inicial
    k = 1                                   #Elegir k que minimiza b[k]
    for i in range(2, m):
        if M[i][0] < M[k][0]: k = i
    if M[k][0] < 0:                         #¿b[k] es negativo?
        c = M[0][:]                         #Guardar función objetivo
        for j in range(n):  M[0][j] = K(0)  #Borrar la f.o. del cuadro
        for i in range(m): M[i].append(K(-1)) #Agregar variable artificial
        if verboso:
            print('Es necesario buscar una solución básica factible inicial.')
            print('Agregando variable y función objetivo artificiales:')
            imprimir_cuadro(M, B, True)
            print('Se elige ({}) para entrar a la base por ser la variable \
artificial.'.format(n))
            print('Se elige ({}) para salir de la base con restricción {}.'\
                  .format(B[k - 1], M[k][0]))
        pivotar(M, B, k, n, verboso)        #Ingresar var. artificial a la base
        simplex(M, B, verboso)              #Buscar sol. básica factible inicial
        if M[0][0] != K(0):                 #¿Es necesaria la var. artificial?
            raise RuntimeError('El programa es infactible.')
        if verboso: print('El programa es factible.')
        if n in B:                          #¿La var. artifical es básica?
            print('Es necesario retirar la variable artificial ({}) de la base\
 para continuar.'.format(n))
            h, e = B.index(n) + 1, 1        #Sacarla de la base
            while e < n and M[0][e] == 0: e += 1 #…metiendo una x[e] no básica
            print('Se elige ({}) para entrar a la base por ser no básica.'\
                  .format(e))
            pivotar(M, B, h, e, verboso)    #…mediante un pivoteo degenerado
        for i in range(m): M[i].pop()       #Borrar var. artificial
        M[0] = c                            #Recuperar función objetivo
        if verboso:
            print('Recuperando la función objetivo original:')
            imprimir_cuadro(M, B, True)
            print('Se necesita expresar la función objetivo en la base actual.')
            print('Haciendo ceros en las columnas {} del renglón 0.'\
                  .format(set(B)))
        for h, e in enumerate(B, 1):        #Para cada x[e] en la base
            r = M[0][e]                     #…hacer cero c[e]
            for j in range(n):
                 M[0][j] -= M[h][j]*r       #…restando c[e] veces M[h] de c
        if verboso:
            print('Cuadro con solución básica factible inicial:')
            imprimir_cuadro(M, B, True)
    #Fase 2: Iterar simplex hasta encontrar la solución básica factible óptima
    simplex(M, B, verboso)
   
## FUNCIONES ADICIONALES ##

def dual(A, b, c):
    m, n = len(b), len(c)
    At = [[-A[i][j] for i in range(m)] for j in range(n)] #At = -transpuesta(A)
    bt = [-c[j] for j in range(n)]          #bt = -c
    ct = [-b[i] for i in range(m)]          #ct = -b
    return At, bt, ct

def resolver_pl(A, b, c, K = Fraction):
    m, n = len(b), len(c)
    M, B = cuadro(A, b, c, K)               #Inicializar
    simplex_dos_fases(M, B, K)              #Resolver mediante Simplex
    x = [K(0)]*n
    for i, j in enumerate(B, 1):
        if j <= n: x[j - 1] = M[i][0]       #Vector solución x
    y = [-M[0][j] for j in range(n + 1, n + m + 1)] #Vector solución dual y
    return x, y, -M[0][0]                   #Soluciones y valor objetivo

def imprimir_cuadro(M, B, verboso = False):
    m, n = len(M), len(M[0])
    x = [list(map(str, r)) for r in M]
    p = [max(len(x[i][j]) for i in range(m)) for j in range(n)]
    for i in range(m):
        for j in range(n):
            x[i][j] = x[i][j].center(p[j])
        x[i] = '│{}│{}│{}'.format(x[i][0], ' '.join(x[i][1:]),
                                  '({})'.format(B[i - 1]) if i > 0 else '')
    print('┌{0}┬{1}┐\n{2}\n├{0}┼{1}┤\n{3}\n└{0}┴{1}┘'.format(
        '─'*p[0], '─'*(sum(p[1:]) + n - 2), x[0], '\n'.join(x[1:])))
    if verboso: input('Presione [Intro] para continuar...')

def instancia_aleatoria(m = 4, n = 4, maxa = 9, mina = -3, maxb = 19,
                        minb = -5, maxc = 9, minc = 0):
    A = tuple(tuple(randint(mina, maxa) for j in range(n)) for i in range(m))
    b = tuple(randint(minb, maxb) for i in range(m))
    c = tuple(randint(minc, maxc) for j in range(n))
    return A, b, c

## INTÉRPRETE DE COMANDOS ##

class Programa(Cmd):
    intro = '''Bienvenido al intérprete de comandos para utilizar Simplex.
Teclea «?» para enlistar los comandos disponibles.'''
    prompt = '▷ '
    doc_header = 'Comandos documentados (escriba help <comando>):'
    misc_header = 'Topicos de ayuda misceláneos:'
    undoc_header = 'Comandos sin documentación:'
    nohelp = '* Sin ayuda para %s'
    nosintax = '* Sintaxis desconocida: {}'
    def __init__(self):
        super().__init__()
        self.do_cargar('ejemplo')
        
    def do_cargar(self, args):
        '''SINOPSIS:
cargar [ejemplo|<archivo>] — carga en memoria un ejemplo generado de forma
aleatoria o un archivo csv que representa un programa lineal en forma estándar.

Un archivo csv es un documento de texto plano que contiene una matriz donde
las entradas están separadas por comas, y los renglones separados por saltos de
línea. Por ejemplo, el programa lineal

maximizar: (5, 4, 5, 6, 4) x
sujeto a: ┌ 9  8  2  5 -1┐     ┌-1┐
          │-5 -3  5  5 -5│     │ 9│
          │-1 -4 -3  1 -1│ x ≤ │ 2│
          └ 9  7  0  4  4┘     └ 4┘

Se representa en el siguiente archivo csv (nótese la coma al final del primer
renglón):
┌───────────────┐
│problema.csv   │
├───────────────┤
│5,4,5,6,4,     │
│9,8,2,5,-1,-1  │
│-5,-3,5,5,-5,9 │
│-1,-4,-3,1,-1,2│
│9,7,0,4,4,4    │
└───────────────┘

EJEMPLOS:
cargar problema.csv     #carga el archivo "problema.csv"
cargar ejemplo          #genera un ejemplo aleatorio'''
        args = args.split()
        if len(args) != 1 or (not args[0].endswith('.csv') and \
           not args[0] == 'ejemplo'):
            print("Se esperaba un nombre de archivo .csv o 'ejemplo'")
            return None
        if args[0] == 'ejemplo':
            self.cuadro = cuadro(*instancia_aleatoria())
        else:
            try:
                with open(args[0]) as archivo:
                    lector = csv.reader(archivo)
                    c = next(iter(lector))
                    c.pop()
                    A, b = [], []
                    for renglon in lector:
                        A.append(renglon)
                        b.append(A[-1].pop())
            except FileNotFoundError:
                print('¡Archivo no encontrado!')
                return None
            self.cuadro = cuadro(A, b, c)

    def do_imprimir(self, args):
        '''SINOPSIS:
imprimir [cuadro] [solucion] [valor]

Muestra en pantalla el cuadro actual. Si se proporcionan los argumentos
"cuadro", "solucion" y "valor", se mostrarán, según sea el caso, el cuadro, el
vector solución, y el valor objetivo.

EJEMPLOS:
imprimir                #Muestra el cuadro actual
imprimir cuadro         #Lo mismo que el ejemplo anterior
imprimir solucion valor #Muestra el vector solución y su valor objetivo.'''
        args = frozenset(args.split())
        M, B = self.cuadro
        if args:
            m, n = len(M) - 1, len(M[0]) - len(M)
            if 'cuadro' in args:
                imprimir_cuadro(M, B)
            if 'solucion' in args:
                x = [Fraction(0)]*n
                for i, j in enumerate(B, 1):
                    if j <= n: x[j - 1] = M[i][0]
                y = [-M[0][j] for j in range(n + 1, n + m + 1)]
                print('({})'.format(', '.join(map(str, x))))
            if 'valor' in args:
                print(-M[0][0])
        else: imprimir_cuadro(*self.cuadro)

    def do_pivotar(self, args):
        '''SINOPSIS:
pivotar <renglon> <columna>

Realiza un pivoteo en el renglón <renglón> y columna <columna>. Note que esto
puede resultar en una solución básica no factible.

EJEMPLOS:
pivotar 2 3'''

        args = args.split()
        if len(args) != 2 or not all(arg.isdecimal() for arg in args):
            print('Se esperaban dos números enteros.')
            return None
        M, B = self.cuadro
        m, n = len(M), len(M[0])
        h, e = map(int, args)
        if not 1 <= h < m or not 1 <= e < n:
            print('Los índices tienen que estar en el rango [1, {}] y \
[1, {}] respectivamente.'.format(m - 1, n - 1))
            return None
        pivotar(M, B, h, e)
        
    def do_simplex(self, args):
        '''SINOPSIS:
simplex [pasos]

Aplica el método simplex de dos fases sobre el cuadro actual con la regla de
Bland. Opcionalmente se puede mostrar el procedimiento paso a paso mediante la
opción "pasos".

EJEMPLOS:
simplex                 #Ejecuta Simplex sobre el cuadro actual.
simplex pasos           #Muestra la ejecución paso a paso.'''
        M, B = self.cuadro
        try:
            simplex_dos_fases(M, B, verboso = 'pasos' in args.split())
        except RuntimeError as err:
            print(err)

if __name__ == '__main__':
    Programa().cmdloop()

voraces.py

inf = float('inf') #Tratar infinito como número
from estructuras import ConjuntosDisjuntos, ColaMin
from grafos import Grafo

def kruskal(G):
    E = [(G[u][v], u, v) for u in G for v in G[u]] #Ordenar E(G) por pesos
    T = set() #Aristas del bosque
    S = ConjuntosDisjuntos() #Componentes conexas del bosque
    for u in G: S.hacer_conjunto(u)
    for _, u, v in sorted(E):
        #Si u--v no forma un ciclo en T, añadirlo a T y unir componentes
        if S.hallar_conjunto(u) != S.hallar_conjunto(v):
            T.add((u, v))
            S.unir(u, v)
    return T


def prim(G, s):
    cost, padre = {u:inf for u in G}, {u:u for u in G}
    cost[s] = 0 #costo[x] = longitud de la arista más pequeña x--v donde v ∈ T
    H = ColaMin(cost)
    while H: #¿Todavía hay vértices por agregar al árbol?
        u = H.extraer_min() #Elegir el más cercano al árbol
        for v in G[u]: #Actualizar costo de sus vecinos
            if v in H and G[u][v] < cost[v]: 
                cost[v], padre[v] = G[u][v], u
                H.bajar_prioridad(v, cost[v])
    return padre #El árbol tiene aristas u--padre[u]

def cobertura_voraz(B, S):
    R, solucion = set(B), set() #R son los elementos restantes por cubrir
    while R: #Mientras falten elementos por cubrir:
        #Buscar el conjunto S[k] que cubra más elementos de R
        indice, aporte = -1, 0
        for (i, X) in enumerate(S):
            if i not in solucion:
                C = R.intersection(X)
                if len(C) > aporte:
                    indice, aporte = i, len(C)
        #... y agregarlo si existe
        if indice >= 0:
            R.difference_update(S[indice])
            solucion.add(indice)
        else: break
    return solucion

def voraz(peso, es_independiente):
    S = [(peso[x], x) for x in peso.keys()] #Ordenar S por pesos
    A = set()
    for _, x in sorted(S, reverse = True):
        if es_independiente(A | {x}):
            A.add(x)
    return A

def planificar(d, w):
    def plan_canonico(A):
        P = list(A)
        P.sort(key = lambda i: d[i]) #Ordenar por tiempo limite
        return P
    
    def tareas_independientes(A): #Subrutina usada en el algoritmo voraz
        P = plan_canonico(A)
        for t, i in enumerate(P, 1):
            if d[i] < t:        #¿La tarea i no se completó a tiempo?
                return False
        return True

    n = len(d)
    if n != len(w) or any(not 1 <= d[i] <= n for i in range(n)):
        raise ValueError('Instancia no válida')
    peso = {i:w[i] for i in range(len(w))}
    return plan_canonico(voraz(peso, tareas_independientes))

if __name__ == '__main__':
    from random import shuffle, randint
    ## Árboles generadores de peso mínimo
    G = Grafo.aleatorio(7, 0.75, dirigido = False, pesos = range(1, 6))
    print('Un grafo ponderado aleatorio:')
    print(G)
    print()
    print('Árbol encontrado por el algoritmo de Prim:')
    print(Grafo.arbol(prim(G, 'A')))
    print()
    print('Árbol encontrado por el algoritmo de Kruskal:')
    print(Grafo(V = G.vertices, E = kruskal(G), dirigido = False))
    print()

    ## El problema de conjunto de cobertura y su aproximación voraz
    S = [set(randint(0, 7) for j in range(randint(1, 10))) for i in range(10)]
    print('Instancia del problema de conjunto de cobertura:')
    B = set()
    for i, X in enumerate(S):
        print('S[{}] = {}'.format(i, X))
        B.update(X)
    print('B =', B)
    print('Conjunto de cobertura elegido vorazmente:')
    print(', '.join('S[{}]'.format(i) for i in cobertura_voraz(B, S)))
    print()

    ## El matroide del problema de planificación de tareas de tiempo unitario
    ## con penalizaciones y fechas límite
    n = 7
    d = list(range(1, n + 1))
    shuffle(d)
    w = [randint(1,9) for i in range(n)]
    print()
    print('Instancia del problema de planificación:')
    print('i =', list(range(0, n)))
    print('d =', d)
    print('w =', w)
    print()
    print('La solución voraz selecciona el siguiente plan de tareas:')
    print(planificar(d, w))