/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 graph.py

  • Committer: David Allouche
  • Date: 2006-05-08 13:03:59 UTC
  • Revision ID: david.allouche@canonical.com-20060508130359-f9a471d0d0b1dcf2
remove --robust, pyflakes fixes, update README

Thanks to Robert Collins' new graphing logic, the --robust option is
no longer needed to prevent extreme graph width on broken branches.
That allows removing a bunch of flaky code.

Remove a few spurious imports (thanks to pyflakes).

Update README to request bzr>=0.8.

Show diffs side-by-side

added added

removed removed

Lines of Context:
graph.py
11
11
__author__    = "Scott James Remnant <scott@ubuntu.com>"
12
12
 
13
13
 
14
 
from bzrlib.errors import NoSuchRevision
15
14
from bzrlib.tsort import merge_sort
16
15
 
17
16
 
113
112
        return dict((revisions[revid], c)
114
113
                    for (revid, c) in self.children_of_id.iteritems())
115
114
 
116
 
    def remove_redundant_parents(self, sorted_revids):
117
 
        children_of_id = self.children_of_id
118
 
        revisions = self.revisions
119
 
        parent_ids_of = self.parent_ids_of
120
 
        
121
 
        # Count the number of children of each revision, so we can release
122
 
        # memory for ancestry data as soon as it's not going to be needed
123
 
        # anymore.
124
 
        pending_count_of = {}
125
 
        for parent_id, children in children_of_id.iteritems():
126
 
            pending_count_of[parent_id] = len(children)
127
 
 
128
 
        # Build the ancestry dictionnary by examining older revisions first,
129
 
        # and remove revision parents that are ancestors of other parents of
130
 
        # the same revision.
131
 
        ancestor_ids_of = {}
132
 
        for revid in reversed(sorted_revids):
133
 
            revision = revisions[revid]
134
 
            parent_ids = parent_ids_of[revision]
135
 
            # ignore candidate parents which are an ancestor of another parent,
136
 
            # but never ignore the leftmost parent
137
 
            redundant_ids = []
138
 
            ignorable_parent_ids = parent_ids[1:] # never ignore leftmost
139
 
            for candidate_id in ignorable_parent_ids: 
140
 
                for parent_id in list(parent_ids):
141
 
                    if candidate_id in ancestor_ids_of[parent_id]:
142
 
                        redundant_ids.append(candidate_id)
143
 
                        parent_ids.remove(candidate_id)
144
 
                        children_of_candidate = children_of_id[candidate_id]
145
 
                        children_of_candidate.remove(revision)
146
 
                        break
147
 
            # save the set of ancestors of that revision
148
 
            ancestor_ids = set(parent_ids)
149
 
            for parent_id in parent_ids:
150
 
                ancestor_ids.update(ancestor_ids_of[parent_id])
151
 
            ancestor_ids_of[revid] = ancestor_ids
152
 
            # discard ancestry data for revisions whose children are already
153
 
            # done
154
 
            for parent_id in parent_ids + redundant_ids:
155
 
                pending_count = pending_count_of[parent_id] - 1
156
 
                pending_count_of[parent_id] = pending_count
157
 
                if pending_count == 0:
158
 
                    ancestor_ids_of[parent_id] = None
159
 
 
160
115
    def sort_revisions(self, sorted_revids, maxnum):
161
116
        revisions = self.revisions
162
117
        parent_ids_of = self.parent_ids_of
282
237
                self.colours[revid] = self.last_colour = self.last_colour + 1
283
238
 
284
239
 
285
 
def distances(branch, start, robust, maxnum):
 
240
def distances(branch, start, maxnum):
286
241
    """Sort the revisions.
287
242
 
288
243
    Traverses the branch revision tree starting at start and produces an
293
248
    """
294
249
    distance = DistanceMethod(branch, start)
295
250
    distance.fill_caches()
296
 
    if robust:
297
 
        print 'robust filtering'
298
 
        distance.remove_redundant_parents(self.graph.keys())
299
251
    distance.merge_sorted = merge_sort(distance.graph, distance.start)
300
252
    children = distance.make_children_map()
301
253