Commits

committed 19b720c

Implemented exact solution for layering using dynamic programming.

• Participants
• Parent commits feab8d5
• Branches default

File gd.py

`             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):`
` `