From 2f77dcb4ce35c909ee289bf47c3411b0aa7b0d21 Mon Sep 17 00:00:00 2001
From: ruki <waruqi@gmail.com>
Date: Thu, 28 Sep 2023 23:54:27 +0800
Subject: add topological sort for graph

---
 xmake/core/base/graph.lua | 26 ++++++++++++++++++++++++++
 1 file changed, 26 insertions(+)

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
-- 
cgit v1.3.1