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:
no_of_nodes = 8 graph_to = [1,1,3,5,6] graph_from = [2,6,4,7,3]
I would receive the following output:
[[1, 2, 3, 4, 6], [5, 7], [8]]
This is what I have so far:
def connections(no_of_nodes, graph_from, graph_to): nodes = list(range(1, no_of_nodes+1)) singles = [] # removes all unconnected nodes for node in nodes: if node not in graph_from + graph_to: singles.append([node]) conns = [[graph_from[0],graph_to[0]]] graph_from.pop(0) graph_to.pop(0) n=0 k = 0 while n < len(graph_from): x = graph_from[n] y = graph_to[n] if x in conns[k]: conns[k].append(y) graph_from.pop(n) graph_to.pop(n) else: conns.append([x,y]) k += 1 print(conns) n+=1 return conns + singles
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.
def connected(graph_nodes, graph_from, graph_to): unseen = [i for i in range(1,graph_nodes + 1)] edges = [[graph_from[i],graph_to[i]] for i in range(len(graph_from))] connects = [] while unseen != []: start = unseen[0] connection = [] queue = [start] unseen.remove(start) while queue != []: end = queue[-1] if end not in connection: connection.append(end) queue = queue[:-1] for k in edges: if k[0] == end: queue.append(k[1]) unseen.remove(k[1]) connects.append(connection) return connects