topological_sort

graph_tool.topology.topological_sort(g)

Return the topological sort of the given graph. It is returned as an array of vertex indices, in the sort order.

Notes

The topological sort algorithm creates a linear ordering of the vertices such that if edge (u,v) appears in the graph, then u comes before v in the ordering. The graph must be a directed acyclic graph (DAG).

The time complexity is \(O(V + E)\).

References

[topological-boost]

http://www.boost.org/libs/graph/doc/topological_sort.html

[topological-wiki]

http://en.wikipedia.org/wiki/Topological_sorting

Examples

>>> g = gt.random_graph(30, lambda: (3, 3))
>>> tree = gt.min_spanning_tree(g)
>>> g.set_edge_filter(tree)
>>> sort = gt.topological_sort(g)
>>> print(sort)
[28 27 29 26 25 24 22 21 20 19 18 16 15 14 13 11  9  8  7  3  2 10  4 17
  5  1  0 12 23  6]