vertex_cover: Added support for self-loop nodes (#5104)

The vertex_cover algorithm updated the cost of u,v twice
in case node v and node u are the same nodes. As a result
self-edged nodes are overlooked. Here we fixed the way vertex_cover
is being updated which also improve the performance compared to the old
implementation

2 files changed, 25 insertions, 6 deletions

diff --git a/networkx/algorithms/approximation/tests/test_vertex_cover.py b/networkx/algorithms/approximation/tests/test_vertex_cover.py
index 8beb40a4..5cc5a38d 100644
--- a/networkx/algorithms/approximation/tests/test_vertex_cover.py
+++ b/networkx/algorithms/approximation/tests/test_vertex_cover.py
@@ -20,7 +20,7 @@ class TestMWVC:
         G.add_edges_from((0, v) for v in range(1, 26))
         G.add_edges_from((v, 0) for v in range(26, 51))
         cover = min_weighted_vertex_cover(G)
-        assert 2 == len(cover)
+        assert 1 == len(cover)
         assert is_cover(G, cover)
 
     def test_unweighted_undirected(self):
@@ -28,7 +28,7 @@ class TestMWVC:
         size = 50
         sg = nx.star_graph(size)
         cover = min_weighted_vertex_cover(sg)
-        assert 2 == len(cover)
+        assert 1 == len(cover)
         assert is_cover(sg, cover)
 
     def test_weighted(self):
@@ -53,3 +53,16 @@ class TestMWVC:
         csum = sum(wg.nodes[node]["weight"] for node in cover)
         assert 4 == csum
         assert is_cover(wg, cover)
+
+    def test_unweighted_self_loop(self):
+        slg = nx.Graph()
+        slg.add_node(0)
+        slg.add_node(1)
+        slg.add_node(2)
+
+        slg.add_edge(0, 1)
+        slg.add_edge(2, 2)
+
+        cover = min_weighted_vertex_cover(slg)
+        assert 2 == len(cover)
+        assert is_cover(slg, cover)
diff --git a/networkx/algorithms/approximation/vertex_cover.py b/networkx/algorithms/approximation/vertex_cover.py
index 943de645..d117c733 100644
--- a/networkx/algorithms/approximation/vertex_cover.py
+++ b/networkx/algorithms/approximation/vertex_cover.py
@@ -67,8 +67,14 @@ def min_weighted_vertex_cover(G, weight=None):
     cost = dict(G.nodes(data=weight, default=1))
     # While there are uncovered edges, choose an uncovered and update
     # the cost of the remaining edges.
+    cover = set()
     for u, v in G.edges():
-        min_cost = min(cost[u], cost[v])
-        cost[u] -= min_cost
-        cost[v] -= min_cost
-    return {u for u, c in cost.items() if c == 0}
+        if u in cover or v in cover:
+            continue
+        if cost[u] <= cost[v]:
+            cover.add(u)
+            cost[v] -= cost[u]
+        else:
+            cover.add(v)
+            cost[u] -= cost[v]
+    return cover