7
$\begingroup$

I have two graphs G1 and G2 with the same vertex set. I would like to take the union of G1 and G2 in such a way that if both G1 and G2 contain the same edge, then the union inherits both of those edges, labeled appropriately. Unfortunately, GraphUnion[G1, G2] seems to lump common edges into one. How can I accomplish my goal?

$\endgroup$
7
$\begingroup$

Update: If EdgeStyle and EdgeLabels for multi-edges are given as lists, we can use the option EdgeShapeFunction to label and style each edge individually:

graphSum = Module[{esf, styles = GroupBy[Flatten[PropertyValue[#, EdgeStyle] & /@ {##}], 
       First -> Last, Flatten],
     labels = GroupBy[Flatten[PropertyValue[#, EdgeLabels] & /@ {##}], 
       First -> Last, Flatten]},
    esf = {Dashing[{}], Text[First[labels[#2] = RotateRight[labels[#2] ]], 
        BSplineFunction[#][1/2]], 
       First[styles[#2] = RotateRight[styles[#2] ]], Arrow[#]} &;
    GraphComputation`GraphSum[##, VertexLabels -> "Name", EdgeShapeFunction -> esf]] &;

Examples:

ga = Graph[{1 -> 2}, EdgeStyle -> {_ :> Red}, 
   EdgeLabels -> {e_ :> Style[{e, "ga"}, 16, Black, Bold]}];
gb = Graph[{1 -> 2, 1 -> 2, 1 -> 2, 2 -> 3}, 
   EdgeStyle -> {_ :> Green , (1 -> 2) -> {Blue, Orange, Magenta}}, 
   EdgeLabels -> {e_ :> Style[{e, "gb"}, 16, Black, Bold], (1 -> 2) ->
      Array[Style[{#, DirectedEdge[1, 2], "gb"}, 16, Black, Bold]&, 3]}] ; 
SetProperty[graphSum[ga, gb], ImageSize -> 800]

enter image description here

SetProperty[graphSum[ga, ga, ga, gb, gb], 
 {ImageSize -> 800, VertexLabels -> Placed["Name", Center], 
  VertexShape -> Graphics[{EdgeForm[Gray], FaceForm[LightBlue], 
     Disk[{0, 0}, Offset[8]]}], AspectRatio -> 1/3}] 

enter image description here

Original answer:

GraphComputation`GraphSum gives the desired result:

g1 = Graph[{1 -> 2}];
g2 = Graph[{1 -> 2, 2 -> 3}];
GraphComputation`GraphSum[g1, g2, VertexLabels -> "Name", EdgeLabels -> "Name" ]

enter image description here

SeedRandom[1]
ga = RandomGraph[{5, 7}, DirectedEdges -> True, VertexLabels -> "Name", 
  ImageSize -> 300];
gb = RandomGraph[{10, 10},  DirectedEdges -> True, VertexLabels -> "Name",
  ImageSize -> 300];
Row[{ga, gb, HighlightGraph[GraphComputation`GraphSum[ga, gb, VertexLabels -> "Name", 
    ImageSize -> 500 ], {ga, gb}]}] 

enter image description here

$\endgroup$
3
$\begingroup$

If you have precisely the same vertices in precisely the same order (i.e. VertexList[g1] === VertexList[g2]), then you can just add the adjacency matrices.

g1 = Graph[{1, 2, 3}, {1 <-> 2}]

enter image description here

g2 = Graph[{1, 2, 3}, {1 <-> 2, 2 <-> 3}]

enter image description here

AdjacencyGraph[VertexList[g1], AdjacencyMatrix[g1] + AdjacencyMatrix[g2]]

enter image description here

Alternatively, join the edge lists. If you do this, it does not matter if the vertex lists are ordered the same. They just need to contain the same vertices.

Graph[VertexList[g1], Join[EdgeList[g1], EdgeList[g2]]]

enter image description here

$\endgroup$
  • $\begingroup$ Excellent. Is it possible to label the edges in the new graph according to which graph they came from? I.e. to inherit the edge labels that were already assigned in g1 and g2? $\endgroup$ – theQman Oct 18 '18 at 14:11
  • 3
    $\begingroup$ @theQman It's quite problematic. Unfortunately, Mathematica does not properly support multigraph properties. It doesn't even say that it doesn't support them, things just go wrong. The one exception is edge weights, which you could "abuse" for this purpose if you wanted to. $\endgroup$ – Szabolcs Oct 18 '18 at 15:49
  • 1
    $\begingroup$ @theQman Here's one discussion of the issue.. If you care about multigraphs, I suggest you contact Wolfram Support and ask them to add this feature. The only chance for it to happen is if many people ask for it (to prove that there really is a demand). $\endgroup$ – Szabolcs Oct 18 '18 at 15:51
  • $\begingroup$ Thank you. How about edge coloring? Is it possible to have color the edges according to which graph they came from, instead of using labels? $\endgroup$ – theQman Oct 18 '18 at 17:13
  • 1
    $\begingroup$ @theQman The only properties that sort of work are EdgeWeight, EdgeCapacity and EdgeCost. None of the rest do, not even EdgeStyle. There are tricks that can be used to display parallel edges with different colours but they are hacky and inconvenient. You will find many questions about this, e.g. mathematica.stackexchange.com/q/84477/12 $\endgroup$ – Szabolcs Oct 18 '18 at 20:32

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.