LAD crashes with certain inputs #927

Open
szhorvat opened this Issue Feb 27, 2016 · 3 comments

Projects

None yet

1 participant

@szhorvat
Contributor

Here's the R version of the crash demo:

g<-make_lattice(c(4,8))
patt<-make_lattice(vcount(g))
subgraph_isomorphisms(patt,g,"lad")

This code attempts to find all Hamiltonian paths in a (4,8) grid graph. For (4,7) it doesn't crash. For (4,8) it does.

Mathematica version:

g = GridGraph[{4, 8}];
IGLADSubisomorphismCount[PathGraph@Range@VertexCount[g], g]

The crash is present in the current master branch version.

It would be reasonable to think that this is an out-of-memory crash. But the (4,5), (4,6) and (4,7) grids have 2012, 7220 and 24020 Hamiltonian paths, respectively. Thus it seems unlikely that the (4,8) one could run out of memory.

Do you have any hints on what may be going on before I test the original (unmodified) LAD code?

@szhorvat szhorvat referenced this issue in szhorvat/IGraphM Feb 27, 2016
Open

Crash in IGLADSubisomorphismCount #1

@szhorvat
Contributor

I tested the original (unmodified) LAD v1 program and it doesn't choke on the (4,8) grid graph. It quickly returns 77968 as the number of solutions.

Thus the problem must be in the igraph adaptation of LAD.

The attachments are the same graphs as above written in a format that LAD can read directly.

patt.txt
g.txt

@szhorvat
Contributor

It appears the crash may be coming form this line, but I am unable to understand how:

https://github.com/igraph/igraph/blob/master/src/lad.c#L1058

@szhorvat
Contributor

While the crash happens ensureGACallDiff, I think the bug is elsewhere and ensureGACallDiff simply receives a corrupted datastructure. I spent a lot of time on this and couldn't figure out what is going wrong, but I am even more confident that there is a difference (bug) between the original and the igraph versions of LAD. I think the following (laborious) method should work for finding the problem: 1. write a function to print the Tdomain data structure and sequentially label each printed item 2. print it in several functions which use it, both in the original and igraph LAD 3. try to figure out where they diverge and why.

I can sort of see where they diverge as the computation proceeds but not the root cause of it.

@szhorvat szhorvat referenced this issue Feb 29, 2016
Open

Update LAD #540

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment