CODEWITHSUNDEEP
pythonnetworkxisomorphic
evil_potato
evil_potato

Reputation: 139

Find isomorphic pairs in list of graphs networkx

I have a list of edge lists of some graphs. For example, let's consider the following list

G_list = [[(0,1), (0,2)], [(0,3), (1,3)], [(0,3), (1,3)], [(0,3), (1,3), (2,3)]]

The graphs generated from the above list, G0, G1, G2 and G3 are shown below:

enter image description here

We can see (and check) that G0 is isomorphic to G3. Also, note that G0 is isomorphic to G1, but G0 and G1 are automorphic to each other.

Now I want to find the fastest way to find all pairs of isomorphic graphs in such a list and output them as a list of tuples. It would be even better if we can reject automorphisms from this list.

Here the ideal output from the list should be G_iso = [(G0, G3)]. However note that there can be more than one isomorphic pairs of graphs in the list.

Upvotes: 3

Views: 438

Answers (1)

Thomas Ahle
Thomas Ahle

Reputation: 31604

Using NetworkX you can just try all pairs of graphs:

import networkx as nx

def find_isomorphic_pairs_networkx(graph_list):
    for i, g1 in enumerate(graph_list):
        for j, g2 in enumerate(graph_list[i+1:], start=i+1):
            if nx.is_isomorphic(nx.Graph(g1), nx.Graph(g2)):
                yield (i, j)

G_list = [[(0,1), (0,2)], [(0,3), (1,3)], [(0,3), (1,3)], [(0,3), (1,3), (2,3)]]
isomorphic_pairs_networkx = list(find_isomorphic_pairs_networkx(G_list))
print("Isomorphic pairs (NetworkX):", isomorphic_pairs_networkx)

Isomorphic pairs (NetworkX): [(0, 1), (0, 2), (1, 2)]

Alternatively you can use Nauty, which computes a canonical representation of each graph:

from pynauty import Graph, canon_label
from itertools import combinations
from collections import defaultdict

def canonical_representation(g):
    nauty_g = Graph(number_of_vertices=len(g))
    for edge in g:
        nauty_g.connect_vertex(edge[0], [v for v, _ in g if v != edge[0]])
    return tuple(canon_label(nauty_g))

def find_isomorphic_pairs_pynauty(graph_list):
    canons = defaultdict(list)
    for i, graph in enumerate(graph_list):
        canon = canonical_representation(graph)
        canons[canon].append(i)
    for canon, graphs in canons.items():
        yield from combinations(graphs, 2)

G_list = [[(0,1), (0,2)], [(0,3), (1,3)], [(0,3), (1,3)], [(0,3), (1,3), (2,3)]]
isomorphic_pairs_pynauty = list(find_isomorphic_pairs_pynauty(G_list))
print("Isomorphic pairs (PyNauty):", isomorphic_pairs_pynauty)

Isomorphic pairs (PyNauty): [(0, 1), (0, 2), (1, 2)]

Some notes: I'm unsure about your definition of automorphisms. Usually, an automorphism is just an isomorphism from a graph to itself, so there isn't really a difference between graphs 0, 1 and 2 under isomorphisms.

Upvotes: 1

Related Questions