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框架做出贡献，请随时与我联系或在问题跟踪系统上创建问题。
