KaHyPar.jl

KaHyPar.jl is a Julia interface to the KaHyPar hypergraph partitioning package.

Hypergraphs and Hypergraph Partitioning

Installation

KaHyPar is a   Julia Language   package. To install KaHyPar, please open Julia's interactive session (known as REPL) and press ] key in the REPL to use the package mode, then type the following command

pkg> add KaHyPar

Usage

KaHyPar.jl natively accepts an incidence matrix as a Julia sparse matrix. The following snippet shows how to define and partition a simple hypergraph that contains 7 vertices and 4 hyperedges.

using KaHyPar
using SparseArrays

# setup incidence matrix
# I and J represent non-zero coordinates in the incidence matrix
I = [1, 3, 1, 2, 4, 5, 4, 5, 7, 3, 6, 7]
J = [1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4]
V = Int.(ones(length(I))) # can technically be any non-zero value

# create the incidence matrix
A = sparse(I, J, V)

# create a KaHyPar hypergraph
h = KaHyPar.HyperGraph(A)

# partition with default edge-cut configuration with maximum imbalance of 10%
KaHyPar.partition(h, 2; configuration=:edge_cut, imbalance=0.1)

# partition with default connectivity configuration with maximum imbalance of 10%
KaHyPar.partition(h, 2; configuration=:connectivity, imbalance=0.1)

Configuration files may also be used to define the partition options like the following snippet. Some sample configuration files can be found here.

# partition with given configuration filepath
KaHyPar.partition(h, 2; configuration="km1_rKaHyPar_sea20.ini")

It is also possible to partition with node and edge weights, set target block weights, set fixed vertices, or run improvement on existing partitions. The Julia API is not documented, but the test files show how to use the aforementioned features.

License

This Julia wrapper package is released under MIT License. The KaHyPar C++ library is licensed with the GPL License.