To get this branch, use:
bzr branch
http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz
« back to all changes in this revision
Viewing changes to branchview/linegraph.py
- browse files at revision 399.1.13
- compare with another revision
- compare with revision 399.1.13
- download diff
- download tarball
- view history from revision 399.1.13
- Committer: Daniel Schierbeck
- Date: 2008-03-15 20:54:34 UTC
- mfrom: (452.2.3 trunk)
- mto: (450.1.11 trunk) (399.1.17 signatures)
- mto: This revision was merged to the branch mainline in revision 458.
- Revision ID: daniel.schierbeck@gmail.com-20080315205434-kyrh22sjeao3g9j4
Merged with mainline.
- files added:
- handle-patch
- files modified:
- NEWS
added
removed
branchview/linegraph.py
11
11
12
12
from bzrlib.tsort import merge_sort
13
13
14
def linegraph(repository, start, maxnum, broken_line_length=None):
14
def linegraph(repository, start, maxnum, broken_line_length = None,
15
graph_data = True, mainline_only = False):
15
16
"""Produce a directed graph of a bzr repository.
16
17
17
18
Returns a tuple of (line_graph, revid_index, columns_len) where
54
55
else:
55
56
merge_sorted_revisions = ()
56
57
58
if mainline_only:
59
merge_sorted_revisions = [elem for elem in merge_sorted_revisions \
60
if len(elem[3])==1 ]
61
57
62
revid_index = {}
58
63
revno_index = {}
59
64
76
81
if maxnum and rev_index >= maxnum:
77
82
break
78
83
revid_index[revid] = rev_index
79
revno_index[revno_sequence] = rev_index
80
81
branch_id = revno_sequence[0:-1]
82
83
branch_line = None
84
if branch_id not in branch_lines:
85
branch_line = []
86
branch_lines[branch_id] = branch_line
87
else:
88
branch_line = branch_lines[branch_id]
89
90
branch_line.append(rev_index)
91
84
92
85
parents = graph_parents[revid]
93
86
for parent_revid in parents:
99
92
parents,
100
93
None,
101
94
revno_sequence])
95
96
if graph_data:
97
revno_index[revno_sequence] = rev_index
98
99
branch_id = revno_sequence[0:-1]
100
101
branch_line = None
102
if branch_id not in branch_lines:
103
branch_line = []
104
branch_lines[branch_id] = branch_line
105
else:
106
branch_line = branch_lines[branch_id]
107
108
branch_line.append(rev_index)
102
109
103
branch_ids = branch_lines.keys()
104
105
def branch_id_cmp(x, y):
106
"""Compaire branch_id's first by the number of digits, then reversed
107
by their value"""
108
len_x = len(x)
109
len_y = len(y)
110
if len_x == len_y:
111
return -cmp(x, y)
112
return cmp(len_x, len_y)
113
114
branch_ids.sort(branch_id_cmp)
115
# This will hold a tuple of (child_index, parent_index, col_index) for each
116
# line that needs to be drawn. If col_index is not none, then the line is
117
# drawn along that column, else the the line can be drawn directly between
118
# the child and parent because either the child and parent are in the same
119
# branch line, or the child and parent are 1 row apart.
120
lines = []
121
empty_column = [False for i in range(len(graph_parents))]
122
# This will hold a bit map for each cell. If the cell is true, then the
123
# cell allready contains a node or line. This use when deciding what column
124
# to place a branch line or line in, without it overlaping something else.
125
columns = [list(empty_column)]
126
127
128
for branch_id in branch_ids:
129
branch_line = branch_lines[branch_id]
130
131
# Find the col_index for the direct parent branch. This will be the
132
# starting point when looking for a free column.
133
parent_col_index = 0
134
parent_index = None
135
if len(branch_id) > 1:
136
parent_revno = branch_id[0:-1]
137
if parent_revno in revno_index:
138
parent_index = revno_index[parent_revno]
139
parent_node = linegraph[parent_index][1]
140
if parent_node:
141
parent_col_index = parent_node[0]
142
143
144
col_search_order = _branch_line_col_search_order(columns,
145
parent_col_index)
146
color = reduce(lambda x, y: x+y, branch_id, 0)
147
cur_cont_line = []
148
149
line_range = []
150
last_rev_index = None
151
for rev_index in branch_line:
152
if last_rev_index:
153
if broken_line_length and \
154
rev_index - last_rev_index > broken_line_length:
155
line_range.append(last_rev_index+1)
156
line_range.append(rev_index-1)
157
else:
158
line_range.extend(range(last_rev_index+1, rev_index))
159
160
line_range.append(rev_index)
161
last_rev_index = rev_index
162
163
if parent_index:
164
if broken_line_length and \
165
parent_index - last_rev_index > broken_line_length:
166
line_range.append(last_rev_index+1)
167
else:
168
line_range.extend(range(last_rev_index+1, parent_index))
169
170
col_index = _find_free_column(columns,
171
empty_column,
172
col_search_order,
173
line_range)
174
node = (col_index, color)
175
for rev_index in branch_line:
176
linegraph[rev_index][1] = node
177
columns[col_index][rev_index] = True
178
179
for rev_index in branch_line:
180
(sequence_number,
181
revid,
182
merge_depth,
183
revno_sequence,
184
end_of_merge) = merge_sorted_revisions[rev_index]
185
186
linegraph[rev_index][4] = graph_children[revid]
187
col_index = linegraph[rev_index][1][0]
188
189
for parent_revid in graph_parents[revid]:
190
if parent_revid in revid_index:
191
192
parent_index = revid_index[parent_revid]
110
if graph_data:
111
branch_ids = branch_lines.keys()
112
113
def branch_id_cmp(x, y):
114
"""Compaire branch_id's first by the number of digits, then reversed
115
by their value"""
116
len_x = len(x)
117
len_y = len(y)
118
if len_x == len_y:
119
return -cmp(x, y)
120
return cmp(len_x, len_y)
121
122
branch_ids.sort(branch_id_cmp)
123
# This will hold a tuple of (child_index, parent_index, col_index) for each
124
# line that needs to be drawn. If col_index is not none, then the line is
125
# drawn along that column, else the the line can be drawn directly between
126
# the child and parent because either the child and parent are in the same
127
# branch line, or the child and parent are 1 row apart.
128
lines = []
129
empty_column = [False for i in range(len(graph_parents))]
130
# This will hold a bit map for each cell. If the cell is true, then the
131
# cell allready contains a node or line. This use when deciding what column
132
# to place a branch line or line in, without it overlaping something else.
133
columns = [list(empty_column)]
134
135
136
for branch_id in branch_ids:
137
branch_line = branch_lines[branch_id]
138
139
# Find the col_index for the direct parent branch. This will be the
140
# starting point when looking for a free column.
141
parent_col_index = 0
142
parent_index = None
143
if len(branch_id) > 1:
144
parent_revno = branch_id[0:-1]
145
if parent_revno in revno_index:
146
parent_index = revno_index[parent_revno]
193
147
parent_node = linegraph[parent_index][1]
194
148
if parent_node:
195
149
parent_col_index = parent_node[0]
150
151
152
col_search_order = _branch_line_col_search_order(columns,
153
parent_col_index)
154
color = reduce(lambda x, y: x+y, branch_id, 0)
155
cur_cont_line = []
156
157
line_range = []
158
last_rev_index = None
159
for rev_index in branch_line:
160
if last_rev_index:
161
if broken_line_length and \
162
rev_index - last_rev_index > broken_line_length:
163
line_range.append(last_rev_index+1)
164
line_range.append(rev_index-1)
196
165
else:
197
parent_col_index = None
198
col_search_order = \
199
_line_col_search_order(columns,
200
parent_col_index,
201
col_index)
202
203
# If this line is really long, break it.
204
if len(branch_id) > 0 and \
205
broken_line_length and \
206
parent_index - rev_index > broken_line_length:
207
child_line_col_index = \
208
_find_free_column(columns,
209
empty_column,
210
col_search_order,
211
(rev_index + 1,))
212
_mark_column_as_used(columns,
213
child_line_col_index,
214
(rev_index + 1,))
215
216
# Recall _line_col_search_order to reset it back to
217
# the beging.
166
line_range.extend(range(last_rev_index+1, rev_index))
167
168
line_range.append(rev_index)
169
last_rev_index = rev_index
170
171
if parent_index:
172
if broken_line_length and \
173
parent_index - last_rev_index > broken_line_length:
174
line_range.append(last_rev_index+1)
175
else:
176
line_range.extend(range(last_rev_index+1, parent_index))
177
178
col_index = _find_free_column(columns,
179
empty_column,
180
col_search_order,
181
line_range)
182
node = (col_index, color)
183
for rev_index in branch_line:
184
linegraph[rev_index][1] = node
185
columns[col_index][rev_index] = True
186
187
for rev_index in branch_line:
188
(sequence_number,
189
revid,
190
merge_depth,
191
revno_sequence,
192
end_of_merge) = merge_sorted_revisions[rev_index]
193
194
linegraph[rev_index][4] = graph_children[revid]
195
col_index = linegraph[rev_index][1][0]
196
197
for parent_revid in graph_parents[revid]:
198
if parent_revid in revid_index:
199
200
parent_index = revid_index[parent_revid]
201
parent_node = linegraph[parent_index][1]
202
if parent_node:
203
parent_col_index = parent_node[0]
204
else:
205
parent_col_index = None
218
206
col_search_order = \
219
207
_line_col_search_order(columns,
220
208
parent_col_index,
221
209
col_index)
222
parent_col_line_index = \
223
_find_free_column(columns,
224
empty_column,
225
col_search_order,
226
(parent_index - 1,))
227
_mark_column_as_used(columns,
228
parent_col_line_index,
229
(parent_index - 1,))
230
lines.append((rev_index,
231
parent_index,
232
(child_line_col_index,
233
parent_col_line_index)))
234
else :
235
line_col_index = col_index
236
if parent_index - rev_index >1:
237
line_range = range(rev_index + 1, parent_index)
238
line_col_index = \
239
_find_free_column(columns,
240
empty_column,
241
col_search_order,
242
line_range)
243
_mark_column_as_used(columns,
244
line_col_index,
245
line_range)
246
lines.append((rev_index,
247
parent_index,
248
(line_col_index,)))
249
250
for (child_index, parent_index, line_col_indexes) in lines:
251
(child_col_index, child_color) = linegraph[child_index][1]
252
(parent_col_index, parent_color) = linegraph[parent_index][1]
210
211
# If this line is really long, break it.
212
if len(branch_id) > 0 and \
213
broken_line_length and \
214
parent_index - rev_index > broken_line_length:
215
child_line_col_index = \
216
_find_free_column(columns,
217
empty_column,
218
col_search_order,
219
(rev_index + 1,))
220
_mark_column_as_used(columns,
221
child_line_col_index,
222
(rev_index + 1,))
223
224
# Recall _line_col_search_order to reset it back to
225
# the beging.
226
col_search_order = \
227
_line_col_search_order(columns,
228
parent_col_index,
229
col_index)
230
parent_col_line_index = \
231
_find_free_column(columns,
232
empty_column,
233
col_search_order,
234
(parent_index - 1,))
235
_mark_column_as_used(columns,
236
parent_col_line_index,
237
(parent_index - 1,))
238
lines.append((rev_index,
239
parent_index,
240
(child_line_col_index,
241
parent_col_line_index)))
242
else :
243
line_col_index = col_index
244
if parent_index - rev_index >1:
245
line_range = range(rev_index + 1, parent_index)
246
line_col_index = \
247
_find_free_column(columns,
248
empty_column,
249
col_search_order,
250
line_range)
251
_mark_column_as_used(columns,
252
line_col_index,
253
line_range)
254
lines.append((rev_index,
255
parent_index,
256
(line_col_index,)))
253
257
254
if len(line_col_indexes) == 1:
255
if parent_index - child_index == 1:
256
linegraph[child_index][2].append(
257
(child_col_index,
258
parent_col_index,
259
parent_color))
258
for (child_index, parent_index, line_col_indexes) in lines:
259
(child_col_index, child_color) = linegraph[child_index][1]
260
(parent_col_index, parent_color) = linegraph[parent_index][1]
261
262
if len(line_col_indexes) == 1:
263
if parent_index - child_index == 1:
264
linegraph[child_index][2].append(
265
(child_col_index,
266
parent_col_index,
267
parent_color))
268
else:
269
# line from the child's column to the lines column
270
linegraph[child_index][2].append(
271
(child_col_index,
272
line_col_indexes[0],
273
parent_color))
274
# lines down the line's column
275
for line_part_index in range(child_index+1, parent_index-1):
276
linegraph[line_part_index][2].append(
277
(line_col_indexes[0],
278
line_col_indexes[0],
279
parent_color))
280
# line from the line's column to the parent's column
281
linegraph[parent_index-1][2].append(
282
(line_col_indexes[0],
283
parent_col_index,
284
parent_color))
260
285
else:
286
# Broken line
261
287
# line from the child's column to the lines column
262
288
linegraph[child_index][2].append(
263
289
(child_col_index,
264
290
line_col_indexes[0],
265
291
parent_color))
266
# lines down the line's column
267
for line_part_index in range(child_index+1, parent_index-1):
268
linegraph[line_part_index][2].append(
269
(line_col_indexes[0],
270
line_col_indexes[0],
271
parent_color))
292
# Broken line end
293
linegraph[child_index+1][2].append(
294
(line_col_indexes[0],
295
None,
296
parent_color))
297
298
# Broken line end
299
linegraph[parent_index-2][2].append(
300
(None,
301
line_col_indexes[1],
302
parent_color))
272
303
# line from the line's column to the parent's column
273
304
linegraph[parent_index-1][2].append(
274
(line_col_indexes[0],
305
(line_col_indexes[1],
275
306
parent_col_index,
276
307
parent_color))
277
else:
278
# Broken line
279
# line from the child's column to the lines column
280
linegraph[child_index][2].append(
281
(child_col_index,
282
line_col_indexes[0],
283
parent_color))
284
# Broken line end
285
linegraph[child_index+1][2].append(
286
(line_col_indexes[0],
287
None,
288
parent_color))
289
290
# Broken line end
291
linegraph[parent_index-2][2].append(
292
(None,
293
line_col_indexes[1],
294
parent_color))
295
# line from the line's column to the parent's column
296
linegraph[parent_index-1][2].append(
297
(line_col_indexes[1],
298
parent_col_index,
299
parent_color))
300
308
return (linegraph, revid_index, len(columns))
309
else:
310
return (linegraph, revid_index, 0)
301
311
302
return (linegraph, revid_index, len(columns))
303
312
304
313
def _branch_line_col_search_order(columns, parent_col_index):
305
314
for col_index in range(parent_col_index, len(columns)):
Loggerhead is a web-based interface for Breezy
Version: 2.0.2.dev0