Skip to content

Latest commit

 

History

History
22 lines (18 loc) · 1.44 KB

README.md

File metadata and controls

22 lines (18 loc) · 1.44 KB
Raw

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.