use dagre to optimize layout

4 files changed, 138 insertions, 38 deletions

diff --git a/html/js/git-deps-data.js b/html/js/git-deps-data.js
index e45217a..f4a107c 100644
--- a/html/js/git-deps-data.js
+++ b/html/js/git-deps-data.js
@@ -1,8 +1,8 @@
 var $ = require('jquery');
 
-// The list of nodes, links, and constraints to feed into WebCola.
+// The list of nodes and links to feed into WebCola.
 // These will be dynamically built as we retrieve them via XHR.
-var nodes = [], links = [], constraints = [];
+var nodes = [], links = [];
 
 // WebCola requires links to refer to nodes by index within the
 // nodes array, so as nodes are dynamically added, we need to
@@ -58,29 +58,6 @@ function add_link(parent_sha1, child_sha1) {
     links.push(link);
 }
 
-function build_constraints() {
-    constraints.length = 0;  // FIXME: only rebuild constraints which changed
-    for (var parent_sha1 in deps) {
-        constraints.push(build_constraint(parent_sha1));
-    }
-}
-
-function build_constraint(parent_sha1) {
-    constraint = {
-        axis: 'y',
-        type: 'alignment',
-        offsets: [],
-        parent: parent_sha1
-    };
-    for (var child_sha1 in deps[parent_sha1]) {
-        constraint.offsets.push({
-            node: node_index[child_sha1],
-            offset: 0
-        });
-    }
-    return constraint;
-}
-
 // Returns true iff new data was added.
 function add_data(data) {
     var new_nodes = 0, new_deps = 0;
@@ -92,7 +69,6 @@ function add_data(data) {
     });
 
     if (new_nodes > 0 || new_deps > 0) {
-        build_constraints();
         return [new_nodes, new_deps, data.root];
     }
 
@@ -103,7 +79,6 @@ module.exports = {
     // Variables
     nodes: nodes,
     links: links,
-    constraints: constraints,
     node_index: node_index,
     deps: deps,
 
diff --git a/html/js/git-deps-graph.js b/html/js/git-deps-graph.js
index 2031355..b9bc1ee 100644
--- a/html/js/git-deps-graph.js
+++ b/html/js/git-deps-graph.js
@@ -6,6 +6,7 @@ d3tip(d3);
 
 global.gdn = require('./git-deps-noty');
 global.gdd = require('./git-deps-data');
+global.gdl = require('./git-deps-layout');
 
 require('./fullscreen');
 
@@ -166,10 +167,12 @@ function init_svg() {
 }
 
 function update_cola() {
+    gdl.build_constraints();
+
     d3cola
         .nodes(gdd.nodes)
         .links(gdd.links)
-        .constraints(gdd.constraints);
+        .constraints(gdl.constraints);
 }
 
 function draw_graph(commitish) {
@@ -338,15 +341,8 @@ function tip_html(d) {
     if (options.debug) {
         var index = gdd.node_index[d.sha1];
         var debug = "node index: " + index;
-        $.each(gdd.constraints, function (i, constraint) {
-            if (constraint.parent == d.sha1) {
-                var siblings = $.map(constraint.offsets,
-                                     function (offset, i) {
-                                         return offset.node;
-                                     });
-                debug += "<br />constrained children: " + siblings.join(", ");
-            }
-        });
+        var dagre_node = gdl.g.graph.node(d.sha1);
+        debug += "<br />dagre: (" + dagre_node.x + ", " + dagre_node.y + ")";
         pre.after(debug);
     }
 
diff --git a/html/js/git-deps-layout.js b/html/js/git-deps-layout.js
new file mode 100644
index 0000000..5f3b4a0
--- /dev/null
+++ b/html/js/git-deps-layout.js
@@ -0,0 +1,128 @@
+var $ = require('jquery');
+var dagre = require('dagre');
+
+var gdd = require('./git-deps-data');
+
+// The list of constraints to feed into WebCola.
+var constraints = [];
+
+// Group nodes by row, as assigned by the y coordinates returned from
+// dagre's layout().  This will map a y coordinate onto all nodes
+// within that row.
+var row_groups = {};
+
+// Expose a container for externally accessible objects.  We can't
+// directly expose the objects themselves because the references
+// change each time they're constructed.  However we don't need this
+// trick for the constraints arrays since we can easily empty that by
+// setting length to 0.
+var externs = {};
+
+function dagre_layout() {
+    var g = new dagre.graphlib.Graph();
+    externs.graph = g;
+
+    // Set an object for the graph label
+    g.setGraph({});
+
+    // Default to assigning a new object as a label for each new edge.
+    g.setDefaultEdgeLabel(function() { return {}; });
+
+    $.each(gdd.nodes, function (i, node) {
+        g.setNode(node.sha1, {
+            label: node.name,
+            width: node.rect_width || 70,
+            height: node.rect_height || 30
+        });
+    });
+
+    $.each(gdd.deps, function (parent_sha1, children) {
+        $.each(children, function (child_sha1, bool) {
+            g.setEdge(parent_sha1, child_sha1);
+        });
+    });
+
+    dagre.layout(g);
+
+    return g;
+}
+
+function dagre_row_groups() {
+    var g = dagre_layout();
+
+    var row_groups = {};
+    externs.row_groups = row_groups;
+
+    g.nodes().forEach(function (sha1) {
+        var x = g.node(sha1).x;
+        var y = g.node(sha1).y;
+        if (! (y in row_groups)) {
+            row_groups[y] = [];
+        }
+        row_groups[y].push({
+            sha1: sha1,
+            x: x
+        });
+    });
+    return row_groups;
+}
+
+function build_constraints() {
+    var row_groups = dagre_row_groups();
+
+    constraints.length = 0;  // FIXME: only rebuild constraints which changed
+
+    // We want alignment constraints between all nodes which dagre
+    // assigned the same y value.
+    for (var y in row_groups) {
+        var row_nodes = row_groups[y];
+        // No point having an alignment group with only one node in.
+        if (row_nodes.length > 1) {
+            constraints.push(build_alignment_constraint(row_nodes));
+        }
+    }
+
+    // We also need separation constraints ensuring that the
+    // top-to-bottom ordering assigned by dagre is preserved.  Since
+    // all nodes within a single row are already constrained to the
+    // same y coordinate from above, it should be enough to only
+    // have separation between a single node in adjacent rows.
+    var row_y_coords = Object.keys(row_groups).sort();
+    for (var i = 0; i < row_y_coords.length - 1; i++) {
+        var upper_y = row_y_coords[i];
+        var lower_y = row_y_coords[i+1];
+        var upper_node = row_groups[upper_y][0];
+        var lower_node = row_groups[lower_y][0];
+        constraints.push({
+            gap: 30,
+            axis: 'y',
+            left: gdd.node_index[upper_node.sha1],
+            right: gdd.node_index[lower_node.sha1]
+        });
+    }
+}
+
+function build_alignment_constraint(row_nodes) {
+    constraint = {
+        axis: 'y',
+        type: 'alignment',
+        offsets: [],
+    };
+    for (var i in row_nodes) {
+        var node = row_nodes[i];
+        constraint.offsets.push({
+            node: gdd.node_index[node.sha1],
+            offset: 0
+        });
+    }
+    return constraint;
+}
+
+module.exports = {
+    // Variables
+    constraints: constraints,
+    g: externs,
+
+    // Functions
+    build_constraints: build_constraints
+};
diff --git a/html/package.json b/html/package.json
index 909b4ba..43cdf4d 100644
--- a/html/package.json
+++ b/html/package.json
@@ -30,7 +30,8 @@
         "webcola": "aspiers/WebCola#fix/main-entrypoints",
         "jquery": "~2.1.3",
         "noty": "aspiers/noty#fix/commonjs",
-        "browserify": "*"
+        "browserify": "*",
+        "dagre": "~0.7.1"
     },
     "devDependencies": {
         "watchify": "*"