# How do I reorder vertices in a graph?

I have a directed acyclic graph $g$, and I'd like to re-order the vertices in this graph object such that when I call

VertexList[myGraph]


the vertices appear in topologically sorted order. The naive solution is to make a new graph as follows:

myGraph = Graph[TopologicalSort[g], EdgeList[g]]


but it seems that the graph object sorts its vertices. So this method is no good.

-
Right! Thank you. – rjkaplan Jun 3 '12 at 5:00
So I still don't understand the question... The two graphs are exactly the same, except that the second has the vertices in a different order and the layout is different. Did you want the vertex order to be different but the layout to be the same? – R. M. Jun 3 '12 at 5:03
I'm not concerned about the layout. I'd like only for the second graph to have vertices in topologically sorted order. My DAG has one source and one sink, so I would want VertexList[g][[1]] to be the source of g and VertexList[g][[-1]] to be the sink. Do you have suggestions for how I might change the question to make this more clear? – rjkaplan Jun 3 '12 at 5:07
But that indeed is the case... With your code above, compare TopologicalSort[g] and VertexList[myGraph]. They're the same. The first element is the source and the last is the sink. I think you've just been looking at the values for the wrong graph. – R. M. Jun 3 '12 at 5:08
I would recommend never to rely on VertexList or EdgeList having a specific order. You can always create your own edge/vertex list with any order you like. What kind of application do you need this for? – Szabolcs Jun 4 '12 at 8:29

At least in v9 if you provide an explicit vertex list for Graph, it maintains that order of the vertices (unless you add/remove vertices or edges via e.g. VertexAdd or EdgeAdd). So your suggested method should work, with an extra caveat! A DAG might have multiple equivalent topological orders, which are not identical. Consider for example (thanks to MichaelE2 for pointing it out):

SeedRandom@3;
g = DirectedGraph[RandomGraph@{10, 15}, "Acyclic"]
g2 = Graph[TopologicalSort@g, EdgeList@g];
TopologicalSort@g
TopologicalSort@g2

{3, 1, 2, 4, 10, 5, 7, 9, 8, 6}
{1, 2, 3, 4, 10, 5, 7, 9, 8, 6}


Both sortings are correct. Unfortunately, since we don't know how vertices are sorted inside Graph, we cannot rely on that specifying a topologically sorted vertex list will result in the same order of vertices when queried by VertexList (the original problem):

 VertexList@g2 === TopologicalSort@g2   (* ==> False *)


This is because g2 lists vertices in the topological order returned by g which is not identical to the topological order returned by g2. I assume that the actual vertex ordering in Graph is based on the order of supplied vertices and edges.

## Quick and dirty solution

The solution is to feed the vertex order that is returned by TopologicalSort for a second time. I've tested it for 10000 different random seeds, it seems consistent.

SeedRandom@1;
g = DirectedGraph[RandomGraph@{10, 15}, "Acyclic"];
g2 = Graph[TopologicalSort@Graph[TopologicalSort@g, EdgeList@g], EdgeList@g];
VertexList@g2 === TopologicalSort@g2       (* ==> True  *)


With the addition, that the layout is not preserved:

{g, g2}


One can try to supply the appropriate vertex coordinates and layout method, just to realize that the edge tolerance cannot be transferred:

coord = Thread[VertexList@g -> (VertexCoordinates /. AbsoluteOptions[g, VertexCoordinates])];
g3 = Graph[TopologicalSort@g, EdgeList@g,
GraphLayout -> "LayeredDigraphEmbedding",
VertexCoordinates -> (TopologicalSort@g /. coord)];

VertexList@g3 === TopologicalSort@g3   (* ==> True *)

g3


I have no idea how to preserve the edge function.

-
Starting with SeedRandom@3, VertexList@g2 === TopologicalSort@g2 returns False for me. – Michael E2 Oct 19 '13 at 17:52
@MichaelE2 God, this is annoying! Let me figure out if there is a solution before I delete it. – István Zachar Oct 19 '13 at 18:16
I don't think that a topological sort is unique. I think that's the issue. – Michael E2 Oct 19 '13 at 18:34
@MichaelE2 Yes, I arrived to the same conclusion. Please see edit. The problem is that one cannot be sure that this will hold for all graphs and/or all future Mathematica version... – István Zachar Oct 19 '13 at 18:39
TopologicalSort@g seems to depend on the form/order of the edges (only) in g. I expect this dependency will be stable - I suspect the algorithm is fairly simple and can't be improved. So as long as you use EdgeList@g each time, the t-sort should give the same order. RandomGraph stores the edges in a SparseArray object, but Graph[v, List[..]] stores the edges as a list of pairs of positions of the vertices in v. That's why the first t-sort you do changes things, but subsequent t-sorts are stable. HTH -- comments have to be short :) – Michael E2 Oct 19 '13 at 19:24

Here is my humble contribution to that issue. Although it only works for "one way" edges but at least it works in v8.

myEdgeList[g_] := Module[{mat, edges},
edges = UndirectedEdge @@@ SortBy[Position[mat, 1], Last]]


With GridGraph:

coor[g_] := (PropertyValue[{g, #}, VertexCoordinates] & /@ VertexList[g])

g = GridGraph[{3, 3}];
GraphicsRow[Graph[#, VertexCoordinates -> coor@g, PlotLabel -> #2,
VertexLabels -> "Name", ImagePadding -> 10]&
@@@ {{EdgeList@g,"EdgeList"}, {myEdgeList@g, "myEdgeList"}},ImageSize->450]


With RandomGraph:

SeedRandom@1;
g = RandomGraph[{10, 15}, PlotLabel -> "Raw Graph"];
GraphicsRow[{g, Graph[EdgeList@g, PlotLabel -> "EdgeList"],
Graph[myEdgeList@g, PlotLabel -> "myEdgeList"]}, ImageSize -> 500]


It's working very well with GridGraph and it's inversing the RandomGraph in this case. Even if it's far to work for every kind of Graph it might help for some.

-