generate a list of permutations that preserve a given partitioning (context: Graph Isomorphism)

Question

I'm working on a python program that tests two given networkx graphs G and H for an isomorphism by using a brute force method. Each node in each graph has been assigned a label and color attribute, and the program should test all possible bijections between graph G, for which the labeling is fixed, and graph H, for which the labeling can be varied. In addition, i only need to examine the bijections which make sure that for a given node color 'i' in graph G is mapped onto a node in H which also has color 'i'. To that end, i've created a class which inherits all the methods/attributes from a nx.Graph, and written several methods of my own.

So far what I've done is gone through both graphs, and created a dictionary which gives the possible valid mappings for each node in G onto H.

e.g. for the graph G == 1-2-3 the coloring would be: color_g = {1: 1, 2: 2, 3:1} because '1' and '3' have the same degree, and 2 has a different degree.

if graph H == 2-1-3 then color_h = {2:1, 1: 2, 3:1}

and when i run a group_by_color function to give possible mappings from G to H i would get the following dictionary

map = {1: [2, 3], 2: [1], 3:[2, 3]}

what that means is that due to the color partitioning node '1' from G could be mapped onto either '2' or '3' from H, '2' from G can only be mapped onto '1' from H, and so on.

Here is the problem: I am struggling to generate a list of all valid permutations from G to H that preserve the partitioning given by coloring, and am struggling to think of how to do it. I am well aware of python's permutations function and in a previous version of the brute force method where i didn't consider the color, which meant the list of permutations was significantly larger (and the run-time much slower), but the implimentation also easier. Now i want to speed things up by only considering permutations which are possible according to the given colorings.

the question: How can i take my map dictionary, and use it to generate the bijection functions that are color-conserving/preserving (german: 'farbe-erhaltend')? Or would you suggest a different method all together?

some other facts:

the nodes in both graphs are labled consecutively and ascending the 'colors' i'm using are numbers because the graphs can become arbitrarily large.

I'd be grateful for any help, ItsAnApe

Answer 1

To answer the algorithmic part of your question: Say your partition has k cells: C_1, ..., C_k. There is a 1 to 1 correspondence between permutations of the overall set that preserve the partition and the Cartesian product P_1 x P_2 x ... x P_k where P_i is the set of permutations of the cell C_i. itertools contains a method for generating the Cartesian product. Exactly how you want to use a tuple like (p_1, p_2, ..., p_k) where each p_i is a permutation of cell C_i depends on your purposes. You could write a function to combine them into a single permutation if you want -- or just iterate over them if you are going to be using the permutations on a cell by cell basis anyway.

The following is proof of concept. It represents a partition as a list of tuples, where each tuple represents a cell, and it lists all permutations of the overall set which preserves the partition. In the test case it lists the 2x6x2 = 24 permutations of {1,2,3,4,5,6,7} which preserve the partition [(1,4), (2,3,5),(6,7)]. No need to step through and filter all 7! = 5040 permutations:

#list_perms.py
import itertools

def combinePermutations(perms):
    a = min(min(p) for p in perms)
    b = max(max(p) for p in perms)
    d = {i:i for i in range(a,b+1)}
    for p in perms:
        pairs = zip(sorted(p),p)
        for i,j in pairs:
            d[i] = j
    return tuple(d[i] for i in range(a,b+1))

def permute(cell):
    return [p for p in itertools.permutations(cell)]

def listGoodPerms(cells):
    products = itertools.product(*(permute(cell) for cell in cells))
    return [combinePermutations(perms) for perms in products]

#to test:
myCells = [(1,4), (2,3,5), (6,7)]
for p in listGoodPerms(myCells): print(p)

The output when the module is run:

(1, 2, 3, 4, 5, 6, 7)
(1, 2, 3, 4, 5, 7, 6)
(1, 2, 5, 4, 3, 6, 7)
(1, 2, 5, 4, 3, 7, 6)
(1, 3, 2, 4, 5, 6, 7)
(1, 3, 2, 4, 5, 7, 6)
(1, 3, 5, 4, 2, 6, 7)
(1, 3, 5, 4, 2, 7, 6)
(1, 5, 2, 4, 3, 6, 7)
(1, 5, 2, 4, 3, 7, 6)
(1, 5, 3, 4, 2, 6, 7)
(1, 5, 3, 4, 2, 7, 6)
(4, 2, 3, 1, 5, 6, 7)
(4, 2, 3, 1, 5, 7, 6)
(4, 2, 5, 1, 3, 6, 7)
(4, 2, 5, 1, 3, 7, 6)
(4, 3, 2, 1, 5, 6, 7)
(4, 3, 2, 1, 5, 7, 6)
(4, 3, 5, 1, 2, 6, 7)
(4, 3, 5, 1, 2, 7, 6)
(4, 5, 2, 1, 3, 6, 7)
(4, 5, 2, 1, 3, 7, 6)
(4, 5, 3, 1, 2, 6, 7)
(4, 5, 3, 1, 2, 7, 6)