Optimising the BFS

Question

The input graph to the bfs function is in the form of edge list representation.

from queue import deque

def neighbour(s,visit,que):

    for i in l:
        if(i[0]==s and i[1] not in visit):
            que.append(i[1])
            visit.append(i[1])
    return que

def bfs(start=0):    
    que=deque()
    visit=[start]
    que.append(start)

    while(que):
        start=que.popleft()
        que=neighbour(start,visit,que)

    return visit
l=[(0,1),(0,2),(1,2),(2,0),(2,3),(3,3)]
visit=bfs(start=1)

This is quite inefficient (when it comes to large no. of edges) since in the neighbour function, it iterates through the entire edge-list every time even when many of the vertices in the edges are already visited in the previous function call.

So, a more efficient way would be to pop out the edges once they entered the if-condition so that in the function-call, there are lesser no. of edges to iterate through.

Like this:

if (i[0]==s and i[1] not in visit):
            que.append(i[1])
            visit.append(i[1])
            l.remove(i)

But the iterator tends to just skip over to the next item in the list after removing a particular edge. Is there a way to implement an user-defined iterator function to improve the performance since reverse-iterators (i.e., _next__() exists but not _reverse__() ) don't exist?

Answer 1

bfs() doesn't actually do anything with the nodes. It just returns a list of the nodes in the order they were visited.

Data structures

Each call to neighbors scans the whole edge list. Which, as you point out, is inefficient. So, preprocess the edge list to create data structure that lets you access the neighbors more efficiently.

If you know how many nodes there are in advance, you can do something like this:

from collections import deque

def neighbors(edge_list, number_of_nodes):
    """ Build a list such that the list at index `n`
        is the set of the neighbors of node `n`.
    """

    neighbors_list = [set() for _ in range(number_of_nodes)]

    for start_node, end_node in edge_list:
        neighbors_list[start_node].add(end_node)    

        # if the edges are not directed, then uncomment the next line
        #neighbors_list[end_node].add(start_node)    

    return neighbors_list

If the nodes have strings for labels, or you don;t know in advance how many there are, neighbors() can be modified like so:

from collections import defauldict, deque

def neighbors(edge_list, number_of_nodes):
    """ Build a list such that the list at index `n`
        is the set of the neighbors of node `n`.
    """

    neighbors_list = defaultdict(set)

    for start_node, end_node in edge_list:
        neighbors_list[start_node].add(end_node)    

        # if the edges are not directed, then uncomment the next line
        #neighbors_list[end_node].add(start_node)    

    return neighbors_list

Then bfs can be done like this (using one of the neighbors() above):

def bfs(edge_list, number_of_nodes, start=0):
    neighbors_of = neighbors(edge_list, number_of_nodes)
    que = deque([start])
    visited = {start:True}

    while(que):
        node = que.popleft()

        neighbor_nodes = neighbors_of[node] - visited.keys()
        que.extend(neighbor_nodes)
        visited.update((neighbor,True) for neighbor in neighbor_nodes)

    return list(visited.keys())

The above relies on python 3.7 features:

1. a dictionary returns keys in the order they were added to the dictionary, so list(visited.keys()) returns the nodes in the order they were visited.
2. the view returned by dict.keys() behaves like a set, so neighbors_of[node] - visited.keys() returns a set of nodes that are neighbors or node but are not in visited.