3
\$\begingroup\$

Question : Build a graph in python, given its edge representation.

from collections import defaultdict

graph = { '1' : ['2' ,'4','5'],
          '2' : ['3'] ,
          '3' : ['5'] ,
          '4' : ['2']
          }

def generate_edges(graph):
    edges = []

    for node in graph:
        for next_node in graph[node]:
            #if edge exist than append
            edges.append((node,next_node))
    return edges


def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path

        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath:
                    return newpath
        return None


print generate_edges(graph)

print find_path(graph, '1','5')

How can i improve this code?

\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

find_path is very inefficient. Consider the following example, where we try to find a short path (just one edge) in a graph with just eleven nodes:

>>> G = {i: list(range(10)) for i in range(10)}
>>> G[0].append(10)
>>> find_path(G, 0, 10)
[0, 10]

How long does this take?

>>> from timeit import timeit
>>> timeit(lambda:find_path(G, 0, 10), number=1)
1.3475657280068845

It really shouldn't take more than a second to find a path with a single edge in such a small graph. So why does it take so long?

The way that find_path works is that it generates all simple paths (paths with no repeated nodes) in depth-first order. However, in general there can be exponentially many simple paths in a graph. I constructed the graph G so that it looks like this:

The depth-first search starts by finding the path 0–1–2–3–4–5–6–7–8–9 but then it reaches a dead end:

So the search backtracks a couple of steps and then finds the path 0–1–2–3–4–5–6–7–9–8, but again it reaches a dead end:

You can see that the search will have to visit every path starting with 0 and visiting all of 1 to 9, before it will consider the path 0–10. But there are \$9! = 362,880\$ such paths.

To avoid this exponential runtime, you'll have to use a different approach, for example Dijkstra's algorithm.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.