Top-rated recipes tagged "toposort"http://code.activestate.com/recipes/tags/toposort/top/2012-09-27T12:21:23-07:00ActiveState Code RecipesTopological Sort (Python)
2012-09-27T12:21:23-07:00Sam Dentonhttp://code.activestate.com/recipes/users/4172262/http://code.activestate.com/recipes/578272-topological-sort/
<p style="color: grey">
Python
recipe 578272
by <a href="/recipes/users/4172262/">Sam Denton</a>
(<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/sort/">sort</a>, <a href="/recipes/tags/sorting/">sorting</a>, <a href="/recipes/tags/topological/">topological</a>, <a href="/recipes/tags/toposort/">toposort</a>).
</p>
<p>A topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG).</p>