Re: [igraph] New igraph feature - shrink graph

[Gábor Csárdi]

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
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM