kahypar
v.1.3.5
超圖是圖形的概括，其中每個（Hyper）邊緣（也稱為Net）可以連接兩個以上的頂點。 k -way HyperGraph分區問題是眾所周知的圖形分區問題的概括：將頂點設置為有界大小的K分離塊（最多是平均塊大小的最多1 +ε乘以），同時最小化網絡上定義的目標函數。
兩個最突出的目標函數是切口和連通性（或λ-1）指標。切割是在圖形分區中對邊緣物鏡的直接概括（即，最大程度地減少連接多個塊的網的重量之和）。連接度量還考慮了由網絡連接的塊的實際數字λ。通過將所有網的（λ-1）值求和，一個準確地模擬了並行稀疏矩陣矢量乘法的總通信量，並再次獲得了一個度量標準，該度量可以恢復為平原圖的邊緣。
KAHYPAR是一種多級超圖形分區框架，用於優化切割和（λ-1）-metric。它支持遞歸分分線和直接的K路分區。作為一種多級算法，它由三個階段組成：在粗糙階段，將超圖形縮放到獲得較小的超圖的層次結構。在第二階段將初始分區算法應用於最小的超圖後，將撤消變形，並且在每個級別上，都使用局部搜索方法來改善由較粗糙的級別引起的分區。 Kahypar以其最極端的版本實例化了多級方法，在每個層次結構的每個級別中僅刪除一個頂點。通過使用這種非常細的N級方法與強大的本地搜索啟發式方法相結合，它可以計算出非常高質量的解決方案。它的算法和詳細的實驗結果在幾個研究出版物中提出。
具有可變塊重量的超圖形分區
Kahypar支持可變的塊權重。如果使用命令行選項--use-individual-part-weights=true ，則分區者試圖分區超圖，以使每個塊VX最多具有BX的重量，其中可以使用命令行參數分別為每個塊指定BX --part-weights= B1 B2 B3 ... Bk-1 。由於該框架尚未支持完美平衡的分區，因此上限需要比超圖的所有頂點的總重量稍大。請注意，此功能仍然是實驗性的。
用固定頂點進行超圖形分區
用固定頂點進行超圖形分區是標準超圖形分區的變體。在這個問題中，對某些頂點的塊分配存在附加限制，即某些頂點在對特定的塊上進行了預分配，然後將其分區後，在將剩餘的“免費”頂點劃分後，固定的頂點仍在分配給它們的塊中。命令行參數--fixed / -f可用於以Hmetis Fix File Format指定修復文件。對於具有V頂點的超圖，修復文件由V線組成 - 每個頂點一個。第1行要么包含-1 ，表明頂點可以自由移動或<part id>以指示該頂點應預先簽名以阻止<part id> 。請注意，零件ID從0開始。
Kahypar目前支持三種不同的收縮政策，用於用固定頂點進行分區：
free_vertex_only允許所有收縮夥伴是一個免費頂點的收縮，即，它允許縮放頂點對，其中兩個頂點都是免費的，或者一個頂點是固定的，另一個頂點是免費的。fixed_vertex_allowed還允許兩個固定頂點的收縮，規定兩個固定頂點，這些頂點均被預先簽名到同一塊。基於初步實驗，這是當前的默認策略。equivalent_vertices僅允許收縮的頂點對，由兩個自由頂點或兩個固定頂點組成，將其預先分配到同一塊。進化框架（Kahypar-E）
Kahypar-e通過Gecco'18出版物中所述的進化框架增強了Kahypar。給定相當大的運行時間，該模因多級算法的性能要比重複執行非方向性Kahypar配置，HMETIS和PATOH更好。命令行參數--time-limit=xxx可用於設置最大運行時間（以秒為單位）。參數--partition-evolutionary=true啟用進化分區。
改善現有分區
Kahypar使用直接的Kway V-Cycles嘗試改進通過參數--part-file=</path/to/file>指定的現有分區。可以通過參數--vcycles=控制V循環的最大數量。
劃分定向的無環超圖
儘管該代碼尚未合併到主要存儲庫中，但仍存在一個支持無環超圖形分區的叉子。更多詳細信息可以在相應的會議出版物中找到。
我們使用性能概況將KAHYPAR與解決方案質量的其他分區算法進行比較。一套
算法和基準集
包含
實例，性能比
將分區p計算的切割與例如所有算法的最小切割相關聯，即
。
性能概況
然後由函數給出算法P的
。
為了優化連接性，使用連接值計算性能比率
而不是剪切值。價值
對應於分區p計算最佳解決方案的實例的比例，而是性能比的概率在
最佳比率。請注意，由於性能概況僅允許評估每種算法相對於最佳算法的性能，所以
值不能用於對算法進行排名（即確定哪種算法是第二好等）。
在我們的實驗分析中，性能概況圖基於每個實例找到的每個算法的最佳解決方案（即，最小連接/切割）。此外，我們選擇參數
對於所有p ，我和
這樣的性能比
且僅當算法p計算不可行的解決方案時，例如i和
當算法無法在給定時間限制內計算解決方案時，並且僅當算法無法計算解決方案時。在我們的性能概況圖中， X軸上的X -Tick上將顯示與不可行解決方案相對應的性能比率，而無法在時間限制內進行分區的實例，通過退出下面的圖的線暗示顯示在時間限制內的實例
。由於性能比率很大，因此性能配置文件圖分為三個段，參數不同反映各個感興趣的領域。第一段突出顯示了小值（
），雖然第二部分包含所有實例的結果，
比最佳比率更糟糕。最後一個段包含所有剩餘比率，即某些算法的性能比最佳算法要差得多，算法產生了不可行的解決方案的實例，以及在給定時間限制內無法分配的實例。
在數字中，我們將Kahypar與質量（PATOH-Q）和默認模式（PATOH-D），K-Way（Hmetis-K）以及HmeTis 2.0（P1）（P1）的遞歸分分變體（P1），Zoltan，基於代數距離距離的二型（Zoltan-Algd）的Mondriryan和Mondriririririary.14.4.14.14.14.14.14.14.進行比較。
解決方案質量
運行時間
我們為所有與Kahypar相關的出版物提供其他資源：
| kkahypar-sea20 / rkahypar-sea20 | Sea'20 | 紙 | tr | 幻燈片 | 實驗結果 |
|---|---|---|---|---|---|
| kkahypar / rkahypar | - | 論文 | - | 幻燈片 | 實驗結果 |
| Kahypar-MF / KAHYPAR-R-MF | 海18 / Jea'19 | 海紙 / JEA紙 | tr | 幻燈片 | 實驗結果： 海 / JEA |
| Kahypar-E（EVOHGP） | Gecco'18 | 紙 | tr | 幻燈片 | 實驗結果 |
| kahypar-ca | 海17 | 紙 | - | 幻燈片 | 實驗結果 |
| kahypar-k | Alenex'17 | 紙 | - | 幻燈片 | 實驗結果 |
| kahypar-r | Alenex'16 | 紙 | tr | 幻燈片 | 實驗結果 |
Karlsruhe HyperGraph分區框架需要：
g++的編譯器，例如9或更高版本或clang版本11.0.3或更高版本。-DKAHYPAR_USE_MINIMAL_BOOST=ON flag on flag下載，提取和自動構建必要的依賴項。 克隆存儲庫，包括子模型：
git clone --depth=1 --recursive [email protected]:SebastianSchlag/kahypar.git
創建一個構建目錄： mkdir build && cd build
運行cmake： cmake .. -DCMAKE_BUILD_TYPE=RELEASE
運行make： make
構建項目時會自動執行測試。另外，還提供了test目標。端到端集成測試可以開始： make integration_tests 。可以通過cmake標誌啟用分析： -DENABLE_PROFILE=ON 。
可以通過make KaHyPar構建獨立程序。二進製文件將位於： build/kahypar/application/ 。
Kahypar有幾個配置參數。有關所有可能參數的列表，請運行： ./KaHyPar --help 。我們將HMETIS格式用於輸入HyperGraph文件以及分區輸出文件。
命令行參數--quiet=1可用於抑制所有記錄輸出。如果您使用的是庫界面，則將quiet=1添加到相應的.ini配置文件中具有相同的效果。
我們提供兩種默認框架配置 - 一種用於遞歸兩部分（ R KAHYPAR），另一種用於直接K -Way分區（ K Kahypar）。
通常，我們建議使用K Kahypar，因為它的運行時間和解決方案質量都比R Kahypar更好。
啟動k Kahypar優化（連接 - 1）目標運行：
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar_sea20.ini
啟動K Kahypar優化剪切目標運行：
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m direct -p ../../../config/cut_kKaHyPar_sea20.ini
啟動r kahypar優化（連接 - 1）目標運行：
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m recursive -p ../../../config/km1_rKaHyPar_sea20.ini
啟動r kahypar優化剪切目標運行：
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o cut -m recursive -p ../../../config/cut_rKaHyPar_sea20.ini
啟動模因算法k kahypar -e優化（連接 - 1）目標運行：
./KaHyPar -h <path-to-hgr> -k <# blocks> -e <imbalance (e.g. 0.03)> -o km1 -m direct -p ../../../config/km1_kKaHyPar-E_sea20.ini
此外，我們提供了與Alenex'16，Alenex'17，Sea'17，Sea'18，Gecco'18以及我們的JEA Journal Journal Paper和Sebastian Schlag的論文中使用的出版物中使用的配置相對應的不同預設。這些配置位於config/old_reference_configs文件夾中。為了使用這些配置，您必須檢查Kahypar Release 1.1.0，因為在最新版本中刪除了一些舊代碼。
啟動KAHYPAR-MF（使用基於流的改進）使用直接K-Way模式運行優化（連接 - 1）目標：
./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
啟動Kahypar-MF（使用基於流量的改進）使用直接K-Way模式運行來優化切割目標：
./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
開始使用直接k-way模式運行evoHGP/kahypar-e優化（連接-1）目標
./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
請注意，配置km1_direct_kway_gecco18.ini基於kahypar-ca。但是，Kahypar-E還可以與基於流的本地改進一起工作。在我們的JEA出版物中，使用了km1_kahypar_e_mf_jea19.ini配置。
啟動Kahypar-CA（使用社區意識更粗化）使用直接K-Way模式運行優化（連接 - 1）目標：
./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
以直接Kway模式（KAHYPAR-K）優化（連接 - 1）目標運行：
./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-R）優化切割目標運行的Kahypar：
./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
所有預設參數都可以通過使用相應的命令行選項來覆蓋。
當創建HyperGraph Kahypar時，驗證輸入實際上是正確的超圖，否則打印錯誤並流產。這適用於HGR輸入文件，C接口和Python接口。在幾乎所有情況下，驗證的運行時成本都應該可以忽略不計。但是，也可以使用CMAKE FLAG -DKAHYPAR_INPUT_VALIDATION=OFF禁用輸入驗證。
此外，針對非致命問題印刷了警告（例如，具有重複銷的超級馬匹）。要將非致命問題視為硬錯誤，請使用CMAKE FLAG -DKAHYPAR_INPUT_VALIDATION_PROMOTE_WARNINGS_TO_ERRORS=ON 。
我們提供了一個簡單的C風格接口，以使用Kahypar作為庫。請注意，此界面尚未線程安全。但是，有一些現有的解決方法。可以通過
make install.library可以這樣使用：
# 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);
}使用g++運行編譯程序：
g++ -std=c++14 -DNDEBUG -O3 -I/usr/local/include -L/usr/local/lib program.cc -o program -lkahypar Note: If boost is not found during linking, you might need to add -L/path/to/boost/lib -I/path/to/boost/include -lboost_program_options to the command.
要從系統中刪除庫，請使用提供的卸載目標：
make uninstall-kahypar要編譯Python界面，請執行以下操作：
mkdir build && cd buildcmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 。如果您沒有安裝Boost，請運行： cmake .. -DCMAKE_BUILD_TYPE=RELEASE -DKAHYPAR_PYTHON_INTERFACE=1 -DKAHYPAR_USE_MINIMAL_BOOST=ON代替。這將自動下載，提取和構建必要的依賴項。cd pythonmakecp kahypar.so <path-to-site-packages>之後，您可以這樣使用Kahypar Libary：
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 )有關Python庫功能的更多信息，請參見：module.cpp
我們還提供了預編譯版本作為a，可以通過以下方式安裝：
python3 -m pip install --index-url https://pypi.org/simple/ --no-deps kahypar
感謝Jordan Jalving（@Jalving）Kahypar現在還提供了朱莉婭界面，目前可以在此處找到：Kahypar/kahypar.jl。
相應的依賴性可以通過：
using Pkg
Pkg . add ( PackageSpec (url = " https://github.com/jalving/KaHyPar.jl.git " ))
Pkg . test ( " KaHyPar " )之後，您可以使用Kahypar這樣的超圖表：
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）為卡希巴爾（Kahypar）創建了Java界面。請參閱README，以獲取有關如何構建和使用接口的詳細說明。
我們鼓勵您通過該項目的GitHub問題跟踪系統報告Kahypar的任何問題。
Kahypar是根據GNU通用公共許可證（GPLV3）提供的免費軟件。有關更多信息，請參見複製文件。我們可以自由分發此框架，以促進HyperGraph分區工具的使用和開發。如果您在學術環境中使用Kahypar，請引用適當的論文。如果您對商業許可感興趣，請與我聯繫。
// 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}
}
如果您有興趣為Kahypar框架做出貢獻，請隨時與我聯繫或在問題跟踪系統上創建問題。
