arboretum是一个用于计算树分解的图库和CLI。实现了各种最先进的预处理、图约简、精确和启发式算法来获取树分解。

功能

• 如最小度数和最小填充等知名快速启发式算法[1]
• 如禁忌局部搜索等元启发式算法[3]
• 最小最小宽度下界启发式算法[4]
• 用于减少图和获取树宽度≤3的图的树分解的基于规则的预处理[5]
• 基于安全分隔符概念的图分解[6]
• 最先进的精确算法[8]

CLI

构建

由于arboretum是用rust实现的，CLI可以通过cargo简单地构建

cargobuild --release --特性="cli"

使用方法

使用.gr格式的图，程序可以使用如下方式

cargo run --release --features="cli" < <graph.gr>

或

./target/release/arboretum-cli < <graph.gr>

CLI会根据输入图自动选择使用哪种算法，但没有启发式标志将始终尝试找到精确解。

可用的CLI参数

USAGE:
    arboretum-cli [OPTIONS] [ARGS]

FLAGS:
    -h, --help       Prints help information
    -V, --version    Prints version information

OPTIONS:
    -m, --mode <mode>          Mode. 'heuristic', 'exact' or 'auto'. Defaults to Exact. Any invalid input fails silently
                               to 'heuristic'
    -s, --seed <seed>          Seed used for all rng. Unsigned 64bit integer value. Defaults to '0' if missing
    -t, --timeout <timeout>    Optional timeout value for heuristic algorithm. In heuristic mode the CLI stops on ctrl+c
                               and outputs the current best solution. This might take a few seconds or minutes depending
                               on the size of the input graph. When timeout is set, the algorithm tries to optimize a
                               solution until the timeout is reached

cargobuild --release

库

使用方法

只需将arboretum-td添加到项目的cargo.toml依赖项中，即可开始使用。有关文档，请参阅docs.rs。

参考文献

Hans L. Bodlaender和Arie M. C. A. Koster。2010. Treewidth computations I. Upper bounds。Inf. Comput. 208, 3 (2010年3月)，259–275。DOI：https://doi.org/10.1016/j.ic.2009.03.008

Bannach, Max & Berndt, Sebastian & Ehlers, Thorsten. (2017). Jdrasil: A Modular Library for Computing Tree Decompositions。10.4230/LIPIcs.SEA.2017.28。

Hammerl T., Musliu N., Schafhauser W. (2015) Metaheuristic Algorithms and Tree Decomposition。在Kacprzyk J., Pedrycz W. (eds) Springer Handbook of Computational Intelligence。Springer Handbooks。Springer, Berlin, Heidelberg。 https://doi.org/10.1007/978-3-662-43505-2_64

Bodlaender H.L., Koster A.M.C.A., Wolle T. (2004) Contraction and Treewidth Lower Bounds。在Albers S., Radzik T. (eds) Algorithms – ESA 2004。ESA 2004。Lecture Notes in Computer Science，vol 3221。Springer, Berlin, Heidelberg。 https://doi.org/10.1007/978-3-540-30140-0_56

艾克霍夫，弗兰克 & 博德兰德，汉斯。 (2002)。加权树宽的安全缩减规则。176-185。

汉斯·L·博德兰德，阿德里安·M.C.A·科斯特。安全分隔符对于树宽，《离散数学》，第306卷，第3期，2006年，第337-350页，ISSN 0012-365X，https://doi.org/10.1016/j.disc.2005.12.017。

德尔，霍尔格，科穆西耶维奇，克里斯蒂安，塔尔蒙，尼姆罗德，韦勒，马蒂亚斯。“PACE 2017参数化算法和计算实验挑战：第二次迭代”（2018）DOI：10.4230/LIPIcs.IPEC.2017.30

田崎，H.。“基于正实例的树宽动态规划。”ESA（2017）。

班纳赫，马克斯和塞巴斯蒂安·伯恩特。“基于正实例的图搜索动态规划。”WADS（2019）。

许可证

本软件根据MIT许可证授权，可在本存储库中的LICENSE文件中找到。