Graph/lattice simplification

Question

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 partitions:

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.

With this property create new lattice with mapping:

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

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

Background:

I had an idea to use Maximum flow network interdiction problem in stuff I was working on. I was thinking on vertex interdiction version where given number of vertices can be removed from network to minimize maximal flow. Network I was working on was very regular planar directed graph (plane divided in hexagons, each vertex is connected to 6 vertices). I wanted to cut (interdict) only shortest paths from source to sink. To make that I used simplification of directed graph, edge (a,b) is in simplified graph if it is on shortest path from a to sink. If edge weight are positive, than simplified directed graph is lattice. This is what I called "directed graph of shortest paths".

I wanted to have vertex cuts that are nice (parallel, propagation, ...), what is easier on (very structured) lattice.

Native cuts are 'waves', e.g. one nice cut C also produce N(C) which is nice. Because of that I tried to simplified lattice with operations described above. I tried to describe 2 subsets of vertices that are interesting for cuts and used in mapping: - wave - parallel set of nodes. If C is one wave, than N(C) is another. - stripe - series of waves without intersection with other stripes. 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.

Mapping maps stripe from initial lattice to node of new lattice. Nodes in new lattice are connected if they share wave. Direction of edge is from stripe that share last wave to stripe that share first wave.

Because mapping produces new lattice with same properties, procedure can be repeated until there is lattice with only one node. That can be shown because lattice diameter is smaller, at least for 1, with each iteration. That is because minimal node M and N(M) are in same stripe, and that reduces lattice diameter.

Now, performing or searching for cuts is recursive task, start with lattice one before the last one with only one node, and make cut on one whole wave or on neighboring waves in staircase way. For nodes in cut take sub-lattice that is mapped in it, and make cut on that sub-lattice. Same is done until reaching initial lattice.

This structure is some kind on lattice compression. I think it can be used for dynamic lattice cuts searching.

In my case, I'm not using it since some other project restrictions. I solved initial problem very simple with only few lines of code, but I didn't realize it can be done like that before :-)

Answer 1

Is there a guarantee to reach a one-node lattice?

If I understand your pseudocode correctly, no: it carries an n-node linear order to an n-node linear order.

I would describe your code as accepting a partial order and finding a series-parallel partial order into which it has a reasonably “faithful” embedding.

If you're just interested in finding max flows/min cuts in planar graphs, there's an O(n log n) algorithm for that.