algorithm - 图形/点阵简化

Question

我正在研究图形切割算法的数据结构。问题是在最短路径上进行不同的切割。我制作了我不确定属性的数据结构。

输入是最短路径的有向图，它是有界格、具有最小和最大元素的偏序集。

将节点 n 的下一个节点 N(n) 定义为 a < b 且不存在 a < c < b 的 c 的一组节点 b。类似地定义前一个节点 P(n)。扩展集合上的定义，对于 S 中的 n，N(n) 的 N(S) 并集，对于 P(S) 类似。

很容易对节点集 L、N(L)、N(N(L))、...没有分区:

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.

使用此属性创建具有映射的新晶格:

子格到一个节点

如果找到上分区而不是创建边(分区基数)。

简单来说，lattice -> lattice mapping 的算法是:

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

这个算法可以在新的格子上重复调用。我担心:

是否有保证达到单节点点阵？

是否有任何迭代次数的度量以达到单节点晶格？对我来说，边界是输入图的直径。

我很欣赏任何类似数据结构的链接。

肿瘤坏死因子

背景:

我有一个想法，在我正在研究的东西中使用最大流量网络拦截问题。我正在考虑顶点拦截版本，其中可以从网络中删除给定数量的顶点以最小化最大流量。我正在研究的网络是非常规则的平面有向图(平面分为六边形，每个顶点连接到 6 个顶点)。我只想从 source 中截断(阻止)最短路径至sink .为了做到这一点，我使用了有向图的简化，边 (a,b)如果它在距离 a 的最短路径上，则在简化图中至sink .如果边权重为正，则简化的有向图是格的。这就是我所说的“最短路径的有向图”。

我想要有很好的顶点切割(平行，传播，......)，在(非常结构化的)晶格上更容易。

原生剪辑是“波浪”，例如一个漂亮的剪裁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.

映射将 strip 从初始晶格映射到新晶格的节点。如果新晶格中的节点共享波，则它们是连接的。边缘的方向是从共享最后一波的条纹到共享第一波的条纹。

因为映射会产生具有相同属性的新格，所以可以重复该过程，直到出现只有一个节点的格为止。这可以显示出来，因为每次迭代时晶格直径都较小，至少对于 1。那是因为最小节点 M和 N(M)是相同的条纹，这减少了晶格直径。

现在，执行或搜索切割是递归任务，从只有一个节点的最后一个之前的格子开始，并以阶梯方式在整个波或相邻波上进行切割。对于 cut 中的节点，获取映射在其中的子晶格，并在该子晶格上进行切割。在到达初始晶格之前也是如此。

这种结构是某种晶格压缩。我认为它可以用于动态晶格切割搜索。

就我而言，由于其他一些项目限制，我没有使用它。我只用几行代码就非常简单地解决了最初的问题，但我没有意识到之前可以这样做:-)

Answer 1

是否可以保证达到单节点晶格？

如果我正确理解了您的伪代码，则不会:它带有 n 节点线性顺序到 n 节点线性顺序。

我会将您的代码描述为接受部分订单并找到 series-parallel partial order它具有合理的“忠实”嵌入。

如果您只想在平面图中找到最大流量/最小切割，这里有 O(n log n) algorithm为了那个原因。