Lib.rs

一个用于在加权、无向图中寻找固定成本电路的快速、通用模块。

用法

speedicycle 二进制文件（在Linux上编译，但预期在大多数Unix派生的系统上运行）可以通过命令行使用，语法为

speedicycle -i ['path_to_input_file.txt'] -s ['index of source node'] -t ['target path cost']

目前，输入文件必须包含无向、加权图的描述，格式为DIMACS。具体来说，文件应仅包含纯文本，具体为

• 以字符 p 开头的标题行，包含图中的节点/顶点和边的数量，例如，对于包含4000个节点和5000条边的图，为 p 4000 5000
• 图中的每个顶点一行，以字符 v 开头并包含一个数值标签，例如 v 11213。这些顶点将在以后通过它们在列表中的位置（从零开始索引）来引用。
• 图中的每条边一行，以字符 e 开头并包含一个起始顶点、一个结束顶点和一个数值权重。这里的顶点通过它们在上面的顶点列表中的索引位置来引用。例如，e 0 1 25，表示连接列表中第0个和第1个顶点的权重为25的边。

此格式的示例包含在 DIMACS_sample.txt。 正在开发对其他格式的支持，欢迎在该方面做出贡献！

背景

此工具最初是为了在街道网格数据中定位固定距离的闭合环路行走路径而设计的（以及由此扩展出的预定时间的步行路线）。然而，寻找指定成本的电路问题具有更广泛的应用。

这里的中心算法实现了Lewis和Corcoran的“双路径启发式”，以找到由两个从源节点 s 到目标节点 t 的边不相交路径组成的可行电路，每个路径的成本约为 k/2，其中 k 是穿越电路的总期望成本。通过策略性地选择目标节点（并在每次计算后消除不可行的路径），可以以令人印象深刻的效率找到合适的路径（如果存在的话）。

实现

Speedicycle 是基于 petgraph 构建的，它提供了双重路径例程运行在之上的底层图结构，以及包括迪杰斯特拉和摩尔最短路径算法在内的基本图遍历算法，这两个算法在这里都被使用。

还包括了 Ramesh Bhandari 的方法，用于在节点 s 和 t 之间找到两条边不交的路径。简要来说，一旦找到了两个节点之间的最短路径，就会沿着路径添加方向，并调整权重以严重惩罚原方向的重新遍历。找到新的最短路径后，然后将它们“解耦”以产生最终的电路。

最后，使用 Hierholzer 算法在无向图中定位欧拉回路，以正确排序结果路径中的顶点。

最后说明

欢迎您的反馈、建议和贡献！如果您发现错误，请提出问题，并请随意（但不强制）提交带有修复的 PR。如果您只是想讨论，请通过 LinkedIn 或我的 个人网站 联系我。不久再见！