我正在为图割算法设计数据结构。问题是在最短路径上进行不同的切割。我已经创建了一种数据结构，但我不确定其属性。
输入是最短路径的有向图，它是一个有界格点图，具有最小元素和最大元素。
将节点n的后继节点N(n)定义为节点b的集合，其中a < b且不存在c使得a < c < b。类似地，定义前驱节点P(n)。将定义扩展到集合上，令N(S)为S中所有节点n的N(n)的并集，P(S)同理。
在节点集合L、N(L)、N(N(L))...上进行不同切割是容易的，对于相邻的节点集合A和B，满足N(A)=B，并且不存在划分。
A = A_1 union A_2
B = B_1 union B_2
with B_i = N(A_i), A_i = P(B_i) for i=1,2.
使用此属性创建新的格子与映射：
- 将子格子映射到一个节点
- 如果找到上分区，则创建边缘（分区基数号码）。
简单来说，格子 -> 格子映射的算法是：
A = {minimum node}
new_node = [A]
1:
while A, N(A) don't have partitions
append N(A) to new_node
A = N(A)
for each partition $B_i$
last_new_node = new_node
create new_node = [B_i]
create edge last_new_node to new_node
go to 1
At the end fix maximum node in new lattice if needed
这个算法可以在新的点阵上重复调用。我担心以下问题：
- 有保证达到单节点点阵的保障吗？
- 是否有达到单节点点阵所需迭代次数的度量方式？对我来说，界限似乎是输入图的直径。
源到汇的最短路径。为此，我使用了有向图的简化，如果边(a，b)在从a到汇的最短路径上，则它在简化图中。如果边缘权重为正，则简化的有向图是点阵。这就是我所谓的“最短路径的有向图”。我希望有漂亮的顶点割（平行，传播，...），在（非常有结构的）点阵上更容易。原始割是'波动'，例如一个好的割
C也产生一个好的N(C)。因此，我尝试用上述操作简化点阵。我试图描述对削减有趣并用于映射的2个顶点子集：
-波浪-平行节点集。如果C是一波，则N(C)是另一波。
-条纹-一系列没有与其他条纹相交的波浪。C，N（C），N（N（C））。 B1--C1--D1 ...
/ \ / \ /
A X X
\ / \ / \
B2--C2--D2
Waves: {A}, {B1,B2}, {C1,C2}, {D1,D2}
Stripe is made of these 4 waves.
将初始化网格中的条带映射到新网格的节点。如果节点共享波，则在新网格中连接节点。边缘的方向是从共享最后一波的条带到共享第一波的条带。
由于映射产生具有相同属性的新网格，因此可以重复该过程，直到只有一个节点的网格存在。这是因为每次迭代都会减小网格直径，至少为1。这是因为最小节点M和N(M)在同一个条带中，这减小了网格直径。
现在，在倒数第二个只有一个节点的网格上开始递归执行或搜索切割任务，并通过阶梯式方式在整个波或相邻波上进行切割。对于切割中的节点，取其映射的子网格，并在该子网格上进行切割。直到达到初始网格为止。
这种结构是某种网格压缩。我认为它可以用于动态网格切割搜索。
在我的情况下，由于其他项目限制，我没有使用它。我用了几行简单的代码来解决最初的问题，但之前我没有意识到可以这样做 :-)