diff options
Diffstat (limited to 'html')
| -rw-r--r-- | html/js/git-deps-layout.coffee | 151 |
1 files changed, 129 insertions, 22 deletions
diff --git a/html/js/git-deps-layout.coffee b/html/js/git-deps-layout.coffee index b3ea092..f3f66af 100644 --- a/html/js/git-deps-layout.coffee +++ b/html/js/git-deps-layout.coffee @@ -1,3 +1,10 @@ +DEBUG = true + +MIN_ROW_GAP = 80 +MIN_NODE_X_GAP = 50 +MAX_NODE_X_GAP = 200 +MAX_NODE_Y_GAP = 100 + dagre = require "dagre" gdd = require "./git-deps-data.coffee" @@ -10,6 +17,10 @@ constraints = [] # within that row. row_groups = {} +debug = (msg) -> + if DEBUG + console.log msg + dagre_layout = -> g = new dagre.graphlib.Graph() exports.graph = g @@ -52,21 +63,90 @@ dagre_row_groups = -> build_constraints = -> row_groups = dagre_row_groups() + debug "build_constraints" + for y, row_nodes of row_groups + debug y + debug row_nodes constraints.length = 0 # FIXME: only rebuild constraints which changed # We want alignment constraints between all nodes which dagre # assigned the same y value. + row_alignment_constraints(row_groups) + + # We need separation constraints ensuring that the left-to-right + # ordering within each row assigned by dagre is preserved. for y, row_nodes of row_groups # No point having an alignment group with only one node in. - if row_nodes.length > 1 - constraints.push build_alignment_constraint(row_nodes) + continue if row_nodes.length <= 1 + + # Multiple constraints per row. + row_node_ordering_constraints(row_nodes) - # We also need separation constraints ensuring that the + # Finally we 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. + row_ordering_constraints(row_groups) + +debug_constraints = () -> + for c in constraints + debug c + +row_alignment_constraints = (row_groups) -> + row_alignment_constraint(row_nodes) \ + for y, row_nodes of row_groups when row_nodes.length > 1 + +row_alignment_constraint = (row_nodes) -> + debug 'row_alignment_constraint' + # A standard alignment constraint (one per row) is too strict + # because it doesn't give cola enough "wiggle room": + # + # constraint = + # axis: "y" + # type: "alignment" + # offsets: [] + # + # for node in row_nodes + # constraint.offsets.push + # node: gdd.node_index[node.sha1], + # offset: 0 + # + # constraints.push constraint + # + # So instead we use vertical min/max separation constraints: + i = 0 + while i < row_nodes.length - 1 + left = row_nodes[i] + right = row_nodes[i+1] + mm = max_unordered_separation_constraints \ + 'y', MAX_NODE_Y_GAP, + gdd.node_index[left.sha1], + gdd.node_index[right.sha1] + exports.constraints = constraints = constraints.concat mm + i++ + debug_constraints() + return + +row_node_ordering_constraints = (row_nodes) -> + debug 'row_node_ordering_constraints' + i = 0 + while i < row_nodes.length - 1 + left = row_nodes[i] + right = row_nodes[i+1] + mm = min_max_ordered_separation_constraints \ + 'x', MIN_NODE_X_GAP, MAX_NODE_X_GAP, + gdd.node_index[left.sha1], + gdd.node_index[right.sha1] + exports.constraints = constraints = constraints.concat mm + + i++ + debug_constraints() + return + +row_ordering_constraints = (row_groups) -> + debug 'row_ordering_constraints' row_y_coords = Object.keys(row_groups).sort() i = 0 @@ -75,27 +155,54 @@ build_constraints = -> lower_y = row_y_coords[i + 1] upper_node = row_groups[upper_y][0] 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] + constraints.push \ + min_separation_constraint \ + MIN_ROW_GAP, 'y', + gdd.node_index[upper_node.sha1], + gdd.node_index[lower_node.sha1] i++ - -build_alignment_constraint = (row_nodes) -> - constraint = - axis: "y" - type: "alignment" - offsets: [] - - for i of row_nodes - node = row_nodes[i] - constraint.offsets.push - node: gdd.node_index[node.sha1] - offset: 0 - - return constraint + debug_constraints() + return + +################################################################## +# helpers + +# Uses approach explained here: +# https://github.com/tgdwyer/WebCola/issues/62#issuecomment-69571870 +min_max_ordered_separation_constraints = (axis, min, max, left, right) -> + return [ + min_separation_constraint(axis, min, left, right), + max_separation_constraint(axis, max, left, right) + ] + +# https://github.com/tgdwyer/WebCola/issues/66 +max_unordered_separation_constraints = (axis, max, left, right) -> + return [ + max_separation_constraint(axis, max, left, right), + max_separation_constraint(axis, max, right, left) + ] + +min_separation_constraint = (axis, gap, left, right) -> + {} = + axis: axis + gap: gap + left: left + right: right + +# We use a negative gap and reverse the inequality, in order to +# achieve a maximum rather than minimum separation gap. However this +# does not prevent the nodes from overlapping or even swapping order. +# For that you also need a min_separation_constraint, but it's more +# convenient to use min_max_ordered_separation_constraints. See +# https://github.com/tgdwyer/WebCola/issues/62#issuecomment-69571870 +# for more details. +max_separation_constraint = (axis, gap, left, right) -> + {} = + axis: axis + gap: -gap + left: right + right: left node = (sha1) -> exports.graph.node sha1 |