Python: How to split multiple non-consecutive lists simultaneously to split graph into sub-graphs?

Question

I have a two lists like this:

list1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47]

list2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]

If you can imagine these two lists represent edges between nodes, so for example node 0 is linked to node 1 (i.e the 0th item in each list), then node 1 is linked to node 2 etc (the 1st item in each list) etc.

However, you can see in that case, that these lists do not represent one network of linked nodes, but multiple networks, because for example there is no link between node 45 and node 46 (i.e. in this case 44 in list 1 linked to 45 in list 2....but then there is no 45 in list 1 linking to 46 in list 2), so in that case, that is one complete network and then that should be cut from the lists and move on to create a new network.

I wrote this code:

edge_index = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]]

    origins_split = edge_index[0]
    dest_split = edge_index[1]
    
    list_of_graph_nodes = []
    list_of_origin_edges = []
    list_of_dest_edges = []
    
    graph_nodes = []
    graph_nodes.append(origins_split[0])
    graph_nodes.append(dest_split[0])
    
    graph_edge_origin = []
    graph_edge_origin.append(origins_split[0])
    
    graph_edge_dest = []
    graph_edge_dest.append(dest_split[0])
    
    for o,d in zip(origins_split[1:],dest_split[1:]): #change
        if o in graph_nodes:
            graph_edge_origin.append(o)
            graph_edge_dest.append(d)
            if d not in graph_nodes:
                graph_nodes.append(d)
    
        elif d in graph_nodes:
            graph_edge_origin.append(o)
            graph_edge_dest.append(d)
            if o not in graph_nodes:
                graph_nodes.append(o)
    
        else:
            list_of_graph_nodes.append(graph_nodes)
            list_of_origin_edges.append(graph_edge_origin)
            list_of_dest_edges.append(graph_edge_dest)
    
            
            graph_nodes = []
            graph_edge_dest = []
            graph_edge_origin = []
            graph_nodes.append(o)
            graph_nodes.append(d)
            graph_edge_origin.append(o)
            graph_edge_dest.append(d)
    
    print(list_of_graph_nodes)
    print(list_of_origin_edges)
    print(list_of_dest_edges)

The output should be:

list_of_graph_nodes = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45], [46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 47, 48, 52, 53]]

list_of_origin_edges = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44], [46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47]]

list_of_destination_edges = [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45],[47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]]

But what I actually get is:

list_of_graph_nodes:
    [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45], [46, 47], [48, 49, 50, 51, 52], [53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83], [47, 48]]

list_of_origin_nodes:
    [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44], [46], [48, 49, 50, 51], [53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82], [47]]

list_of_destination_nodes:
    [[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45], [47], [49, 50, 51, 52], [54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83], [48]]

Which you can see if not correct (e.g. the [47] is alone sometimes, as is [48] etc)

Could someone demonstrate how to fix this?

"I wrote this code:" - OK, but what is the code trying to do? What problem are you trying to solve? Please be more specific. — Ryan Zhang, Jun 21 '22 at 14:28
Does this answer your question https://stackoverflow.com/questions/21739569/finding-separate-graphs-within-a-graph-object-in-networkx? — Carlos Horn, Jun 21 '22 at 14:30
Thank you. @RyanZhang thank you, my ultimate aim is to split a graph into sub-graphs, based on having a list of the origin nodes, and a list of the destination nodes (and therefore the edges between them). I'll also edit the code now to comment it to explain more clearly; but the lists are not consecutive numbers where you can just split each list based on non-consecutive numbers, as you can see in example above. — Slowat_Kela, Jun 21 '22 at 14:34

score 0 · Answer 1 · answered Jun 21 '22 at 14:50

Solution based on suggestion to use networkX:

import networkx as nx

G = nx.DiGraph()
edge_index = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 49, 50, 51, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 47, 52, 47], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 47, 49, 50, 51, 52, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 48, 53, 53]]
node_list = []

for i in edge_index[0]:
    node_list.append(i)

for i in edge_index[1]:
    node_list.append(i)

node_list = list(set(node_list))
G.add_nodes_from(node_list)

for o,d in zip(edge_index[0],edge_index[1]):
    G.add_edge(o,d)

UG = G.to_undirected()
subgraphs = (UG.subgraph(c) for c in nx.connected_components(UG))
for i in subgraphs:
        origin_edges = [x[0] for x in i.edges]
        dest_edges =  [x[1] for x in i.edges]
        nodes = [x for x in i.nodes]
        print(origin_edges)
        print(dest_edges)
        print(nodes)
        print('*')

Python: How to split multiple non-consecutive lists simultaneously to split graph into sub-graphs?

1 Answers1