[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[igraph] Decompose a graph into connected components

From: Dr Karl
Subject: [igraph] Decompose a graph into connected components
Date: Wed, 28 Apr 2010 07:22:39 -0700 (PDT)
User-agent: G2/1.0


   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 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, 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.

Is there an easy way to accomplish this? In the aforementioned file
igraph_decompose.c there was a commented code block which looked very
much to what I was trying to do

/* The same graph, this time with vertex attributes */
/*   igraph_vector_init_seq(&idvect, 0, igraph_vcount(&g)-1); */
/*   igraph_add_vertex_attribute(&g, "id", IGRAPH_ATTRIBUTE_NUM); */
/*   igraph_set_vertex_attributes(&g, "id", IGRAPH_VS_ALL(&g),
&idvect); */
/*   igraph_vector_destroy(&idvect); */

/*   igraph_decompose(&g, &complist, IGRAPH_WEAK, 3, 2); */
/*   for (i=0; i<igraph_vector_ptr_size(&complist); i++) { */
/*     igraph_t *comp=VECTOR(complist)[i]; */
/*     igraph_es_t es; */
/*     igraph_es_all(comp, &es); */
/*     while (!igraph_es_end(comp, &es)) { */
/*       igraph_real_t *from, *to;  */
/*       igraph_get_vertex_attribute(comp, "id", igraph_es_from(comp,
&es), */
/*                                (void**) &from, 0); */
/*       igraph_get_vertex_attribute(comp, "id", igraph_es_to(comp,
&es), */
/*                                (void**) &to, 0); */
/*       printf("%li %li\n", (long int) *from, (long int) *to); */
/*       igraph_es_next(comp, &es); */
/*     } */
/*   } */

/*   free_complist(&complist); */
/*   igraph_destroy(&g);   */

But there are some problems with this commented code (and I guess
that's the reason it is commented). I grepped throught the source
files and the igraph.info file and couldn't find any reference to:


There is, thought, a function named igraph_es_fromto(...)

So, is there any function to solve this problem?

Thank you very much.

Best regards

reply via email to

[Prev in Thread] Current Thread [Next in Thread]