Python Patterns – Implementing Graphs | Python.org

Notas de cambio: 22/2/98, 3/2/98, 12/4/00: Esta versión de este ensayo corrige varios errores en el código. 6/10/19: Retracción defind_shortest_pathcomo «casi óptimo». 8/11/19: Se corrige el uso accidental defind_graph()en lugar defind_path()

Copyright (c) 1998, 2000, 2003, 2019 Python Software Foundation.All rights reserved.Licensed under the PSF license.

Los grafos son redes formadas por nodos conectados por aristas o arcos. En los grafos dirigidos, las conexiones entre nodos tienen una dirección y se llaman arcos; en los grafos no dirigidos, las conexiones no tienen dirección y se llaman aristas. Hablamos principalmente de los grafos dirigidos. Los algoritmos en los grafos incluyen la búsqueda de un camino entre dos nodos, la búsqueda del camino más corto entre dos nodos, la determinación de ciclos en el grafo (un ciclo es un camino no vacío desde un nodo hasta sí mismo), la búsqueda de un camino que llegue a todos los nodos (el famoso «problema del viajante de comercio»), etc. A veces, los nodos o arcos del grafo tienen pesos o costes asociados, y nos interesa encontrar el camino más barato.

Existe una considerable literatura sobre algoritmos de grafos, que son una parte importante de las matemáticas discretas. Los grafos también tienen mucho uso práctico en los algoritmos informáticos. Se pueden encontrar ejemplos obvios en la gestión de redes, pero abundan los ejemplos en muchas otras áreas. Por ejemplo, las relaciones entre el que llama y el que recibe en un programa de ordenador pueden verse como un grafo (donde los ciclos indican la recursividad, y los nodos inalcanzables representan el código muerto).

Pocos lenguajes de programación proporcionan soporte directo para los grafos como tipo de datos, y Python no es una excepción. Sin embargo, los gráficos se construyen fácilmente a partir de listas y diccionarios. Por ejemplo, aquí hay un gráfico simple (no puedo usar dibujos en estas columnas, así que escribo los arcos del gráfico):

 A -> B A -> C B -> C B -> D C -> D D -> C E -> F F -> C

Este gráfico tiene seis nodos (A-F) y ocho arcos. Se puede representar mediante la siguiente estructura de datos de Python:

 graph = {'A': , 'B': , 'C': , 'D': , 'E': , 'F': }

Es un diccionario cuyas claves son los nodos del gráfico. Para cada clave, el valor correspondiente es una lista que contiene los nodos que están conectados por un arco directo desde este nodo. Esto es lo más simple que se puede hacer (aún más simple, los nodos podrían ser representados por números en lugar de nombres, pero los nombres son más convenientes y se pueden hacer fácilmente para llevar más información, como los nombres de las ciudades).

Escribamos una función simple para determinar una ruta entre dos nodos. Toma un gráfico y los nodos iniciales y finales como argumentos. Devuelve una lista de nodos (incluyendo los nodos iniciales y finales) que componen la ruta.Cuando no se encuentra ninguna ruta, devuelve None. El mismo nodo no aparecerá más de una vez en el camino devuelto (es decir, no contendrá ciclos). Elalgoritmo utiliza una técnica importante llamada «backtracking»: intenta cada posibilidad por turnos hasta que encuentra una solución.

 def find_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None for node in graph: if node not in path: newpath = find_path(graph, node, end, path) if newpath: return newpath return None

Un ejemplo de ejecución (utilizando el gráfico anterior):

 >>> find_path(graph, 'A', 'D') >>>

La segunda declaración «if» es necesaria sólo en caso de que haya nodos que figuran como puntos finales de los arcos, pero que no tienen arcos de salida, y no figuran en el gráfico en absoluto. Estos nodos también podrían estar contenidos en el gráfico, con una lista vacía de arcos de salida, pero a veces es más conveniente no requerir esto.

Nótese que mientras el usuario llama a find_path() con tres argumentos, éste se llama a sí mismo con un cuarto argumento: el camino que ya ha sido recorrido.El valor por defecto de este argumento es la lista vacía, », lo que significa que aún no se ha recorrido ningún nodo. Este argumento se utiliza para evitar ciclos (el primer ‘if’ dentro del bucle ‘for’). El argumento ‘path’ no se modifica: la asignación «path = path + » crea una nueva lista. Si hubiéramos escrito «path.append(start)» en su lugar, habríamos modificado la variable’path’ en el llamador, con resultados desastrosos. (Usando tuplas, podríamos haber estado seguros de que esto no ocurriría, a costa de tener que escribir «ruta = ruta + (inicio,)» ya que «(inicio)» no es una tupla singleton — es sólo una expresión entre paréntesis.)

Es sencillo cambiar esta función para que devuelva una lista de todos los caminos (sin ciclos) en lugar del primer camino que encuentre:

 def find_all_paths(graph, start, end, path=): path = path + if start == end: return if not graph.has_key(start): return paths = for node in graph: if node not in path: newpaths = find_all_paths(graph, node, end, path) for newpath in newpaths: paths.append(newpath) return paths

Una ejecución de ejemplo:

 >>> find_all_paths(graph, 'A', 'D') , , ] >>>

Otra variante encuentra el camino más corto:

 def find_shortest_path(graph, start, end, path=): path = path + if start == end: return path if not graph.has_key(start): return None shortest = None for node in graph: if node not in path: newpath = find_shortest_path(graph, node, end, path) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest

Ejecución de ejemplo:

 >>> find_shortest_path(graph, 'A', 'D') >>>

Estas funciones son de lo más sencillas. Sin embargo, son casi óptimas (para el código escrito en Python). En otra columna de Python Patterns, intentaré analizar su velocidad de ejecución y mejorar su rendimiento, a costa de más código.

Actualización: Eryk Kopczyński ha señalado que estas funciones no son óptimas. Por el contrario, «este programa se ejecuta en tiempo exponencial, mientras que find_shortest_path se puede hacer en tiempo lineal utilizando BFS . Además, un BFS lineal es más sencillo:»

 # Code by Eryk Kopczyński def find_shortest_path(graph, start, end): dist = {start: } q = deque(start) while len(q): at = q.popleft() for next in graph: if next not in dist: dist = , next] q.append(next) return dist.get(end)

Nótese que esto devuelve el camino en un formato extraño, por ejemplo,, 'B'], 'D']. En particular,len(find_shortest_path(graph, 'A', 'D'))dará la respuesta incorrecta (2, porque la lista exterior es de longitud 2). Esto se debe a que la adición se realiza como, next]en lugar dedist+. El segundo método utilizaría tiempo cuadrático y memoria, pero aún así debería estar bien para los gráficos relativamente pequeños; de lo contrario, es fácil convertir la lista en el formato correcto.

Otra variación sería añadir más abstracción de datos: crear una clase para representar los gráficos, cuyos métodos implementan los diversos algoritmos. Aunque esto apela al deseo de una programación estructurada, no hace que el código sea más eficiente (al contrario). Lo que sí facilita es añadir diversas etiquetas a los nodos o arcos y añadir algoritmos que tengan en cuenta esas etiquetas (por ejemplo, para encontrar la ruta más corta entre dos ciudades en un mapa). Esto también será objeto de otra columna.