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