add partial topo test

2 files changed, 109 insertions, 75 deletions

diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index 33e1f3fa7..3d5a0aede 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -38,6 +38,65 @@ function test_topo_sort(t)
     end
 end
 
+function test_paritail_topo_sort(t)
+    local function partiail_topo_sort(dag)
+        dag:partial_topo_sort_reset()
+
+        local order_vertices = {}
+        local batch_size = math.huge
+        local batch, has_cycle = dag:partial_topo_sort_next(batch_size)
+        while #batch > 0 do
+            for _, v in ipairs(batch) do
+                table.insert(order_vertices, v)
+            end
+            batch, has_cycle = dag:partial_topo_sort_next(batch_size)
+
+            if has_cycle then
+                break
+            end
+        end
+
+        return order_vertices, has_cycle
+    end
+
+    local edges = {
+        {0, 5},
+        {0, 2},
+        {0, 1},
+        {3, 6},
+        {3, 5},
+        {3, 4},
+        {5, 4},
+        {6, 4},
+        {6, 0},
+        {3, 2},
+        {1, 4},
+    }
+    local dag = graph.new(true)
+    for _, e in ipairs(edges) do
+        dag:add_edge(e[1], e[2])
+    end
+    local order_path = partiail_topo_sort(dag)
+    local orders = {}
+    for i, v in ipairs(order_path) do
+        orders[v] = i
+    end
+    for _, e in ipairs(edges) do
+        t:require(orders[e[1]] < orders[e[2]])
+    end
+
+    dag = dag:reverse()
+    order_path = partiail_topo_sort(dag)
+    orders = {}
+    for i, v in ipairs(order_path) do
+        orders[v] = i
+    end
+    for _, e in ipairs(edges) do
+        t:require(orders[e[1]] > orders[e[2]])
+    end
+end
+
+
 function test_find_cycle(t)
     local edges = {
         {9, 1},
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua
index 448eebb88..496bffeba 100644
--- a/xmake/core/base/graph.lua
+++ b/xmake/core/base/graph.lua
@@ -122,15 +122,15 @@ function graph:remove_vertex(v)
         end
 
         -- reset partial topological sort state since graph structure changed
-        self:partial_topo_sort_reset()
+        self._partial_topo_dirty = true
     end
 end
 
 -- check if there's a cycle in the remaining unprocessed nodes
 function graph:_check_cycle_in_remaining()
     -- if all remaining nodes have in-degree > 0, we have a cycle
-    if self._topo_remaining_count > 0 and self._topo_remaining_count == self._topo_non_zero_indegree_count then
-        self._topo_has_cycle = true
+    if self._partial_topo_remaining_count > 0 and self._partial_topo_remaining_count == self._partial_topo_non_zero_indegree_count then
+        self._partial_topo_has_cycle = true
         return true
     end
     return false
@@ -138,13 +138,14 @@ end
 
 -- reset partial topological sort state
 function graph:partial_topo_sort_reset()
-    self._topo_in_progress = false
-    self._topo_in_degree = nil
-    self._topo_queue = nil
-    self._topo_processed = nil
-    self._topo_has_cycle = nil
-    self._topo_remaining_count = nil
-    self._topo_non_zero_indegree_count = nil
+    self._partial_topo_in_progress = false
+    self._partial_topo_in_degree = nil
+    self._partial_topo_queue = nil
+    self._partial_topo_processed = nil
+    self._partial_topo_has_cycle = nil
+    self._partial_topo_remaining_count = nil
+    self._partial_topo_non_zero_indegree_count = nil
+    self._partial_topo_dirty = false
 end
 
 -- get next batch of nodes in topological order with limit
@@ -168,19 +169,23 @@ function graph:partial_topo_sort_next(limit)
         return {}, false
     end
 
+    if self._partial_topo_dirty then
+        self:partial_topo_sort_reset()
+    end
+
     limit = limit or math.huge
 
     -- check if we already detected a cycle
-    if self._topo_has_cycle then
+    if self._partial_topo_has_cycle then
         return {}, true
     end
 
     -- initialize topological sort state if not already in progress
-    if not self._topo_in_progress then
+    if not self._partial_topo_in_progress then
         -- calculate in-degree for each vertex
-        self._topo_in_degree = {}
+        self._partial_topo_in_degree = {}
         for _, v in ipairs(self:vertices()) do
-            self._topo_in_degree[v] = 0
+            self._partial_topo_in_degree[v] = 0
         end
 
         -- count incoming edges for each vertex
@@ -190,56 +195,56 @@ function graph:partial_topo_sort_next(limit)
                 for _, e in ipairs(edges) do
                     if e:from() == v then
                         local w = e:to()
-                        self._topo_in_degree[w] = (self._topo_in_degree[w] or 0) + 1
+                        self._partial_topo_in_degree[w] = (self._partial_topo_in_degree[w] or 0) + 1
                     end
                 end
             end
         end
 
         -- initialize queue with vertices that have no incoming edges
-        self._topo_queue = queue.new()
+        self._partial_topo_queue = queue.new()
         for _, v in ipairs(self:vertices()) do
-            if self._topo_in_degree[v] == 0 then
-                self._topo_queue:push(v)
+            if self._partial_topo_in_degree[v] == 0 then
+                self._partial_topo_queue:push(v)
             end
         end
 
         -- track processed vertices
-        self._topo_processed = hashset.new()
-        self._topo_in_progress = true
+        self._partial_topo_processed = hashset.new()
+        self._partial_topo_in_progress = true
 
         -- track counts for efficient cycle detection
-        self._topo_remaining_count = #self:vertices()
-        self._topo_non_zero_indegree_count = self._topo_remaining_count - self._topo_queue:size()
+        self._partial_topo_remaining_count = #self:vertices()
+        self._partial_topo_non_zero_indegree_count = self._partial_topo_remaining_count - self._partial_topo_queue:size()
 
         -- quick cycle detection: if no nodes have zero in-degree, we have a cycle
-        if self._topo_queue:empty() and self._topo_remaining_count > 0 then
-            self._topo_has_cycle = true
+        if self._partial_topo_queue:empty() and self._partial_topo_remaining_count > 0 then
+            self._partial_topo_has_cycle = true
             return {}, true
         end
     end
 
     -- return empty batch if queue is empty (all processed or cycle detected)
-    if self._topo_queue:empty() then
+    if self._partial_topo_queue:empty() then
         -- check if all vertices were processed
-        local processed_count = self._topo_processed:size()
-        self._topo_has_cycle = processed_count ~= #self:vertices()
+        local processed_count = self._partial_topo_processed:size()
+        self._partial_topo_has_cycle = processed_count ~= #self:vertices()
 
         -- if this is the first call and we detect a cycle, mark as complete
         if processed_count == 0 then
-            self._topo_in_progress = false
+            self._partial_topo_in_progress = false
         end
 
-        return {}, self._topo_has_cycle
+        return {}, self._partial_topo_has_cycle
     end
 
     -- collect up to 'limit' nodes with zero in-degree
     local batch = {}
-    while not self._topo_queue:empty() and #batch < limit do
-        local v = self._topo_queue:pop()
+    while not self._partial_topo_queue:empty() and #batch < limit do
+        local v = self._partial_topo_queue:pop()
         table.insert(batch, v)
-        self._topo_processed:insert(v)
-        self._topo_remaining_count = self._topo_remaining_count - 1
+        self._partial_topo_processed:insert(v)
+        self._partial_topo_remaining_count = self._partial_topo_remaining_count - 1
     end
 
     -- update in-degrees based on the nodes in this batch
@@ -249,15 +254,15 @@ function graph:partial_topo_sort_next(limit)
             for _, e in ipairs(edges) do
                 if e:from() == v then
                     local w = e:to()
-                    self._topo_in_degree[w] = self._topo_in_degree[w] - 1
+                    self._partial_topo_in_degree[w] = self._partial_topo_in_degree[w] - 1
 
                     -- update non-zero in-degree count
-                    if self._topo_in_degree[w] == 0 then
-                        self._topo_non_zero_indegree_count = self._topo_non_zero_indegree_count - 1
+                    if self._partial_topo_in_degree[w] == 0 then
+                        self._partial_topo_non_zero_indegree_count = self._partial_topo_non_zero_indegree_count - 1
 
                         -- if in-degree becomes zero, add to queue for next batch
-                        if not self._topo_processed:has(w) then
-                            self._topo_queue:push(w)
+                        if not self._partial_topo_processed:has(w) then
+                            self._partial_topo_queue:push(w)
                         end
                     end
                 end
@@ -271,17 +276,17 @@ function graph:partial_topo_sort_next(limit)
     end
 
     -- if queue is now empty and all vertices processed, reset state
-    if self._topo_queue:empty() then
-        local processed_count = self._topo_processed:size()
+    if self._partial_topo_queue:empty() then
+        local processed_count = self._partial_topo_processed:size()
         if processed_count == #self:vertices() then
-            self._topo_in_progress = false
+            self._partial_topo_in_progress = false
         else
             -- if queue is empty but we still have unprocessed nodes, we have a cycle
-            self._topo_has_cycle = true
+            self._partial_topo_has_cycle = true
         end
     end
 
-    return batch, self._topo_has_cycle
+    return batch, self._partial_topo_has_cycle
 end
 
 -- topological sort, use kahn's algorithm
@@ -292,34 +297,6 @@ end
 -- add_edge(b, c) -- b depend on c
 --
 -- it will return {c, b, a}
---[[
-function graph:topo_sort()
-    if not self:is_directed() then
-        return
-    end
-
-    -- reset partial sort state to ensure we start fresh
-    self:partial_topo_sort_reset()
-
-    local order_vertices = {}
-    local batch_size = math.huge  -- no limit, get all at once
-
-    -- get all nodes in one go
-    local batch, has_cycle = self:partial_topo_sort_next(batch_size)
-    while #batch > 0 do
-        for _, v in ipairs(batch) do
-            table.insert(order_vertices, v)
-        end
-        batch, has_cycle = self:partial_topo_sort_next(batch_size)
-
-        -- quick exit if cycle is detected
-        if has_cycle then
-            break
-        end
-    end
-
-    return order_vertices, has_cycle
-end]]
 function graph:topo_sort()
     if not self:is_directed() then
         return
@@ -352,10 +329,8 @@ function graph:topo_sort()
         end
     end
 
-    -- result list for topologically sorted vertices
-    local order_vertices = {}
-
     -- process queue
+    local order_vertices = {}
     while not queue:empty() do
         -- remove a vertex with no incoming edges
         local v = queue:pop()
@@ -457,7 +432,7 @@ function graph:add_edge(from, to)
     table.insert(self._edges, e)
 
     -- reset partial topological sort state since graph structure changed
-    self:partial_topo_sort_reset()
+    self._partial_topo_dirty = true
 end
 
 -- has the given edge?