Counterexample

[benjaminbartsch]

If two graphs are isomophic, then your algorithm always computes the same signature. BUT the opposite is not true. If two graphs are not isomorphic the signature may be equal.

NODE-PERMUTATIONS = 720
NODES = 6, EDGES = 7, GROUPS = 18
COUNTEREAXAMPLE FOUND!
GRAPH 1
[0, 0, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 1]
[0, 1, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 1]
[1, 1, 0, 0, 1, 0]
GRAPH 2
[0, 0, 0, 1, 0, 1]
[0, 0, 1, 1, 1, 0]
[0, 1, 0, 0, 1, 0]
[1, 1, 0, 0, 0, 1]
[0, 1, 1, 0, 0, 0]
[1, 0, 0, 1, 0, 0]

If you draw them, one can see, that the first graph has no circles with three nodes (triangles), but the secons graph has.

[neerajmw]

Yes, it fails when it is possible to split the graph into two parts and these two parts are the exact mirror images of each other. There may be other cases when it does not work. I am trying an approach where we break this symmetry by adding a node to the vertices that have the same signature in the two graphs. I am exploring if the new graphs( with the odd number of vertices) are isomorphic then the original graphs are isomorphic. otherwise not. In the attached image, as you showed, the algorithm will conclude them as isomorphic. But the graphs c and d will be concluded as non-isomorphic. All we have done is added a single edge between a new node and a node of the corresponding graphs that have the same signature according to the algorithm.

I am yet to find a connected graph with the odd number of nodes and the above algorithm does not work

.

[benjaminbartsch]

NODE-PERMUTATIONS = 5040
NODES = 7, EDGES = 8, GROUPS = 66
COUNTEREAXAMPLE FOUND!
GRAPH 1
[0, 1, 0, 0, 0, 0, 1]
[1, 0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 1, 0, 1]
[0, 0, 1, 1, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 1]
[1, 0, 0, 1, 0, 1, 0]
GRAPH 2
[0, 1, 0, 1, 0, 1, 0]
[1, 0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0, 1]
[1, 0, 0, 0, 0, 1, 0]
[0, 1, 1, 0, 0, 0, 1]
[1, 0, 0, 1, 0, 0, 0]
[0, 0, 1, 0, 1, 0, 0]

[benjaminbartsch]

[neeraj8us]

Can you please confirm if this is fixed in latest code?

[benjaminbartsch]

IsoMorphicGraphSignatureDP

This import does not make sense. It cannot be resolved. import sun.font.TrueTypeFont;

[benjaminbartsch]

The first counterexample I've found is for nodes=6, and edges=7.

` GRAPH 1 [0, 0, 0, 1, 0, 1] [0, 0, 1, 1, 0, 1] [0, 1, 0, 0, 1, 0] [1, 1, 0, 0, 0, 0] [0, 0, 1, 0, 0, 1] [1, 1, 0, 0, 1, 0] GRAPH 2 [0, 0, 0, 1, 0, 1] [0, 0, 1, 1, 1, 0] [0, 1, 0, 0, 1, 0] [1, 1, 0, 0, 0, 1] [0, 1, 1, 0, 0, 0] [1, 0, 0, 1, 0, 0]

`

[benjaminbartsch]

[neeraj8us]

Try IsoMorphicGraphSignatureSelfDP.java, this contains the new algorithm

On Thu, 9 Jun 2022, 14:35 B. Bartsch, @.***> wrote:

The first counterexample I've found is for nodes=6, and edges=7.

` GRAPH 1 [0, 0, 0, 1, 0, 1] [0, 0, 1, 1, 0, 1] [0, 1, 0, 0, 1, 0] [1, 1, 0, 0, 0, 0] [0, 0, 1, 0, 0, 1] [1, 1, 0, 0, 1, 0] GRAPH 2 [0, 0, 0, 1, 0, 1] [0, 0, 1, 1, 1, 0] [0, 1, 0, 0, 1, 0] [1, 1, 0, 0, 0, 1] [0, 1, 1, 0, 0, 0] [1, 0, 0, 1, 0, 0]

`

— Reply to this email directly, view it on GitHub https://github.com/neeraj8us/isomorphism/issues/1#issuecomment-1150864656, or unsubscribe https://github.com/notifications/unsubscribe-auth/AC33GB7YHOYWMKIMUSJSVJDVOGXU7ANCNFSM5VWIRTIA . You are receiving this because you commented.Message ID: @.***>

[neeraj8us]

Check out the latest code and run the following command to verify that issue has been fixed for the above graphs. Files ./graphs/issue1_1_graph.txt and ./graphs/issue1_2_graph.txt contains the above two graphs in adjacency list.

git clone git@github.com:neeraj8us/isomorphism.git cd isomorphism ./gradlew build java -cp ./build/libs/untitled-1.0-SNAPSHOT.jar com.neer.IsomorphismCheck graphs/graph1.txt graphs/graph2.txt