我在研究图切割算法的数据结构。问题是在最短路径上进行不同的切割。我做的数据结构，我不确定属性。
输入是最短路径的有向图，它是有界格，具有最小和最大元的偏序集。
将节点n的下一个节点n（n）定义为a在节点集L，N（L），N（N（L）），…其中，对于每个相邻的集对a，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
该算法可以在新格上重复调用。我担心的是：
有保证达到一个节点格吗？
有没有达到一个节点格的迭代次数的度量？我觉得界是输入图的直径。
我很感激任何类似的数据结构。
TNX公司
背景：
我有一个想法，使用最大流网络拦截问题，我正在工作的东西。我正在考虑顶点遮挡版本，其中给定数量的顶点可以从网络中移除，以最小化最大流。我所研究的网络是非常规则的平面有向图（平面分成六边形，每个顶点连接到6个顶点）。我只想切断从
source到sink的最短路径。为了使我使用有向图的简化，如果edge(a,b)在从a到sink的最短路径上，则edgeC在简化图中。如果边权为正，则简化有向图为格。这就是我所说的“最短路径有向图”。我想有很好的顶点切割（平行，传播，…），什么是更容易（非常结构化）晶格。
原生切割是“波浪”，例如，一个漂亮的切割也会产生漂亮的切割。正因为如此，我尝试用上面描述的操作来简化格。我试着描述了2个子集的顶点，它们是有趣的切割和用于映射的：
-波并行节点集。如果c是一个波，那么
N(C)是另一个波。-条纹-没有与其他条纹相交的一系列波。
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，每次迭代。这是因为最小的节点
C, N(C), N(N(C))和M位于同一条带上，从而减小了晶格直径。现在，执行或搜索切割是一个递归任务，在最后一个只有一个节点的网格之前开始一个，并以阶梯方式在一个整波或相邻波上进行切割。对于切割中的节点，获取映射在其中的子晶格，并在该子晶格上进行切割。直到到达初始晶格为止。
这种结构是一种点阵压缩结构。我认为它可以用于动态格割搜索。
在我的情况下，我没有使用它，因为一些其他项目的限制。我只用几行代码就很简单地解决了最初的问题，但我以前并没有意识到这一点：-）
最佳答案
有保证达到单节点晶格吗？
如果我正确理解你的伪码，不：它携带一个n节点线性顺序到一个n节点线性顺序。
我将您的代码描述为接受一个部分顺序并找到一个series-parallel partial order，其中它有一个合理的“忠实”嵌入。
如果你只想在平面图中找到最大流/最小割，那就有一个O(n log n) algorithm的值。