I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would like to compare with the others.

$\begingroup$ Also, I came up with an algorithm for computing chromatic polynomials that has a better running time than that employed by MATLAB's MuPad notebook. This is on account of better average branching of my algorithm. Do you have any suggestions of chromatic polynomial computation algorithms with which I can compare my algorithm? $\endgroup$ – Victor Rielly Mar 26 '16 at 21:59
To be taken seriously as a competitor you should be able to perform well on at least some of the difficult graph classes collected by Adolfo Piperno.

$\begingroup$ I believe igraph has C implementation of bliss and vf2, (there is link in the other answer). $\endgroup$ – joro Mar 27 '16 at 11:11

$\begingroup$ Is any of these provably subexponential? Not asking if they are significantly faster than subexponential almost always. $\endgroup$ – joro Mar 27 '16 at 11:59

1$\begingroup$ @joro: No, they are exponential in the worst case. $\endgroup$ – Brendan McKay Mar 27 '16 at 22:47

$\begingroup$ I'd also link the paper B. D. McKay, A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation, 60, 94112 (2014) for a recent comparison of these (except VF2, it seems). $\endgroup$ – Janne Kokkala Mar 30 '16 at 5:41

2$\begingroup$ @Victor: Random graphs are too easy. A better way to seek false negatives is to take graphs from Piperno's collection and form two random relabellings of them. $\endgroup$ – Brendan McKay Apr 17 '16 at 23:17
To compare your implementation with others, I would recommend to benchmark it against sage
,igraph
and McKay's canonical labelling (IIRC part of the nauty
package). The last two are optional packages in sage, so probably installing sage (possibly in a virtual machine) is the easiest way.

$\begingroup$ Don't forgett bliss: tcs.hut.fi/Software/bliss $\endgroup$ – Max Horn Mar 26 '16 at 18:46

$\begingroup$ @MaxHorn igraph implements bliss in case it is the same algorithm: igraph.org/c/doc/igraphIsomorphism.html $\endgroup$ – joro Mar 27 '16 at 5:48