randesu algorithm speedup

[Eric Weese]

In igraph_motifs_randesu_no() and other related functions it looks like currently each subgraph of size N is enumerated N times, and then the correct count is obtained by dividing the total number counted by N. This division is the line

*no /= size;

It seems like it would be faster to only count each subgraph once, which would also match the original specification of the RANDESU algorithm. It looks to me like this could be done by removing the

added[father] -= 1;

and

*no /= size;

lines. No changes other than deleting these two lines are necessary. It seems like the time required should be 1/N of the old time required.

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

Thanks for your report!

I'll need to look at this more carefully, because I already forgot the details of the algorithm and the implementation. Your fix seems to work when the cut probabilities are zero. If they are not zero, then some more changes are needed....

Will fix it asap. Thanks again!

[Eric Weese (eric-weese)]

I think you could just force the cut probability to zero at the first level, and you wouldn't lose much. The function actually doesn't work for sizes less than 3 (should this be an error message?), and any desired total cut probability would still be obtainable for sizes of 3 or more. I have to admit I didn't look at it carefully, but my intuition would be that everything's fine as long as there's no cutting at the first level...
-eric

On 2012/06/11, at 23:07, Gábor Csárdi wrote:

> Thanks for your report!
>
> I'll need to look at this more carefully, because I already forgot the
> details of the algorithm and the implementation. Your fix seems to work
> when the cut probabilities are zero. If they are not zero, then some
> more changes are needed....
>
> Will fix it asap. Thanks again!
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1011472
>
> Title:
> randesu algorithm speedup
>
> Status in The igraph library:
> New
>
> Bug description:
> In igraph_motifs_randesu_no() and other related functions it looks
> like currently each subgraph of size N is enumerated N times, and then
> the correct count is obtained by dividing the total number counted by
> N. This division is the line
>
> *no /= size;
>
> It seems like it would be faster to only count each subgraph once,
> which would also match the original specification of the RANDESU
> algorithm. It looks to me like this could be done by removing the
>
> added[father] -= 1;
>
> and
>
> *no /= size;
>
> lines. No changes other than deleting these two lines are necessary.
> It seems like the time required should be 1/N of the old time
> required.
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/igraph/+bug/1011472/+subscriptions

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

Fixed in revision #2848 (0.6-main).

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

Interestingly, igraph_motifs_randesu was good.....

[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/108