How to find graph isomorphism?

Question

Python

a, b, c, d, g, h, i, j = range(8)

#    a, b, c, d, g, h, i, j
G = [
    [0, 0, 0, 0, 1, 1, 1, 0],  # a
    [0, 0, 0, 0, 1, 1, 0, 1],  # b
    [0, 0, 0, 0, 1, 0, 1, 1],  # c
    [0, 0, 0, 0, 0, 1, 1, 1],  # d
    [1, 1, 1, 0, 0, 0, 0, 0],  # g
    [1, 1, 0, 1, 0, 0, 0, 0],  # h
    [1, 0, 1, 1, 0, 0, 0, 0],  # i
    [0, 1, 1, 1, 0, 0, 0, 0]   # j
]

#    1, 2, 3, 4, 5, 6, 7, 8
H = [
    [0, 1, 0, 1, 1, 0, 0, 0],  # 1
    [1, 0, 1, 0, 0, 1, 0, 0],  # 2
    [0, 1, 0, 1, 0, 0, 1, 0],  # 3
    [1, 0, 1, 0, 0, 0, 0, 1],  # 4
    [1, 0, 0, 0, 0, 1, 0, 1],  # 5
    [0, 1, 0, 0, 1, 0, 1, 0],  # 6
    [0, 0, 1, 0, 0, 1, 0, 1],  # 7
    [0, 0, 0, 1, 1, 0, 1, 0]   # 8
]

To define isomorphism, it is necessary to obtain the adjacency matrix of graph H by permuting the rows and columns of the adjacency matrix of graph G. (???)
How to get to the answer of the form:

?

Answer 1

A simple option to implement - iterate over the permutation. Here in your answer letters are compared with numbers. Fix the order of letters (vertices in one graph). Then the vertices of the second graph (numbers in the answer) will be a permutation. Iterate over all permutations. Then check that one adjacency matrix after permutation becomes equal to the second one. Literally for everyone i, j, check that a[p[i]][p[j]] == b[i][j].
Iterating over permutations is a well-known problem . Loop through this algorithm on the current permutation (which is initially p[i] == i) until you get it. The implementation of this algorithm is already in python .
As soon as you have found a permutation for which the matrices matched, output the permutation in response and fall out of the enumeration.
A little more difficult to implement, but faster - permutations are sorted out by a recursive function from one end. At the same time, as a new element is selected, all checks are immediately performed (here, you fixed p[i] at the i-th level of recursion, immediately see that for all j a[p[i]][p[j] ]==b[i][j] are executed).
How to collect the entire permutation (reach the nth level of recursion) - you have found the answer.
If the implementation gives the wrong answer, try a[p[i]][p[j]]==b[i][j]changing the condition to a[i][j]==b[p[i]][p[j]](It's hard to understand here whether you want a direct or reverse permutation in the answer).