How do I reorder vertices in a graph?

Question

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.

Answer 1

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.

Answer 2

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},
  mat = UpperTriangularize@(List @@@ AdjacencyMatrix@g);
  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.