Algoritmo para saber si existe un camino posible

Cuando queremos comprobar si existe un camino posible entre 2 puntos, lo que queremos hacer es trabajar con grafos. Además, necesitaremos un algoritmo encargado de recorrer todos los caminos, de una forma relativamente eficiente, y darnos una respuesta. Para ellos podemos utilizar el algoritmo en anchura (BFS - Breadth First Search).

Antes de resolver el problema debemos ponernos en contexto. Un grafo es un conjunto de nodos (o vértices) que están conectados entre sí. Cada nodo puede tener 0 o más nodos vecinos.

Algunos ejemplos de grafos son:

• Mapas, para encontrar la ruta más óptima.
• Correcciones de palabras (“pulgo” no existe, ¿cuales sería la palabra más cercana? Tal vez”pulga” o “pulpo”)
• Sistemas de rutas (como trenes, vuelos, carreteras…), para encontrar el camino con menos paradas.
• Sugerencias de productos
• Relaciones entre personas

Y en todos estos casos necesitamos comprobar si podemos ir del punto A al punto B. Lo primero que nos viene a la cabeza es un GPS, que al indicar un origen y un destino primero debe comprobar si existe un camino posible.

En el artículo vamos a utilizar de ejemplo una red de amigos. Cada nodo es una persona y las aristas son las relaciones de amistad entre ellos.

Las flechas indican la dirección de las relaciones. Por ejemplo, “me” (o yo) soy amigo de “bob”, “claire” y “alice”. Mientras que “alice” es amiga de “peggy”. “bob”, en cambio, es amigo de “anuj” y “peggy”. Y así sucesivamente.

El algoritmo de búsqueda en anchura (BFS) se utiliza para recorrer un grafo y encontrar el camino más corto entre 2 nodos. Por supuesto si no hay esfuerzos entre ellos (en las conclusiones te doy más detalles). Además, indirectamente, nos indica si el camino es posible. Esto es lo que realmente nos interesa. Aprenderemos a implementarlo, pero primero necesitamos entender cómo se representa un grafo en Python.

El grafo se puede representar como un diccionario de Python (hash table). Cada nodo es una clave en el diccionario y los valores son una lista de nodos vecinos.

# Graph
friends = {}
friends["me"] = ["bob", "claire", "alice"]
friends["alice"] = ["peggy"]
friends["peggy"] = []
friends["bob"] = ["anuj", "peggy"]
friends["anuj"] = []
friends["claire"] = ["jonny", "thom"]
friends["thom"] = []
friends["jonny"] = []

Ahora que tenemos el grafo, vamos a implementar el algoritmo de búsqueda en anchura.

Los pasos a seguir son los siguientes:

1. Si es la primera vez que se ejecuta la función, añadir la persona de origen a la lista de consulta. Si una query está vacía, significa que no hay más amigos que consultar, por ello añadimos la persona de origen para que inicie la búsqueda con un nodo (persona).
2. Inicializar una lista de consulta (query) con los amigos de la persona de origen.
3. Comprobar si la persona actual es el objetivo que estamos buscando.
4. Si no es el objetivo, añadir los amigos de la persona actual a la lista de consulta.
5. Repetir los pasos 2 y 3 hasta que encontremos el objetivo o no haya más amigos que consultar.

El objetivo del ejemplo será encontrar a un amigo cuyo nombre contenga la letra determinada. Por ejemplo, comprobar si existe una relación entre yo (“me”) y un amigo cuyo nombre contenga la letra “b” (por ejemplo, “Bob”).

La implementación sería de la siguiente forma:

def search_query(
    graph: dict,
    person: str,
    target: str,
    query: list or None = None,
    verifies: list or None = None,
    first_run: bool = True,
) -> str or None:
    """
    Search for a target in a graph
    """
    # Fix anti-pattern: Using a mutable default value as an argument
    # Source: https://docs.quantifiedcode.com/python-anti-patterns/correctness/mutable_default_value_as_argument.html
    if query is None:
        query = []
    if verifies is None:
        verifies = []
    # If first run, add person to query
    if first_run:
        query = [person]
    # Add friends from person to query
    if person and person not in verifies:
        query = query + graph[person]
    # Pop a person off the query
    query_without_person = query[1:]
    # Check if person is a target and person is verifies. If so, return person
    if person and target.lower() in person.lower() and person not in verifies:
        return person
    # If query is empty, return None because no more neighbours
    if len(query) == 0:
        return None
    # Add new neighbour
    next_person = query_without_person[0] if len(query_without_person) > 0 else None
    return search_query(
        graph=graph,
        person=next_person,
        target=target,
        query=query_without_person,
        verifies=verifies + [person],
        first_run=False,
    )

El algoritmo es una función recursiva que recibe el grafo, la persona de origen y el objetivo que estamos buscando.

result = search_query(friends, "me", "b")
print(result)  # bob

En el caso que no exista un camino posible, la función devolverá None.

result = search_query(friends, "me", "k")
print(result)  # None

¿Qué pasa si buscamos un amigo con la letra “o”? Hay varios amigos que cumplen con esa condición (“bob”, “jonny”, “thom”). ¿Cuál de ellos devolverá la función? El más cercano: Bob. El algoritmo buscará siempre el camino con menos paos.

result = search_query(friends, "me", "o")
print(result)  # bob

El código completo es el siguiente:

# Graph
friends = {}
friends["me"] = ["bob", "claire", "alice"]
friends["alice"] = ["peggy"]
friends["peggy"] = []
friends["bob"] = ["anuj", "peggy"]
friends["anuj"] = []
friends["claire"] = ["jonny", "thom"]
friends["thom"] = []
friends["jonny"] = []


def search_query(
    graph: dict,
    person: str,
    target: str,
    query: list or None = None,
    verifies: list or None = None,
    first_run: bool = True,
) -> str or None:
    """
    Search for a target in a graph
    """
    # Fix anti-pattern: Using a mutable default value as an argument
    # Source: https://docs.quantifiedcode.com/python-anti-patterns/correctness/mutable_default_value_as_argument.html
    if query is None:
        query = []
    if verifies is None:
        verifies = []
    # If first run, add person to query
    if first_run:
        query = [person]
    # Add friends from person to query
    if person and person not in verifies:
        query = query + graph[person]
    # Pop a person off the query
    query_without_person = query[1:]
    # Check if person is a target and person is verifies. If so, return person
    if person and target.lower() in person.lower() and person not in verifies:
        return person
    # If query is empty, return None because no more neighbours
    if len(query) == 0:
        return None
    # Add new neighbour
    next_person = query_without_person[0] if len(query_without_person) > 0 else None
    return search_query(
        graph=graph,
        person=next_person,
        target=target,
        query=query_without_person,
        verifies=verifies + [person],
        first_run=False,
    )


# Some test cases
assert search_query(friends, "me", "y") == "jonny"
assert search_query(friends, "me", "h") == "thom"
assert search_query(friends, "me", "m") == "me"
assert search_query(friends, "me", "k") == None

Si prestas atención se han incorporado varias comprobaciones para evitar bucles infinitos y acelerar la búsqueda. Por ejemplo, si una persona ya ha sido verificada, no se vuelve a comprobar. Tampoco nos comprobamos a nosotros mismos. O si no hay más amigos que consultar, devolvemos None.

¡Y eso es todo! Ahora tienes un algoritmo para saber si existe un camino posible entre 2 nodos en un grafo.

¿Devuelve el camino más rápido? Si y no, me explico. Si las flechas fueran caminos, tendríamos diferentes esfuerzos de un nodo a otro (4 min, 7 min otro…). El algoritmo no nos ayudaría. Pero si todos los nodos estuvieran a la misma distancia, ¡nos diría cual es el camino más corto! (se tarda 1 min de ir a un nodo a otro). Sin embargo es un buen punto de partida para entender cómo funcionan los grafos y los algoritmos de búsqueda. Para resolver el problema mencionado deberías investigar el algoritmo de Dijkstra (cuando sean esfuerzos positivos) y Bellman-Ford (cuando sean negativos). Puedes visitar el artículo donde los implementeo.

Espero que hayas disfrutado resolviendo el problema. Los grafos son realmente divertidos y útiles. ¡Hasta la próxima!

Nota: El esquema de red de amigos, y sus nombres, no es una idea original. He utilizado el mismo ejemplo del libro “Grokking Algorithms” de Aditya Bhargava que encontrarás como parte del capítulo 6. El libro es muy recomendable para aprender algoritmos. ¡Además está ilustrado de una forma muy divertida!