Graph isomorphism
I'm looking for an algorithm to determine if two graphs are isomorphic or not. I don't need the isomorphism itself. I know that this is a hard problem, and that it might be an NP-complete problem, but right now I'm using the naive method, where I permute all the vertices in the graph - just to make it work. I have searched around on the net for an algorithm, and I have found some algorithms, but none in Java. I hope anyone know of some implementation in Java.
I found an algorithm called Nauty, and it is supposed to be the fastest known algorithm, but it is implemented in C++. Is it in any way possible that a java program can use this implementation in C++? I really don't want to rewrite the whole thing to C++.
If anyone knows of an algorithm in Java, available to the public, I would really appreciate it.
Thanks.
Alg O.
> I found an algorithm called Nauty, and it is supposed
> to be the fastest known algorithm, but it is
> implemented in C++. Is it in any way possible that a
> java program can use this implementation in C++? I
> really don't want to rewrite the whole thing to C++.
You could try to embed the C++ code through the Java Native Interface:
http://java.sun.com/j2se/1.5.0/docs/guide/jni/index.html
Just write your own code.
Use progressive invarients.
The graphs are NOT isomorphic if they have a different number of nodes.
The graphs are NOT isomorphic if they have a different number of edges.
The graphs are NOT isomporhic if the histogram of node degrees are not identical (if one graph has 4 nodes of degree 5 then the other graph must also have exactly 4 nodes of degree 5)
Choose any node of degree N in one graph. You can create a histogram of the degrees seen in those N neighbors. There MUST be a degree N node in the other graph that has the same degree histogram.
etc
What I mean by etc is this:
You are essentially creating signatures (Histograms of degrees) for each node in one graph and confirming that the other graph has a node that matches that signature. If you ever fail the graphs are not isomorphic.
The first signature for a node was simply that it existed. Next you counted the edges leaving the node (that signature was called degree - you needed to check that the other graph had nodes with all those same degrees). The next signature was the histogram of degrees for the nodes that were immediate neighbors. The next signature would be the histogram of degrees for negihbors that are 2 nodes away. The next would be for nodes that are 3 away.
At some point, assuming that your graph is finite, (generally a safe assumption on a computer) you have computed a long signature for each node (sig 0 = degree of node, sig 1 = degrees seen one node out, sig 2 = degrees n nodes out ... the long sig is concatination of all these signatures)
Presumabaly you created a HashMap that represents a bag of signatures from one of the graphs, a bag where you added each signature as it came in from the first graph, and then you emptied the bag as you found the same signatures on the the second graph. You did this each time you extended the signature by one more level and you bailed out with the old "Not Isomporphic" anytime the bag did not empty properly.
If you never failed then you might have an isomorphism which you will confirm by using a backtracking algorithm to try to create the isomorphism.
A node with a long signature can only be paired with another node with the identical signature.
If your graphs had any character (nodes of differnt degrees) the signatures will greatly reduce the space of possible matches that you need to examine to create your isomorphism (or to confirm that none exists). On the other hand if your graph is some nearly complete graph (many nodes all of the same degree - all of the same signature) then the number of possible isomorphisms is large and finding one should not be that difficult. (work from rare signatures to common)
Should be an afternoon's work.
Enjoy
Oh yes, if your graphs are very large, the signatures will be quite huge and you will run out of memory. On the other hand, if your graphs are quite large and if the problem of graph isomorphism is nearly NP complete, or hard or high degree polynomial time you weren't going to solve it in your lifetime anyway.
And thanks for the post of the Mathematica comment. It was the comment that there are polynomial time algorithms if there are limits on the degrees of the nodes that suggested this algorithm.
