A = ['node1', 'node2', 'node3', 'node4', 'node5'] #nodes
B = {'node1':'node2', 'node3':'node4', 'node4':'node5'} #connections

C = [['node1', 'node2'], ['node3', 'node4', 'node5']] #wanted result

I want to have all nodes that are connected to each other; I want to have C when the input is A,B.

def demo(A, B): 
    # code
    return C

I have tried complicated ways to get the wanted results but no success. I hope some one can help me with this.

CodePudding user response：

networkx is an option:

import networkx as nx

# Initialize graph
G = nx.Graph()
# Put all your nodes into graph
G.add_nodes_from(A)
# Add edges to graph
for n1, n2 in B.items():
    G.add_edge(n1, n2)
# Create list of connected components of G
C = [list(c) for c in nx.connected_components(G)]

CodePudding user response：

Try this code

Just looping into the dictionary and converting the key-value pair into a list

And merging them in a separate loop

Code:

B1 = {'node1':'node2', 'node3':'node4', 'node4':'node5'}
B2 = {'node1':'node2', 'node3':'node4', 'node4':'node5', 'node5':'node6'}

def nodes_to_list(_dict):
  res = sorted([[i, j] for i, j in _dict.items()])

  for index1, i in enumerate(res):
    for index2, j in enumerate(res):
      if index1 != index2:
        if any(a in j for a in i):
          res[index1] = sorted(set(i j))
          del res[index2]
  return res

print(nodes_to_list(B1))
print(nodes_to_list(B2))

Outputs:

[['node1', 'node2'], ['node3', 'node4', 'node5']]
[['node1', 'node2'], ['node3', 'node4', 'node5', 'node6']]

Tell me if its not working...

CodePudding user response：

You can use a recursive generator function:

nodes = {'node1':'node2', 'node3':'node4', 'node4':'node5'}
def paths(n=None, c = []):
   if n is None:
      for a in nodes:
         if all(j != a for j in nodes.values()):
            yield from paths(a)
   elif n not in nodes:
      yield c [n]
   else:
      yield from paths(nodes[n], c [n])

print(list(paths()))

Output:

[['node1', 'node2'], ['node3', 'node4', 'node5']]
   

On a larger dictionary of nodes:

nodes = {'node1':'node2', 'node3':'node4', 'node4':'node5', 'node5':'node6' }

Output:

[['node1', 'node2'], ['node3', 'node4', 'node5', 'node6']]