1
$\begingroup$

I run into some unexpected behaviour of GraphIntersection and GraphDifference. Behaviour is the same for both so the example is only on the GraphIntersection:

Suppose I have two lists of directed edges, forming a cycle:

cycle1 = {a \[DirectedEdge] b, b \[DirectedEdge] c, c \[DirectedEdge] d, d \[DirectedEdge] e, e \[DirectedEdge] f, f \[DirectedEdge] g, g \[DirectedEdge] h, h \[DirectedEdge] a};

cycle2 = {g \[DirectedEdge] c, c \[DirectedEdge] d, d \[DirectedEdge] e, e \[DirectedEdge] f, f \[DirectedEdge] g};

I construct two graphs and I want to select the Intersection between them. This seems to work only for the edges and not for the vertices!

GraphIntersection[Graph[cycle1], Graph[cycle2]] // EdgeList
GraphIntersection[Graph[cycle1], Graph[cycle2]] // VertexList

(* Out:

{c \[DirectedEdge] d, d \[DirectedEdge] e, e \[DirectedEdge] f, f \[DirectedEdge] g}

{a, b, c, d, e, f, g, h}

*)

I would have expected bahaviour identical to the approach of first intersecting the edges and then constructing a graph:

Graph[Intersection[cycle1, cycle2]] // EdgeList

Graph[Intersection[cycle1, cycle2]] // VertexList

(* Out:
{c \[DirectedEdge] d, d \[DirectedEdge] e, e \[DirectedEdge] f, f \[DirectedEdge] g}

{c, d, e, f, g}
*)

Please note the vertices are correct in the last example, the first example, all vertices are listed.

Could anyone explain the reason behind this?

$\endgroup$
2
$\begingroup$

From the documentation on GraphIntersection > Details and Options:

enter image description here

Similarly, GraphDifference > Details and Options

enter image description here

In both cases, the vertex set of the graph produced by the two functions is the Union of the vertex sets of the input graphs.

$\endgroup$
  • $\begingroup$ Ah, I read that but only now I realise that this is what it means. Thanks! Do you have any idea what the rationale is behind taking the Union of both the vertex sets vs taking the Intersection? It seems to me redundant somehow... $\endgroup$ – Sander Oct 10 '14 at 5:34
  • $\begingroup$ @Sander, i don't know why; not familiar enough with graph theory to hazard a guess. $\endgroup$ – kglr Oct 10 '14 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.