1. Kirill Simonov
  2. grrdrr

Commits

Kirill Simonov  committed 19b720c

Implemented exact solution for layering using dynamic programming.

  • Participants
  • Parent commits feab8d5
  • Branches default

Comments (0)

Files changed (1)

File gd.py

View file
             node.set_rank(value)
 
     def layering(self):
-        max_nodes_per_layer = int(len(self.nodes)**0.5)
-        nodes = sorted(self.nodes, key=(lambda node: node.rank.value))
+        max_nodes_per_layer = int(len(self.nodes)**0.5)*2
+        nodes = sorted(self.nodes, key=(lambda node: -node.rank.value))
         while nodes:
             candidates = []
             for node in nodes:
                 layer.add_arc_item(arc)
 
     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 item.is_arc:
+                    arc_orders[item.arc] = item_orders[item]
+                else:
+                    for arc in item.node.incoming+item.node.outgoing:
+                        arc_orders[arc] = item_orders[item]
+            return arc_orders
+
+        def sweep(base_layer, active_layer):
+            arc_orders = get_arc_orders(base_layer)
+
+            barycenters = {}
+            for item in active_layer.items:
+                if item.is_arc:
+                    center = 1.0*item_orders[item]
+                    if item.arc in arc_orders:
+                        center = 1.0*arc_orders[item.arc]
+                else:
+                    weight = 0.0
+                    order = 0.0
+                    for arc in item.node.incoming+item.node.outgoing:
+                        if arc in arc_orders:
+                            weight += arc.weight
+                            order += arc_orders[arc]*arc.weight
+                    if weight:
+                        center = order/weight
+                    else:
+                        center = 1.0*item_orders[item]
+                barycenters[item] = center
+
+            items = sorted(active_layer.items, key=(lambda item: barycenters[item]))
+            new_item_orders = {}
+            for idx, item in enumerate(items):
+                new_item_orders[item] = idx
+
+            return new_item_orders
+
+        def exchange_neighbors():
+            for idx in range(len(self.layers)):
+                prev_arc_orders = {}
+                if idx > 0:
+                    prev_arc_orders = get_arc_orders(self.layers[idx-1])
+                next_arc_orders = {}
+                if idx < len(self.layers)-1:
+                    next_arc_orders = get_arc_orders(self.layers[idx+1])
+
+                items = sorted(self.layers[idx].items, key=(lambda item: item_orders[item]))
+                for item_idx in range(len(items)-1):
+                    left_arcs = []
+                    right_arcs = []
+                    left_item = items[item_idx]
+                    right_item = items[item_idx+1]
+                    if left_item.is_arc:
+                        left_arcs.append(left_item.arc)
+                    else:
+                        left_arcs.extend(left_item.node.incoming)
+                        left_arcs.extend(left_item.node.outgoing)
+                    if right_item.is_arc:
+                        right_arcs.append(right_item.arc)
+                    else:
+                        right_arcs.extend(right_item.node.incoming)
+                        right_arcs.extend(right_item.node.outgoing)
+                    crossings = 0
+                    non_crossings = 0
+                    for left_arc in left_arcs:
+                        for right_arc in right_arcs:
+                            for arc_orders in [prev_arc_orders, next_arc_orders]:
+                                if left_arc not in arc_orders or right_arc not in arc_orders:
+                                    continue
+                                if arc_orders[left_arc] < arc_orders[right_arc]:
+                                    non_crossings += 1
+                                if arc_orders[left_arc] > arc_orders[right_arc]:
+                                    crossings += 1
+                    if crossings > non_crossings:
+                        new_item_orders = {}
+                        new_item_orders[left_item] = item_idx+1
+                        new_item_orders[right_item] = item_idx
+                        return new_item_orders
+
+            return {}
+
+        def exchange_pairs():
+            crossings = get_number_of_crossings()
+            for idx in range(len(self.layers)):
+                items = self.layers[idx].items
+                for left_idx in range(len(items)-1):
+                    left_item = items[left_idx]
+                    left_order = item_orders[left_item]
+                    for right_idx in range(left_idx+1, len(items)):
+                        right_item = items[right_idx]
+                        right_order = item_orders[right_item]
+                        item_orders[left_item] = right_order
+                        item_orders[right_item] = left_order
+                        new_crossings = get_number_of_crossings()
+                        item_orders[left_item] = left_order
+                        item_orders[right_item] = right_order
+                        if new_crossings < crossings:
+                            new_item_orders = {}
+                            new_item_orders[left_item] = right_order
+                            new_item_orders[right_item] = left_order
+                            return new_item_orders
+            return {}
+
+        def best_solution():
+            min_crossings = None
+            min_item_orders = None
+            sequence = dynamic(0)
+            for crossings, item_orders in sequence:
+                if min_crossings is None or crossings < min_crossings:
+                    min_crossings = crossings
+                    min_item_orders = item_orders
+            return min_item_orders
+
+        def greedy_solution():
+            min_crossings = None
+            min_item_orders = None
+            sequence = greedy_dynamic(0)
+            for crossings, item_orders in sequence:
+                if min_crossings is None or crossings < min_crossings:
+                    min_crossings = crossings
+                    min_item_orders = item_orders
+            return min_item_orders
+
+        def get_permutations(values):
+            permutations = []
+            if not values:
+                permutations.append([])
+            else:
+                for idx in range(len(values)):
+                    value = values[idx]
+                    reduction = values[:idx]+values[idx+1:]
+                    for permutation in get_permutations(reduction):
+                        permutation.append(value)
+                        permutations.append(permutation)
+            return permutations
+
+        def dynamic(layer_idx):
+            layer = self.layers[layer_idx]
+            permutations = get_permutations(range(len(layer.items)))
+            sequence = []
+            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))
+            for permutation in permutations:
+                item_orders = {}
+                for item_idx, item_order in enumerate(permutation):
+                    item = layer.items[item_idx]
+                    item_orders[item] = item_order
+                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]))
+                    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]
+                        if best_crossings is None or crossings < best_crossings:
+                            best_item_orders = next_item_orders
+                            best_crossings = crossings
+                    item_orders.update(best_item_orders)
+                    crossings = best_crossings
+                else:
+                    crossings = 0
+                sequence.append((crossings, item_orders))
+            return sequence
+
+        def greedy_dynamic(layer_idx):
+            layer = self.layers[layer_idx]
+            permutations = get_permutations(range(len(layer.items)))
+            sequence = []
+            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))
+            for permutation in permutations:
+                item_orders = {}
+                for item_idx, item_order in enumerate(permutation):
+                    item = layer.items[item_idx]
+                    item_orders[item] = item_order
+                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]))
+                    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]
+                        if best_crossings is None or crossings < best_crossings:
+                            best_item_orders = next_item_orders
+                            best_crossings = crossings
+                    item_orders.update(best_item_orders)
+                    crossings = best_crossings
+                else:
+                    crossings = 0
+                sequence.append((crossings, item_orders))
+            greedy_value = min(crossings for crossings, item_orders in sequence)
+            sequence = [(crossings, item_orders)
+                            for crossings, item_orders in sequence
+                            if crossings == greedy_value]
+            return sequence
+
+        def get_number_of_crossings():
+
+            crossings = 0
+
+            for idx in range(len(self.layers)-1):
+                base_layer = self.layers[idx]
+                active_layer = self.layers[idx+1]
+
+                arc_orders = {}
+                for item in base_layer.items:
+                    if item.is_arc:
+                        arc_orders[item.arc] = item_orders[item]
+                    else:
+                        for arc in item.node.incoming+item.node.outgoing:
+                            arc_orders[arc] = item_orders[item]
+
+                items = sorted(active_layer.items, key=(lambda item: item_orders[item]))
+                for left_idx in range(len(items)-1):
+                    left_arcs = []
+                    left_item = items[left_idx]
+                    if left_item.is_arc:
+                        left_arcs.append(left_item.arc)
+                    else:
+                        left_arcs.extend(left_item.node.incoming)
+                        left_arcs.extend(left_item.node.outgoing)
+                    for right_idx in range(left_idx+1, len(items)):
+                        right_arcs = []
+                        right_item = items[right_idx]
+                        if right_item.is_arc:
+                            right_arcs.append(right_item.arc)
+                        else:
+                            right_arcs.extend(right_item.node.incoming)
+                            right_arcs.extend(right_item.node.outgoing)
+                        for left_arc in left_arcs:
+                            if left_arc not in arc_orders:
+                                continue
+                            left_order = arc_orders[left_arc]
+                            for right_arc in right_arcs:
+                                if right_arc not in arc_orders:
+                                    continue
+                                right_order = arc_orders[right_arc]
+                                if left_order > right_order:
+                                    print "CROSS:", left_arc.label.text, right_arc.label.text
+                                    crossings += 1
+
+            return crossings
+
+        degree = get_degree()
+
+        item_orders = {}
         for layer in self.layers:
-            node_items = [item for item in layer.items if item.is_node]
-            arc_items = [item for item in layer.items if item.is_arc]
-            node_items_index = 0
-            arc_items_index = 0
-            value = 0
+            for idx, item in enumerate(layer.items):
+                item_orders[item] = idx
 
-            while node_items_index < len(node_items) and arc_items_index < len(arc_items):
-                if node_items_index <= arc_items_index:
-                    item = node_items[node_items_index]
-                    node_items_index += 1
-                else:
-                    item = arc_items[arc_items_index]
-                    arc_items_index += 1
-                item.set_order(value)
-                value += 1
+        #for idx in range(len(self.layers)-1):
+        #    new_item_orders = sweep(self.layers[idx], self.layers[idx+1])
+        #    item_orders.update(new_item_orders)
 
-            while node_items_index < len(node_items):
-                item = node_items[node_items_index]
-                node_items_index += 1
-                item.set_order(value)
-                value += 1
+        #for idx in range(len(self.layers)-1, 1, -1):
+        #    new_item_orders = sweep(self.layers[idx], self.layers[idx-1])
+        #    item_orders.update(new_item_orders)
 
-            while arc_items_index < len(arc_items):
-                item = arc_items[arc_items_index]
-                arc_items_index +=  1
-                item.set_order(value)
-                value += 1
+        #for idx in range(len(self.layers)-1):
+        #    new_item_orders = sweep(self.layers[idx], self.layers[idx+1])
+        #    item_orders.update(new_item_orders)
+
+        #while True:
+        #    new_item_orders = exchange_neighbors()
+        #    item_orders.update(new_item_orders)
+        #    if not new_item_orders:
+        #        break
+
+        #while True:
+        #    new_item_orders = exchange_pairs()
+        #    item_orders.update(new_item_orders)
+        #    if not new_item_orders:
+        #        break
+
+        new_item_orders = greedy_solution()
+        item_orders.update(new_item_orders)
+
+        for layer in self.layers:
+            for item in layer.items:
+                item.set_order(item_orders[item])
+
+        crossings = get_number_of_crossings()
+        print "NUMBER OF CROSSINGS:", crossings
 
     def placing(self):