infinite loop while looking for all the paths in a graph in python

Question

this is the dictionary I'm using:

{
    'timar': ['rimar', 'timas'], 
    'lares': ['pares', 'mares', 'laves'], 
    'lomas': ['lamas', 'limas', 'lemas'], 
    'gemas': ['lemas', 'remas', 'gimas'], 
    'lamas': ['lavas', 'latas', 'limas', 'lomas', 'lemas'], 
    'rimar': ['remar', 'timar', 'rimas'], 
    'lavas': ['laves', 'latas', 'lamas'], 
    'rimas': ['rimar', 'remas', 'timas', 'gimas', 'limas'], 
    'lemas': ['lomas', 'lamas', 'remas', 'limas', 'gemas'], 
    'mesas': [], 
    'remas': ['remos', 'rezas', 'remar', 'lemas', 'gemas', 'rimas'], 
    'pares': ['mares', 'lares'], 
    'teñir': ['reñir', 'tañir'], 
    'ceras': [], 
    'regar': ['rogar', 'regir', 'retar', 'rezar', 'remar'], 
    'remos': ['rezos', 'remas'], 
    'moras': [], 
    'regir': ['regar', 'reñir'], 
    'rezar': ['regar', 'rezas', 'retar', 'remar'], 
    'rezos': ['rezas', 'remos'], 
    'broma': [], 
    'lapiz': [], 
    'reñir': ['regir', 'teñir'], 
    'mares': ['pares', 'lares'], 
    'tocas': [], 
    'remar': ['remas', 'regar', 'rezar', 'retar', 'rimar'], 
    'timas': ['timar', 'limas', 'gimas', 'rimas'], 
    'laves': ['lares', 'lavas'], 'tañir': ['teñir'], 
    'bogar': ['rogar'],
    'gimas': ['gemas', 'timas', 'limas', 'rimas'], 
    'latas': ['lavas', 'lamas'], 
    'rogar': ['bogar', 'regar'], 
    'rezas': ['rezar', 'rezos', 'remas'], 
    'retar': ['regar', 'rezar', 'remar'], 
    'limas': ['lamas', 'lomas', 'lemas', 'timas', 'gimas', 'rimas']
}

And this is the code I'm using to find the paths

def busqueda(self, start_vertex, end_vertex, path=[]):
    """ find all paths from start_vertex to end_vertex in graph """
    print (start_vertex)
    graph = self.diccionario
    path = path + [start_vertex]
    if start_vertex == end_vertex:
        return [path]
    if start_vertex not in graph:
        return []
    paths = []
    for vertex in graph[start_vertex]:
        if vertex not in path:
            extended_paths = self.busqueda(vertex, end_vertex, path)
            for p in extended_paths: 
                paths.append(p)
    return paths

So you are doing dfs on the graph, it is usually easier to do this with a stack. What start and end are you using that goes into an infinite loop. — AChampion
– AChampion, Commented Dec 12, 2016 at 1:24
Sorry, i'm using 'mares' and 'tañir' as start and end respectively — fabian bohorquez
– fabian bohorquez, Commented Dec 12, 2016 at 1:30
Are you sure it is going into an infinite loop, there are 12012 different paths through your network from mares to tañir. — AChampion
– AChampion, Commented Dec 12, 2016 at 1:34

AChampion · Accepted Answer · 2016-12-12 04:40:27Z

2

I find these search problems to be easier to do with a stack than recursively.
With very connected graphs you will find the number of paths increases exponentially with the number of nodes.

But here's a quick dfs on your graph:

def dfs(graph, start, end):
    stack = [[start]]
    while stack:
        path = stack.pop()
        if path[-1] == end:
            yield path
            continue
        for next_state in graph[path[-1]]:
            if next_state in path: # Stop cycles
                continue
            stack.append(path+[next_state])

>>> paths = list(dfs(graph, 'mares', 'tañir'))
>>> len(paths)
12012
>>> paths[0]
['mares', 'lares', 'laves', 'lavas', 'lamas', 'lemas', 'gemas', 'gimas',
 'rimas', 'limas', 'timas', 'timar', 'rimar', 'remar', 'retar', 'rezar',
 'regar', 'regir', 'reñir', 'teñir', 'tañir']
>>> max(paths, key=len)
['mares', 'pares', 'lares', 'laves', 'lavas', 'latas', 'lamas', 'lemas',
 'lomas', 'limas', 'rimas', 'rimar', 'timar', 'timas', 'gimas', 'gemas',
 'remas', 'remos', 'rezos', 'rezas', 'rezar', 'remar', 'retar', 'regar',
 'regir', 'reñir', 'teñir', 'tañir']

edited Dec 12, 2016 at 4:40

answered Dec 12, 2016 at 1:40

AChampion

30.5k4 gold badges63 silver badges79 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Nath Over a year ago

@fabianbohorquez welcome to stack overflow. If achampions answer Solved your issue please mark it as the accepted answer. This way he receives reputation points for his efforts.

fabian bohorquez Over a year ago

what if i have a very large dictionary, how can i find the longest path available

AChampion Over a year ago

max(path, key=len) will return the longest path between start and end.

fabian bohorquez Over a year ago

@AChampion but the program does not work when the dictionary is very large

AChampion Over a year ago

This is a form of the traveling salesman problem and is NP hard. There is no efficient algorithm for large N. You will need to investigate efficient approximations: en.wikipedia.org/wiki/Longest_path_problem

Collectives™ on Stack Overflow

infinite loop while looking for all the paths in a graph in python

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related