1
\$\begingroup\$

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?

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Are the edges directed or undirected? The edge list in your code has both (0,2) and (2,0), which implies they are directed. \$\endgroup\$
    – RootTwo
    Jul 24, 2019 at 22:38
  • \$\begingroup\$ @RootTwo They are directed \$\endgroup\$
    – Your IDE
    Jul 25, 2019 at 3:01

1 Answer 1

1
\$\begingroup\$

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.
\$\endgroup\$
4
  • \$\begingroup\$ You don't actually need to call .keys() most of the time anymore. Iterating over a dict or converting to list automatically does this. You should still use .items() and .values() where appropriate, though. \$\endgroup\$ Jul 25, 2019 at 12:53
  • \$\begingroup\$ @HoboProber, you are correct. For example, .keys() isn't needed in return list(visited.keys()) , but it is needed to get the set-like features of a dict view as in neighbors_of[node] - visited.keys(). \$\endgroup\$
    – RootTwo
    Jul 25, 2019 at 14:47
  • \$\begingroup\$ @RootTwo This would require converting from edge_list to adjacency list type of format. I know how to do in this way, but as I've mentioned in the last line in my question, popping out the edge after it has been visited is more helpful, but doing that will lead to list pointer skipping over to the next element. How to do it in this way? \$\endgroup\$
    – Your IDE
    Oct 7, 2019 at 10:20
  • \$\begingroup\$ Removing items from a list while iterating over it can cause items to be skipped. The list iterator uses an index internally. The first time through the loop, it is at index 0, so the iterator returns list[0]. When list[0] is removed, the remaining items in the list move up one place: list[1] is now list[0], list[2] is now list[1], and so on. The iterator index goes to 1 and returns list[1]. But that is the old list[2], list[1] got skipped. Solutions are to iterate over the list backward, or is to iterate over a copy of the list. There are a lot of related stackoverflow questions. \$\endgroup\$
    – RootTwo
    Oct 7, 2019 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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