Merge pull request #1908 from Arafatk/patch-4

Exclude self-loops from maximal matching

2 files changed, 15 insertions, 1 deletions

diff --git a/networkx/algorithms/matching.py b/networkx/algorithms/matching.py
index afc505e5..6bb064de 100644
--- a/networkx/algorithms/matching.py
+++ b/networkx/algorithms/matching.py
@@ -46,7 +46,7 @@ def maximal_matching(G):
     for u,v in G.edges():
         # If the edge isn't covered, add it to the matching
         # then remove neighborhood of u and v from consideration.
-        if u not in nodes and v not in nodes:
+        if u not in nodes and v not in nodes and u!=v:
             matching.add((u,v))
             nodes.add(u)
             nodes.add(v)
diff --git a/networkx/algorithms/tests/test_matching.py b/networkx/algorithms/tests/test_matching.py
index 05fa8c1b..ac86da9b 100644
--- a/networkx/algorithms/tests/test_matching.py
+++ b/networkx/algorithms/tests/test_matching.py
@@ -251,6 +251,20 @@ def test_maximal_matching():
         u, v = edge
         ok_(len(set([v]) & vset) > 0 or len(set([u]) & vset) > 0, \
                 "not a proper matching!")
+    graph = nx.Graph()
+    graph.add_edge(1, 1)
+    graph.add_edge(1, 2)
+    graph.add_edge(2, 2)
+    graph.add_edge(2, 3)
+    matching = nx.maximal_matching(graph)
+    assert(len(matching)==1)
+    vset = set(u for u, v in matching)
+    vset = vset | set(v for u, v in matching)
+
+    for edge in graph.edges():
+        u, v = edge
+        ok_(len(set([v]) & vset) > 0 or len(set([u]) & vset) > 0, \
+                "not a proper matching!")
 
 def test_maximal_matching_ordering():
     # check edge ordering