Check motif estimation

[Gábor Csárdi]

Continued from http://code.google.com/p/igraph/issues/detail?id=147

[Eric Weese (eric-weese)]

I think this is due to the code around line 421 of motifs.c (as of 0.5.3):

      if (level < size-1 &&
          !igraph_vector_empty(&adjverts) &&
          (cp==0 || RNG_UNIF01() > cp)) {
        /* yes, step down */
...

but this means if the random number is low, then we go to "else", which might get rid of additional adjverts, rather than just the one in question. Should this be

      if (level < size-1 &&
          !igraph_vector_empty(&adjverts)) {
        /* yes, step down */
        long int neifather=igraph_vector_pop_back(&adjverts);
        long int nei=igraph_vector_pop_back(&adjverts);
        IGRAPH_CHECK(igraph_stack_push(&stack, neifather));
        IGRAPH_CHECK(igraph_stack_push(&stack, nei));
        IGRAPH_CHECK(igraph_stack_push(&stack, level+1));
        if(cp==0 || RNG_UNIF01() > cp) {
          IGRAPH_CHECK(igraph_vector_push_back(&vids, nei));
...

instead?
-Eric

[Gábor Csárdi (gabor.csardi)]

Hmmm, for the first look, this should not be the problem. The 'if' should be read as
"if there we need to check the next level, and there is a vertex at the next level and (the cut probability is zero or we choose _not_ to cut), then we examine the next level"

So this looks OK to me. Not 100%, but 99%. But there is obviously a mistake somewhere......

[Gábor Csárdi (gabor.csardi)]

Oh, actually, I just got our comment, you are absolutely right, this is the problem!

Not sure about the fix yet, though, but that is secondary now, the important thing is, that the problem is indeed here.
Huge thanks and kudos for pointing it out!

[Gábor Csárdi (gabor.csardi)]

This was fixed in revision 2027, in the 0.6-main tree. Thanks a lot Eric!

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/40