I am looking for the most efficient algorithm in order to find both the number of connected components in a network, and the number of nodes for each connected component.
Example:
Given the following inputs:
JavaScript
x
6
1
no_of_nodes = 8
2
3
graph_to = [1,1,3,5,6]
4
5
graph_from = [2,6,4,7,3]
6
I would receive the following output:
JavaScript
1
2
1
[[1, 2, 3, 4, 6], [5, 7], [8]]
2
This is what I have so far:
JavaScript
1
38
38
1
def connections(no_of_nodes, graph_from, graph_to):
2
3
nodes = list(range(1, no_of_nodes+1))
4
5
singles = []
6
7
# removes all unconnected nodes
8
9
for node in nodes:
10
if node not in graph_from + graph_to:
11
singles.append([node])
12
13
conns = [[graph_from[0],graph_to[0]]]
14
15
graph_from.pop(0)
16
graph_to.pop(0)
17
18
n=0
19
k = 0
20
21
while n < len(graph_from):
22
23
x = graph_from[n]
24
y = graph_to[n]
25
26
if x in conns[k]:
27
conns[k].append(y)
28
graph_from.pop(n)
29
graph_to.pop(n)
30
else:
31
conns.append([x,y])
32
k += 1
33
print(conns)
34
n+=1
35
36
return conns + singles
37
38
I have found a way to iterate through the nodes assuming that all connections are adjacently placed in the graph_from list, but this, of course, will not hold up for all cases.
EDIT: I am looking for a way to do this without importing a module
Advertisement
Answer
Using the summarized process answered above, I was able to formulate the following which after testing looks to check out.
JavaScript
1
39
39
1
def connected(graph_nodes, graph_from, graph_to):
2
3
4
unseen = [i for i in range(1,graph_nodes + 1)]
5
6
edges = [[graph_from[i],graph_to[i]] for i in range(len(graph_from))]
7
8
9
connects = []
10
11
while unseen != []:
12
start = unseen[0]
13
connection = []
14
15
queue = [start]
16
unseen.remove(start)
17
18
while queue != []:
19
20
end = queue[-1]
21
22
if end not in connection:
23
connection.append(end)
24
25
queue = queue[:-1]
26
27
for k in edges:
28
29
if k[0] == end:
30
31
queue.append(k[1])
32
unseen.remove(k[1])
33
34
connects.append(connection)
35
36
37
38
return connects
39