fix remove vertex

2 files changed, 33 insertions, 18 deletions

diff --git a/tests/modules/graph/test.lua b/tests/modules/graph/test.lua
index a13737b6e..fe1d63e8d 100644
--- a/tests/modules/graph/test.lua
+++ b/tests/modules/graph/test.lua
@@ -110,11 +110,14 @@ function test_paritail_topo_sort_dynamic(t)
             if node then
                 if not dynamic_adjust then
                     dag:add_edge(1, 4)
-                    dag:add_edge(2, 9)
-                    dynamic_adjust = true
+                    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!")
@@ -148,8 +151,20 @@ function test_paritail_topo_sort_dynamic(t)
     for i, v in ipairs(order_path) do
         orders[v] = i
     end
-    table.insert(edges, {1, 4})
-    table.insert(edges, {2, 9})
+    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
diff --git a/xmake/core/base/graph.lua b/xmake/core/base/graph.lua
index dcb274318..658b71e73 100644
--- a/xmake/core/base/graph.lua
+++ b/xmake/core/base/graph.lua
@@ -107,17 +107,15 @@ function graph:remove_vertex(v)
         self._edges_map[v] = nil
         self._adjacent_edges[v] = nil
         -- remove the adjacent edge with this vertex in the other vertices
-        if not self:is_directed() then
-            for _, w in ipairs(self:vertices()) do
-                local edges = self:adjacent_edges(w)
-                if edges then
-                    table.remove_if(edges, function (_, e)
-                        if e:other(w) == v then
-                            self._edges_map[w] = nil
-                            return true
-                        end
-                    end)
-                end
+        for _, w in ipairs(self:vertices()) do
+            local edges = self:adjacent_edges(w)
+            if edges then
+                table.remove_if(edges, function (_, e)
+                    if e:other(w) == v then
+                        self._edges_map[w] = nil
+                        return true
+                    end
+                end)
             end
         end
 
@@ -176,7 +174,7 @@ function graph:partial_topo_sort_next()
 
     -- recompute all nodes if has dirty nodes
     if self._partial_topo_dirty then
-        self:_partial_topo_sort_recompute_all()
+        self:_partial_topo_sort_recompute_dirty()
     end
 
     -- check if we already detected a cycle
@@ -487,8 +485,10 @@ function graph:_partial_topo_sort_init()
     return true
 end
 
--- recompute all nodes
-function graph:_partial_topo_sort_recompute_all()
+-- recompute all dirty nodes
+--
+-- TODO we recompute all nodes now, but we should optimize to recompute only dirty nodes
+function graph:_partial_topo_sort_recompute_dirty()
     self._partial_topo_in_progress = false
     self._partial_topo_in_degree = nil
     self._partial_topo_queue = nil