Re: [igraph] Intersect graphs with different vertices

[Gábor Csárdi]

Magnus, thanks a lot, I have added the functions:
http://bazaar.launchpad.net/~igraph/igraph/0.6-main/revision/1691

Best Regards,
Gabor

On Fri, Oct 30, 2009 at 5:05 PM, Magnus Torfason <address@hidden> wrote:
> Gábor Csárdi wrote:
>>
>> Magnus Torfason wrote:
>>>
>>> If I end up having to write the function, I'd be willing to share it (it
>>> seems pretty general), but it would be written in R, not in C, so I'm not
>>> sure if it would be suitable for inclusion in igraph itself (Gábor/Tamas?).
>>
>> I think we can put it in the R version. If we end up having a C
>> version later, then we will just replace it with keeping the
>> interface, so the users don't recognize anything.
>
> OK, here goes. I've attached the code I wrote for this. I separated this
> from the igraph functions by adding ".by.name" to the function names.
>
> Some of the code is self-evident, but some of the decisions require
> judgment calls. Most important is the fact that one does not always
> want to perform the same operation on vertices as edges. If an edge
> is in the result, the vertices must be in the result as well, but
> the converse is not true. So one may want to intersect the edges,
> but keep all vertices from one graph (currently supported) or from
> both (currently not supported). Function by function:
>
> * graph.intersection.by.name()
>    * Defaults to intersecting both edges and vertices
>    * Supports keeping all vertices from x
>    * Support keeping all vertex attributes from x
>    * Supports keeping all edge attributes from x
>    * Does NOT support unioning the vertices. The reason
>      is that deciding what to do with the attributes in
>      the case of union operations is a bit more complex
>
> * graph.union.by.name()
>    * Defaults to unioning both edges and vertices.
>    * Intersecting vertices while unioning edges makes
>      no sense and so is not supported
>    * Does not support keeping attributes, since deciding
>      how to handle attributes in a union operation is
>      a bit more complex
>
> * graph.difference.by.name()
>    * Defaults to differencing edges, but keeping x vertices
>    * Differencing or intersecting vertices makes no sense,
>      so it is not supported
>    * Unioning vertices makes some sense, but is not
>      supported, since deciding how to handle attributes
>      in a union operation is a bit more complex
>
> * get.vertices.as.data.frame()
> * get.edges.as.data.frame()
>    * Support functions needed for the set functions
>    * Can be configured to preserve attributes
>    * For undirected graphs, all vertex names in
>      the edge data.frame will fulfill (V1<V2)
>    * The idea is that
>        g == graph.data.frame(
>          get.edges.as.data.frame(g,TRUE),
>          is.directed(g),
>          get.vertices.as.data.frame(g,TRUE)
>        )
>     * Could be private/hidden, but also seem useful enough
>       to be public/exposed to users.
>
> * safer.merge()
>     * 'Better' merge function.
>     * Needed for the difference function
>     * Could be replaced with regular merge and some extra code
>     * Should probably be hidden
>
>
>
> Full code and examples are attached to the email. The run
> of the example code is also included below:
>
> Best regards,
> Magnus
>
> ############
>
>
>> # Load library and set parameters for better printing
>> library(igraph)
>> igraph.par("print.vertex.attributes", TRUE)
>> igraph.par("print.edge.attributes", TRUE)
>>
>> # Define input graphs
>> g1 <- graph.formula(a-b-c)
>> V(g1)$v.attr=c(1,2,3)
>> E(g1)$e.attr=c(5,7)
>> g2 <- graph.formula(b-c-d)
>>
>> # Test the functions
>> graph.intersection.by.name(g1,g2) # Vertices are intersected as well
> Vertices: 2
> Edges: 1
> Directed: FALSE
> Vertex attributes:
>    name
> [0]    b
> [1]    c
> Edges and their attributes:
>    e
> e [0] 'b' -- 'c'
>> graph.union.by.name(g1,g2)        # Vertices are unioned as well
> Vertices: 4
> Edges: 3
> Directed: FALSE
> Vertex attributes:
>    name
> [0]    a
> [1]    b
> [2]    c
> [3]    d
> Edges and their attributes:
>
> [0] 'a' -- 'b'
> [1] 'b' -- 'c'
> [2] 'c' -- 'd'
>> graph.difference.by.name(g1,g2)   # Vertices from x (g1) are used
> Vertices: 3
> Edges: 1
> Directed: FALSE
> Vertex attributes:
>    name
> [0]    a
> [1]    b
> [2]    c
> Edges and their attributes:
>    e
> e [0] 'a' -- 'b'
>>
>> # graph.intersection.by.name() has some extra parameters
>> graph.intersection.by.name(g1,g2,
> +     keep.x.vertices          = TRUE) # Keep all x vertices (only intersect
> edges)
> Vertices: 3
> Edges: 1
> Directed: FALSE
> Vertex attributes:
>    name
> [0]    a
> [1]    b
> [2]    c
> Edges and their attributes:
>    e
> e [0] 'b' -- 'c'
>>
>> graph.intersection.by.name(g1,g2,
> +     keep.x.vertices          = FALSE, # Keep all x vertices (only
> intersect edges)
> +     keep.x.vertex.attributes = TRUE, # Don't throw away V(g1) attributes
> +     keep.x.edge.attributes   = TRUE) # Don't throw away E(g1) attributes
> Vertices: 2
> Edges: 1
> Directed: FALSE
> Vertex attributes:
>    name v.attr
> [0]    b      2
> [1]    c      3
> Edges and their attributes:
>    e            e.attr
> e [0] 'b' -- 'c'      7
>>
>> # graph.difference.by.name() has some extra parameters
>> graph.difference.by.name(g1,g2,
> +     keep.x.vertex.attributes = TRUE, # Don't throw away V(g1) attributes
> +     keep.x.edge.attributes   = TRUE) # Don't throw away E(g1) attributes
> Vertices: 3
> Edges: 1
> Directed: FALSE
> Vertex attributes:
>    name v.attr
> [0]    a      1
> [1]    b      2
> [2]    c      3
> Edges and their attributes:
>    e            e.attr
> e [0] 'a' -- 'b'      5
>>
>
>
> ############
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM