Algoritmos del curso básico de Algoritmia

algsenredes.py

## Algoritmos en redes (grafos con pesos en las aristas)
##
## Autor: Mario Abarca (asma@uaem.mx)
## Fecha: 20 de octubre de 2015

from grafos import Grafo
from estructuras import Cola
from estructuras import ColaMin
from estructuras import ConjuntosDisjuntos

def prim(G, w, 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 a T?
        u = H.extraer_min()             #Elegir el más cercano a T
        for v in G.vecinos(u):          #Actualizar costo de sus vecinos
            if v in H and w[u, v] < cost[v]: 
                cost[v], padre[v] = w[u, v], u
                H.bajar_prioridad(v, cost[v])
    return padre                        #El árbol T tiene aristas u--padre[u]

def kruskal(G, w):
    E = [(w[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)     #Al inicio cada v
    for _, u, v in sorted(E):
        if S.hallar_conjunto(u) != S.hallar_conjunto(v):#¿u──v en comps. difs.?
            T.add((u, v))               #Agregar u──v a T
            S.unir(u, v)                #Unir sus componentes conexas
    return T
        
def dijkstra(G, w, s):
    dist = {u: float('inf') for u in G.vertices()}
    padre = {u: None for u in G.vertices()}
    dist[s] = 0                         #La dist. de s a sí mismo es cero
    H = ColaMin(dist)                   #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]:              
            atajo = dist[u] + w[u, v]   #Buscar un atajo a v pasando por u──v
            if v in H and atajo < dist[v]: #¿Este atajo reduce la distancia?
                dist[v], padre[v] = atajo, u #Actualizar camino más cortro a v
                H.bajar_prioridad(v, dist[v]) #Reacomodar a v en H
    return dist, padre
    
def floyd_warshall(A):
    n = len(A)
    D = [A[i][:] for i in range(n)]     #Sin intermediarios todavia
    P = [[None]*n for i in range(n)]
    for k in range(n):                  #Buscar atajos que pasan por k
        for u in range(n):
            for v in range(n):
                atajo = D[u][k] + D[k][v] #Distancia del camino u → k → v
                if atajo < D[u][v]:     #¿Es un atajo pasar por k?
                    D[u][v], P[u][v] = atajo, P[k][v] #Actualizar cam. más corto
    return D

#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.vecinos(u): marcar(c[u, v] - f[u, v]) #Marcar arcos salientes
        for v in H.vecinos(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, c, 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, a = camino_aum(G, H, s, t, f) #Camino de aumento y su valor
        if a == 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] += a  #¿Arista de avance? Añadir flujo
            else: f[v, u] -= a          #¿Arista de retroceso? Cancelar flujo

#Reducción del problema de emparejamiento a Flujo en redes
def emparejamiento(R):
    s, t = object(), object()           #Crear una red de flujo s-t
    G, c = Grafo(V = {s, t}, dirigido = True), dict() 
    for (x, y) in R:                    #Para cada pareja potencial (x, y)
        G.agregar_vertice(x)            #…se crea el camino s → x → y → t
        G.agregar_vertice(y)            #…con capacidad 1 en las aristas.
        for (u, v) in ((s, x), (x, y), (y, t)):
            G.agregar_arista(u, v)
            c[u, v] = 1
    f = ford_fulkerson(G, c, s, t)      #Flujo máximo = emparejamiento máximo
    return {(x, y) for (x, y) in R if f[x, y] > 0} #Devolver parejas selectas

estructuras.py

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

grafos.py

## Pequeña biblioteca para grafos, dirigidos o simples: su representación,
## manipulación básica, y dibujo
## 
## Autor: Mario Abarca (asma@uaem.mx)
## Fecha: 24 de septiembre de 2015

from collections import Set
from random import shuffle
from random import sample
from random import getrandbits
from math import sqrt
from math import sin
from math import cos
from math import pi
from itertools import combinations
from collections import namedtuple
from collections import Iterable
from tkinter import *
from tkinter import ttk

#---Estructuras de datos para representar un grafo-------------------------------
class VistaDeVertices(Set):             #Clase wrapper inmutable de conjunto
    __slots__ = '_S', '__weakref__'
    
    def __init__(V, S):                 #Constructor
        V._S = S

    def __len__(V):                     #Cardinalidad del conjunto
        return len(V._S)

    def __iter__(V):                    #Iterar sobre sus elementos
        yield from V._S

    def __contains__(V, u):             #Relación de pertenencia
        return u in V._S

class VistaDeAristas(Set):              #Conjunto inmutable de aristas
    __slots__ = '_G', '__weakref__'
    
    def __init__(E, G):                 #Constructor
        E._G = G
    
    def __len__(E):                     #Cantidad de aristas del grafo
        return E._G._tamano
    
    def __iter__(E):                    #Iterar sobre las aristas sin repetición
        G = E._G
        visitados = set()               #Conjunto de vértices visitados
        for u in G._vecinos:            #Para cada vértice:
            for v in G._vecinos[u]:     #Cada vecino suyo forma una arista
                if G._dirigido or v not in visitados: #…que puede estar repetida
                    yield (u, v)
            visitados.add(u)            #No repetir aristas que terminan en u
                    
    def __contains__(E, e):
        vecinos = E._G._vecinos
        u, v = e                        #Desempacamos los extremos de la arista
        return u in vecinos and v in vecinos[u] #Consultamos la adyacencia

class Grafo:
    __slots__ = '_dirigido', '_vecinos', '_tamano', '__weakref__'
    def __init__(G, V = None, E = None, dirigido = False):
        G._dirigido = bool(dirigido)    #¿El grafo es dirigido?
        G._vecinos = dict()             #Estructura de conjuntos de adyacencias
        G._tamano = 0                   #Número de aristas
        if V is not None:
            for u in V: G.agregar_vertice(u) #V es el conjunto de vértices
        if E is not None:
            for (u, v) in E: G.agregar_arista(u, v) #E es el conjunto de aristas

    def es_dirigido(G):                 #¿El grafo es dirigido?
        return G._dirigido

    def vecinos(G, u):                  #Conjunto de vecinos del vértice u
        return VistaDeVertices(G._vecinos[u])

    def vertices(G):                    #Conjunto de vértices del grafo
        return VistaDeVertices(G._vecinos)

    def aristas(G):                     #Conjunto de aristas del grafo
        return VistaDeAristas(G)

    def agregar_arista(G, u, v):        #Agregar arista (u, v) a G
        mensaje = '{} no está en el conjunto de vértices'
        for x in (u, v):                #Los extremos deben ser vértices de G
            if x not in G._vecinos: raise ValueError(mensaje.format(x))
        if u == v: raise ValueError('No se admiten lazos')
        if v not in G._vecinos[u]:
            G._vecinos[u].add(v)        #Hacmos v vecino de u
            if not G._dirigido: G._vecinos[v].add(u) #¿Es arista no dirigida?
            G._tamano += 1              #Actualizar tamaño del grafo
    
    def agregar_vertice(G, u):          #Agregar un vértice u al grafo G
        if u not in G._vecinos:         #Si u no es un vértice de G
            G._vecinos[u] = set()       #Lo agregamos sin vecinos

    def remover_arista(G, u, v):        #Quitar la arista (u, v) de G
        if v in G._vecinos[u]:
            G._vecinos[u].remove(v)     #v ya no es vecino de u
            if not G._dirigido: G._vecinos[v].remove(u) #¿Arista no dirigida?
            G._tamano -= 1              #Actualizar tamaño
        
    def remover_vertice(G, u):          #Quitar un vértice y aristas incidentes
        if u in G._vecinos:             
            if not G._dirigido:         #Quitar las aristas entrantes
                for v in G._vecinos[u]:
                    G._vecinos[v].remove(u)
            del G._vecinos[u]           #Quitar aristas salientes
            G._tamano -= G._vecinos[u]  #Actualizar tamaño

    def __repr__(G):
        V, E, d = set(G.vertices()), set(G.aristas()), G._dirigido
        args = []
        if V: args.append(repr(V))      #¿Requiere conjunto de vértices?
        if E: args.append(repr(E))      #¿Requiere conjunto de aristas?
        if not d: args.append('dirigido = False') #¿Es no dirigido?
        return 'Grafo({})'.format(', '.join(args)) #Así se representa

#---Manipulación de grafos------------------------------------------------------
def agregar_camino(G, *args):           #agregar_camino(G, x, y, z, w,...)
    if not args: return                 #¿Nada que agregar? Salir
    if len(args) == 1 and isinstance(args[0], str):
        camino = args[0].split()
    else: camino = args
    G.agregar_vertice(camino[0])
    for i in range(len(camino) - 1):
        G.agregar_vertice(camino[i + 1])
        G.agregar_arista(camino[i], camino[i + 1])

def revertir_grafo(G):
    V = G.vertices()
    E = ((v, u) for (u, v) in G.aristas())
    return Grafo(V, E, G.es_dirigido())

#---Obtención de grafos-----------------------------------------------------------
def _generar_vertices(n, alfabeto = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    alfabeto = tuple(alfabeto)
    i, w, m, ell = 0, [0], len(alfabeto), 1
    while i < n:
        yield ''.join(alfabeto[c] for c in reversed(w))
        j = 0
        while j < ell:
            w[j] += 1
            if w[j] >= m:
                w[j] = 0
            else: break
            j += 1
        if j >= ell:
            w.append(0)
            ell += 1
        i += 1
    
def grafo_aleatorio(n, m):
    assert 0 <= m <= (n*(n - 1))//2
    if isinstance(n, int):
        V = tuple(_generar_vertices(n))
    elif isinstance(n, Iterable): V = frozenset(n)
    return Grafo(V, sample(list(combinations(V, 2)), m))

def orientacion_aleatoria(G):
    E = ((u, v) if getrandbits(1) else (v, u) for (u, v) in G.aristas())
    return Grafo(G.vertices(), E, dirigido = True)

#---Representación de grafos en otros formatos----------------------------------
def imprimir_grafo(G):
    V = sorted(G.vertices())
    print('Vértices:')
    print('\t' + ', '.join(str(u) for u in V))
    print('Vecindades:')
    for u in V:
        vecinos = ', '.join(sorted(map(str, G.vecinos(u))))
        print('\t', u, ': ', vecinos, sep='')

def inversa(d):
    inv = dict()
    for x, y in d.items():
        if y not in inv:
            inv[y] = [x]
        else: inv[y].append(x)
    return inv
        
def grafo_a_conjuntos(G):
    V = sorted(G.vertices())
    E = sorted(tuple(sorted((u, v))) for (u, v) in G.aristas())
    return (V, E)

def grafo_a_matriz(G):
    v = sorted(grafo.vertices())
    E = grafo.aristas()
    I = range(len(v))
    return [[int((v[i], v[j]) in E) for j in I] for i in I]

def grafo_a_graphviz(G, w = None):
    V, E = grafo_a_conjuntos(G)
    lineas = []
    if G.es_dirigido():
        lineas.append('digraph {')
        e = '->'
    else:
        lineas.append('graph {')
        e = '--'
    for u in V:
        lineas.append('\t{};'.format(u))
    for (u, v) in E:
        lineas.append('\t{} {} {};'.format(u, e, v))
    lineas.append('}')
    return '\n'.join(lineas)

def grafo_a_tikz(G, w = None, disposicion = None):
    lineas = [r'\begin{tikzpicture}', '    %Vertices:']
    if disposicion is None: disposicion = disponer_por_energia(G)
    nodestr = r'    \node ({0}) at ({1[0]},{1[1]}) {{${0}$}};'
    lineas.extend(nodestr.format(u, disposicion[u]) for u in disposicion)
    drawstr = r'    \draw' + ('[->] ' if G.es_dirigido() else ' ')
    lineas.append('    %Aristas:')
    if w is not None:
        drawstr += '({}) to node[auto] {{${}$}} ({});'
        lineas.extend(drawstr.format(u, w[u, v], v) for (u, v) in G.aristas())
    else:
        drawstr += '({}) -- ({});'
        lineas.extend(drawstr.format(u,v) for (u, v) in G.aristas())
    lineas.append(r'\end{tikzpicture}')
    return '\n'.join(lineas)

#---Dibujo de grafos------------------------------------------------------------
class Punto(namedtuple('Punto', 'x y')):
    __slots__ = ()

    def __add__(p, q):
        if isinstance(p, Punto):
            return Punto(p.x + q.x, p.y + q.y)
        return NotImplemented

    def __radd__(p, q):
        if isinstance(p, Punto):
            return Punto(p.x + q.x, p.y + q.y)
        return NotImplemented

    def __sub__(p, q):
        if isinstance(p, Punto):
            return Punto(p.x - q.x, p.y - q.y)
        else: return NotImplemented

    def __mul__(p, c):
        if isinstance(c, (int, float)):
            return Punto(p.x*c, p.y*c)
        else: return NotImplemented

    def __rmul__(p, c):
        if isinstance(c, (int, float)):
            return Punto(p.x*c, p.y*c)
        else: return NotImplemented

    def __truediv__(p, c):
        if isinstance(c, (int, float)):
            return Punto(p.x/c, p.y/c)
        else: return NotImplemented

    def __neg__(p):
        return Punto(-p.x, -p.y)
    
    def __abs__(p):
        return sqrt(p.x*p.x + p.y*p.y)

    def __complex__(p):
        return complex(p.x, p.y)

    def __round__(p, n):
        return Point(round(p.x, n), round(p.y, n))

    @staticmethod
    def polar(dist, angulo):
        return Punto(dist*cos(angulo), dist*sin(angulo))

    def normalizar(mi):
        return mi/abs(mi)
        
def disponer_por_energia(grafo, iteraciones = 50, temperatura = 1.0):
    vertices = list(grafo.vertices())
    shuffle(vertices)
    aristas = grafo.aristas()
    n = len(vertices)
    pos = {u:Punto.polar(0.5, (2*pi)*(k/n)) for (k, u) in enumerate(vertices)}
    enfriar = temperatura/iteraciones
    for i in range(iteraciones):
        desp = {v:Punto(0.0, 0.0) for v in vertices}
        for (u, v) in combinations(vertices, 2):
                q = pos[v] - pos[u]
                dist2 = q.x**2 + q.y**2
                if dist2 < 4:
                    vec_repulsion = q/dist2
                    desp[v] += vec_repulsion
                    desp[u] -= vec_repulsion
                if (u, v) in aristas or (v, u) in aristas:
                    vec_atraccion = abs(q)*q
                    desp[u] += vec_atraccion
                    desp[v] -= vec_atraccion
        for v in vertices:
            dist_desp = abs(desp[v])
            if dist_desp == 0.0: continue
            pos[v] += (desp[v]/dist_desp)*min(dist_desp, temperatura)
        temperatura -= enfriar
    return pos

def dibujar_grafo(grafo, letra = 'times', tam = 12, borde = 8, grosor = 1,
                  disposicion = None):
    def redraw(event):
        canvas.delete('all')
        k = min((event.width - blft - brgt)/w,
                (event.height - btop - bbot)/h)
        p = {u:k*pos[u] + b for u in V}
        for (u, v) in E:
            x1, y1 = p[u]
            x2, y2 = p[v]
            canvas.create_line(x1, y1, x2, y2, smooth = 1, width = grosor)
            if grafo.es_dirigido():
                arg = (p[v] - p[u]).normalizar() #Vector v --> u
                ort = Punto(arg.y, -arg.x) #Vector ortogonal
                x0, y0 = ti0 = p[u] + rad[v]*arg
                x1, y1 = ti0 + (0.5*tam)*arg + (0.25*tam)*ort
                x2, y2 = ti0 + (0.25*tam)*arg
                x3, y3 = ti0 + (0.5*tam)*arg - (0.25*tam)*ort
                canvas.create_polygon(x0, y0, x1, y1, x2, y2, x3, y3,
                                      fill = 'black', outline = '')
                
        for u in V:
            x, y = p[u]
            canvas.create_oval(x - rad[u], y - rad[u],
                               x + rad[u], y + rad[u],
                               fill = 'lightgray', outline = '')
            canvas.create_text(x, y, text = u,
                               font = (letra, tam))

    V, E = grafo.vertices(), grafo.aristas()
    if not V: raise RuntimeError('*** Dibujo vacio.')
    pos = disposicion if disposicion else disponer_por_energia(grafo)
    ilft = min(V, key = lambda u: pos[u].x)
    irgt = max(V, key = lambda u: pos[u].x)
    itop = min(V, key = lambda u: pos[u].y)
    ibot = max(V, key = lambda u: pos[u].y)

    d = Punto(pos[ilft].x, pos[itop].y)
    for u in V: pos[u] -= d
    
    w = pos[irgt].x
    h = pos[ibot].y
    
    root = Tk()
    root.title('Dibujo')
    root.columnconfigure(0, weight = 1)
    root.rowconfigure(0, weight = 1)
    canvas = Canvas(root, background = 'white')

    rad = {u:0.0 for u in V}
    aux = canvas.create_text(0, 0, fill = 'white', font = (letra, tam))
    for u in grafo.vertices():
        canvas.itemconfig(aux, text = u)
        x1, y1, x2, y2 = canvas.bbox(aux)
        rad[u] = 0.5*sqrt((x2 - x1)**2 + (y2 - y1)**2)
    canvas.delete(aux)
    del aux

    blft, btop, brgt, bbot = (rad[u] + borde \
                              for u in (ilft, itop, irgt, ibot))
    b = Punto(blft, btop)

    k = 5*tam
    canvas.config(width = k*w + blft + brgt, height = k*h + btop + bbot)
    
    canvas.grid(column = 0, row = 0, sticky='NWES')
    canvas.bind('<Configure>', redraw)
    root.bind('<Return>', lambda e: root.destroy())
    root.mainloop()
        

ordenamiento.py

from random import randint
from random import shuffle

def esta_ordenado(s):                   #¿Está ordenada la lista s?
    for i in range(len(s) - 1):         
        if s[i] > s[i + 1]: return False #Si hay un par desordenado, no
    return True                         #En otro caso, sí.

def bogo_sort(s):                       #Bogo sort: mal ejemplo de ordenamiento
    while not esta_ordenado(s):         #Mientras la lista no esté ordenada:
        shuffle(s)                      #…reordena de forma aleatoria

def ordenamiento_por_insercion(s):
    for i in range(1, len(s)):          #Cada s[i]…
        j = i
        while j > 0 and s[j] < s[j - 1]:    #…se inserta en orden en s[0:i]
            s[j], s[j - 1] = s[j - 1], s[j] #…recorriéndose una casilla a la vez
            j = j - 1

def ordenamiento_por_seleccion(s):
    n = len(s)                          
    for i in range(n):                  #Para cada i = 0,…,n
        m = i                           #…buscamos el mínimo de s[i:n]
        for j in range(i + 1, n):
            if s[j] < s[m]: m = j       #…que debe de estar en algún s[m]
        s[i], s[m] = s[m], s[i]         #…y lo intercambiamos con s[i]

def ordenamiento_por_mezcla(s):
    n = len(s)
    if n <= 1: return None              #Una lista pequeña no necesita ordenarse
    p, q = s[:n//2], s[n//2:]           #Dividimos la lista en dos mitades
    ordenamiento_por_mezcla(p)          #…y ordenamos cada mitad recursivamente
    ordenamiento_por_mezcla(q)
    k, i, j = 0, 0, 0                   #Mezclamos las dos mitades:
    while i < len(p) and j < len(q):    
        if p[i] <= q[j]:                #…eligiendo el elemento menor de p y q
            s[k] = p[i]; i += 1         #…y colocándolo en s
        else: s[k] = q[j]; j += 1
        k += 1
    while i < len(p): s[k] = p[i]; i += 1; k += 1 #Vaciamos el resto de p
    while j < len(q): s[k] = q[j]; j += 1; k += 1 #…o de q

def particionar(s, a, b):               #Subrutina de ordenamiento_rapido
    q = randint(a, b)                   #Elegimos algún s[q] como pivote
    s[q], s[b] = s[b], s[q]             #Lo pasamos al final de s[a:b + 1]
    i = a
    for j in range(a, b):               #Mantenemos el siguiente invariante:
        if s[j] <= s[b]:                # s[k] <= pivote para k = a,…,i - 1 y
            s[i], s[j] = s[j], s[i]     # s[k] > pivote para k = i,…,b - 1
            i += 1
    s[b], s[i] = s[i], s[b]             #Colocamos el pivote en su pos. correcta
    return i                            #…y devolvemos su posición final

def ordenamiento_rapido(s, a = None, b = None):
    if a == b == None:
        (a, b) = (0, len(s) - 1)        #Se desea ordenar s[a:b+1]
    if b - a > 1:                       #…sólo cuando b - a > 1, claro está
        q = particionar(s, a, b)        #Primero biparticionamos s[a:b+1]
        ordenamiento_rapido(s, a, q - 1) #…y ordenamos cada parte recursivamente
        ordenamiento_rapido(s, q + 1, b)

def flotar(H, i):                       #Flotar el nodo i en el montículo H
    while True:
        padre = (i - 1)//2 if i > 0 else 0 #La posición del padre de i
        if H[padre] <= H[i]: break      #Si su padre es menor, terminamos
        H[padre], H[i] = H[i], H[padre] #Si no, los intercambiamos
        i = padre                       #…y repetimos

def hundir(H, i):                       #Hundir el nodo i en el montículo H
    n = len(H)
    while True:
        izquierdo, derecho = 2*i + 1, 2*i + 2 #Posiciones de los hijos
        k = i                           #El mínimo del nodo actual y sus hijos
        if izquierdo < n and H[izquierdo] < H[k]: #¿El hijo izq. es menor?
            k = izquierdo
        if derecho < n and H[derecho] < H[k]: #¿El hijo derecho es menor?
            k = derecho
        if k == i: break                #¿Nodo actual es el menor?
        H[i], H[k] = H[k], H[i]         #Si no, intercambiamos posiciones
        i = k                           #…y repetimos

def extraer_minimo(H):                  #Extraer elemento mínimo de un montículo
    n = len(H) - 1
    H[0], H[n] = H[n], H[0]             #Intercambiar la raiz con el último nodo
    x = H.pop()                         #Sacar el último nodo
    hundir(H, 0)                        #Hundir la nueva raíz
    return x

def insertar(H, x):                     #Insertar un elemento al montículo
    H.append(x)                         #Insertar x en el último nodo
    flotar(H, len(H) - 1)               #Flotarlo a su posición correcta

def ordenamiento_por_monticulos(s):
    H = []                              #Crear un montículo vacío
    for x in s: insertar(H, x)          #Meter todos los elementos al montículo
    for i in range(len(s)):
        s[i] = extraer_minimo(H)        #…y sacarlos en el orden correcto

def busqueda_lineal(s, x):
    for i in range(len(s)):             #Ver de uno en uno los elementos de s
        if x == s[i]: return i          #…a ver si uno de ellos es el buscado
    raise ValueError('{} no está en la lista'.format(x))

def busqueda_binaria(s, x):             #Buscar x en la lista ordenada s
    a, b = 0, len(s) - 1                #Límites superior e inferior
    while b - a >= 0:
        k = (a + b)//2                  #Elegir el punto medio de los límites
        if s[k] == x:                   #¿Lo encontramos?
            return k
        elif x < s[k]:                  #¿Está antes del punto medio?
            b = k - 1
        else: a = k + 1                 #¿Está después?
    raise ValueError('{} no está en la lista'.format(x))

def mediana(s, i = None):               #Buscar el i-ésimo elemento más pequeño
    if i == None: i = (len(s) - 1)//2   #Por defecto es la mediana
    a, b = 0, len(s) - 1                
    while True:
        k = particionar(s, a, b)        #s[i] ≤ s[k] ≤ s[j] para i < k < j
        if k == i:                      #¿La encontramos?
            return s[i]
        elif i < k:                     #¿Está antes de s[k]?
            b = k - 1
        else: a = k + 1                 #¿Está después?

if __name__ == '__main__':
    for algoritmo in (ordenamiento_por_insercion, ordenamiento_por_mezcla,
                      ordenamiento_por_seleccion, ordenamiento_rapido,
                      ordenamiento_por_monticulos, bogo_sort):
        print('----' + algoritmo.__name__ + '-'*(76 - len(algoritmo.__name__)))
        L = [randint(10, 99) for k in range(10)]
        shuffle(L)
        print('Entrada:', L)
        algoritmo(L)
        print('Salida: ', L)

recorridos.py

from grafos import Grafo
from collections import namedtuple
from collections import defaultdict
from estructuras import Cola

def componentes_conexas(G):
    def visita(v):                      #Subrutina de recorrido en profundidad
        cc[v] = c
        for u in G.vecinos(v):
            if u not in cc:             #u no visitado <=> u no tiene componente
                visita(u)
    cc = dict()                         #Etiqueta de componente conexa
    c = 0
    for v in G.vertices():
        if v not in cc:
            visita(v)
            c += 1
    return cc

def puntos_de_separacion(G, impre = True):
    def visita(u):
        #Descubrimiento (de la raíz hacia las hojas):
        nonlocal t
        d[u] = t                        #u es descubierto al tiempo t
        t += 1

        #Exploración:
        for v in G.vecinos(u):          #Para cada vecino v de u:
            if v not in d:              #¿v no ha sido descubierto?
                padre[v] = u            #Crear arista u -> v en el árbol
                visita(v)               #Adentrarse en v

        #Finalización (de las hojas hacia la raíz):
        tag[u] = d[u]                   #Aquí se calcula:
        hijos = 0                       #               ⎧d[u]
        for v in G.vecinos(u):          #• tag[u] = min ⎨d[v] : v ancestro de u
            if v == padre[u]: continue  #               ⎩tag[v] : v hijo de u
            if padre[v] != u:           #• hijos = no. de hijos de u
                tag[u] = min(tag[u], d[v]) #tag[u] == d[v] si v es el punto más…
            else:                       #alto que se puede alcanzar bajando por…
                hijos += 1              #el árbol y subiendo por una sola…
                tag[u] = min(tag[u], tag[v]) #arista de retroceso.

        #Usando tag[u] determinar si u o su padre v es un punto de separación:
        v = padre[u]
        if v is None:                   #¿u es una raíz?
            if hijos > 1: separadores.add(u) #Si separa dos ramas, u es un p.s.
        elif padre[v] is not None:      #Si v no es una raiz:
            if d[v] == tag[u]:          #¿v es el punto más alto…
                separadores.add(v)      #del bloque? Es un p.s.
            if tag[u] == d[u]:          #¿v─u es un puente?
                separadores.add(v)      #Entonces v es un p.s.

    separadores = set()                 #Los pp.ss. serán hallados en visita(u)
    padre = dict()
    tag = dict()
    d = dict()
    t = 0
    for r in G.vertices():              #Para cada vértice r:
        if r not in d:                  #Si r no ha sido descubierto…
            padre[r] = None             #entonces r es una raíz…
            visita(r)                   #y hay que explorarla
    return separadores                  #Devolver los pp.ss. hallados

def postorden(G):
    def visita(u):                      #Subrutina del recorrido en profundidad
        visitados.add(u)
        for v in G.vecinos(u):
            if v not in visitados:
                visita(v)
        lista.append(u)
    lista, visitados = [], set()
    for u in G.vertices():
        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.vertices() for v in G.vecinos(u)):
        raise ValueError('No existe orden topológico para este grafo.')
    
    return lista

def componentes_fuertemente_conexas(G):
    def visita(v):                      #Subrutina de recorrido en profundidad
        cfc[v] = componente_actual
        for u in G.vecinos(v):
            if u not in cfc:            #u no visitado == no tiene componente
                visita(u)
    V = postorden(revertir_grafo(G))     #Calcular posorden en el grafo volteado 
    V.reverse()                         #Invertir el orden
    cfc = dict()                        #Etiqueta de comp. fuertemente conexa
    componente_actual = 0
    for v in V:                         #Posorden invertido en el grafo volteado
        if v not in cfc:
            visita(v)
            componente_actual += 1
    return cfc

def recorrido_en_amplitud(G, s, inf = float('inf')):
    dist = dict()
    dist[s] = 0
    padre = {s:None}
    Q = Cola([s])
    while Q:
        u = Q.desencolar()
        for v in G.vecinos(u):
            if v not in dist:
                padre[v] = u
                dist[v] = dist[u] + 1
                Q.encolar(v)
    return dist, padre

def bicolorear(G):
    color = dict()
    for r in G.vertices():
        if r not in color:
            padre = {r:None}
            color[r] = 0
            Q = Cola([r])
            while Q:
                u = Q.desencolar()
                for v in G.vecinos(u):
                    if v not in color:
                        padre[v] = u
                        color[v] = (color[u] + 1) % 2
                        Q.encolar(v)
                    elif color[u] == color[v]:
                        raise RuntimeError('Grafo no bicoloreable.')
    return color, padre

if __name__ == '__main__':
    from graflib import *
    ## Componentes conexas
    G = grafo_aleatorio(10, 7)
    imprimir_grafo(G)
    cc = inversa(componentes_conexas(G))
    print('Componentes conexas:')
    for c in cc.values():
        print(', '.join(sorted(c)))
    dibujar_grafo(G)

    ## Puntos de separación
    G = grafo_aleatorio(10, 12)
    imprimir_grafo(G)
    print('Puntos de separación:', ', '.join(puntos_de_separacion(G)))
    dibujar_grafo(G)

    ## Ordenamiento topologico y componentes fuertemente conexas
    G = orientacion_aleatoria(grafo_aleatorio(10, 11))
    imprimir_grafo(G)
    try:
        L = ordenamiento_topologico(G)
    except ValueError as e:
        L = False
        print(e.args[0])
    if L: print('Ordenamiento topologico:', ', '.join(L))
    cfc = inversa(componentes_fuertemente_conexas(G))
    print('Componentes fuertemente conexas:')
    for c in cfc.values():
        print(', '.join(sorted(c)))
    dibujar_grafo(G)

    ## Distancias en grafos
    inf = float('inf')
    G = grafo_aleatorio(10, 11)
    imprimir_grafo(G)
    dist, padre = recorrido_en_amplitud(G, 'A')
    print('Distancias hacia A:')
    for u in sorted(sorted(G.vertices()), key = lambda u: dist.get(u, inf)):
        print(u, ':', dist.get(u, inf))
    dibujar_grafo(G)