Commits

Kirill Simonov committed 2715358

Optimized dynamic programming for layer ordering; implemented uniform placing.

  • Participants
  • Parent commits 19b720c

Comments (0)

Files changed (2)

 
         extents = dummy_context.text_extents('M')
         x_bearing, y_bearing, width, height, x_advance, y_advance = extents
-        m_width = int(width)
-        m_height = int(height)
+        m_width = int(width)*2
+        m_height = int(height)*2
 
         if self.margins is None:
             self.set_margins(m_height, m_width, m_height, m_width)
             node.set_rank(value)
 
     def layering(self):
-        max_nodes_per_layer = int(len(self.nodes)**0.5)*2
+        max_nodes_per_layer = int(len(self.nodes)**0.5)
         nodes = sorted(self.nodes, key=(lambda node: -node.rank.value))
         while nodes:
             candidates = []
 
     def ordering(self):
 
-        def get_degree():
-            degree = {}
-            for layer_idx in range(len(self.layers)-1):
-                curr_layer = self.layers[layer_idx]
-                next_layer = self.layers[layer_idx+1]
-                for curr_item in curr_layer.items:
-                    for next_item in next_layer.items:
-                        value = 0
-                        if curr_item.is_arc:
-                            if next_item.is_arc:
-                                if curr_item.arc is next_item.arc:
-                                    value += 1
-                            else:
-                                if curr_item.arc.origin is next_item.node or curr_item.arc.target is next_item.node:
-                                    value += 1
-                        else:
-                            if next_item.is_arc:
-                                if next_item.arc.origin is curr_item.node or next_item.arc.target is curr_item.node:
-                                    value += 1
-                            else:
-                                for arc in curr_item.node.incoming:
-                                    if arc.origin is next_item.node:
-                                        value += 1
-                                for arc in curr_item.node.outgoing:
-                                    if arc.target is next_item.node:
-                                        value += 1
-                        degree[curr_item, next_item] = value
-            return degree
-
         def get_arc_orders(layer):
             arc_orders = {}
             for item in layer.items:
             if layer_idx < len(self.layers)-1:
                 next_sequence = dynamic(layer_idx+1)
                 print "SOLVING LAYER %s; PERMUTATIONS: %s" % (layer_idx, len(permutations)*len(next_sequence))
+
+                arc_items = {}
+                node_items = {}
+                for item in layer.items:
+                    if item.is_arc:
+                        arc_items[item.arc] = item
+                    else:
+                        node_items[item.node] = item
+                next_item_neighbors = {}
+                for item in self.layers[layer_idx+1].items:
+                    neighbors = []
+                    if item.is_arc:
+                        item_arcs = [item.arc]
+                    else:
+                        item_arcs = item.node.incoming+item.node.outgoing
+                    for arc in item_arcs:
+                        if arc in arc_items:
+                            neighbors.append(arc_items[arc])
+                        if arc.origin in node_items:
+                            neighbors.append(node_items[arc.origin])
+                        if arc.target in node_items:
+                            neighbors.append(node_items[arc.target])
+                    next_item_neighbors[item] = neighbors
+
             for permutation in permutations:
                 item_orders = {}
                 for item_idx, item_order in enumerate(permutation):
                 if layer_idx < len(self.layers)-1:
                     best_item_orders = None
                     best_crossings = None
-                    ordered_items = sorted(layer.items, key=(lambda item: item_orders[item]))
+
+                    crossing_numbers = {}
+                    for left_item in self.layers[layer_idx+1].items:
+                        for right_item in self.layers[layer_idx+1].items:
+                            count = 0
+                            if left_item is not right_item:
+                                for left_neighbor in next_item_neighbors[left_item]:
+                                    for right_neighbor in next_item_neighbors[right_item]:
+                                        if item_orders[left_neighbor] > item_orders[right_neighbor]:
+                                            count += 1
+                            crossing_numbers[left_item, right_item] = count
+
                     for next_crossings, next_item_orders in next_sequence:
                         crossings = next_crossings
                         next_ordered_items = sorted(self.layers[layer_idx+1].items,
                                                     key=(lambda item: next_item_orders[item]))
-                        for top_left_idx in range(len(ordered_items)-1):
-                            top_left_item = ordered_items[top_left_idx]
-                            for bottom_right_idx in range(1, len(next_ordered_items)):
-                                bottom_right_item = next_ordered_items[bottom_right_idx]
-                                if not degree[top_left_item, bottom_right_item]:
-                                    continue
-                                for top_right_idx in range(top_left_idx+1, len(ordered_items)):
-                                    top_right_item = ordered_items[top_right_idx]
-                                    for bottom_left_idx in range(bottom_right_idx):
-                                        bottom_left_item = next_ordered_items[bottom_left_idx]
-                                        crossings += degree[top_left_item, bottom_right_item]   \
-                                                    *degree[top_right_item, bottom_left_item]
+                        for left_idx in range(len(next_ordered_items)-1):
+                            left_item = next_ordered_items[left_idx]
+                            for right_idx in range(left_idx+1, len(next_ordered_items)):
+                                right_item = next_ordered_items[right_idx]
+                                crossings += crossing_numbers[left_item, right_item]
                         if best_crossings is None or crossings < best_crossings:
                             best_item_orders = next_item_orders
                             best_crossings = crossings
             if layer_idx < len(self.layers)-1:
                 next_sequence = greedy_dynamic(layer_idx+1)
                 print "SOLVING LAYER %s; PERMUTATIONS: %s" % (layer_idx, len(permutations)*len(next_sequence))
+
+                arc_items = {}
+                node_items = {}
+                for item in layer.items:
+                    if item.is_arc:
+                        arc_items[item.arc] = item
+                    else:
+                        node_items[item.node] = item
+                next_item_neighbors = {}
+                for item in self.layers[layer_idx+1].items:
+                    neighbors = []
+                    if item.is_arc:
+                        item_arcs = [item.arc]
+                    else:
+                        item_arcs = item.node.incoming+item.node.outgoing
+                    for arc in item_arcs:
+                        if arc in arc_items:
+                            neighbors.append(arc_items[arc])
+                        if arc.origin in node_items:
+                            neighbors.append(node_items[arc.origin])
+                        if arc.target in node_items:
+                            neighbors.append(node_items[arc.target])
+                    next_item_neighbors[item] = neighbors
+
             for permutation in permutations:
                 item_orders = {}
                 for item_idx, item_order in enumerate(permutation):
                 if layer_idx < len(self.layers)-1:
                     best_item_orders = None
                     best_crossings = None
-                    ordered_items = sorted(layer.items, key=(lambda item: item_orders[item]))
+
+                    crossing_numbers = {}
+                    for left_item in self.layers[layer_idx+1].items:
+                        for right_item in self.layers[layer_idx+1].items:
+                            count = 0
+                            if left_item is not right_item:
+                                for left_neighbor in next_item_neighbors[left_item]:
+                                    for right_neighbor in next_item_neighbors[right_item]:
+                                        if item_orders[left_neighbor] > item_orders[right_neighbor]:
+                                            count += 1
+                            crossing_numbers[left_item, right_item] = count
+
                     for next_crossings, next_item_orders in next_sequence:
                         crossings = next_crossings
                         next_ordered_items = sorted(self.layers[layer_idx+1].items,
                                                     key=(lambda item: next_item_orders[item]))
-                        for top_left_idx in range(len(ordered_items)-1):
-                            top_left_item = ordered_items[top_left_idx]
-                            for bottom_right_idx in range(1, len(next_ordered_items)):
-                                bottom_right_item = next_ordered_items[bottom_right_idx]
-                                if not degree[top_left_item, bottom_right_item]:
-                                    continue
-                                for top_right_idx in range(top_left_idx+1, len(ordered_items)):
-                                    top_right_item = ordered_items[top_right_idx]
-                                    for bottom_left_idx in range(bottom_right_idx):
-                                        bottom_left_item = next_ordered_items[bottom_left_idx]
-                                        crossings += degree[top_left_item, bottom_right_item]   \
-                                                    *degree[top_right_item, bottom_left_item]
+                        for left_idx in range(len(next_ordered_items)-1):
+                            left_item = next_ordered_items[left_idx]
+                            for right_idx in range(left_idx+1, len(next_ordered_items)):
+                                right_item = next_ordered_items[right_idx]
+                                crossings += crossing_numbers[left_item, right_item]
                         if best_crossings is None or crossings < best_crossings:
                             best_item_orders = next_item_orders
                             best_crossings = crossings
 
             return crossings
 
-        degree = get_degree()
-
         item_orders = {}
         for layer in self.layers:
             for idx, item in enumerate(layer.items):
         new_item_orders = greedy_solution()
         item_orders.update(new_item_orders)
 
+        #new_item_orders = best_solution()
+        #item_orders.update(new_item_orders)
+
         for layer in self.layers:
             for item in layer.items:
                 item.set_order(item_orders[item])
 
     def placing(self):
 
-        layer_top = self.margins.top
-        max_layer_bottom = layer_top
-        layer_left = self.margins.left
-        max_layer_right = layer_left
-        is_leading_line = True
+        bounding_width = 0
+        bounding_height = 0
+        is_top_line = True
+        layer_dimensions = {}
         for layer in self.layers:
+            if is_top_line:
+                is_top_line = False
+            else:
+                bounding_height += max(self.margins.top, self.margins.bottom)
+            width = 0
+            height = 0
+            is_left_column = True
+            for item in layer.items:
+                if is_left_column:
+                    is_left_column = False
+                else:
+                    width += max(self.margins.left, self.margins.right)
+                if item.is_node:
+                    width += item.node.dimensions.width
+                    height = max(height, item.node.dimensions.height)
+            layer_dimensions[layer] = (width, height)
+            bounding_width = max(width, bounding_width)
+            bounding_height += height
+
+        is_top_line = True
+        top = self.margins.top
+        for layer_idx, layer in enumerate(self.layers):
             items = sorted(layer.items, key=(lambda item: item.order.value))
-            if is_leading_line:
-                is_leading_line = False
+            layer_width, layer_height = layer_dimensions[layer]
+            extra = (bounding_width - layer_width)/(len(items) + 1)
+            left = self.margins.left + extra
+            if is_top_line:
+                is_top_line = False
             else:
-                layer_top += max(self.margins.top, self.margins.bottom)
-            layer_bottom = layer_top
-            layer_right = layer_left
-            is_leading_column = True
+                top += max(self.margins.top, self.margins.bottom)
+            is_left_column = True
             for item in items:
-                if is_leading_column:
-                    is_leading_column = False
+                if is_left_column:
+                    is_left_column = False
                 else:
-                    layer_right += max(self.margins.left, self.margins.right)
-                if item.is_node:
-                    layer_bottom = max(layer_bottom, layer_top+item.node.dimensions.height)
-                    layer_right += item.node.dimensions.width
-            
-            item_left = layer_left
-            is_leading_column = True
-            for item in items:
-                if is_leading_column:
-                    is_leading_column = False
-                else:
-                    item_left += max(self.margins.left, self.margins.right)
+                    left += max(self.margins.left, self.margins.right) + extra
+
                 if item.is_node:
                     node = item.node
-                    x1 = item_left
-                    y1 = (layer_top + layer_bottom - node.dimensions.height)/2
+                    x1 = left
+                    y1 = top + (layer_height - node.dimensions.height)/2
                     x2 = x1 + node.dimensions.width
                     y2 = y1 + node.dimensions.height
                     node.set_position(x1, y1, x2, y2)
-                    cx = (x1 + x2)/2
-                    cy = (y1 + y2)/2
-                    for arc in node.incoming + node.outgoing:
-                        arc.add_vertex(cx, cy)
-                    item_left += node.dimensions.width
+                    for other_layer_idx, arc_y in [(layer_idx-1, y1+1), (layer_idx+1, y2-1)]:
+                        if not (0 <= other_layer_idx < len(self.layers)):
+                            continue
+                        other_layer = self.layers[other_layer_idx]
+                        arc_orders = {}
+                        for other_item in other_layer.items:
+                            if other_item.is_arc:
+                                arc_orders[other_item.arc] = other_item.order.value
+                            else:
+                                for arc in other_item.node.incoming+other_item.node.outgoing:
+                                    arc_orders[arc] = other_item.order.value
+                        arcs = [arc for arc in item.node.incoming+item.node.outgoing if arc in arc_orders]
+                        arcs.sort(key=(lambda arc: arc_orders[arc]))
+                        if arcs:
+                            distance = node.dimensions.width / (len(arcs)+1)
+                            arc_x = x1
+                            for arc in arcs:
+                                arc_x += distance
+                                arc.add_vertex(arc_x, arc_y)
+                    left += node.dimensions.width
+                    cx = (x1+x2)/2
+                    cy = (y1+y2)/2
+                    for arc in node.incoming:
+                        if arc.origin is node:
+                            arc.add_vertex(cx, cy)
                 else:
                     arc = item.arc
-                    x = item_left
-                    y = layer_top
+                    x = left
+                    y = top
                     arc.add_vertex(x, y)
-                    x = item_left
-                    y = layer_bottom
+                    x = left
+                    y = top + layer_height
                     arc.add_vertex(x, y)
 
-            layer_top = layer_bottom
+            top += layer_height
 
-            max_layer_bottom = layer_bottom
-            max_layer_right = max(max_layer_right, layer_right)
-
-        graph_width = max_layer_right + self.margins.right
-        graph_height = max_layer_bottom + self.margins.bottom
-
+        graph_width = self.margins.left + bounding_width + self.margins.right
+        graph_height = self.margins.top + bounding_height + self.margins.bottom
         self.set_size(graph_width, graph_height)
 
     def layout(self):
         context = cairo.Context(surface)
         context.set_font_size(self.style.font_size)
 
+        context.set_source_rgb(*self.style.background_color)
+        context.rectangle(0, 0, self.size.width, self.size.height)
+        context.fill()
+
         context.set_source_rgb(*self.style.arc_color)
         for arc in self.arcs:
+            context.set_line_width(2.0*abs(arc.weight))
             context.new_path()
-            vertex = arc.vertices[0]
-            context.move_to(vertex.x, vertex.y)
-            for vertex in arc.vertices[1:]:
-                context.line_to(vertex.x, vertex.y)
+            if len(arc.vertices) > 2:
+                vertex = arc.vertices[0]
+                x, y = vertex.x, vertex.y
+                context.move_to(x, y)
+                for idx in range(1, len(arc.vertices)-1):
+                    if idx == 1:
+                        vertex = arc.vertices[0]
+                        s_x, s_y = vertex.x, vertex.y
+                    else:
+                        vertex1 = arc.vertices[idx-1]
+                        vertex2 = arc.vertices[idx]
+                        s_x, s_y = (vertex1.x+vertex2.x)/2, (vertex1.y+vertex2.y)/2
+                    if idx == len(arc.vertices)-2:
+                        vertex = arc.vertices[-1]
+                        e_x, e_y = vertex.x, vertex.y
+                    else:
+                        vertex1 = arc.vertices[idx]
+                        vertex2 = arc.vertices[idx+1]
+                        e_x, e_y = (vertex1.x+vertex2.x)/2, (vertex1.y+vertex2.y)/2
+                    vertex = arc.vertices[idx]
+                    q_x, q_y = vertex.x, vertex.y
+                    x1, y1 = 1.0/3.0*s_x+2.0/3.0*q_x, 1.0/3.0*s_y+2.0/3.0*q_y
+                    x2, y2 = 1.0/3.0*e_x+2.0/3.0*q_x, 1.0/3.0*e_y+2.0/3.0*q_y
+                    x3, y3 = e_x, e_y
+                    context.curve_to(x1, y1, x2, y2, x3, y3)
+            else:
+                vertex = arc.vertices[0]
+                context.move_to(vertex.x, vertex.y)
+                for vertex in arc.vertices[1:]:
+                    context.line_to(vertex.x, vertex.y)
             context.stroke()
 
         context.set_source_rgb(*self.style.node_color)
             context.new_path()
             x = position.x1
             y = position.y1
-            w = position.x2 - position.x1
-            h = position.y2 - position.y1
+            w = position.x2 - position.x1 + 1
+            h = position.y2 - position.y1 + 1
             context.rectangle(x, y, w, h)
             context.fill()
 

File gd_htsql_test.py

         node_color=(0.0, 0.0, 0.5),
         arc_color=(0.5, 0.0, 0.0),
         text_color=(1.0, 1.0, 1.0),
-        font_size=14.0)
+        font_size=18.0)
 
 stream = open('gd_htsql_test.png', 'wb')
 graph.draw(stream)