Algorithm for determining if 2 graphs are isomorphic

Question

Disclaimer: I'm a total newbie at graph theory and I'm not sure if this belongs on SO, Math SE, etc.

Given 2 adjacency matrices A and B, how can I determine if A and B are isomorphic.

For example, A and B which are not isomorphic and C and D which are isomorphic.

A = [ 0 1 0 0 1 1     B = [ 0 1 1 0 0 0
      1 0 1 0 0 1           1 0 1 1 0 0
      0 1 0 1 0 0           1 1 0 1 1 0
      0 0 1 0 1 0           0 1 1 0 0 1
      1 0 0 1 0 1           0 0 1 0 0 1
      1 1 0 0 1 0 ]         0 0 0 1 1 0 ]

C = [ 0 1 0 1 0 1     D = [ 0 1 0 1 1 0
      1 0 1 0 0 1           1 0 1 0 1 0
      0 1 0 1 1 0           0 1 0 1 0 1
      1 0 1 0 1 0           1 0 1 0 0 1
      0 0 1 1 0 1           1 1 0 0 0 1
      1 1 0 0 1 0 ]         0 0 1 1 1 0 ]   

(sorry for this ugly notation, I'm not quite sure how to draw matrices on SO)

Here's how I've started my algorithm (pardon my lack of mathematical rigor) please help me complete/correct!

1. If size (number of edges, in this case amount of 1s) of A != size of B => graphs are not isomorphic
2. For each vertex of A, count its degree and look for a matching vertex in B which has the same degree and was not matched earlier. If there is no match => graphs are not isomorphic.
3. Now that we cannot quickly prove that A and B are not isomorphic, what's the next step? Would it be correct try every permutation of lines in A until A matches B? Really not sure about this one...

Solution 1

That's a quite difficult problem to solve. There is a Wikipedia page about it:

• Graph isomorphism problem

According to that page there are a number of special cases that have been solved with efficient polynomial time solutions, but the complexity of the optimal solution is still unknown.

Solution 2

My project - Griso - at sf.net: http://sourceforge.net/projects/griso/ with this description:
Griso is a graph isomorphism testing utility written in C++ and based on my own algo.
See Griso's sample input/output on this page: http://funkybee.narod.ru/graphs.htm

Comments

[Olivier Lalonde]

Thanks for the reference. Strangely enough, I have an intuition that graph isomorphism should be an easy problem to solve since it seems quite easy for my brain to visually determine if 2 graphs are isomorph. Maybe I haven't tried on a big enough graph...

[Gleno]

Haha, I have the exact opposite problem. Can't see if two graphs are isomorphic even if they are very small.

[MAK]

@olivier Lalonde: How long does your brain take to check for isomorphism in dense graphs with 50, 100 or more nodes?