/b-gtk/fix-viz

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 viz/linegraph.py

  • Committer: Gary van der Merwe
  • Date: 2007-09-06 17:55:13 UTC
  • mto: (256.2.37 gtk)
  • mto: This revision was merged to the branch mainline in revision 289.
  • Revision ID: garyvdm@gmail.com-20070906175513-rmu73x7zhqhtx3u2
Better line drawing with info from merge_sort

Show diffs side-by-side

added added

removed removed

Lines of Context:
viz/linegraph.py
14
14
def linegraph(branch, start, maxnum):
15
15
    """Produce a directed graph of a bzr branch.
16
16
 
17
 
    Returns a list of tuples of (revision,
 
17
    Returns a list of tuples of (revid,
18
18
                                 node,
19
19
                                 lines,
20
20
                                 parents,
41
41
    graph_children = {}
42
42
    for revid in graph_parents.keys():
43
43
        graph_children[revid] = []
44
 
    
45
 
    rev_index = {}
46
 
    
47
 
    
 
44
 
48
45
    merge_sorted_revisions = merge_sort(
49
46
        graph_parents,
50
47
        start,
51
48
        mainline,
52
49
        generate_revno=True)
53
50
    
54
 
    revids = [revid for (sequence_number,
55
 
                 revid,
56
 
                 merge_depth,
57
 
                 revno_sequence,
58
 
                 end_of_merge) in merge_sorted_revisions]
59
 
    
60
 
    revisions = branch.repository.get_revisions(revids)
61
 
    linegraph = []
 
51
    revid_index = {}
 
52
    revno_index = {}
 
53
    branch_lines = {}
 
54
    linegraph = []    
62
55
    
63
56
    for (index, (sequence_number,
64
57
                 revid,
66
59
                 revno_sequence,
67
60
                 end_of_merge)) in enumerate(merge_sorted_revisions):
68
61
        
69
 
        revision = revisions[index]
70
 
        rev_index[revid] = index
71
 
        
72
 
        color = reduce(lambda x, y: x+y, revno_sequence[0:-2], 0)
73
 
        
74
 
        parents = [parent for parent in graph_parents[revid] \
75
 
                   if parent!="null:"]
76
 
        
 
62
        revid_index[revid] = index
 
63
        revno_index[revno_sequence] = index
 
64
        
 
65
        branch_id = revno_sequence[0:-1]
 
66
        
 
67
        branch_line = None
 
68
        if branch_id not in branch_lines:
 
69
            branch_line = {}
 
70
            branch_lines[branch_id] = branch_line
 
71
            branch_line["rev_indexes"] = []
 
72
            branch_line["min_index"] = index - 1            
 
73
            branch_line["max_index"] = 0
 
74
        else:
 
75
            branch_line = branch_lines[branch_id]
 
76
        branch_line["rev_indexes"].append(index)
 
77
        
 
78
        parents = graph_parents[revid]
77
79
        for parent_revid in parents:
78
80
            graph_children[parent_revid].append(revid)
79
81
        
80
 
        children = graph_children[revid]
81
 
        
82
 
        for child_revid in children:
83
 
            child_index = rev_index[child_revid]
84
 
            child_merge_depth = merge_sorted_revisions[child_index][2]
85
 
            #out from the child to line
86
 
            linegraph[child_index][2].append(
87
 
                (child_merge_depth,    #the column of the child
88
 
                 merge_depth,     #the column of the line
89
 
                 color))
90
 
            
91
 
            for line_part_index in range(child_index+1, index):
92
 
                linegraph[line_part_index][2].append(
93
 
                    (merge_depth,    #the column of the child
94
 
                     merge_depth,     #the column of the line
95
 
                     color))
96
 
        
97
 
        linegraph.append((revision,
98
 
                          (merge_depth, color),
 
82
        linegraph.append([revid,
 
83
                          None,
99
84
                          [],
100
85
                          parents,
101
 
                          children,
102
 
                          revno_sequence))
103
 
 
104
 
    return (linegraph, rev_index, revisions)
 
86
                          None,
 
87
                          revno_sequence])
 
88
 
 
89
    branch_ids = branch_lines.keys()
 
90
    branch_ids.sort()
 
91
    columns = []
 
92
    
 
93
    for branch_id in branch_ids:
 
94
        branch_line = branch_lines[branch_id]
 
95
        branch_line["inward_line_ends"] = []
 
96
        for rev_index in branch_line["rev_indexes"]:
 
97
            (sequence_number,
 
98
                 revid,
 
99
                 merge_depth,
 
100
                 revno_sequence,
 
101
                 end_of_merge) = merge_sorted_revisions[rev_index]
 
102
            for parent_revid in graph_parents[revid]:
 
103
                if parent_revid in revid_index:
 
104
                    parent_index = revid_index[parent_revid]
 
105
                    parent_merge_depth = merge_sorted_revisions[parent_index][2]
 
106
                    if parent_merge_depth < merge_depth:
 
107
                        branch_line["inward_line_ends"].append(parent_index)
 
108
                        if branch_line["max_index"] < parent_index:
 
109
                            branch_line["max_index"] =parent_index
 
110
            
 
111
            for child_revid in graph_children[revid]:
 
112
                if child_revid in revid_index:
 
113
                    child_index = revid_index[child_revid]
 
114
                    child_merge_depth = merge_sorted_revisions[child_index][2]
 
115
                    if child_merge_depth < merge_depth:
 
116
                        branch_line["inward_line_ends"].append(child_index)
 
117
        
 
118
        col_index = None
 
119
        start_col_index = 0
 
120
        if branch_id:
 
121
            start_col_index = branch_lines[branch_id[0:-2]]["col_index"]+1
 
122
        for col_search_index in range(start_col_index,len(columns)):
 
123
            column = columns[col_search_index]
 
124
            clashing_lines = []
 
125
            for line in column:
 
126
                if (line["min_index"] <= branch_line["min_index"] and \
 
127
                    line["max_index"] >  branch_line["min_index"]) or \
 
128
                   (line["max_index"] >= branch_line["max_index"] and \
 
129
                    line["min_index"] <  branch_line["max_index"]):
 
130
                        clashing_lines.append(line)
 
131
            
 
132
            if not clashing_lines:
 
133
                col_index = col_search_index
 
134
                break
 
135
        
 
136
        if not col_index:
 
137
            col_index = len(columns)
 
138
            columns.append([])
 
139
        
 
140
        columns[col_index].append(branch_line)
 
141
        branch_line["col_index"] = col_index
 
142
 
 
143
 
 
144
    for branch_id in branch_ids:
 
145
        branch_line = branch_lines[branch_id]
 
146
        color = reduce(lambda x, y: x+y, branch_id, 0)
 
147
        col_index = branch_line["col_index"]
 
148
        node = (col_index, color)
 
149
        
 
150
        for rev_index in branch_line["rev_indexes"]:
 
151
            (sequence_number,
 
152
                 revid,
 
153
                 merge_depth,
 
154
                 revno_sequence,
 
155
                 end_of_merge) = merge_sorted_revisions[rev_index]
 
156
            children = graph_children[revid]
 
157
            
 
158
            linegraph[rev_index][1] = node
 
159
            linegraph[rev_index][4] = children
 
160
            for child_revid in children:
 
161
                if child_revid in revid_index:
 
162
                    child_index = revid_index[child_revid]
 
163
                    child_revno_sequence = \
 
164
                                        merge_sorted_revisions[child_index][3]
 
165
                    child_merge_depth = merge_sorted_revisions[child_index][2]
 
166
                    child_branch_id = child_revno_sequence[0:-1]
 
167
                    child_col_index = branch_lines[child_branch_id]["col_index"]
 
168
                    if child_merge_depth < merge_depth:
 
169
                        #out from the child to line
 
170
                        linegraph[child_index][2].append(
 
171
                            (child_col_index,
 
172
                             col_index,
 
173
                             color))
 
174
                        for line_part_index in range(child_index+1, rev_index):
 
175
                            linegraph[line_part_index][2].append(
 
176
                                (col_index,
 
177
                                 col_index,
 
178
                                 color))
 
179
                    else:
 
180
                        for line_part_index in range(child_index, rev_index-1):
 
181
                            linegraph[line_part_index][2].append(
 
182
                                (child_col_index,   
 
183
                                 child_col_index,
 
184
                                 color))
 
185
 
 
186
                        linegraph[rev_index-1][2].append(
 
187
                            (child_col_index,
 
188
                             col_index,
 
189
                             color))
 
190
    
 
191
    return (linegraph, revid_index)
105
192
 
106
193
 
107
194
def same_branch(a, b):