Re: [igraph] New igraph feature - shrink graph

[Gábor Csárdi]

Tom, great!

It looks good after a quick check, will have a more detailed look in a minute.

Thanks,
Gabor

On Sat, Oct 17, 2009 at 6:12 PM, Tom Gregorovic <address@hidden> wrote:
> 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
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM