Commits

Kirill Simonov  committed 0b2271d

Fixed layering; sped up hybrid ordering, simplex algorithms.
Also added graphviz rendering and generating graph from a database schema.

  • Participants
  • Parent commits d12c690

Comments (0)

Files changed (4)

File algorithm.py

         w = arc.weight.value
         i1 = arc.origin.idx
         i2 = arc.target.idx
-        if arc.origin.rank < arc.target.rank:
+        if arc.origin.rank.value < arc.target.rank.value:
             i1, i2 = i2, i1
         j = arc.idx
         A[i1,j] = +1
         B[i1] += w
         B[i2] -= w
 
-    positions = simplex(A, B, C)
+    positions = simplex_fast(A, B, C)
 
     idx_by_position = {}
     for idx in range(len(positions)):
 
 
 def order(graph):
-    return order_median(graph)
+    return order_hybrid(graph)
 
 
 def order_by_default(graph):
     return graph
 
 
+def order_hybrid(graph):
+    ensure(graph.readonly(WithLayers), "without layers", graph)
+    ensure(not graph.readable(WithBeadOrder), "already with bead orders", graph)
+
+    graph.upgrade(WithBeadOrder)
+
+    weights = {}
+    layer = graph.layers[0]
+    for next_layer in graph.layers[1:]:
+        for bead in layer.beads:
+            for next_bead in next_layer.beads:
+                arcs = []
+                if bead.is_node:
+                    for arc in bead.node.incoming+bead.node.outgoing:
+                        if next_bead.is_node and next_bead.node in [arc.origin, arc.target]:
+                            arcs.append(arc)
+                        elif next_bead.is_arc and next_bead.arc is arc:
+                            arcs.append(arc)
+                else:
+                    if next_bead.is_node and bead.arc in next_bead.node.incoming+next_bead.node.outgoing:
+                        arcs.append(bead.arc)
+                    elif next_bead.is_arc and bead.arc is next_bead.arc:
+                        arcs.append(bead.arc)
+                weight = 0.0
+                for arc in arcs:
+                    weight += arc.weight.value
+                weights[bead, next_bead] = weight
+                weights[next_bead, bead] = weight
+        layer = next_layer
+
+    order_by_bead = {}
+    next_order_by_layer = {}
+    for layer in graph.layers:
+        next_order_by_layer[layer] = 0
+    stack = []
+    stack.extend(reversed(graph.beads))
+    while stack:
+        bead = stack.pop()
+        if bead in order_by_bead:
+            continue
+        value = next_order_by_layer[bead.layer]
+        order_by_bead[bead] = value
+        next_order_by_layer[bead.layer] = value+1
+        stack.extend(bead.neighbors)
+
+    def crossings():
+        total = 0.0
+        layer = graph.layers[0]
+        for next_layer in graph.layers[1:]:
+            for lbead in layer.beads:
+                lorder = order_by_bead[lbead]
+                for rbead in layer.beads:
+                    rorder = order_by_bead[rbead]
+                    if rorder <= lorder:
+                        continue
+                    for next_lbead in next_layer.beads:
+                        if not weights[lbead, next_lbead]:
+                            continue
+                        next_lorder = order_by_bead[next_lbead]
+                        for next_rbead in next_layer.beads:
+                            if not weights[rbead, next_rbead]:
+                                continue
+                            next_rorder = order_by_bead[next_rbead]
+                            if next_rorder >= next_lorder:
+                                continue
+                            total += weights[lbead, next_lbead]*weights[rbead, next_rbead]
+            layer = next_layer
+        return total
+
+    best_crossings = crossings()
+    best_order_by_bead = order_by_bead.copy()
+
+    next_layouts = zip(graph.layers[1:], graph.layers[:-1])
+    current_layouts = zip(graph.layers[:-1][::-1], graph.layers[1:][::-1])
+    for count in range(len(graph.layers)):
+        current_layouts, next_layouts = next_layouts, current_layouts
+
+        for layer, opposite_layer in current_layouts:
+            beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
+            medians = {}
+            for bead in beads:
+                neighbors = sorted(order_by_bead[neighbor]
+                                  for neighbor in opposite_layer.beads if weights[bead,neighbor] > 0.0)
+                if not neighbors:
+                    value = order_by_bead[bead]
+                else:
+                    length = len(neighbors)
+                    if length % 2 == 1:
+                        value = neighbors[length/2]
+                    elif length == 2:
+                        value = 0.5*sum(neighbors)
+                    else:
+                        l = neighbors[length/2-1] - neighbors[0]
+                        r = neighbors[-1] - neighbors[length/2]
+                        value = 1.0*(l*neighbors[length/2-1]+r*neighbors[length/2])/(l+r)
+                medians[bead] = value
+            beads = sorted(beads, key=(lambda bead: medians[bead]))
+            for idx, bead in enumerate(beads):
+                order_by_bead[bead] = idx
+
+        improved = True
+        while improved:
+            improved = False
+            for prev_layer, layer, next_layer in zip([None]+graph.layers[:-1],
+                                                     graph.layers,
+                                                     graph.layers[1:]+[None])[::-1]:
+                beads = sorted(layer.beads, key=(lambda bead: order_by_bead[bead]))
+                for delta in [+1, -1]:
+                    if delta > 0:
+                        idx = 0
+                    else:
+                        idx = len(beads)-2
+                    while 0 <= idx < len(beads)-1:
+                        left = beads[idx]
+                        right = beads[idx+1]
+                        direct = 0.0
+                        reverse = 0.0
+                        for opposite_layer in [prev_layer, next_layer]:
+                            if opposite_layer is None:
+                                continue
+                            for left_neighbor in opposite_layer.beads:
+                                left_weight = weights[left_neighbor, left]
+                                for right_neighbor in opposite_layer.beads:
+                                    right_weight = weights[right_neighbor, right]
+                                    if order_by_bead[left_neighbor] > order_by_bead[right_neighbor]:
+                                        direct += left_weight*right_weight
+                                    if order_by_bead[left_neighbor] < order_by_bead[right_neighbor]:
+                                        reverse += left_weight*right_weight
+                        if reverse < direct:
+                            beads[idx] = right
+                            beads[idx+1] = left
+                            order_by_bead[left] = idx+1
+                            order_by_bead[right] = idx
+                            improved = True
+                        idx += delta
+
+        curr_crossings = crossings()
+        if curr_crossings < best_crossings:
+            best_crossings = curr_crossings
+            best_order_by_bead = order_by_bead.copy()
+            #print "NEW LAYOUT:", best_crossings
+
+    for bead in graph.beads:
+        value = best_order_by_bead[bead]
+        bead.set_order(value)
+
+    graph.freeze(WithBeadOrder)
+
+    return graph
+
+
 def place(graph):
     return place_simplex(graph)
 
                     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]:
+                    if B[i]/A[i,j0] < B[i0]/A[i0,j0]:
                         i0 = i
         assert i0 is not None and j0 is not None
         AA = {}
     #print "solution:", solution
     return solution
 
+def simplex_fast(A, B, C):
+    M = len(B)
+    N = len(C)
+    A = [[float(A[i,j]) for j in range(N)] for i in range(M)]
+    B = [float(b) for b in B]
+    C = [float(-c) for c in C]
+    X = [i for i in range(M)]
+    Y = [None for j in range(N)]
+
+    eps = 1e-5
+    while not (all(c >= -eps for c in C) and all(b >= -eps for b in B)):
+        i0 = None
+        j0 = None
+        p0 = None
+        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:
+                    p = B[i]/A[i][j0]
+                    if p0 is None or p < p0:
+                        i0 = i
+                        p0 = p
+        else:
+            for i in range(M):
+                if B[i] < -eps:
+                    i0 = i
+                    break
+            assert i0 is not None
+            for j in range(N):
+                if A[i0][j] < -eps:
+                    j0 = j
+                    break
+            assert j0 is not None
+            p0 = B[i0]/A[i0][j0]
+            for i in range(M):
+                if A[i][j0] > eps and B[i] > -eps:
+                    p = B[i]/A[i][j0]
+                    if p < p0:
+                        i0 = i
+                        p0 = p
+        assert i0 is not None and j0 is not None
+        AA = [None]*M
+        BB = [None]*M
+        CC = [None]*N
+        irange = range(i0)+range(i0+1, M)
+        jrange = range(j0)+range(j0+1, N)
+        s = A[i0][j0]
+
+        p = B[i0]/s
+        for i in irange:
+            BB[i] = B[i]-A[i][j0]*p
+        BB[i0] = p
+        q = C[j0]/s
+        for j in jrange:
+            CC[j] = C[j]-A[i0][j]*q
+        CC[j0] = -q
+        for i in irange:
+            r = A[i][j0]/s
+            AA[i] = A[i]
+            if abs(r) > eps:
+                for j in jrange:
+                    AA[i][j] -= A[i0][j]*r
+            AA[i][j0] = -r
+        AA[i0] = A[i0]
+        for j in jrange:
+            AA[i0][j] /= s
+        AA[i0][j0] = 1/s
+        A, B, C = AA, BB, CC
+        X[i0], Y[j0] = Y[j0], X[i0]
+
+    solution = [0]*M
+    for y, c in zip(Y, C):
+        if y is not None:
+            solution[y] = int(c)
+    #print "solution:", solution
+    return solution
+
 
 def place_simplex(graph):
     ensure(graph.readonly(WithLayers), "without layers", graph)
             if (i,j) not in A:
                 A[i,j] = 0
 
-    centers = simplex(A, B, C)
+    centers = simplex_fast(A, B, C)
     left = None
     right = None
     for bead in graph.beads:
+
+
+from model import build, WithNodeLabel, WithArcWeight
+from htsql import HTSQL
+from htsql.introspect import introspect
+
+
+def build_schema(db):
+    with HTSQL(db):
+        catalog = introspect()
+
+    graph = build(WithNodeLabel, WithArcWeight)
+
+    node_by_table = {}
+    for schema in catalog.schemas:
+        for table in schema.tables:
+            node = graph.add_node()
+            node.set_label(table.name)
+            node_by_table[table] = node
+
+    for schema in catalog.schemas:
+        for table in schema.tables:
+            origin = node_by_table[table]
+            for foreign_key in table.foreign_keys:
+                target_schema = catalog.schemas[foreign_key.target_schema_name]
+                target_table = target_schema.tables[foreign_key.target_name]
+                target = node_by_table[target_table]
+                is_parental = (target_table.primary_key is not None and
+                               all(column_name in target_table.primary_key.origin_column_names
+                                   for column_name in foreign_key.origin_column_names))
+                if is_parental:
+                    weight = 1.0
+                else:
+                    weight = 0.5
+                arc = graph.add_arc(origin, target)
+                arc.set_weight(weight)
+
+    graph.freeze()
+    return graph
+
+

File example-schema.py

+
+from model import WithGraphStyle
+from draw import measure, draw_smooth
+from algorithm import rank, layer, order, place
+from database import build_schema
+from graphviz import draw_graphviz
+import sys
+import re
+
+if len(sys.argv) != 2:
+    print "Usage: %s <db>" % sys.argv[0]
+    sys.exit(1)
+db = sys.argv[1]
+basename_match = re.search(r'[0-9a-zA-Z_-]+$', db)
+if basename_match is not None:
+    basename = basename_match.group()
+else:
+    basename = db
+
+example = build_schema(db)
+example.upgrade(WithGraphStyle)
+example.set_style(
+        arc_width=1.5,
+        border_width=1.5,
+        font_size=16.0)
+example.freeze()
+
+print "MEASURING..."
+measure(example)
+print "RANKING..."
+rank(example)
+print "LAYERING..."
+layer(example)
+print "ORDERING..."
+order(example)
+print "PLACING..."
+place(example)
+print "DONE"
+
+#print
+#print repr(example)
+
+#print
+#for node in example.nodes:
+#    print repr(node)
+
+#print
+#for arc in example.arcs:
+#    print repr(arc), arc.weight.value
+
+#print
+#for node in example.nodes_by_rank:
+#    print node, node.rank.value
+
+#print
+#for layer in example.layers:
+#    print repr(layer)
+#    for bead in layer.beads:
+#        print "\t", repr(bead)
+
+#print
+#for layer in example.layers:
+#    print repr(layer)
+#    for bead in layer.beads_by_order:
+#        print "\t", repr(bead)
+
+#print
+#print "(%s, %s)" % (example.size.width, example.size.height)
+#for node in example.nodes_by_rank:
+#    print node, "(%s, %s, %s, %s)" % (node.position.x, node.position.y, node.position.w, node.position.h)
+
+filename = "%s.sugiyama.png" % basename
+stream = open(filename, 'wb')
+draw_smooth(example, stream)
+stream.close()
+print "Sugiyama rendering is written to: %s" % filename
+
+filename = "%s.graphviz.png" % basename
+stream = open(filename, 'wb')
+draw_graphviz(example, stream)
+stream.close()
+print "GraphViz rendering is written to: %s" % filename
+
+
+from model import ensure, WithNodeLabel
+import StringIO
+import subprocess
+
+
+def draw_graphviz(graph, stream):
+    ensure(graph.readonly(WithNodeLabel), "without node labels", graph)
+    io = StringIO.StringIO()
+    print >>io, 'digraph "_" {'
+    print >>io, '  node [shape=box];'
+    for node in graph.nodes:
+        print >>io, '  "%s";' % node.label.text
+    for arc in graph.arcs:
+        print >>io, '  "%s" -> "%s";' % (arc.target.label.text, arc.origin.label.text)
+    print >>io, "}"
+    cmd = ["dot", "-Tpng"]
+    process = subprocess.Popen(cmd, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
+    out, err = process.communicate(io.getvalue())
+    if process.returncode != 0:
+        raise RuntimeError("graphviz returned non-zero error code: %s (%r)" % (process.returncode, err))
+    stream.write(out)
+
+