I have a Weighted Graph of g which looks like this.

vertex = {a, b, c, d, e}
g = Graph[#[[1]] -> #[[2]] & /@ Permutations[vertex, {2}], 
VertexLabels -> Placed["Name", Center], VertexSize -> 0.3, 
EdgeWeight -> 
RandomReal[{10, 20}, 
Count[#[[1]] -> #[[2]] & /@ Permutations[vertex, {2}], _]], 
EdgeLabels -> "EdgeWeight"]

enter image description here

Could you please help me to merge two or even more vertices from g (Please just g I used Permutations just to build a graph), in the way that in the end, I have a graph with added up the weights of the previous edges.For example, if vertices a and b merged together, in new vertex all of weights from old edges added up together to have new edges weights with connected vertices?


2 Answers 2

mergeV[g_, v1_, v2_] := Graph[#[[1]], EdgeWeight -> #[[2]], EdgeLabels -> "EdgeWeight", 
      VertexLabels -> Placed["Name", Center], VertexSize -> 0.3] &@
  Transpose[{EdgeList[g], PropertyValue[g, EdgeWeight]}] /. 
     {v1-> new, v2 -> new} /. {new \[DirectedEdge] new, x_} -> Sequence[] //. 
     {a___, {new \[DirectedEdge] x_, k1_}, b___, {new \[DirectedEdge] x_, k2_}, c___} -> {a, {new \[DirectedEdge] x, k1 + k2}, b, c} //. 
     {a___, {x_ \[DirectedEdge] new, k1_}, b___, {x_ \[DirectedEdge] new, k2_}, c___} -> {a, {x \[DirectedEdge] new, k1 + k2}, b, c}]

mergeV[g, a, b]

Mathematica graphics


Also, using the adjacency matrix:

m = WeightedAdjacencyMatrix[g];
{f1, f2} = VertexIndex[g, #] & /@ {a, b};
m[[f2]] += m[[f1]];
m[[All, f2]] += m[[All, f1]];
m = Delete[Transpose[Delete[m, f1]], f1] + SparseArray[{{i_, i_} -> Infinity}, Length@m -1 {1, 1}];
WeightedAdjacencyGraph[(Delete[VertexList@g /. b -> new, f1]), m, 
             VertexLabels -> Placed["Name", Center], EdgeLabels -> "EdgeWeight", VertexSize -> 0.3]

For the operations on rows and columns see this

  • $\begingroup$ But probably using VertexOutComponent and VertexInComponent is the best way to go $\endgroup$ Oct 3, 2013 at 16:35
  • $\begingroup$ Great!!!!You got me absolutely right!!Thanks.That is exactly what I was looking for!!! $\endgroup$
    – Alex
    Oct 3, 2013 at 16:58
  • $\begingroup$ Coule you please also do that with your mentioned commands? $\endgroup$
    – Alex
    Oct 3, 2013 at 17:05

IGraph/M has functionality to make it easy.

IGVertexContract can preserve all edges of the original graph with the same ordering, even if this creates multigraphs. We can use this to transfer the original weights to the new graph after vertex contraction.

IGWeightedSimpleGraph will merge parallel edges (edges connecting the same vertices) and will combine their weights using a customizable combiner function. The default is to add them up.

These functions are partially implemented in C and C++, so they are quite fast.


Options to achieve the styling you used:

style = {EdgeLabels -> "EdgeWeight", VertexSize -> Large, VertexLabels -> Placed["Name", Center]};

Build the graph using IGShorthand:

g = IGShorthand["A:B:C:D:E <-> A:B:C:D:E", 
      EdgeWeight -> RandomInteger[{10, 20}, 2 Binomial[5, 2]], style

enter image description here

Contract vertices "A" and "E". To maintain the edge count and edge ordering of the original graph, we must explicitly turn off self-loop and multi-edge removal.

contracted = 
 IGVertexContract[g, {{"A", "E"}}, SelfLoops -> True, MultiEdges -> True,
  EdgeWeight -> IGEdgeProp[EdgeWeight][g]]

enter image description here

Now merge those parallel edges and re-style the graph:

IGWeightedSimpleGraph[contracted, style]

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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