Graph Isomorphism X34401

optilog

Write a program in Python that, using the optilog library, check if two graphs are isomorphic.

[l] [r]

In order to use the optilog library, the program has to include something like:

from optilog.solvers.sat import *
...
solver = Glucose41()
solver.add_clauses(...)
solver.solve()
solver.model()

Input

The input is a text (in the stdin) with pairs of connected nodes representing two graphs, both separated by an empty line. Fo instance, the following text for the two graphs above:

a g
a h
a i
b g
b h
b j
c g
c i
c j
d h
d i
d j

1 2
1 4
1 5
2 3
2 6
3 4
3 7
4 8
5 6
5 8
6 7
7 8

Output

The output is also a text (in the stdout) with a list of pairs representing the isomorphism between the first graph and the second, if they are isomorphic. In this example:

a 3
b 1
c 6
d 8
g 2
h 4
i 7
j 5

If both graphs are not isomorphic, the missage must be one of the following:

Distinct number of nodes
Distinct number of edges
Not isomorphic

Scoring

Samples have been selected in order to ensure that there exist at most one mapping representing the solution. This mapping can be represented with any permutation.