Sugiyama算法n-level BC布局Phase 2的正确解读与流程问询

背景 #

我正试图理解原论文《Methods for Visual Understanding of Hierarchical System Structures》中描述的Sugiyama图布局算法。已掌握核心步骤：打破循环、分层、添加虚拟顶点、减少交叉、优化水平位置，也理解2-level BC方法（重心排序）——该方法迭代执行Phase 1（按重心稳定排序行/列）和Phase 2（反转重心相等的行/列）。

核心困惑 #

但难以解读论文中n-level BC方法的描述，该方法迭代应用“DOWN-UP过程”：先重排层[1..n-1]的底层顶点，再重排层[2..n]的顶层顶点。尤其困惑的是Phase 2（反转重心相等节点）在n-level方法中的位置——论文表述模糊，且示例与描述不符。

论文指出需按层迭代减少交叉，每次迭代包含DOWN和UP扫描，称此迭代过程为Phase 1，但未明确Phase 1是完整DOWN-UP迭代还是单次DOWN/UP扫描（示例暗示后者但无明确说明）。论文提到“Phase 1执行后若存在重心相等的行/列集合，则执行Phase 2”，其描述为：

Phase 2包含DOWN和UP两个过程。在DOWN（或UP）过程中，反转第i层中重心相等的列（或行）的顺序，然后从DOWN（或UP）过程开始执行Phase 1；当Phase 1以DOWN（或UP）过程终止时，Phase 2从DOWN（或UP）过程开始。

反复阅读并对照示例后，仍无法明确Phase 1与Phase 2的交错流程结构。考虑到重排后会同时存在重心相等的行和列，顶层迭代流程是否为以下选项之一：

• 选项1：Phase-1 DOWN → Phase-2 DOWN → Phase-2 UP → Phase-1 UP
• 选项2：Phase-1 DOWN → Phase-2 DOWN → Phase-1 UP → Phase-2 UP
• 选项3：Phase-1 DOWN → Phase-1 UP → Phase-2 UP → Phase-2 DOWN → Phase-1 DOWN
• 选项4：其他结构？

论文示例的操作顺序暗示选项1，但配套文本（“Phase-1 DOWN开始”→“Phase-1结束”→“Phase-2 DOWN”→“Phase-2 UP”→“Phase-1 UP”→“Phase 1 DOWN”→“Phase 2结束”）让我十分困惑。

补充信息 #

查阅了Sugiyama算法的开源实现，发现均未针对n-level BC过程实现Phase 2，可能是该步骤实用性不高，或是无人完全理解论文此处内容。

请求 #

希望获得清晰明确的顶层迭代循环算法规范，仅需循环结构，无需具体步骤细节（已掌握）。

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