igraph-help
[Top][All Lists]

## Re: [igraph] Graphs union

 From: Moses Boudourides Subject: Re: [igraph] Graphs union Date: Mon, 10 Oct 2011 21:07:06 +0300

I was also wondering if igraph might do this. However, what Rossano
sees as a sort of conjunction (union of graphs), I would like to see
in the dual form, as a sort of disjunction (lumping of vertices). Let
me explain what I mean, using Rossano's notation. Say we have k graphs
Gk = (Vk, Ek) such that one may define the following attributes on the
set of all vertices: for instance, a(v) = a1, for all v \in V1 and all
v \in Vk which may be identified with the vertices of V1, a(v) = a2,
for all v \in V2 other than those identified with the vertices of V1
and all other similar v \in Vk and so on. Then, the problem would be
the following (where V denotes the set of all "distinct" vertices in
the union of the Vk's): form a weighted graph G(V) = (V, F, w) such
that, for any pair of u, v \in V, one has (u, v) \in F as far as a(u)
= a(v) and (u, v) belongs to at least one Ek and the weight w(u, v) is
the number of such Ek's.

I'm not saying this might be easier to implement in igraph the way
Gabor has suggested. I'm only raising the remark on the duality of
graph conjunctions-disjunctions.

--Moses

On Mon, Oct 10, 2011 at 8:32 PM, Gábor Csárdi <address@hidden> wrote:
> On Mon, Oct 10, 2011 at 1:27 PM, Rossano Gaeta <address@hidden> wrote:
>> Il 10/10/2011 19:10, Gábor Csárdi ha scritto:
>>>
>>> Dear Rossano,
>>>
>>> it seems to me that you simply need the igraph_disjoint_union function:
>>> http://igraph.sourceforge.net/doc/html/igraph_disjoint_union.html
>>>
>>> Best,
>>> Gabor
>>
>> According to my understanding, the igraph_disjoint_union function will
>> output a graph where the set of vertices is relabeled before union so to
>> have |V| = |V1|+|V2|. In my problem a node x belonging to both V1 and V2
>> must appear only once in G but must maintain
>> all edges it had in G1 and G2. It is a sort of superposition of two graphs
>> where common vertices are fused to obtain only one node.
>
> Oh, I see. So you would need something like igraph_union(), but with
> keeping the multiple edges?
>
> One solution would be to query the edge lists of both graphs, put them
> in vectors, concatenate the vectors, and create
> a new graph. This might be even faster than igraph_union(), because it
> does not look for multiple edges.
>
> G.
>
>> Did I miss any details in the semantic of the igraph_disjoint_union
>> function?
>>
>> Rossano
>>
>> --
>> Rossano Gaeta - Associate Professor
>>
>> Dipartimento di Informatica
>> Universitŕ di Torino
>>
>>
>>
>
>
>
> --
> Gabor Csardi <address@hidden>     MTA KFKI RMKI
>
> _______________________________________________
> igraph-help mailing list