Re: Need Graph Isomorphism Algorithm De-bunked

Mike Amling wrote :
I've coded up something I think is equivalent to what you
suggest. It works for up to 7 nodes (simply connected,
undirected, no loopback), but for 8 it only found 10126
equivalence classes, not 11117. I'll look again at the code
to see if something obvious is amiss.

My intent was to write an equivalent to the (second)
Bill Cox algorithm that you verified up to 8 nodes, except
not relying on a hash. I'd bet the problem (assuming it is
not in your implementation) is in my rendering of Bill Cox's
algorithm, not in the removal of the hash. Maybe I should
have used Bill Cox's code as a basis, rather than his text.
I'll check this in more detail.

It would help if you could give two graphs that are not
distinguished by your new code, but are distinguished by
the previous version (is it Bill Cox's?).



I notice a fun thing: when using any variant of the algorithm
to compare two graphs, we can detect with certainty when the
algorithm fails, as follow.

We use the algorithm to produce a hash for each vertex.

If these hashes are not identical within order, we have
proved the graphs are not isomorphic.

Else, we reorder both graph's matrix according to
nondecreasing hashes. If the reordered graphs are equal,
we have proved the graphs are isomorphic.

Else, the algorithm failed.


François Grieu

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. ...
    (sci.crypt)
  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ...
    (talk.origins)
  • Re: Sean PItman and nested hierarchy
    ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... Separate creation can produce any pattern whatsoever, including a nested hierarchy. ...
    (talk.origins)
  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... This is also why the average running time is not a good measure; ... isomorphism problem, where you only look at graphs with at most 400 ...
    (sci.math)
  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... create a tangled loop in the graph. ...
    (talk.origins)