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$
$\endgroup$
1
-
$\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 RiellyMar 26, 2016 at 21:59
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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$– joroMar 27, 2016 at 11:11
-
$\begingroup$ Is any of these provably sub-exponential? Not asking if they are significantly faster than sub-exponential almost always. $\endgroup$– joroMar 27, 2016 at 11:59
-
1$\begingroup$ @joro: No, they are exponential in the worst case. $\endgroup$ Mar 27, 2016 at 22:47
-
$\begingroup$ I'd also link the paper B. D. McKay, A. Piperno, Practical graph isomorphism, II, Journal of Symbolic Computation, 60, 94-112 (2014) for a recent comparison of these (except VF2, it seems). $\endgroup$ Mar 30, 2016 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$ Apr 17, 2016 at 23:17
$\begingroup$
$\endgroup$
2
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 HornMar 26, 2016 at 18:46
-
$\begingroup$ @MaxHorn igraph implements bliss in case it is the same algorithm: igraph.org/c/doc/igraph-Isomorphism.html $\endgroup$– joroMar 27, 2016 at 5:48