Re: [igraph] New igraph feature - shrink graph

[Tom Gregorovic]

On Fri, Jun 5, 2009 at 10:19 AM, Gábor Csárdi <address@hidden> wrote:
> Tom,
>
> I am sorry for the delay.
>
> On Wed, Jun 3, 2009 at 12:17 PM, Tom Gregorovic<address@hidden> wrote:
>> Hi,
>> I plan to implement function for igraph that would shrink graph
>> according to vertex membership to give a global point of view on the
>> network. The same feature is for example in Pajek.
>
> Great!
>
>> I want to consult it before I start.
>> First thing I would need is function that will reindex membership
>> vector to have member IDs continuous starting from 0, to match
>> vertices in shrunken graph. Is this function somewhere in igraph
>> already implemented?
>
> Not as a separate function, but it is really just a couple of lines, e.g.
>
>  for (remaining_vertices=0, i=0; i<no_of_nodes; i++) {
>    if (VECTOR(vertex_recoding)[i]==0) {
>      VECTOR(vertex_recoding)[i]=remaining_vertices+1;
>      remaining_vertices++;
>    } else {
>      VECTOR(vertex_recoding)[i]=0;
>    }
>  }
>
> This keeps the vertices for which vertex_recoding is not zero and
> creates a mapping in place (i.e. in vertex_recoding) for the vertices
> that are kept. Something similar would work for you, probably.
>
>> Vertices with one member ID (-1 as default) set
>> via parameter should be considered not to be shrunken (will get unique
>> ID in reindex function).
>> Second thing is what method to use for constructing shrunken graph.
>> The simple way would be to create empty graph with vertices according
>> to number of unique member IDs and then add edge by edge. One question
>> is if it would add multiple edges.
>
> Probably yes. It is easier to add them than explicitly check for them.
> So, basically, you just create your mapping of vertex ids and then go
> over all edges and rewrite them according to the mapping.
>
>> The function should also return which vertices were shrunken to which
>> vertex (as vector of vector?) and similar thing for edges (in case of
>> merging multiple edges).
>
> A convenient way to do this (I mean, convenient for the user of the
> function) is that it is allowed to supply null pointers, and then
> these are not calculated.
>
> Btw. please implement it against the 0.6-main tree on Launchpad. Thanks.
>
> Tell me if you need more input, best,
> Gabor
>
>> Thank you in advance for your feedback.
>>
>> Regards,
>> Tom Gregorovic
>>

Hi,
I finally made it. Not sure if I haven't done any glitch there,
because I am not so familiar with C.
The first function igraph_membership_reindex is more auxilliary, but
maybe it would be also useful somewhere else.

Regards,
Tom Gregorovic

shrink.c
Description: Text Data