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

[gaborcsardi]

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

---

Imported from Launchpad using lp2gh.

• date created: 2008-10-16T12:38:42Z
• owner: gabor.csardi
• assignee: gabor.csardi
• the launchpad url was https://bugs.launchpad.net/bugs/284380

Code:

• graph.disjoint.union
• graph.union
• graph.intersection
• graph.difference
• graph.compose
• what should "+" do for named graphs? union or disjoint union?
• warning for non-unique vertex names after a disjoint union

Docs:

• graph.disjoint.union
• graph.union
• graph.intersection
• graph.difference
• graph.compose

[gaborcsardi]

(by gabor.csardi)
We have some R code now in the 0.6-main tree, contributed by Magnus Torfason

[gaborcsardi]

(by gabor.csardi)
After some failed attempts, as I see these are the possible solutions to this issue:

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.

---

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.

---

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.

[gaborcsardi]

A lot of work was done in the 0.7-ropbyname branch.