kahypar
v.1.3.5
Hypergraphen sind eine Verallgemeinerung von Graphen, wobei jede (Hyper-) Kante (auch als Netz genannt) mehr als zwei Eckpunkte verbinden kann. Das k -Way -Hypergraph -Partitionierungsproblem ist die Verallgemeinerung des bekannten Graph -Partitionierungsproblems: Partition Der Scheitelpunkt, der in k -Disjoint -Blöcke der begrenzten Größe eingestellt ist (höchstens 1 + ε -mal die durchschnittliche Blockgröße), während eine auf den NETs definierte Zielfunktion minimiert wird.
Die beiden bekanntesten Zielfunktionen sind das Schnittnetz und die Konnektivität (oder λ-1) Metriken. Cut-Net ist eine einfache Verallgemeinerung des Kanten-Cut-Ziels bei der Grafikpartitionierung (dh, minimiert die Summe der Gewichte der Netze, die mehr als einen Block verbinden). Die Konnektivitätsmetrik berücksichtigt zusätzlich die tatsächliche Zahl λ der durch ein Netz verbundenen Blöcke. Durch die Summierung der (λ-1) -Werbilder aller Netze modelliert man genau das Gesamtkommunikationsvolumen der parallelen spärlichen Matrixvektor-Multiplikation und erhält erneut eine Metrik, die für einfache Graphen in Kantenschnitte zurückkehrt.
Kahypar ist ein mehrstufiges Hypergraph-Partitionierungsgerüst zur Optimierung des Cut- und (λ- 1) -Metric. Es unterstützt sowohl rekursive Halbierung als auch direkte K-Way -Partitionierung. Als mehrstufiger Algorithmus besteht es aus drei Phasen: In der Verhandlungsphase ist der Hypergraphen vergrößert, um eine Hierarchie kleinerer Hypergraphen zu erhalten. Nachdem ein anfänglicher Partitionierungsalgorithmus auf den kleinsten Hypergraphen in der zweiten Phase angewendet wurde, wird das Verurteilungen rückgängig gemacht, und auf jeder Ebene wird eine lokale Suchmethode verwendet, um die durch das grobe Niveau induzierte Partition zu verbessern. Kahypar instanziiert den mehrstufigen Ansatz in seiner extremsten Version und beseitigt nur einen einzelnen Scheitelpunkt in jeder Ebene der Hierarchie. Durch die Verwendung dieses sehr feinkörnigen n -Level -Ansatzes in Kombination mit starken lokalen Suchheuristik berechnet er Lösungen von sehr hoher Qualität. Seine Algorithmen und detaillierten experimentellen Ergebnisse werden in mehreren Forschungsveröffentlichungen vorgestellt.
Hypergraph -Partitionierung mit variablen Blockgewichten
Kahypar unterstützt variable Blockgewichte. Wenn die Befehlszeilenoption --use-individual-part-weights=true verwendet wird, versucht der Partner, den Hypergraph zu partitionieren, so dass jeder Block VX ein Gewicht von höchstens BX hat, wobei BX für jeden Block einzeln unter Verwendung des Befehlszeilenparameters --part-weights= B1 B2 B3 ... Bk-1 angegeben werden kann. Da das Framework noch nicht perfekt ausbalanciert wird, müssen die Obergrenzen etwas größer sein als das Gesamtgewicht aller Scheitelpunkte des Hypergraphen. Beachten Sie, dass diese Funktion noch experimentell ist.
Hypergraph -Partitionierung mit festen Eckpunkten
Hypergraph -Partitionierung mit festen Eckpunkten ist eine Variation der Standard -Hypergraph -Partitionierung. In diesem Problem gibt es eine zusätzliche Einschränkung für die Blockzuordnung einiger Scheitelpunkte, dh einige Scheitelpunkte werden vor der Partitionation mit der Bedingung auf bestimmte Blöcke ausgestattet, die nach der Partitionation der verbleibenden „freien“ Eckpunkte die festen Scheitelpunkte immer noch im Block befinden. Der Befehlszeilenparameter --fixed / -f kann verwendet werden, um eine Fixdatei im HMETIS -Fixdateiformat anzugeben. Für einen Hypergraph mit V -Scheitelpunkten besteht die Fixdatei aus V -Zeilen - einen für jeden Scheitelpunkt. Die I -Th -Zeile enthält entweder -1 um anzuzeigen, dass der Scheitelpunkt frei zu bewegen ist, oder <part id> um anzuzeigen, dass dieser Scheitelpunkt vorgefertigt werden sollte, um <part id> zu blockieren. Beachten Sie, dass Teil -IDs von 0 beginnen.
Kahypar unterstützt derzeit drei verschiedene Kontraktionsrichtlinien für die Partitionierung mit festen Eckpunkten:
free_vertex_only ermöglicht alle Kontraktionen, bei denen der Kontraktionspartner ein freier Scheitelpunkt ist, dh ermöglicht die Kontraktionen von Scheitelpunktpaaren, bei denen beide Scheitelpunkte frei sind oder ein Scheitelpunkt festgelegt ist und der andere Scheitelpunkt frei ist.fixed_vertex_allowed ermöglicht zusätzlich Kontraktionen von zwei festen Scheiteln, sofern beide in denselben Block angewiesen sind. Basierend auf vorläufigen Experimenten ist dies derzeit die Standardrichtlinie.equivalent_vertices ermöglicht nur Kontraktionen von Scheitelpunktpaaren, die entweder aus zwei freien Scheitelpunkten oder zwei festen Scheitelpunkten bestehen, die am selben Block vorgesehen sind.Evolutionsrahmen (Kahypar-e)
Kahypar-e verbessert Kahypar mit einem evolutionären Rahmen, wie in unserer GECCO'18-Veröffentlichung beschrieben. Angesichts einer ziemlich hohen Laufzeit leistet dieser memetische Multilevel -Algorithmus besser als wiederholte Ausführungen von Non -Volutionary Kahypar -Konfigurationen, Hmetis und Patoh. Der Befehlszeilenparameter --time-limit=xxx kann verwendet werden, um die maximale Laufzeit (in Sekunden) festzulegen. Parameter --partition-evolutionary=true ermöglicht die evolutionäre Partitionierung.
Verbesserung bestehender Partitionen
Kahypar verwendet direkte K-Way-V-Cycles, um zu versuchen, eine vorhandene Partition zu verbessern, die über Parameter --part-file=</path/to/file> angegeben wurde. Die maximale Anzahl von V-Zyklen kann über Parameter --vcycles= gesteuert werden.
Verteilte gerichtete acyclische Hypergraphen
Obwohl der Code noch nicht in das Haupt -Repository zusammengefasst wurde, gibt es eine Gabel, die die partitionelle Acycl -Hypergraph -Verteilung unterstützt. Weitere Details finden Sie in der entsprechenden Veröffentlichung der Konferenz.
Wir verwenden die Leistungsprofile , um Kahypar mit anderen Partitionierungsalgorithmen in Bezug auf die Lösungsqualität zu vergleichen. Für eine Reihe von
Algorithmen und ein Benchmark -Set
enthält
Instanzen das Leistungsverhältnis
bezieht den Schnitt, der von Partitioner P berechnet wurde, zum Beispiel I auf den kleinsten Minimumschnitt aller Algorithmen, dh.
.
Das Leistungsprofil
des Algorithmus P wird dann durch die Funktion gegeben
.
Zur Optimierung der Konnektivität werden die Leistungsverhältnisse mit den Konnektivitätswerten berechnet
anstelle der Schnittwerte. Der Wert von
entspricht dem Anteil der Instanzen, für die Partitioner P die beste Lösung berechnet hat ist die Wahrscheinlichkeit, dass ein Leistungsverhältnis ist innerhalb eines Faktors von
des bestmöglichen Verhältnisses. Beachten Sie, dass die Leistungsprofile, da er nur die Leistung jedes Algorithmus relativ zum besten Algorithmus bewerten kann
Werte können nicht verwendet werden, um Algorithmen zu bewerten (dh zu bestimmen, welcher Algorithmus der zweitbeste usw. ist).
In unserer experimentellen Analyse basieren die Leistungsprofilplots auf den besten Lösungen (dh minimaler Konnektivität/Schnitt). Jeder Algorithmus, der für jede Instanz gefunden wurde. Darüber hinaus wählen wir Parameter aus
für alle p , ich und
so dass ein Leistungsverhältnis
Wenn und nur wenn Algorithmus P eine unmöglichbare Lösung für i , und und
Wenn und nur, wenn der Algorithmus eine Lösung nicht in der angegebenen Zeitlimit berechnen konnte. In unseren Leistungsprofilplots werden die Leistungsverhältnisse, die nicht realisierbaren Lösungen entsprechen
. Da die Leistungsverhältnisse stark mit rechts gedreht sind, sind die Leistungsprofildiagramme in drei Segmente mit unterschiedlichen Parametern unterteilt verschiedene Bereiche von Interesse widerspiegeln. Das erste Segment zeigt kleine Werte (
), während das zweite Segment Ergebnisse für alle Instanzen enthält, die dem Faktor von entspricht
Schlimmer als das bestmögliche Verhältnis. Das letzte Segment enthält alle verbleibenden Verhältnisse, dh Fälle, für die einige Algorithmen erheblich schlechter abschnitten als der beste Algorithmus, für die Algorithmen nicht realisierbare Lösungen erzeugten, und Fälle, die nicht innerhalb des angegebenen Zeitlimits verteilt werden konnten.
In den Figuren vergleichen wir Kahypar mit Patoh in Qualität (Patoh-Q) und Standardmodus (Patoh-D), K-Way (Hmetis-K) und rekursiver Bisektion-Variante (Hmetis-R) von HMetis 2.0 (p1), Zoltan mit Algebraic-Basis (Zoltan-Algd), Mondrian V.4.4. Algorithmus.
Lösungsqualität 
Laufzeit 
Wir bieten zusätzliche Ressourcen für alle kahyparbezogenen Veröffentlichungen:
| KKAHYPAR-SEA20 / Rkahypar-Sea20 | Sea'20 | Papier | Tr | Folien | Experimentelle Ergebnisse |
|---|---|---|---|---|---|
| KKAHYPAR / Rkahypar | - - | Dissertation | - - | Folien | Experimentelle Ergebnisse |
| Kahypar-mf / Kahypar-R-MF | Sea'18 / Jea'19 | Seereite / JEA -Papier | Tr | Folien | Experimentelle Ergebnisse: Meer / JEA |
| Kahypar-e (evohgp) | Gecco'18 | Papier | Tr | Folien | Experimentelle Ergebnisse |
| Kahypar-Ca | Sea'17 | Papier | - - | Folien | Experimentelle Ergebnisse |
| Kahypar-K | Alenex'17 | Papier | - - | Folien | Experimentelle Ergebnisse |
| Kahypar-R | Alenex'16 | Papier | Tr | Folien | Experimentelle Ergebnisse |
Das Karlsruhe Hypergraph Partitioning -Framework erfordert:
g++ Version 9 oder höher oder clang Version 11.0.3 oder höher.-DKAHYPAR_USE_MINIMAL_BOOST=ON Flag zum Flag hinzufügen, um die erforderlichen Abhängigkeiten automatisch herunterzuladen, zu extrahieren und zu erstellen. Klonen Sie das Repository einschließlich Submodules:
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
Erstellen Sie ein Build -Verzeichnis: mkdir build && cd build
Führen Sie cmake: cmake .. -DCMAKE_BUILD_TYPE=RELEASE
Lauf machen: make
Tests werden automatisch ausgeführt, während das Projekt erstellt wird. Zusätzlich wird ein test bereitgestellt. End-to-End-Integrationstests können gestartet werden mit: make integration_tests . Das Profiling kann über CMAKE -Flag aktiviert werden: -DENABLE_PROFILE=ON .
Das eigenständige Programm kann über make KaHyPar erstellt werden. Die Binärdatei befindet sich unter: build/kahypar/application/ .
Kahypar hat mehrere Konfigurationsparameter. Für eine Liste aller möglichen Parameter führen Sie bitte aus: ./KaHyPar --help . Wir verwenden das HMETIS -Format für die Eingabe -Hypergraph -Datei sowie die Partition -Ausgabedatei.
Der Befehlszeilenparameter --quiet=1 kann verwendet werden, um die gesamte Protokollierungsausgabe zu unterdrücken. Wenn Sie die Schnittstellen der Bibliothek verwenden, hat das Hinzufügen quiet=1 zur entsprechenden .ini -Konfigurationsdatei den gleichen Effekt.
Wir bieten zwei Standard -Framework -Konfigurationen - eine für rekursive Bipartitionierung ( R Kahypar) und eine für die direkte K -Way -Partitionierung ( K Kahypar).
Im Allgemeinen empfehlen wir, K Kahypar zu verwenden, da es sowohl in Bezug auf die Laufzeit als auch die Lösungsqualität besser als R Kahypar abschneidet.
Starten von K Kahypar optimieren Sie den (Konnektivität - 1) objektiven Lauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
Starten von K Kahypar optimieren Sie den geschnittenen Netto -Ziellauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
Um r Kahypar zu starten, optimieren Sie den (Konnektivität - 1) objektiven Lauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
Um r Kahypar zu starten, optimieren Sie den Cut -Net -Ziellauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
Um den memetischen Algorithmus K Kahypar -e zu starten, optimieren Sie den (Konnektivität - 1) objektiven Lauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
Darüber hinaus bieten wir verschiedene Voreinstellungen an, die den Konfigurationen entsprechen, die in den Veröffentlichungen von Alenex'16, Alenex'17, Sea'17, Sea'18, Gecco'18 sowie in unserem JEA -Journalpapier und in der Dissertation von Sebastian Schlag verwendet werden. Diese Konfigurationen befinden sich im Ordner config/old_reference_configs. Um diese Konfigurationen zu verwenden, müssen Sie Kahypar Release 1.1.0 auschecken, da ein alter Code in der aktuellsten Version entfernt wurde.
Starten von Kahypar-MF (unter Verwendung von Flow-basierter Verfeinerung ) Optimierung des (Konnektivität-1) Ziels mit dem direkten K-Way-Modus:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_kahypar_mf_jea19.ini
Starten von Kahypar-MF (unter Verwendung von Flow-basierter Verfeinerung ) Optimierung des Cut-Net-Ziels mit dem direkten K-Way-Modus:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/old_reference_configs/cut_kahypar_mf_jea19.ini
Um evoHgp/kahypar-e zu starten, optimieren Sie das Objektiv (Konnektivität-1) mit dem direkten K-Wege-Modus
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_gecco18.ini
Beachten Sie, dass die Konfiguration km1_direct_kway_gecco18.ini auf Kahypar-CA basiert. Kahypar-E arbeitet jedoch auch mit fließenden lokalen Verbesserungen. In unserer JEA -Veröffentlichung wurde die km1_kahypar_e_mf_jea19.ini -Konfiguration verwendet.
Starten von Kahypar-CA (unter Verwendung von Community-of-Coarning-Vergrößen ) Optimierung des (Konnektivität-1) Ziels mit dem direkten K-Wege-Modus:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_sea17.ini
Kahypar im direkten K-Way-Modus (Kahypar-K) zu starten, optimieren Sie den (Konnektivität-1) objektiven Lauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/old_reference_configs/km1_direct_kway_alenex17.ini
Kahypar im rekursiven Bisektionsmodus (Kahypar-R) zu starten, optimieren Sie den Cut-Net-Objektivlauf:
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/old_reference_configs/cut_rb_alenex16.ini
Alle voreingestellten Parameter können über die entsprechenden Befehlszeilenoptionen überschrieben werden.
Beim Erstellen eines Hypergraph -Kahypars bestätigt, dass die Eingabe tatsächlich ein korrekter Hypergraphen ist, andernfalls drucken Sie einen Fehler und Abbruch. Dies gilt für HGR -Eingabedateien, die C -Schnittstelle und die Python -Schnittstelle. Die Laufzeitkosten der Validierung sollten in fast allen Fällen vernachlässigbar sein. Die Eingabevalidierung kann jedoch auch unter Verwendung des CMake -Flag -DKAHYPAR_INPUT_VALIDATION=OFF deaktiviert werden.
Darüber hinaus werden Warnungen für nicht tödliche Probleme (z. B. Hyperedges mit doppelten Stiften) gedruckt. Um nicht tödliche Probleme als harte Fehler zu behandeln, verwenden Sie das CMake -Flag -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON .
Wir bieten eine einfache Schnittstelle im C-Stil, um Kahypar als Bibliothek zu verwenden. Beachten Sie, dass diese Schnittstelle noch nicht threadsicher ist. Es gibt jedoch einige bestehende Problemumgehungen. Die Bibliothek kann über die Erstellung und Installation über
make install.libraryund kann so verwendet werden:
# include < memory >
# include < vector >
# include < iostream >
# include < libkahypar.h >
int main ( int argc, char * argv[]) {
kahypar_context_t * context = kahypar_context_new ();
kahypar_configure_context_from_file (context, " /path/to/config.ini " );
kahypar_set_seed (context, 42 );
const kahypar_hypernode_id_t num_vertices = 7 ;
const kahypar_hyperedge_id_t num_hyperedges = 4 ;
std::unique_ptr< kahypar_hyperedge_weight_t []> hyperedge_weights = std::make_unique< kahypar_hyperedge_weight_t []>( 4 );
// force the cut to contain hyperedge 0 and 2
hyperedge_weights[ 0 ] = 1 ; hyperedge_weights[ 1 ] = 1000 ;
hyperedge_weights[ 2 ] = 1 ; hyperedge_weights[ 3 ] = 1000 ;
std::unique_ptr< size_t []> hyperedge_indices = std::make_unique< size_t []>( 5 );
hyperedge_indices[ 0 ] = 0 ; hyperedge_indices[ 1 ] = 2 ;
hyperedge_indices[ 2 ] = 6 ; hyperedge_indices[ 3 ] = 9 ;
hyperedge_indices[ 4 ] = 12 ;
std::unique_ptr< kahypar_hyperedge_id_t []> hyperedges = std::make_unique< kahypar_hyperedge_id_t []>( 12 );
// hypergraph from hMetis manual page 14
hyperedges[ 0 ] = 0 ; hyperedges[ 1 ] = 2 ;
hyperedges[ 2 ] = 0 ; hyperedges[ 3 ] = 1 ;
hyperedges[ 4 ] = 3 ; hyperedges[ 5 ] = 4 ;
hyperedges[ 6 ] = 3 ; hyperedges[ 7 ] = 4 ;
hyperedges[ 8 ] = 6 ; hyperedges[ 9 ] = 2 ;
hyperedges[ 10 ] = 5 ; hyperedges[ 11 ] = 6 ;
const double imbalance = 0.03 ;
const kahypar_partition_id_t k = 2 ;
kahypar_hyperedge_weight_t objective = 0 ;
std::vector< kahypar_partition_id_t > partition (num_vertices, - 1 );
kahypar_partition (num_vertices, num_hyperedges,
imbalance, k,
/* vertex_weights */ nullptr , hyperedge_weights. get (),
hyperedge_indices. get (), hyperedges. get (),
&objective, context, partition. data ());
for ( int i = 0 ; i != num_vertices; ++i) {
std::cout << i << " : " << partition[i] << std::endl;
}
kahypar_context_free (context);
} So kompilieren Sie das Programm mit g++ Run:
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar Hinweis: Wenn beim Verknüpfen keine Boost gefunden wird, müssen Sie möglicherweise -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options zum Befehl hinzufügen.
Um die Bibliothek von Ihrem System aus zu entfernen, verwenden Sie das bereitgestellte Deinstallationsziel:
make uninstall-kahyparUm die Python -Schnittstelle zu kompilieren, machen Sie Folgendes:
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 Wenn Sie keinen Boost installiert haben, rennen Sie: cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON stattdessen. Dadurch wird die erforderlichen Abhängigkeiten automatisch heruntergeladen, extrahiert und erstellt.cd pythonmakecp kahypar.so <path-to-site-packages>Danach können Sie die Kahypar -Libary wie diese verwenden:
import os
import kahypar as kahypar
num_nodes = 7
num_nets = 4
hyperedge_indices = [ 0 , 2 , 6 , 9 , 12 ]
hyperedges = [ 0 , 2 , 0 , 1 , 3 , 4 , 3 , 4 , 6 , 2 , 5 , 6 ]
node_weights = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ]
edge_weights = [ 11 , 22 , 33 , 44 ]
k = 2
hypergraph = kahypar . Hypergraph ( num_nodes , num_nets , hyperedge_indices , hyperedges , k , edge_weights , node_weights )
context = kahypar . Context ()
context . loadINIconfiguration ( "<path/to/config>/km1_kKaHyPar_sea20.ini" )
context . setK ( k )
context . setEpsilon ( 0.03 )
kahypar . partition ( hypergraph , context )Weitere Informationen zur Funktionalität der Python Library finden Sie unter: Modul.cpp
Wir bieten auch eine vorkompilierte Version als a, die durch:
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
Vielen Dank an Jordan Jalving (@jalving) Kahypar bietet jetzt auch eine Julia -Schnittstelle an, die derzeit hier zu finden ist: kahypar/kahypar.jl.
Die entsprechende Abhängigkeit kann über:
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )Danach können Sie Kahypar verwenden, um Ihre Hypergraphen wie diese zu partitionieren:
using KaHyPar
using SparseArrays
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)))
A = sparse (I,J,V)
h = KaHyPar . hypergraph (A)
KaHyPar . partition (h, 2 ,configuration = :edge_cut )
KaHyPar . partition (h, 2 ,configuration = :connectivity )
KaHyPar . partition (h, 2 ,configuration = joinpath ( @__DIR__ , " ../src/config/km1_kKaHyPar_sea20.ini " ))Romain Wallon hat eine Java -Schnittstelle für Kahypar geschaffen. In der Readme finden Sie eine detaillierte Beschreibung zum Erstellen und Verwenden der Schnittstelle.
Wir ermutigen Sie, Probleme mit Kahypar über das GitHub -Problemverfolgungssystem des Projekts zu melden.
Kahypar ist eine kostenlose Software, die gemäß der GNU General Public Lizenz (GPLV3) bereitgestellt wird. Weitere Informationen finden Sie in der Kopierdatei. Wir verteilen diesen Rahmen frei, um die Verwendung und Entwicklung von Hypergraph -Partitionierungswerkzeugen zu fördern. Wenn Sie Kahypar in einer akademischen Umgebung verwenden, zitieren Sie bitte die entsprechenden Papiere. Wenn Sie an einer kommerziellen Lizenz interessiert sind, kontaktieren Sie mich bitte.
// Overall KaHyPar framework
@phdthesis{DBLP:phd/dnb/Schlag20,
author = {Sebastian Schlag},
title = {High-Quality Hypergraph Partitioning},
school = {Karlsruhe Institute of Technology, Germany},
year = {2020}
}
@article{10.1145/3529090,
author = {Schlag, Sebastian and
Heuer, Tobias and
Gottesb"{u}ren, Lars and
Akhremtsev, Yaroslav and
Schulz, Christian and
Sanders, Peter},
title = {High-Quality Hypergraph Partitioning},
url = {https://doi.org/10.1145/3529090},
doi = {10.1145/3529090},
journal = {ACM J. Exp. Algorithmics},
year = {2022},
month = {mar}
}
// KaHyPar-R
@inproceedings{shhmss2016alenex,
author = {Sebastian Schlag and
Vitali Henne and
Tobias Heuer and
Henning Meyerhenke and
Peter Sanders and
Christian Schulz},
title = {k-way Hypergraph Partitioning via emph{n}-Level Recursive
Bisection},
booktitle = {18th Workshop on Algorithm Engineering and Experiments, (ALENEX 2016)},
pages = {53--67},
year = {2016},
}
// KaHyPar-K
@inproceedings{ahss2017alenex,
author = {Yaroslav Akhremtsev and
Tobias Heuer and
Peter Sanders and
Sebastian Schlag},
title = {Engineering a direct emph{k}-way Hypergraph Partitioning Algorithm},
booktitle = {19th Workshop on Algorithm Engineering and Experiments, (ALENEX 2017)},
pages = {28--42},
year = {2017},
}
// KaHyPar-CA
@inproceedings{hs2017sea,
author = {Tobias Heuer and
Sebastian Schlag},
title = {Improving Coarsening Schemes for Hypergraph Partitioning by Exploiting Community Structure},
booktitle = {16th International Symposium on Experimental Algorithms, (SEA 2017)},
pages = {21:1--21:19},
year = {2017},
}
// KaHyPar-MF
@inproceedings{heuer_et_al:LIPIcs:2018:8936,
author ={Tobias Heuer and Peter Sanders and Sebastian Schlag},
title ={{Network Flow-Based Refinement for Multilevel Hypergraph Partitioning}},
booktitle ={17th International Symposium on Experimental Algorithms (SEA 2018)},
pages ={1:1--1:19},
year ={2018}
}
@article{KaHyPar-MF-JEA,
author = {Heuer, T. and Sanders, P. and Schlag, S.},
title = {Network Flow-Based Refinement for Multilevel Hypergraph Partitioning},
journal = {ACM Journal of Experimental Algorithmics (JEA)}},
volume = {24},
number = {1},
month = {09},
year = {2019},
pages = {2.3:1--2.3:36},
publisher = {ACM}
}
// KaHyPar-E (EvoHGP)
@inproceedings{Andre:2018:MMH:3205455.3205475,
author = {Robin Andre and Sebastian Schlag and Christian Schulz},
title = {Memetic Multilevel Hypergraph Partitioning},
booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference},
series = {GECCO '18},
year = {2018},
pages = {347--354},
numpages = {8}
}
// KaHyPar-SEA20 (KaHyPar-HFC)
@InProceedings{gottesbren_et_al:LIPIcs:2020:12085,
author = {Lars Gottesb{"u}ren and Michael Hamann and Sebastian Schlag and Dorothea Wagner},
title = {{Advanced Flow-Based Multilevel Hypergraph Partitioning}},
booktitle = {18th International Symposium on Experimental Algorithms (SEA)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = {2020}
}
Wenn Sie daran interessiert sind, zum Kahypar -Framework beizutragen, können Sie mich gerne kontaktieren oder ein Problem mit dem Problemverfolgungssystem erstellen.
