2
$\begingroup$

It appears that when I use EdgeContract on an undirected graph, the vertex that is the result of contracting an edge is always named the smaller of the two vertices. So

VertexList@EdgeContract[g, UndirectedEdge[1,3]]

will no longer contain the vertex 3. Is it guaranteed anywhere in the Mathematica documentation that this will always be the behavior of EdgeContract (at least on an undirected graph where we contract a single vertex)? I couldn't find any mention of this on the documentation page for EdgeContract. I would hate to be surprised by some subtly in how EdgeContract is implemented where it renames the vertices some other way.

$\endgroup$
2
$\begingroup$

Yes, it is always the case that EdgeContract replaces the vertices appearing in the contracted edges with the "smallest" vertex.

The function EdgeContract calls the function GraphComputation`GraphContractDump`edgeContract which takes the Union of the vertices appearing in the contracted edges (see the highlighted lines below) and calls VertexContract,

Mathematica graphics

and

Mathematica graphics

Example:

VertexList[EdgeContract[Graph[{1 <-> 2, 3 <-> 1, 1 <-> 4, 1 <-> 5, 1 <-> 6, 1 <-> 7, 
    2 <-> 3, 2 <-> 7, 3 <-> 4, 5 <-> 4, 5 <-> 6, 6 <-> 7}],
  {UndirectedEdge[6, 7], UndirectedEdge[5, 4]}]]

{1, 2, 3, 4}

Temporarily replacing Union with DeleteDuplicates we get

Block[{Union = DeleteDuplicates}, 
 VertexList[EdgeContract[Graph[{1 <-> 2, 3 <-> 1, 1 <-> 4, 1 <-> 5, 1 <-> 6, 1 <-> 7, 
     2 <-> 3, 2 <-> 7, 3 <-> 4, 5 <-> 4, 5 <-> 6, 6 <-> 7}],  
    {UndirectedEdge[6, 7], UndirectedEdge[5, 4]}]]]

{1, 2, 3, 6}

Note: See the answers by Simon Woods and Taliesin Beynon in Spelunking tools for useful ways to get the definitions of Mathematica functions.

$\endgroup$
  • $\begingroup$ Wow. Thank you very much. $\endgroup$ – Mike Pierce Mar 2 '16 at 17:07
  • $\begingroup$ @mapierce271, my pleasure. Thank you for the Accept. $\endgroup$ – kglr Mar 2 '16 at 17:10

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.