title: NetworkX isomorphic connected components
body: <p>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.</p>
  <p><strong>The Problem</strong>: Given a graph <code>G</code>, lets say you get a set of connected component subgraphs <code>{C_1, C_2, ....., C_N}</code>. Now partition the aforementioned set into <code>K</code> subsets such that every element in the subset are isomorphic with each-other. You can have atmost <code>N</code> subsets.</p>
  <p><strong>The Solution</strong>:</p>
  <ol>
  <li>Run a find connected sugraphs. This will return all the connected components as graphs.</li>
  <li>Partition this connected components subgraphs based on  number of nodes (Which should be fine in our case). <strong>Optional</strong></li>
  <li>For the subgraphs. Run the following:
  <ul>
  <li>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 <code>deque</code>.</li>
  <li>For the remaining nodes:
  <ul>
  <li><p>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.</p>
  </li>
  <li><p>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 <code>&lt;graph:set([graph])&gt;</code> entry to the dictionary mentioned before. Repeat until there are elements left in the queue.</p>
  </li>
  </ul>
  </li>
  </ul>
  </li>
  </ol>
  <p><strong>Can this be further otpimized?</strong></p>
  <pre class="lang-py prettyprint-override"><code>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)
  </code></pre>
  <p>Graph:</p>
  <p><a href="https://i.stack.imgur.com/ETb3Z.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ETb3Z.png" alt="enter image description here" /></a></p>
  <pre class="lang-py prettyprint-override"><code>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())
  </code></pre>