Share your code. npm Orgs help your team discover, share, and reuse code. Create a free org »

    bipartite-matchingpublic

    bipartite-matching

    Finds a maximum bipartite matching in an unweighted graph. The current implementation uses the Hopcroft-Karp algorithm and runs in O(sqrt(V) * E + V) time. Works in both node.js and in a browser.

    Example

    var findMatching = require("bipartite-matching")
     
    console.log(findMatching(5, 5, [
          [0, 0],
          [0, 1],
          [1, 0],
          [2, 1],
          [2, 2],
          [3, 2],
          [3, 3],
          [3, 4],
          [4, 4]
        ]))

    Install

    npm install bipartite-matching
    

    require("bipartite-matching")(n, m, edges)

    Computes a bipartite matching for the graph

    • n is the number of vertices in the first component
    • m is the number of vertices in the second component
    • edges is the list of edges, represented by pairs of integers between 0 and n-1,m-1 respectively.

    Returns A list of edges representing the matching

    Credits

    (c) 2014 Mikola Lysenko. MIT License

    install

    npm i bipartite-matching

    Downloadsweekly downloads

    24

    version

    1.0.0

    license

    MIT

    repository

    githubgithub

    last publish

    collaborators

    • avatar