Commits

Kirill Simonov  committed feab8d5

Implemented feedback set removal, rank assignment and simple layer assignment.

  • Participants
  • Parent commits d9d3222

Comments (0)

Files changed (1)

             node.set_dimensions(node_width, node_height)
 
     def sorting(self):
-        existing_ranks = set(node.rank.value for node in self.nodes if node.rank is not None)
-        value = 0
-        for node in self.nodes:
-            if node.rank is not None:
-                continue
-            while value in existing_ranks:
-                value += 1
+
+        def get_cycle(forbidden):
+
+            path = []
+            active = {}
+            used = set()
+
+            def dfs(node):
+                if node in used:
+                    return None
+                if node in active:
+                    cycle = path[active[node]:]
+                    return cycle
+                active[node] = len(path)
+                for arc in node.outgoing:
+                    if arc in forbidden:
+                        continue
+                    path.append(arc)
+                    cycle = dfs(arc.target)
+                    if cycle is not None:
+                        return cycle
+                    path.pop()
+                used.add(node)
+                return None
+
+            for node in self.nodes:
+                cycle = dfs(node)
+                if cycle is not None:
+                    return cycle
+            return None
+
+        def get_node_weights(forbidden):
+            weights = {}
+            active = set()
+
+            def dfs(node):
+                assert node not in weights and node not in active
+                active.add(node)
+                total = 0.0
+                for arc in node.outgoing:
+                    if arc in forbidden:
+                        continue
+                    if arc.target not in weights:
+                        weights[arc.target] = dfs(arc.target)
+                    total += arc.weight + weights[arc.target]
+                return total
+
+            for node in self.nodes:
+                if node not in weights:
+                    weights[node] = dfs(node)
+            return weights
+
+        feedback = []
+        arc_weights = dict((arc, arc.weight) for arc in self.arcs)
+
+        cycle = get_cycle(feedback)
+        while cycle is not None:
+            min_weight = min(arc_weights[arc] for arc in cycle)
+            for arc in cycle:
+                if arc_weights[arc] == min_weight:
+                    feedback.append(arc)
+                arc_weights[arc] -= min_weight
+            cycle = get_cycle(feedback)
+
+        for arc in feedback[:]:
+            feedback.remove(arc)
+            cycle = get_cycle(feedback)
+            if cycle is not None:
+                feedback.append(arc)
+
+        node_weights = get_node_weights(feedback)
+        ordered_nodes = sorted(self.nodes, key=(lambda node: (node_weights[node], node.index)))
+        for value, node in enumerate(ordered_nodes):
             node.set_rank(value)
-            value += 1
 
     def layering(self):
-        nodes_per_layer = int(len(self.nodes)**0.5)
-        layer = None
-        for node in sorted(self.nodes, key=(lambda node: node.rank.value)):
-            if node.layer_item is not None:
-                continue
-            if layer is None or len(layer.items) > nodes_per_layer:
-                layer = self.add_layer()
-            layer.add_node_item(node)
+        max_nodes_per_layer = int(len(self.nodes)**0.5)
+        nodes = sorted(self.nodes, key=(lambda node: node.rank.value))
+        while nodes:
+            candidates = []
+            for node in nodes:
+                is_candidate = True
+                for arc in node.incoming:
+                    if arc.origin.rank < node.rank and arc.origin in nodes:
+                        is_candidate = False
+                for arc in node.outgoing:
+                    if arc.target.rank < node.rank and arc.target in nodes:
+                        is_candidate = False
+                if is_candidate:
+                    candidates.append(node)
+                if len(candidates) >= max_nodes_per_layer:
+                    break
+            assert candidates
+            layer = self.add_layer()
+            for node in candidates:
+                layer.add_node_item(node)
+                nodes.remove(node)
+
         for arc in self.arcs:
             origin_layer_index = arc.origin.layer_item.layer.index
             target_layer_index = arc.target.layer_item.layer.index
 
     def ordering(self):
         for layer in self.layers:
-            node_items = [node.layer_item for node in self.nodes
-                        if node.layer_item.layer is layer]
-            arc_items = [layer_item for arc in self.arcs for layer_item in arc.layer_items
-                        if layer_item.layer is layer]
+            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