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) [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]