From fb252d07fb5cf634a2a426642e201d8d9935629f Mon Sep 17 00:00:00 2001
From: David Aguilar <davvid@gmail.com>
Date: Wed, 28 Dec 2011 00:15:35 -0800
Subject: [PATCH] dag: Improve the graph layout algorithm

Walk the nodes from parent to children so that the nodes have
a stronger tendency to stay left-aligned.

Special-case the single-parent case to favor aligning nodes
relative to their parents.

What's really nice is that merges pull nodes towards the left which
is exactly what you'd expect ("merging features into master")
when visualizing branchy histories.

The previous algorithm basically did this in the reverse
order and caused branches to diverge more along the X axis
due to the order of traversal.

Signed-off-by: David Aguilar <davvid@gmail.com>
---
 cola/dag/view.py | 51 +++++++++++++++++++++++++++++++--------------------
 1 file changed, 31 insertions(+), 20 deletions(-)

diff --git a/cola/dag/view.py b/cola/dag/view.py
index 7685813c..2e184816 100644
--- a/cola/dag/view.py
+++ b/cola/dag/view.py
@@ -1222,36 +1222,47 @@ class GraphView(QtGui.QGraphicsView):
             item.setPos(x, y)
 
     def position_nodes(self, nodes):
+        positions = {}
+
         x_max = self.x_max
         y_min = self.y_min
+        x_off = self.x_off
+        y_off = self.y_off
+        x_offsets = self.x_offsets
 
-        positions = {}
-        for node in reversed(nodes):
+        for node in nodes:
             generation = node.generation
             sha1 = node.sha1
 
-            xoff = self.x_off
-            cur_xoff = self.x_offsets[generation]
+            if len(node.children) > 1:
+                # This is a fan-out so sweep over child generations and
+                # shift them to the right to avoid overlapping edges
+                child_gens = [c.generation for c in node.children]
+                maxgen = reduce(max, child_gens)
+                mingen = reduce(min, child_gens)
+                if maxgen > mingen:
+                    for g in xrange(generation+1, maxgen):
+                        x_offsets[g] += x_off
+
+            if len(node.parents) == 1:
+                # Align nodes relative to their parents
+                parent_gen = node.parents[0].generation
+                parent_off = x_offsets[parent_gen]
+                x_offsets[generation] = max(parent_off-x_off,
+                                            x_offsets[generation])
+
+            cur_xoff = x_offsets[generation]
             next_xoff = cur_xoff
-            next_xoff += xoff
-            self.x_offsets[generation] = next_xoff
-
-            if len(node.parents) > 1:
-                # Sweep across generations from child to farthest
-                # parents and reserve padding for intermediate
-                # nodes.  This minimizes overlapping edges.
-                mingen = reduce(min, [p.generation for p in node.parents])
-                for gen in xrange(mingen+1, node.generation):
-                    new_xoff = self.x_offsets[gen] + xoff
-                    self.x_offsets[gen] = max(new_xoff, next_xoff)
+            next_xoff += x_off
+            x_offsets[generation] = next_xoff
 
-            xpos = cur_xoff
-            ypos = -node.generation * self.y_off
+            x_pos = cur_xoff
+            y_pos = -generation * y_off
+            positions[sha1] = (x_pos, y_pos)
 
-            x_max = max(x_max, xpos)
-            y_min = min(y_min, ypos)
+            x_max = max(x_max, x_pos)
+            y_min = min(y_min, y_pos)
 
-            positions[sha1] = (xpos, ypos)
 
         self.x_max = x_max
         self.y_min = y_min
-- 
2.11.4.GIT