search

fozziethebeat / S-Space

The S-Space repsitory, from the AIrhead-Research group
GNU General Public License v2.0
205 stars 106 forks source link

VF2State - backtrack assert #61

Open jumlu opened 9 years ago

jumlu commented 9 years ago

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 commented 9 years ago

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 https://github.com/fozziethebeat/S-Space/issues/61.

jumlu commented 9 years ago

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