Merging Vertices of a Graph and adding up the edges weights

Question

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

vertex = {a, b, c, d, e}
SeedRandom[1]
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"]

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?

Answer 1

mergeV[g_, v1_, v2_] := Graph[#[[1]], EdgeWeight -> #[[2]], EdgeLabels -> "EdgeWeight", 
      VertexLabels -> Placed["Name", Center], VertexSize -> 0.3] &@
 Transpose[
  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]

Edit

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

Answer 2

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.

Example

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
    ]

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]]

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

IGWeightedSimpleGraph[contracted, style]