VF2State - backtrack assert

[jumlu]

Hi there,

first of all, great job on porting VF2 to Java!
However, i think there is a bug in the method addPair(int,int) in edu.ucla.sspace.graph.isomorphism.VF2State.

Before incrementing coreLen (line 387), the origCoreLen should be updated:
origCoreLen = corLen

Otherwise line 497 results in an AssertionError, when trying to backtrack after more than one found matches.

Regards,
Julian

[davidjurgens]

Hi Julian,

Wow, it's actually exciting to hear that someone is interested in using
the VF2 port. :)

For the line you mentioned, we ported that code straight from the C++
code which doesn't seem to have the change to origCoreLen (
http://web.cs.ucdavis.edu/~iliast/files/SBROME_v08/VFLIB/vf2_state.cc).
Perhaps there is a bug in both implementations that has escaped notice?
It's been a while since I dug into this code so I would have to piece back
together how it all worked.

Thanks,
David

On Fri, Feb 27, 2015 at 10:13 AM, jumlu notifications@github.com wrote:

Hi there,

first of all, great job on porting VF2 to Java!
However, i think there is a bug in the method addPair(int,int) in
edu.ucla.sspace.graph.isomorphism.VF2State.

Before incrementing coreLen (line 387), the origCoreLen should be updated:
origCoreLen = corLen

Otherwise line 497 results in an AssertionError, when trying to backtrack
after more than one found matches.

Regards,
Julian

—
Reply to this email directly or view it on GitHub
#61.

[jumlu]

Hi David,

thanks for you fast reply.
I just tried to contact the author of the VF2 implementation (P. Foggia), but the mail address does not exist anymore ..
Anyway, if you or any user of this VFLib port will ever run into an AssertionError, you / he / she might remember that line ;)

I changed my code as mentioned before and doublechecked my results with other algorithms:
No more AssertionErrors and correct results :)

Cheers,
Julian