Commits

Kirill Simonov committed d12c690

Implemented optimal layering algorithm.

Comments (0)

Files changed (1)

 
 
 def layer(graph):
-    return layer_respecting_rank(graph)
+    return layer_simplex(graph)
 
 
 def layer_neatly(graph):
     return graph
 
 
+def layer_simplex(graph):
+    ensure(graph.readonly(WithNodeRank), "without node ranks", graph)
+    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
+    ensure(not graph.readable(WithLayers), "already with layers", graph)
+
+    graph.upgrade(WithLayers)
+
+    A = dict(((i,j),0) for i in range(len(graph.nodes)) for j in range(len(graph.arcs)))
+    B = [0]*len(graph.nodes)
+    C = [0]*len(graph.arcs)
+
+    for arc in graph.arcs:
+        if arc.origin is arc.target:
+            continue
+        w = arc.weight.value
+        i1 = arc.origin.idx
+        i2 = arc.target.idx
+        if arc.origin.rank < arc.target.rank:
+            i1, i2 = i2, i1
+        j = arc.idx
+        A[i1,j] = +1
+        A[i2,j] = -1
+        C[j] = 1
+        B[i1] += w
+        B[i2] -= w
+
+    positions = simplex(A, B, C)
+
+    idx_by_position = {}
+    for idx in range(len(positions)):
+        position = int(positions[idx])
+        idx_by_position.setdefault(position, [])
+        idx_by_position[position].append(idx)
+    for position in sorted(idx_by_position):
+        layer = graph.add_layer()
+        for idx in idx_by_position[position]:
+            node = graph.nodes[idx]
+            layer.add_node_bead(node)
+
+    for arc in graph.arcs:
+        head = min(arc.origin.layer.idx, arc.target.layer.idx) + 1
+        tail = max(arc.origin.layer.idx, arc.target.layer.idx)
+        for idx in range(head, tail):
+            graph.layers[idx].add_arc_bead(arc)
+
+    graph.freeze(WithLayers)
+
+    return graph
+
+
 def order(graph):
     return order_median(graph)
 
     #debug_simplex(A, B, C)
 
     eps = 1e-5
-    assert all(b >= -eps for b in B)
-    while not all(c >= -eps for c in C):
+    while not (all(c >= -eps for c in C) and all(b >= -eps for b in B)):
         i0 = None
         j0 = None
-        for j in range(N):
-            if C[j] < -eps:
-                j0 = j
-                break
-        for i in range(M):
-            if A[i,j0] > eps:
-                if i0 is None or B[i]/A[i,j0] < B[i0]/A[i0,j0]:
+        if all(b >= -eps for b in B):
+            for j in range(N):
+                if C[j] < -eps:
+                    j0 = j
+                    break
+            for i in range(M):
+                if A[i,j0] > eps:
+                    if i0 is None or B[i]/A[i,j0] < B[i0]/A[i0,j0]:
+                        i0 = i
+        else:
+            for i in range(M):
+                if B[i] < -eps:
                     i0 = i
-        assert i0 is not None
+                    break
+            for j in range(N):
+                if A[i0,j] < -eps:
+                    j0 = j
+                    break
+            for i in range(M):
+                if A[i,j0] > eps and B[i] > -eps:
+                    if B[i]/A[i,j0] <B[i0]/A[i0,j0]:
+                        i0 = i
+        assert i0 is not None and j0 is not None
         AA = {}
         BB = [None]*M
         CC = [None]*N