add partial topo test

1 files changed, 59 insertions, 0 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},