Union, intersection, etc. (?) based on an attribute

Bug #284380 reported by Gábor Csárdi
6
This bug affects 1 person
Affects Status Importance Assigned to Milestone
igraph
In Progress
High
Gábor Csárdi

Bug Description

At least, there should be methods for union and intersection, based on a vertex attribute.

Changed in igraph:
assignee: nobody → gabor.csardi
importance: Undecided → High
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote :

We have some R code now in the 0.6-main tree, contributed by Magnus Torfason

Changed in igraph:
milestone: none → 0.7
Changed in igraph:
status: New → In Progress
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote :

After some failed attempts, as I see these are the possible solutions to this issue:

1. Extend/redesign the attribute handler to make it more flexible, because right now we cannot express that we are merging and combining attributes from multiple graphs, possibly with renaming them.

This is not very clean, a bigger piece of work, and unclear where else we could actually use the new, fairly difficult attribute API functions.

-------------------------------

2. Implement the whole thing in R/Python, independently of the C level. This is not really the igraph way, but attributes are probably not really used from C, anyway. Also, it might be slower. The good thing is that for R the code by Magnus is a very good starting point.

-------------------------------

3. Probably the winner. Add an optional argument to the C functions, that allows the tracking of the edges. Everything everything else in R/Python.

E.g. for intersection a possible implementation might do the following:
    1) in R, delete vertices that are not present in all graphs (based on named, obviously)
    2) permute the vertices in these subgraphs, so that the same symbolic vertices have the same internal ids
    3) call the plain C intersection function, this would return the mapping for tracking the edges
    4) copy and rename all the graph attributes to the result graph
    5) copy and rename all vertex attributes to the result graph, this is easy, because the vertex ids map to names the same way in all permuted subgraphs .
    6) copy and rename all edge attributes to the result graph, based on the tracking information returned by the C function.

Revision history for this message
Gábor Csárdi (gabor.csardi) wrote : Continue on github

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/20

To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.