Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  rm -rf 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
2  
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. –  rm -rf 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

2 Answers 2

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}

Mathematica graphics

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

Mathematica graphics

I have no idea how to preserve the edge function.

share|improve this answer
    
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},
  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]

EdgeList issue with GridGraph

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]

EdgeList issue with RandomGraph

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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