2
$\begingroup$

I am guessing this will be a duplicate(it seems like a common task), but I obviously can't find the right page. I have a directed graph showing dependencies, and I want to list the vertices in an order such that for a given vertex, all vertices which leading to it appear prior to it in the list. If a vertex has no verticies leading to it, it is an entry point and has no constraints on where it is placed.

For example with the following graph, I would want an order similar to the one I provide (which I found by hand). I know that many lists satisfy these constraints, but I am just interested in finding a single solution.

enter image description here

edges = {1 -> 2, 2 -> 3, 3 -> 4, 3 -> 6, 6 -> 7, 7 -> 4, 4 -> 8, 3 -> 9, 10 -> 3};
TreePlot[edges, VertexLabeling -> True, DirectedEdges -> True]

result={1, 2, 10, 3, 6, 7, 4, 8};
$\endgroup$
4
  • $\begingroup$ Cycles will get you into trouble ... $\endgroup$ Oct 12, 2015 at 18:20
  • $\begingroup$ I think the nature of the graphs I'm working with will not allow cycles $\endgroup$
    – BenP1192
    Oct 12, 2015 at 18:24
  • 1
    $\begingroup$ You can verify that with AcyclicGraphQ. For plotting, just use Graph[edges], for this simple case, or Graph[edges, GraphLayout -> "LayeredDigraphEmbedding"] to force the right embedding for directed acyclic graphs. This is not a tree. The old LayeredGraphPlot would also do. $\endgroup$
    – Szabolcs
    Oct 12, 2015 at 19:42
  • $\begingroup$ Thanks for the tip. I wanted to have the vertexes labeled and arrows shown and I found this command did that: Graph[edges, GraphLayout -> "LayeredDigraphEmbedding", VertexLabels -> "Name", EdgeShapeFunction -> "Arrow"] $\endgroup$
    – BenP1192
    Oct 13, 2015 at 1:48

1 Answer 1

4
$\begingroup$
edges = {1 -> 2, 2 -> 3, 3 -> 4, 3 -> 6, 6 -> 7, 7 -> 4, 4 -> 8,  3 -> 9, 10 -> 3};
TopologicalSort@Graph@edges

(* {10, 1, 2, 3, 9, 6, 7, 4, 8} *)
$\endgroup$
1
  • $\begingroup$ Thanks. I knew there was bound to be a simple solution $\endgroup$
    – BenP1192
    Oct 12, 2015 at 19:27

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.