5

Estoy implementando en Python el algoritmo de Floyd-Warshall para hallar caminos mínimos en un grafo. He tenido un problema escribiendo una función recursiva para imprimir dicho camino mínimo utilizando la matriz de predecesores (del inglés predecessor matrix):

def print_path(p_ij, ii, jj):
     """Recursive function to reconstruct the shortest path from i to j.

     """
     if ii != jj:
        print_path(p_ij, ii, p_ij[ii, jj])

     print(jj)

Quería hacerlo con generadores, pero me he topado con algo curioso. Esta forma no funciona, porque solo imprime el último número:

def build_path(p_ij, ii, jj):
    """Recursive function to reconstruct the shortest path from i to j.

    """
    if ii != jj:
        build_path(p_ij, ii, p_ij[ii, jj])

    yield jj

def print_path(p_ij, ii, jj):
    for jj in build_path(p_ij, ii, jj):
        print(jj)

Y esta otra forma (solo cambio build_path) me devuelve una lista con un número y un generador, totalmente inútil:

def build_path(p_ij, ii, jj):
    """Recursive function to reconstruct the shortest path from i to j.

    """
    if ii != jj:
        yield build_path(p_ij, ii, p_ij[ii, jj])  # <-- Añado un yield

    yield jj

¿Cómo puedo conseguir algo equivalente a la primera versión usando generadores?

5
  • Casi quemo cerebro pensando que estas haciendo "sorting recursivo", pero creo que es "shortest" en vez de "sortest"
    – César
    el 18 dic. 2015 a las 13:50
  • 1
    Me da que te estaba pasando lo mismo que a mi con los generadores de caliair. El que te imprima solo el último número es por que va mutando el objeto que te devuelve, no creando objetos nuevos, y al final dicho objeto queda con el último estado del generador.. Tampoco estaría de más que explicaras que es p_ij, ii, jj, o usar nombres más explicativos.
    – tinproject
    el 19 dic. 2015 a las 18:31
  • Tienes razón @tinproject, no quería «ensuciar» la pregunta pero creo que me he quedado un poco corto de información y falta contesto. Hoy la completo. el 20 dic. 2015 a las 15:22
  • Hecho @tinproject, se trataba de una parte del algoritmo de Floyd-Warshall (hay poca literatura en español, desgraciadamente). Creo que la pregunta se entiende mejor ahora. el 21 dic. 2015 a las 6:47
  • 1
    El problema esta en que con yield build_path(p_ij, ii, p_ij[ii, jj]) estas devolviendo un generador de generadores, no un generador de objetos del tipo de jj. Con yield from 'delega' el generador y no crea generadores de generadores... En resumen, aunque Python es dinámico, los tipos importan.
    – tinproject
    el 21 dic. 2015 a las 18:53

2 respuestas 2

1

En recursión todo es de atrás hacia adelante:

def build_path(matrix, i=0, j=0):
    """Recursive function to reconstruct the sortest path from i to j."""
    try:
        yield matrix[i][j]
        j += 1
        yield from build_path(matrix, i, j) if j < len(matrix[i]) else\
                build_path(matrix, i + 1)
    except IndexError:
        pass

def print_path(matrix):
    for jj in build_path(matrix):
        print(jj)

test_matrix = (
    (1, 2, 3),
    (4, 5, 6),
    (7, 8, 9)
)
print_path(test_matrix)
4
  • Precisamente la clave está en yield from, voy a poner una solución más simple :) ¡Gracias! el 18 dic. 2015 a las 15:07
  • 1
    En tu codigo no consegui entender porque usas un diccionario o mejor dicho porque pasas una tupla como clave a p_js p_ij[ii, jj] De Cualquier modo encontre una forma mas compresa de escribir el ejemplo que te pase el 18 dic. 2015 a las 15:33
  • Porque es un array de NumPy, olvidé mencionarlo :/ el 18 dic. 2015 a las 15:45
  • jajaja ahi va. Muchas gracias por sacarme esa duda. Abrazo de pato el 18 dic. 2015 a las 15:46
1

Ricardo ha dado la clave con su respuesta, que es utilizar yield from, añadido en Python 3.3:

La PEP 380 añade la expresión yield from, que permite a un generador delegar parte de su funcionalidad en otro generador. Esto posibilita factorizar una sección del código que contenga yield o ponerlo en un nuevo generador.

Así que la solución final es tan simple como esto:

def build_path(p_ij, ii, jj):
    """Recursive function to reconstruct the shortest path from i to j.

    """
    if ii != jj:
        yield from build_path(p_ij, ii, p_ij[ii, jj])  # ¡Ahora sí!

    yield jj

En versiones a Python anteriores, se puede seguir esta sintaxis, como comenta @Darkhogg:

def build_path(p_ij, ii, jj):
    """Recursive function to reconstruct the sortest path from i to j.

    """
    if ii != jj:
        for ee in build_path(p_ij, ii, p_ij[ii, jj]):
            yield ee

    yield jj
3
  • 1
    en ausencia de yield from x siempre puedes usar for e in x: yield e que viene a ser lo mismo.
    – Darkhogg
    el 18 dic. 2015 a las 19:21
  • Añadido a la respuesta, ¡gracias! el 21 dic. 2015 a las 7:58
  • 1
    En general no es 100% equivalente, como se puede comprobar en el texto del PEP 380, particularmente porque yield from puede devolver un resultado y este sistema no.
    – Darkhogg
    el 21 dic. 2015 a las 9:18

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.