diff options
| -rw-r--r-- | xmake/core/base/graph.lua | 26 |
1 files changed, 26 insertions, 0 deletions
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua index b3d368e13..c4b28cd37 100644 --- a/xmake/core/base/graph.lua +++ b/xmake/core/base/graph.lua @@ -106,6 +106,32 @@ function graph:remove_vertex(v) end end +-- topological sort +function graph:topological_sort() + local marked = {} + for _, v in ipairs(self:vertices()) do + marked[v] = false + end + local order_vertices = {} + local function graph_topological_sort_dfs(v) + marked[v] = true + local edges = self:adjacent_edges(v) + if edges then + for _, e in ipairs(edges) do + local w = e:other(v) + if marked[w] == false then + graph_topological_sort_dfs(w) + end + end + end + table.insert(order_vertices, v) + end + for _, v in ipairs(self:vertices()) do + graph_topological_sort_dfs(v) + end + return order_vertices +end + -- get edges function graph:edges() return self._edges |