Commits

Kirill Simonov committed a9416df

Added a naive implementation of a force-based grid layout.

  • Participants
  • Parent commits b9ef922

Comments (0)

Files changed (3)

demo/example-schema-grid.py

+
+from grrdrr.model import WithGraphStyle
+from grrdrr.draw import measure_uniform, draw_smooth, draw_smooth_cut
+from grrdrr.algorithm import array, place_grid
+from grrdrr.database import build_schema
+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_uniform(example)
+print "ARRAYING..."
+array(example)
+print "PLACING..."
+place_grid(example)
+print "DONE"
+
+filename = "%s.grid.png" % basename
+stream = open(filename, 'wb')
+draw_smooth_cut(example, stream)
+stream.close()
+print "Grid rendering is written to: %s" % filename
+

src/grrdrr/algorithm.py

 
 
-from model import (ensure, WithArcWeight, WithNodeRank, WithLayers, WithBeadOrder,
+from model import (ensure, WithArcWeight, WithNodeRank, WithNodeCell,
+                   WithLayers, WithBeadOrder,
                    WithGraphSize, WithNodeDimensions, WithGraphMargins,
                    WithNodePosition, WithArcVertices, WithArcPolarity)
 import itertools
+import random
 
 
 def rank(graph):
     return graph
 
 
+def array(graph):
+    return array_force(graph)
+
+
+def array_random(graph):
+    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
+    ensure(not graph.readable(WithNodeCell), "already with node cells", graph)
+
+    graph.upgrade(WithNodeCell)
+
+    size = int(1+2*len(graph.nodes)**0.5)
+
+    cells = []
+    for row in range(size):
+        for col in range(size):
+            cells.append((row, col))
+
+    RND = random.Random(0)
+    RND.shuffle(cells)
+
+    for node in graph.nodes:
+        row, col = cells.pop()
+        node.set_cell(row, col)
+
+    graph.freeze()
+    return graph
+
+
+def array_force(graph):
+    ensure(graph.readonly(WithArcWeight), "without arc weights", graph)
+    ensure(not graph.readable(WithNodeCell), "already with node cells", graph)
+
+    graph.upgrade(WithNodeCell)
+
+    RND = random.Random(0)
+
+    lengths = {}
+    for node1 in graph.nodes:
+        for node2 in node1.neighbors:
+            lengths[node1, node2] = lengths[node2, node1] = 1
+    for node in graph.nodes:
+        lengths[node, node] = 0
+    for aux in graph.nodes:
+        for origin in graph.nodes:
+            if (aux, origin) not in lengths:
+                continue
+            for target in graph.nodes:
+                if (aux, target) not in lengths:
+                    continue
+                if (origin, target) not in lengths:
+                    lengths[origin, target] = lengths[target, origin] = \
+                            lengths[aux, origin]+lengths[aux, target]
+                else:
+                    lengths[origin, target] = lengths[target, origin] = \
+                            min(lengths[origin, target], lengths[aux, origin]+lengths[aux, target])
+
+    weights = {}
+    for node1 in graph.nodes:
+        for node2 in graph.nodes:
+            length = lengths.get((node1, node2))
+            if length is not None:
+                if length <= 1:
+                    weight = 3
+                elif length == 2:
+                    weight = 1
+                elif length == 3:
+                    weight = 0
+                elif length == 4:
+                    weight = -1
+                elif length >= 5:
+                    weight = -2
+            else:
+                weight = -2
+            weights[node1, node2] = weight
+
+    size = int(1+2*len(graph.nodes)**0.5)
+
+    cell_by_node = {}
+    node_by_cell = {}
+    free_cells = []
+
+    cells = []
+    for row in range(size):
+        for col in range(size):
+            cells.append((row, col))
+    RND.shuffle(cells)
+
+    for node in graph.nodes:
+        cell = cells.pop()
+        cell_by_node[node] = cell
+        node_by_cell[cell] = node
+
+    def force(node1, node2):
+        weight = weights[node1, node2]
+        row1, col1 = cell_by_node[node1]
+        row2, col2 = cell_by_node[node2]
+        dist = abs(row1-row2)+abs(col1-col2)
+        if weight < 0:
+            dist = min(dist, 5)
+        return dist*weight
+
+    def node_force(node1):
+        total = 0
+        for node2 in graph.nodes:
+            total += force(node1, node2)
+        return total
+
+    def total_force():
+        total = 0
+        for node1 in graph.nodes:
+            for node2 in graph.nodes:
+                total += force(node1, node2)
+        return total/2
+
+    def local_optimize():
+        improved = True
+        while improved:
+            improved = False
+            for node in graph.nodes:
+                curr_score = best_score = node_force(node)
+                curr_cell = cell_by_node[node]
+                best_cells = [cell_by_node[node]]
+                for row in range(size):
+                    for col in range(size):
+                        cell = (row, col)
+                        if cell in node_by_cell:
+                            continue
+                        cell_by_node[node] = cell
+                        cell_score = node_force(node)
+                        cell_by_node[node] = curr_cell
+                        if cell_score < best_score:
+                            best_score = cell_score
+                            best_cells = [cell]
+                        elif cell_score == best_score:
+                            best_cells.append(cell)
+                if best_score < curr_score:
+                    cell = RND.choice(best_cells)
+                    del node_by_cell[curr_cell]
+                    node_by_cell[cell] = node
+                    cell_by_node[node] = cell
+                    improved = True
+
+    print "FORCE0:", total_force()
+    local_optimize()
+    print "FORCE1:", total_force()
+
+    for node in graph.nodes:
+        row, col = cell_by_node[node]
+        node.set_cell(row, col)
+
+    graph.freeze()
+    return graph
+
+
 def layer(graph):
     return layer_simplex(graph)
 
     return graph
 
 
+def place_grid(graph):
+    ensure(graph.readonly(WithNodeCell), "without node cells", graph)
+    ensure(graph.readonly(WithNodeDimensions), "without node dimensions", graph)
+    ensure(graph.readonly(WithGraphMargins), "without graph margins", graph)
+    ensure(not graph.readable(WithGraphSize), "already with graph size", graph)
+    ensure(not graph.readable(WithNodePosition), "already with node positions", graph)
+    ensure(not graph.readable(WithArcVertices), "already with arc vertices", graph)
+
+    graph.upgrade(WithGraphSize)
+    graph.upgrade(WithNodePosition)
+    graph.upgrade(WithArcVertices)
+
+    min_row = min(node.cell.row for node in graph.nodes)
+    max_row = max(node.cell.row for node in graph.nodes)
+    min_col = min(node.cell.col for node in graph.nodes)
+    max_col = max(node.cell.col for node in graph.nodes)
+    rows = range(min_row, max_row+1)
+    cols = range(min_col, max_col+1)
+
+    height_by_row = dict((row, 0) for row in rows)
+    width_by_col = dict((col, 0) for col in cols)
+    for node in graph.nodes:
+        row = node.cell.row
+        col = node.cell.col
+        height_by_row[row] = max(height_by_row[row], node.dimensions.height)
+        width_by_col[col] = max(width_by_col[col], node.dimensions.width)
+
+    cy_by_row = {}
+    cx_by_col = {}
+    y = graph.margins.vertical
+    for row in rows:
+        height = height_by_row[row]
+        cy_by_row[row] = y+height/2
+        y += height+graph.margins.vertical
+    x = graph.margins.horizontal
+    for col in cols:
+        width = width_by_col[col]
+        cx_by_col[col] = x+width/2
+        x += width+graph.margins.horizontal
+    graph.set_size(x, y)
+
+    for node in graph.nodes:
+        cy = cy_by_row[node.cell.row]
+        cx = cx_by_col[node.cell.col]
+        x = cx-node.dimensions.width/2
+        y = cy-node.dimensions.height/2
+        w = node.dimensions.width
+        h = node.dimensions.height
+        node.set_position(x, y, w, h)
+
+    for arc in graph.arcs:
+        y0 = cy_by_row[arc.origin.cell.row]
+        x0 = cx_by_col[arc.origin.cell.col]
+        y1 = cy_by_row[arc.target.cell.row]
+        x1 = cx_by_col[arc.target.cell.col]
+        arc.add_vertex(x0, y0)
+        arc.add_vertex(x1, y1)
+
+    graph.freeze(WithGraphSize)
+    graph.freeze(WithNodePosition)
+    graph.freeze(WithArcVertices)
+
+    return graph
+
+

src/grrdrr/model.py

 inject_property(WithNodeRank, NodeWithRank, Rank, True)
 
 
+class Cell(object):
+
+    def __init__(self, row, col):
+        self.row = row
+        self.col = col
+
+
+class WithNodeCell(WithGraph):
+    pass
+
+
+@WithNodeCell
+class NodeWithCell(Node):
+    pass
+
+
+inject_property(WithNodeCell, NodeWithCell, Cell, True)
+
+
 class WithLayers(WithGraph):
     pass