6
$\begingroup$

From the documentation,

VertexContract[g, {v1, v2, ...}] contracts a collection of vertices v1, v2, ... into a single vertex of the graph g.

Let's try it:

VertexContract[CycleGraph[6], {3,4}] // EdgeList

(* {1 <-> 2, 1 <-> 6, 2 <-> 3, 5 <-> 6, 5 <-> 3} *)

Vertices 3 and 4 were contracted into a single vertex now named 3. Effectively we have a cycle on vertices 1, 2, 3, 5, 6. So far so good.

VertexContract[g, {{v1, v2, ...}, ...}] contracts several collections of vertices.

I am not getting this one. I expected

VertexContract[CycleGraph[6], {{1, 2}, {3, 4}, {5, 6}}]

to contract the pairs {1,2}, {3,4} and {5,6}, each, and get this graph:

{1 <-> 3, 3 <-> 5, 5 <-> 1}

I.e. a cycle on 1, 3, 5.

Instead I get a graph with a single vertex and no edges. Why? What does this command actually do?


I can do

Fold[VertexContract[#1, #2] &, g, {{v1, v2, ...}, ...}] 

to achieve the result I expected, but it's pretty slow when there's a lot to contract.

$\endgroup$
  • 2
    $\begingroup$ True, and surprising, this is not what one expects. Maybe the contraction of {1,2} lead to the new node three, contraction with {3,4} and after that {5,6} contracts to a single node. But this is not what I (one) would expect. $\endgroup$ – mgamer Sep 18 '16 at 22:06
  • $\begingroup$ @mgamer I need this functionality, and I need it to work fast, so I exposed the corresponding function in IGraph/M. It will be in the next release. $\endgroup$ – Szabolcs Sep 19 '16 at 15:04
  • $\begingroup$ I now had this problem, too. Making an example of the construction of the Petersen-Graph of tuples {I,j} with empty intersection to {k,l}. I did a ToString /@ VertexList[graph]... and similar for EdgeList. This than worked as expected (but up to now I did not do timing analysis - the PetersenGraph is not too large ;-) ) $\endgroup$ – mgamer Feb 15 '17 at 19:52
2
$\begingroup$

It looks as if there is no difference between passing a list of lists and the same vertices in a single list. To check this, I try a variety of random cases

test := Module[{n, m, p, q, g, list, g1, g2},
  n = 100;
  m = 300;
  p = RandomInteger[{2, 5}];
  q = RandomInteger[{2, 5}];
  g = RandomGraph[{n, m}];
  list = RandomChoice[VertexList[g], {p, q}];
  g1 = VertexContract[g, list];
  g2 = VertexContract[g, Flatten[list]];
  g1 === g2]

I have never seen the test fail

And @@ Table[test, 1000]
(* True *)

Obviously, this is not absolute proof, but if there were some subtle difference one might expect the documentation to make it a little clearer!

$\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.