Lattice simplification

Question

Update: There is an answer on same question I posted on Stack Overflow.

I'm working on a data structure for the graph cut algorithm. The problem is to make different cuts on the shortest paths. I made a data structure for which I'm not sure about properties.

The input is a directed graph of shortest paths, which is a bounded lattice, partially ordered set with a minimum and a maximum element.

Define next node N(n) of node n as a set of nodes b for which a < b and there is no c with a < c < b. Similarly, define previous node P(n). Extend definitions on sets, N(S) union of N(n) for $n \in S$, and similarly for P(S).

It is easy to make different cuts on list of set of nodes $L, N(L), N(N(L)), ...$ where for each neighboring pair of sets A, N(A)=B holds that there is no partition of $A=A_1 \cup A_2$ and $B=B_1 \cup B_2$ with $B_i = N(A_i)$, $A_i = P(B_i)$ for $i=1,2$.

With this property create new lattice with mapping:

• sub-lattice to one node
• if upper partition is found create partition cardinality number of edges.

In simple, algorithm for lattice -> lattice mapping is:

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

This algorithm can be called repeatedly on new lattices. I'm concern about:

• Is there guaranty to reach one-node lattice?
• Is there any measure of number of iterations to reach one-node lattice? It seams to me that bound is diameter of input graph.

I appreciate link to any similar data structure.

Thanks.

Answer 1

There is an answer on same question I posted on Stack Overflow.

Structure I was looking for is series-parallel partial order.