Merge branch 'dev' of https://github.com/xmake-io/xmake into dev

1 files changed, 138 insertions, 3 deletions

diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index 63095be12..fe1d63e8d 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -1,6 +1,6 @@
 import("core.base.graph")
 
-function test_topological_sort(t)
+function test_topo_sort(t)
     local edges = {
         {0, 5},
         {0, 2},
@@ -18,7 +18,7 @@ function test_topological_sort(t)
     for _, e in ipairs(edges) do
         dag:add_edge(e[1], e[2])
     end
-    local order_path = dag:topological_sort()
+    local order_path = dag:topo_sort()
     local orders = {}
     for i, v in ipairs(order_path) do
         orders[v] = i
@@ -28,7 +28,7 @@ function test_topological_sort(t)
     end
 
     dag = dag:reverse()
-    order_path = dag:topological_sort()
+    order_path = dag:topo_sort()
     orders = {}
     for i, v in ipairs(order_path) do
         orders[v] = i
@@ -38,6 +38,138 @@ function test_topological_sort(t)
     end
 end
 
+function test_paritail_topo_sort(t)
+    local function partiail_topo_sort(dag)
+        dag:partial_topo_sort_reset()
+
+        local node, has_cycle
+        local order_vertices = {}
+        while true do
+            node, has_cycle = dag:partial_topo_sort_next()
+            if node then
+                table.insert(order_vertices, node)
+                dag:partial_topo_sort_remove(node)
+            else
+                if has_cycle then
+                    raise("has cycle!")
+                end
+                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},
+        {2, 9},
+    }
+    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_paritail_topo_sort_dynamic(t)
+    local function partiail_topo_sort(dag)
+        dag:partial_topo_sort_reset()
+
+        local node, has_cycle
+        local order_vertices = {}
+        local dynamic_adjust = false
+        while true do
+            node, has_cycle = dag:partial_topo_sort_next()
+            if node then
+                if not dynamic_adjust then
+                    dag:add_edge(1, 4)
+                    dag:remove_vertex(6)
+                end
+                table.insert(order_vertices, node)
+                dag:partial_topo_sort_remove(node)
+                if not dynamic_adjust then
+                    dag:add_edge(2, 9)
+                    dynamic_adjust = true
+                end
+            else
+                if has_cycle then
+                    raise("has cycle!")
+                end
+                break
+            end
+        end
+
+        assert(#order_vertices == #dag:vertices(), "vertices count not matched, %d != %d", #order_vertices, #dag:vertices())
+        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},
+    }
+    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
+    edges = {
+        {0, 5},
+        {0, 2},
+        {0, 1},
+        -- {3, 6},
+        {3, 5},
+        {3, 4},
+        {5, 4},
+        -- {6, 4},
+        -- {6, 0},
+        {3, 2},
+        {1, 4},
+        {2, 9}
+    }
+    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},
@@ -52,5 +184,8 @@ function test_find_cycle(t)
     end
     local cycle = dag:find_cycle()
     t:are_equal(cycle, {1, 6, 0})
+
+    local _, has_cycle = dag:topo_sort()
+    t:require(has_cycle)
 end