Re: [igraph] Decompose a graph into connected components

[Gábor Csárdi]

Hi,

On Wed, Apr 28, 2010 at 4:22 PM, Dr Karl <address@hidden> wrote:
> Hi,
>
>   I'm building discussion trees from raw message logs data. The fact
> is that for any given mailbox (forum), there are a number of
> discussions. I need to separate each discussion in a different graph,
> but at this momenty I create a graph with all the discussions (even
> the isolated messages with no response).
>
> In order to separate the discussions, at first I thought of coding a
> recursive function which would iterate over each node, find the
> neighbors of the node and so on, to find connected components, but
> then I realized of the existence of the igraph_decompose() function,
> which hopefully would save me some work.
> I looked in the /examples directory and found igraph_decompose.c
>
> With that function I can easily get a vector of pointers to vectors of
> edges

You mean vertices.

> to build a graph for each discussion, just what I need, but I am
> also using vertex attributes and edge attributes to write on the
> graphml the mailId, senderId, and other metrics and data. For that
> purpose I'm using the macros
> SETVANV, and their kind.
>
> The problem is that the resulting graphs after invoking the
> igraph_decompose() function have diferent ids for every vertex, which
> means that the vectors where I store the additional attributes are now
> worthless,

Something is not clear to me. Why do you keep vertex attributes in
separate vectors if you already added them to the graph?

> because I don't have a way to correlate every new vertex id
> in the separate graphs with the previous vertex id with the full graph
> with multiple connected components.

igraph_decompose() keeps vertex attributes, so I don't see what is the
problem here. I mean, you certainly have a problem if you keep your
attributes in separate vectors, independent of the graph. But this is
the whole point of having vertex attributes in igraph. You add them to
the graph (e.g. with SETVANV) and then igraph takes care about them if
the structure changes.

Alternatively, you can keep your attributes in separate vectors and
add only a (numeric of textual) vertex id to the graph as vertex
attribute. Then you can query this vertex attribute after calling
igraph_decompose on the graph, to follow the vertices.

Best,
Gabor

[...]
-- 
Gabor Csardi <address@hidden>     UNIL DGM