Skip to content

A memory-efficient matching algorithm (Kuhn–Munkres and Hopcroft–Karp) implementation based on JGraphT in Java

License

Notifications You must be signed in to change notification settings

ShreckYe/jgrapht-memory-efficient-bipartite-graph

Repository files navigation

JGraphT memory-efficient bipartite graph

A JGraphT memory-efficient bipartite graph implementation for matching algorithms (Kuhn–Munkres and Hopcroft–Karp) in Kotlin

Introduction

This repo includes a memory-efficient implementation of A bipartite graph based on JGraphT and Eclipse Collections, along with examples on how to call optimal matching algorithms (assignment algorithms) such as Kuhn–Munkres algorithm (Hungarian algorithm) and Hopcroft–Karp algorithm on such a graph, intended to solve optimal matching problems for really large data on a single machine.

A project based on this implemetation has successfully solved a matching problem of 400000 vertices in each bipartite set, each with 20000 edges on average in half a day on a machine with 32GB RAM.

Apache License

   Copyright 2019 Yongshun Ye

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.

About

A memory-efficient matching algorithm (Kuhn–Munkres and Hopcroft–Karp) implementation based on JGraphT in Java

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages