5
$\begingroup$

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

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?

$\endgroup$
5
$\begingroup$
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]

Mathematica graphics

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

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

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
    ]

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

$\endgroup$

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.