I'm practising with graphs, and trying to solve a problem of calculating the minimum number of flight segments, applying breadth-first search.

The code is working, but I think, that it's not clean.

Can anyone suggest how I refactor it to make it cleaner?

def distance(adj, s, t):

    n = len(adj)
    queue = []
    visited = set()
    path = []

    queue.append([s])

    dist = 0

    while (len(queue) > 0):
        path = queue.pop(0)

        last_vertex = path[-1]

        if last_vertex == t:
            # print(path)
            dist = len(path)-1

        elif last_vertex not in visited:
            for w in adj[last_vertex]:
                new_path = list(path)
                new_path.append((w))
                queue.append(new_path)
            visited.add(last_vertex)

    if dist != 0:
        return dist
    else:
        return -1

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n, m = data[0:2]
    data = data[2:]
    edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
    adj = [[] for _ in range(n)]
    for (a, b) in edges:
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    s, t = data[2 * m] - 1, data[2 * m + 1] - 1

    print(distance(adj, s, t))

I represent graph in such way. The first line contains non-negative integers n and m — the number of vertices and the number of edges respectively. The vertices are always numbered from 1 to n. Each of the following m lines defines an edge in the format u v where 1 ≤ u, v ≤ n are endpoints of the edge :

4 5
2 1
4 3
1 4
2 4
3 2
1 3

The last two digits stands for two vertices, we need to find path between.

enter image description here

up vote 4 down vote accepted

1. Review

  1. There's no docstring. What does this function do? What arguments does it take? What does it return?

  2. The code uses a list to represent the queue of nodes to be visited. But if you look at the TimeComplexity page on the Python wiki, you'll see that list.pop(0) takes time proportional to the length of the list, and that means that the algorithm takes time that's quadratic in the number of nodes in the graph.

    Instead of keeping the queue of nodes in a list, you need a collections.deque, which has an efficient popleft method.

  3. Each time the code reaches a new node, it copies the path to reach that node, and puts the path on the queue. But this is wasteful of memory (because paths might become long and have to be copied out many times) and leads to quadratic runtime.

    Since the code only needs to return the distance to the target (not the path), it only needs to store the distance to each node.

  4. The variable n is not used.

  5. Instead of:

    while (len(queue) > 0):
    

    write:

    while queue:
    
  6. It would be faster to check whether a node has been visited before adding it to the queue (rather than after removing it from the queue). This avoids unnecessary append and pop operations on visited nodes.

  7. It would be faster to check whether the target has been reached before adding it to the queue (rather than after removing it from the queue). This avoids having to wait for the target to move all the way up the queue.

  8. distance returns -1 if there was no path from source to target. But it is risky to return an exceptional value like this: it would be all too easy for the caller to forget to check the result. It is better to raise an exception for exceptional cases.

2. Revised code

from collections import deque

class Unreachable(Exception):
    """Exception raised when there is no path between nodes in a graph."""

def distance(graph, source, target):
    """Return the number of edges in the shortest path from source to
    target in a directed graph. The graph must be represented as a
    mapping from a node to a collection of its neighbours. If there is
    no path from source to target, raise Unreachable.

    >>> distance({1: [2, 3], 2: [3, 4], 3: [4, 5]}, 1, 5)
    2

    """
    if source == target:
        return 0
    queue = deque([(source, 0)]) # Queue of pairs (node, distance).
    visited = set()              # Set of visited nodes.
    while queue:
        node, dist = queue.popleft()
        visited.add(node)
        for neighbour in graph[node]:
            if neighbour in visited:
                continue
            elif neighbour == target:
                return dist + 1
            else:
                queue.append((neighbour, dist + 1))
    else:
        raise Unreachable("No path from {!r} to {!r}".format(source, target))

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.