It seems that built-in
EdgeContract function doesn't work properly with weighted graphs, to be more precise, I mean that if I'm going to contract edge $e$ which connects vertex $v_1$ with weight $a$ and vertex $v_2$ with weight $b$ I expected to obtain one vertex which has $a+b$ weight.
So I'm going to implement my own function which will behave in the mentioned way.
My idea is to perform the following steps:
- Use built-in
EdgeContractfunction to obtain a new graph which has necessary numbers of edges and vertices.
- Check which of vertices was deleted due to edge contraction and assign to another vertex weight equal to original plus weight of deleted vertex.
- Assign new list of vertex weights to a graph obtained from the output of
To implement this algorithm I wrote the following code:
contrEdge[graph_, edge_, weights_] := new_weights = weights; p1 = Flatten[Position[VertexList[graph], edge[]]]; p2 = Flatten[Position[VertexList[graph], edge[]]]; If[MemberQ[VertexList[EdgeContract[graph, edge]], edge[]] == False, new_weights[[ Flatten[Position[VertexList[new_graph], edge[]]]]] = weights[[p1]] + weights[[p2]], new_weights[[Flatten[Position[VertexList[new_graph], edge[]]]]] = weights[[p1]] + weights[[p2]] ]; new_graph = Graph[VertexList[EdgeContract[graph, edge]], EdgeList[EdgeContract[graph, edge]], VertexWeight -> new_weights];
graph_ stands for input graph object,
edge_ is for edge that we going to contract and
weights_ stands for list of original weights.
Unfortunately it gives me a lot of errors and I can't manage to debug them.
I will be very grateful if someone helps me to understand what is going wrong, correct these errors and implement the desired function. Suggestions of simpler algorithms, if they exist, are also welcome.