将带互连的网格聚类为相似长度连通段的算法咨询

我拥有一个包含大量互连结构的网格，该网格由不同长度的边构成。我希望将其聚类为相似长度的连通段，要求：

• 同一簇中的边必须相互连通
• 可设定最大簇长度以控制簇的数量
• 目标是创建尽可能少的簇

目前我已用NetworkX构建了对应图结构，但通过ChatGPT获取的方案未达预期，想咨询适配的算法。

附网格边缘特征节点提取图：

针对这种带连通性、长度约束的边聚类场景，推荐以下几种可直接适配NetworkX的算法思路：

1. 贪心合并算法 #

这是最贴合“最小簇数量”目标且易实现的方案：

• 执行步骤：
  • 初始状态：每条边单独作为一个簇，记录簇的长度范围、边集合及连通节点范围
  • 循环迭代：查找满足条件的相邻簇——簇内边与待合并边的长度差异在阈值内，且合并后总长度不超过设定的最大簇长度；优先合并规模大或长度差异最小的组合
  • 终止条件：无合法可合并簇时停止
• NetworkX适配：用nx.edges()遍历边，nx.neighbors()定位相邻边节点，维护簇的核心属性即可快速实现

2. 带连通约束的层次聚类 #

在传统层次聚类基础上加入长度与连通性限制：

• 执行步骤：
  • 仅为共享节点的相邻边计算长度相似度（如1减去长度差的归一化值），非相邻边相似度设为0
  • 采用凝聚式层次聚类，每次合并相似度最高且连通的簇，同时校验合并后总长度是否符合阈值
• NetworkX适配：结合scipy.cluster.hierarchy工具，自定义距离函数，用NetworkX的连通性检查过滤无效合并

3. 整数规划（最优解方向） #

若需严格最小化簇数量，可建模为整数规划问题：

• 核心设定：
  • 目标函数：最小化簇的总数量
  • 约束条件：每条边仅属一个簇；同一簇内边必须连通；簇内边长度差异在阈值内且总长度不超最大限制
• 实现：用pulp/gurobi等库构建模型，NetworkX提供连通性约束逻辑

4. 自定义社区检测算法 #

调整经典社区检测的目标函数，适配“相似长度+连通”规则：

• 例如修改Louvain算法的模块度计算，将边的长度相似度纳入权重，优先划分长度相似的连通边为同一社区；若存在超阈值簇，再做二次拆分
• NetworkX适配：借助python-louvain库，自定义边权重为长度相似度，运行检测后做阈值校验调整

内容的提问来源于stack exchange，提问作者Matthias