pythongraph-algorithmbreadth-first-searchconnected-components

connected components using Breadth first search


I need to find the connected components of a graph. I have a neighbour list of nodes:

neighbour_list = [[4], [2, 5], [1, 3, 8], [2, 14], [0, 9], [1], [10, 12], [13], [2, 14], [4, 10, 15], [6, 9], [17], [6], [7, 19, 20], [3, 8], [9, 21], [22], [11, 18], [17, 19], [13, 18, 26], [13, 26], [15, 27], [16, 23], [22, 24, 28], [23, 25, 29], [24], [19, 20, 30, 31], [21], [23, 29], [24, 28], [26, 31], [26, 30]]

For example node 0 has neighbour 4, node 1 has neighbours 2 and 5 etc... What I want to find is a list of connected components. Say node 0 has neighbour 4, yet neighbour 4 also is a neighbour of node 9. Node 9 also has number 10 and 15 neighbours. So the list would be something like

[4,10,15....] etc including following neihbours.

the method I am trying to use is breadth first search. I wrote the following algorithm:

 def bfs(neighbour_list, node):

    label_list =[]   
    for sub_neighbour_list in neighbour_list: 

      label_list.append(node)

      queue = [node]

    while queue:
        u = queue[0]
        for sub_neighbour in neighbour_list[u]:
           if sub_neighbour not in queue:
             label_list[sub_neighbour] = 0
             queue.append(sub_neighbour)
             queue.pop(0)

   print(label_list)
   return (label_list)

nothing happens when I run it. What is wrong?

thanks


Solution

  • What about:

    neighbour_list = [[4], [2, 5], [1, 3, 8], [2, 14], [0, 9], [1], [10, 12], [13], 
                     [2, 14], [4, 10, 15], [6, 9], [17], [6], [7, 19, 20], [3, 8], 
                     [9, 21], [22], [11, 18], [17, 19], [13, 18, 26], [13, 26], 
                     [15, 27], [16, 23], [22, 24, 28], [23, 25, 29], [24], 
                     [19, 20, 30, 31], [21], [23, 29], [24, 28], [26, 31], [26, 30]]
    
    def bfs(neighbour_list, root):
        queue = []
        seen = set()
    
        queue.append(root)
        seen.add(root)
    
        while queue:
            cn = queue.pop(0)
            print("Current node: %d" % cn)
            for nn in neighbour_list[cn]:
                if nn not in seen:
                    queue.append(nn)
                    seen.add(nn)
                    print("  Found %d" % nn)
    
        return seen
    
    print bfs(neighbour_list, 0)
    

    Which outputs:

    Current node: 0
      Found 4
    Current node: 4
      Found 9
    Current node: 9
      Found 10
      Found 15
    Current node: 10
      Found 6
    Current node: 15
      Found 21
    Current node: 6
      Found 12
    Current node: 21
      Found 27
    Current node: 12
    Current node: 27
    set([0, 4, 6, 9, 10, 12, 15, 21, 27])
    

    Note that set isn't ordered. So the result of this function will return all nodes reachable by root, but not in any sort of order of when the algorithm reached it. If you want that, you could easily change seen to be a list.