8
$\begingroup$

I think there may be two bugs in the VertexContract function:

1) The updated graph does not include reasonable edgeweights 2) The function does not actually reduce the number of vertices in the graph. If I have n vertices, and I merge m of them, I would expect to have n-m+1 vertex after the operation.

Let me run through a simple example. In the following a simple graph is built:

gr = { {"a" \[DirectedEdge] "b", 1000}, {"b" \[DirectedEdge] "c", 2000}, {"c" \[DirectedEdge] "d", 3000}, {"d" \[DirectedEdge] "a", 4000}}

test1 = Graph[  (First[#]) & /@ gr, VertexLabels -> "Name", EdgeWeight -> (Last[#] & /@ gr), EdgeLabels -> "EdgeWeight"]

The graph, then, is:

Graph With weights

I now wish to merge vertices a and b:

test2 = VertexContract[test1, {"a", "b"}]

which gives me the following graph:

enter image description here

Now, as you can see, the edge weights are now strangely set to all 1's, even on the c -> d edge that is not modified.

Normal[WeightedAdjacencyMatrix[test2]  ]

Yields

{{0, 1, 0, 0}, {0, 0, 0, 1}, {0, 0, 0, 0}, {1, 0, 0, 0}}

Clearly showing that:

  • There is one vertex too many: There should be three, but there are 4 (including a phantom one with all 0's in the weights)
  • The weights are all reduced to 1 for some reason.

If I do

VertexList[test2]

I get

{"c", "d", "a", 1}

There is a phantom node lying around, as you can see in the graph above and in the vertex list. I had expected {c, d, 1}.

Are these bugs? Is the new vertex always added as the last one in the vertex list? Are there workarounds?

$\endgroup$
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – user9660 Dec 31 '14 at 5:37
6
$\begingroup$

1) is not a bug. It's a missing feature. There should be a way to decide how to combine the weights of edges (and vertices) when contracting vertices.

2) looks like a bug (from your description), but it doesn't seem to be present in M11.2 anymore.

Here's how to handle (1) using the IGraph/M package.

Consider this test graph:

style = {VertexLabels -> "Name", EdgeLabels -> "EdgeWeight"};
g = Graph[{1 -> 2, 2 -> 3, 3 -> 4, 4 -> 1, 1 -> 3}, 
  EdgeWeight -> {2, 3, 4, 5, 6}, style]

enter image description here

Let's contract vertices 1 and 2 using the IGVertexContract function. If we turn off self-loop and multi-edge removal, the edge ordering will be strictly preserved. This allows us to manually re-add edge weights, but we will end up with a multigaph.

gc = IGVertexContract[g, {{1, 2}}, SelfLoops -> True, MultiEdges -> True, 
         EdgeWeight -> IGEdgeProp[EdgeWeight][g]]

enter image description here

Now we merge parallel edges and add up their weights:

IGWeightedSimpleGraph[gc, style, SelfLoops -> False]

enter image description here

IGWeightedSimpleGraph can also combine weights using other combiner functions (e.g. multiply them instead of adding them up). See its second argument.

| improve this answer | |
$\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.