I would like to swap labels of nodes on a directed graph.

For instance:

h = Graph[{2 \[DirectedEdge] 1, 3 \[DirectedEdge] 1, 4 -> 2, 5 -> 2}, 
  EdgeStyle -> Arrowheads[.04], 
  VertexLabels -> Placed["Name", Center], VertexSize -> 0.2, 
  VertexStyle -> White, EdgeStyle -> Blue, 
  VertexShapeFunction -> "Square"]
h = ReverseGraph[h, VertexCoordinates -> GraphEmbedding[h]]

Drop[VertexOutComponent[h, 2, 1], 1]

This code yields the out vertices of the directed graph namely 4 and 5 (dropping the vertex 2 that we start from).

How does Mathematica incorporate operations over labels such as:

Exchange the label of the starting node (2) with the minimum label of the out-vertices of 2 (i.e. 4 which is minimum among the labels of the out-vertices of 2: i.e. the minimum of the labels of nodes 4 and 5).

ETA: I found documentation on VertexReplace. However it does not give me the right outcome as it deals with Vertices, not the labels of vertices.

A more general question: these are basic constructions on graphs. I have the elementary introduction to the Wolfram Language and the Mathematica book, neither of which are comprehensive enough to deal with general graph questions. The online info is very scattered. Are there thorough introductions available to graph manipulation (labels, vertices, edges) for Mathematica that include basic constructions such as the above?

  • $\begingroup$ Is this for a graph algorithm? Will the number of vertices change during the process? If not, I suggest storing the labels in a separate vector, and when you need to visualize, you can Graph[g, VertexLabels -> Thread[VertexList[g], labelVector]] $\endgroup$
    – Szabolcs
    Feb 23, 2021 at 17:05
  • $\begingroup$ Thanks, yes it is for a graph algorithm. For instance, implementing Heapsort, where repeated pushdowns and pushups are performed creating larger heaps. The graph structure would change. I looked up Heapify to see if the code is available, but it is not (and the function does not seem to work when I call it on a permutation, but that is another matter). I need it in a more general context than Heapsort (i.e. heap creation), but the Heapsort example illustrates what I need. $\endgroup$ Feb 23, 2021 at 17:12

1 Answer 1

swapLabel[g_, v_] := Module[{vo = Rest @ VertexOutComponent[g, v, 1]}, 
 If[vo === {}, {v -> PropertyValue[{g, v}, VertexLabels]}, 
   {v -> Placed[Min[vo], Center], Min[vo] -> Placed[v, Center]}]]

SetProperty[h, VertexLabels -> swapLabel[h, 2]]

enter image description here

  • 1
    $\begingroup$ Thanks, this seems a valid answer. I will chase up the various commands I am not yet familiar with and upgrade to an answer following it. $\endgroup$ Feb 23, 2021 at 17:21
  • $\begingroup$ Ok, I see the code is adapted to work at extremal elements. I am puzzled at the command {v -> Placed[Min[vo], Center], Min[vo] -> Placed[v, Center]}. Does the first not overwrite v's label? In that case, does the second still access the correct value for v? It seems it does during the execution. Can you clarify why this is the case? Is it because v is passed in as an input to swapLabel? $\endgroup$ Feb 23, 2021 at 18:13
  • 2
    $\begingroup$ @Mike, re " the first not overwrite v's label?", no it doesn't; it just assigns Min[vo] as the label for v (if you remove the second rule Min[vo] -> Placed[v, Center], you see that the label for Min[vo] is not changed.) $\endgroup$
    – kglr
    Feb 23, 2021 at 18:34
  • $\begingroup$ thanks. Will experiment with it a little more $\endgroup$ Feb 24, 2021 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.