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
[topological-boost][topological-wiki]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]