graph_tool.topology.topological_sort#

graph_tool.topology.topological_sort(g)[source]#

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

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)
[27 25 23 21 19 18 16 15 14 13 10 29 11 26 28  9  8  7  4  2  3  1  0 20
 12  6 24  5 22 17]