Re: [igraph] InfoMap integration

[Gábor Csárdi]

I thought I would continue this in the Launchpad bug tracking
comments, but actually some of this might be useful for people who
consider sending patches, so it is good have it on this mailing list
once.

Random number generators

>From 0.6 igraph uses a flexible random number generator API, which
basically means, that 1) in R it uses R's RNG (like in the past), 2)
in Python it uses Python's RNG, and 3) in C you can use any RNG you
want, possibly from an external library. (By default a good quality
built-in RNG is used in C instead of the standard libc one.)

For generating random numbers in an igraph function, you need to do
three things: 1. call RNG_BEGIN() before the first random number is
generated, 2. call RNG_END() after the last random number is generated
and 3. use the following macros to generate the actual random numbers:
RNG_INTEGER(l,h), RNG_NORMAL(m,s), RNG_UNIF(l,h), RNG_UNIF01(),
RNG_GEOM(p), RNG_BINOM(n,p), RNG_INT31(). 'l' and 'h' give the low and
high limits, other arguments give the parameters of the various
distributions.

Error handling

igraph functions use a global stack for freeing the memory when an
error happens. This means that every time one allocates memory, it
must be registered in this stack. This is done by calling
IGRAPH_FINALLY(dest, obj), the first argument is a pointer to the
destructor function to call, the second argument is a pointer to the
object to be deallocated. Every time an object is deallocated, it must
be removed from this stack, by calling IGRAPH_FINALLY_CLEAN(1). (Or
another number than '1' if more than one objects where cleanly
destroyed.) The stack is really a stack, objects must be deallocated
in reverse order of their allocation. This might seem restricting, but
in practice it almost never is.

Interrupting

To make it possible to interrupt a long calculation, you need to place
IGRAPH_ALLOW_INTERRUPTION() somewhere in your function. This call
involves some work, so don't call it too often. It is OK to do O(n)
calculations before calling it. Of course a function can only support
interruption if it uses the error handling

These are probably the most important things. Some others are progress
bar and status bar support, but most igraph functions don't support
these at the moment, and they need some improvements as well. So these
are not crucial.

We can discuss more details at the launchpad bug tracking site.

Best,
Gabor

On Thu, Oct 7, 2010 at 11:34 AM, Emmanuel Navarro <address@hidden> wrote:
> Thanks,
> I will follow this bug.
>
> The patch mainly consist of original Martin R. code.
> I modify it as less as possible...
> But of course more "igraph mechanisms" should be used.
>
> I may help for a more "clean" adaptation of this code,
> but I will need some precise requirements and advices :-).
>
> Best regards,
> Emmanuel
>
> On Thu, Oct 7, 2010 at 10:34 AM, Gábor Csárdi <address@hidden> wrote:
>> Emmanuel,
>>
>> thanks a lot, this is very useful. It is quite a big patch, so it will
>> take some time to look it over and adapt it a bit more (e.g. it should
>> use igraphs's RNGs, ideally igraph's memory allocator if possible,
>> etc.) I have opened an issue for it here:
>> https://bugs.launchpad.net/igraph/+bug/656175
>>
>> Thanks again, Best Regards,
>> Gabor
>>
>> On Wed, Oct 6, 2010 at 4:24 PM, Emmanuel Navarro <address@hidden> wrote:
>>> Hello,
>>>
>>> For my work I had to (have to) play with different community detection
>>> algorithms.
>>> So to make playing time more fun (by using python...), I have
>>> integrated InfoMap C++ code into igraph.
>>> (Infomap is a nice community detection method by Rosvall and
>>> Bergstrom: http://www.tp.umu.se/~rosvall/code.html#map)
>>>
>>> Here is the patch of this hack.
>>> It may be integrated in igraph development branch on launchpad ?
>>>
>>> Note that :
>>> - it only use the directed version of Rosvall's code (undirected
>>> version is more efficient over undirected networks, directed version
>>> can however deal with undirected graphs...),
>>> - it is based on the 0.6 branch on launchpad,
>>> - I wrote python wrapper GraphBase.community_infomap (which may need a
>>> second level method in Graph object, as for walktrap), but not the R
>>> one...
>>> - I have tested it, but not deeply, so I may introduced bugs or memory
>>> leaks (I hope I do not :-))
>>> - I have written some documentation with reference to Rosvall and
>>> Bergstrom papers and website (http://www.mapequation.org), here too it
>>> may have some mistakes,
>>> - Roswall is ok to make it publish in igraph,
>>>
>>> Sincerly yours
>>> Emmanuel
>>>
>>> ----
>>> Emmanuel Navarro
>>> PhD Studient (University of Toulouse, IRIT, RPDMP team)
>>> tel: (+33) 05 61 55 74 36
>>> email: address@hidden
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>>
>>>
>>
>>
>>
>> --
>> Gabor Csardi <address@hidden>     UNIL DGM
>>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM