1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
DEBUG = false
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"
# The list of constraints to feed into WebCola.
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.
row_groups = {}
debug = (msg) ->
if DEBUG
console.log msg
dagre_layout = ->
g = new dagre.graphlib.Graph()
exports.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 -> {}
for node in gdd.nodes
g.setNode node.sha1,
label: node.name
width: node.rect_width or 70
height: node.rect_height or 30
for parent_sha1, children of gdd.deps
for child_sha1, bool of children
g.setEdge parent_sha1, child_sha1
dagre.layout g
return g
dagre_row_groups = ->
g = dagre_layout()
row_groups = {}
exports.row_groups = row_groups
for sha1 in g.nodes()
x = g.node(sha1).x
y = g.node(sha1).y
row_groups[y] = [] unless y of row_groups
row_groups[y].push
sha1: sha1
x: x
for y, nodes of row_groups
nodes.sort (n) -> -n.x
return 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.
continue if row_nodes.length <= 1
# Multiple constraints per row.
row_node_ordering_constraints(row_nodes)
# 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
while i < row_y_coords.length - 1
upper_y = row_y_coords[i]
lower_y = row_y_coords[i + 1]
upper_node = row_groups[upper_y][0]
lower_node = row_groups[lower_y][0]
constraints.push \
min_separation_constraint \
MIN_ROW_GAP, 'y',
gdd.node_index[upper_node.sha1],
gdd.node_index[lower_node.sha1]
i++
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
module.exports = exports =
# Variables have to be exported every time they're assigned,
# since assignment creates a new object and associated reference
# Functions
build_constraints: build_constraints
node: node
|
