Re: [igraph] InfoMap integration

[Emmanuel Navarro]

Thanks for all this explanations !
I will try to improve my patch taking it into account.

Concerning RNG, I see how to replace infomap mechanism
(MersenneTwister.h) by igraph macros.
However, with python interface, it will make infomap called -inside
the core loop- a python function (randint I guess).
I wonder if there is no overhead with such python calls from C ?
(maybe not as randint should actually be a C function...)

Otherwise, I saw there is some unit tests with python interface, is
there some at C level ? (test directory looks odd to me...)
(It may be good to first write some tests...)

Best,
Emmanuel

On Fri, Oct 8, 2010 at 2:24 PM, Gábor Csárdi <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>