I am solving a specific problem, I would appreciate any suggestions you had for this problem, its trivial but I am not sure if this is the best way to solve this problem.

The Problem: Given a graph G, lets say you get a set of connected component subgraphs {C_1, C_2, ....., C_N}. Now partition the aforementioned set into K subsets such that every element in the subset are isomorphic with each-other. You can have atmost N subsets.

The Solution:

1. Run a find connected sugraphs. This will return all the connected components as graphs.
2. Partition this connected components subgraphs based on number of nodes (Which should be fine in our case). Optional
3. For the subgraphs. Run the following:
   • Initialize a dictionary with the following. A random node as the key and a singleton set containing the graph itself as its value and add remaining nodes to a deque.
   • For the remaining nodes:

     • pop the element in the front of the deque. If there's an isomorphism match add that graph to the dictionary of subgraph, else push the element to its back.

     • Once there's absolute certainity that we have reached a cycle. I.e. we are scanning the same element which we pushed to the back of the queue. This node's cycle is done. Pop the front of the queue and add the <graph:set([graph])> entry to the dictionary mentioned before. Repeat until there are elements left in the queue.

Can this be further otpimized?

import networkx as nx
nx_graph = nx.Graph()
edges = [
    (1, 2),
    (2, 3),
    (3, 4),
    (5, 6),
    (6, 7),
    (7, 8),
    (9, 10),
    (10, 11),
    (10, 12)
]
for edge in edges:
    nx_graph.add_edge(edge[0], edge[1])
    
nx.draw(nx_graph, pos=nx.spring_layout(nx_graph), node_color='#1ab2c3', with_labels=True)

Graph:

from collections import deque

def paritition_isomorphic_subgraphs(graph):
    subgraphs_gen = (graph.subgraph(c) for c in nx.connected_components(graph))
    subgraphs_list = list(subgraphs_gen)

    graph_queue = deque(subgraphs_list)

    graph_of_interest = graph_queue.popleft()
    isomprohic_elements = {
        graph_of_interest: set([graph_of_interest])
    }

    last_element_popped = None
    count = 0
    first_mismatch = None

    while graph_queue:
        if graph_queue[0] == first_mismatch:
            count = 0
            graph_of_interest = graph_queue.popleft()
            isomprohic_elements[graph_of_interest] = set([graph_of_interest])
        if graph_queue:
            graph = graph_queue.popleft()
            if nx.is_isomorphic(graph_of_interest, graph):
                isomprohic_elements[graph_of_interest].add(graph)
            else:
                if count == 0:
                    first_mismatch = graph
                graph_queue.append(graph)
                count += 1
    return list(isomprohic_elements.values())