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
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.