networkx maximal_matching() does not return maximum matching

Question

I'm learning to use the networkx python module to do some matchings of a bipartite graph. There are two functions in the module that give the maximum cardinality matching of a graph:

1. nx.maximal_matching()
2. nx.bipartite.maxmum_matching()

Note that although with the name of maximal_matching, its doc does state that it "Find a maximal cardinality matching in the graph."

Since my graph is a bipartite one, I assume these 2 would give same results, at least both with the same number of edges. However my code seems to suggest that the nx.maximal_matching() gives the wrong answer: it is possible to have one more edge, as the nx.bipartite.maxmum_matching() suggests.

Below is my working code:

import networkx as nx
from networkx import bipartite    

def plotGraph(graph,ax,title):    
    pos=[(ii[1],ii[0]) for ii in graph.nodes()]
    pos_dict=dict(zip(graph.nodes(),pos))
    nx.draw(graph,pos=pos_dict,ax=ax,with_labels=True)
    ax.set_title(title)
    return   

if __name__=='__main__':    
    #---------------Construct the graph---------------
    g=nx.Graph()
    edges=[
            [(1,0), (0,0)],
            [(1,0), (0,1)],
            [(1,0), (0,2)],
            [(1,1), (0,0)],
            [(1,2), (0,2)],
            [(1,2), (0,5)],
            [(1,3), (0,2)],
            [(1,3), (0,3)],
            [(1,4), (0,3)],
            [(1,5), (0,2)],
            [(1,5), (0,4)],
            [(1,5), (0,6)],
            [(1,6), (0,1)],
            [(1,6), (0,4)],
            [(1,6), (0,6)]
            ]

    for ii in edges:
        g.add_node(ii[0],bipartite=0)
        g.add_node(ii[1],bipartite=1)

    g.add_edges_from(edges)

    #---------------Use maximal_matching---------------
    match=nx.maximal_matching(g)    
    g_match=nx.Graph()
    for ii in match:
        g_match.add_edge(ii[0],ii[1])

    #----------Use bipartite.maximum_matching----------
    match2=bipartite.maximum_matching(g)    
    g_match2=nx.Graph()
    for kk,vv in match2.items():
        g_match2.add_edge(kk,vv)

    #-----------------------Plot-----------------------
    import matplotlib.pyplot as plt
    fig=plt.figure(figsize=(10,8))

    ax1=fig.add_subplot(2,2,1)
    plotGraph(g,ax1,'Graph')

    ax2=fig.add_subplot(2,2,2)
    plotGraph(g_match,ax2,'nx.maximal_matching()')

    ax3=fig.add_subplot(2,2,3)
    plotGraph(g_match2,ax3,'bipartite.maximum_matching()')

    plt.show()

And here is the generated plot. As is shown subplot-2 has 6 edges while 3 has 7. Is this a bug in the networkx's implementation or I'm doing anything wrong here?

PS: my networkx is version 1.11

Answer 1

The networkx.maximal_matching algorithm does not give a maximal cardinality match in the manner you intend. It implements a simple greedy algorithm whose result is maximal purely in the sense that no additional edge can be added to it.

Its counterpart, for the global maximum cardinality match you intend, is networkx.max_weight_matching

Answer 2

According to the answer to this bug report, the matching returned is maximal, rather than a maximum matching. Which in their terminology (I don't know how common this is) means that is gives a local optimum rather than a global optimum.

So, for the matching returned by maximal_matching it is only guaranteed that it can not be made larger by adding an edge to that matching (while still being a matching). However, it is not guaranteed that there does not exist a matching that has more edges.