# Lattice simplification

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

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

Input is directed graph of shortest paths, which is bounded lattice, partially ordered set with minimum and 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. Similar define previous node P(n). Extend definitions on sets, N(S) union of N(n) for $n \in S$, similar 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.

Tnx

-