134
134
ancestor of all border ancestors.
136
136
border_common, common, sides = self._find_border_ancestors(revisions)
137
return self._filter_candidate_lca(border_common)
137
# We may have common ancestors that can be reached from each other.
138
# - ask for the heads of them to filter it down to only ones that
139
# cannot be reached from each other - phase 2.
140
return self.heads(border_common)
139
142
def find_difference(self, left_revision, right_revision):
140
143
"""Determine the graph difference between two revisions"""
212
215
for searcher in searchers:
213
216
update_common(searcher, revision)
215
def _filter_candidate_lca(self, candidate_lca):
216
"""Remove candidates which are ancestors of other candidates.
218
This is done by searching the ancestries of each border ancestor. It
219
is perfomed on the principle that a border ancestor that is not an
220
ancestor of any other border ancestor is a lowest common ancestor.
222
Searches are stopped when they find a node that is determined to be a
223
common ancestor of all border ancestors, because this shows that it
224
cannot be a descendant of any border ancestor.
226
This will scale with the number of candidate ancestors and the length
227
of the shortest path from a candidate to an ancestor common to all
218
def heads(self, keys):
219
"""Return the heads from amongst keys.
221
This is done by searching the ancestries of each key. Any key that is
222
reachable from another key is not returned; all the others are.
224
This operation scales with the relative depth between any two keys. If
225
any two keys are completely disconnected all ancestry of both sides
228
:param keys: An iterable of keys.
229
:return: A set of the heads. Note that as a set there is no ordering
230
information. Callers will need to filter their input to create
231
order if they need it.
233
candidate_heads = set(keys)
230
234
searchers = dict((c, self._make_breadth_first_searcher([c]))
231
for c in candidate_lca)
235
for c in candidate_heads)
232
236
active_searchers = dict(searchers)
233
237
# skip over the actual candidate for each searcher
234
238
for searcher in active_searchers.itervalues():
248
252
del active_searchers[candidate]
250
254
for ancestor in ancestors:
251
if ancestor in candidate_lca:
252
candidate_lca.remove(ancestor)
255
if ancestor in candidate_heads:
256
candidate_heads.remove(ancestor)
253
257
del searchers[ancestor]
254
258
if ancestor in active_searchers:
255
259
del active_searchers[ancestor]
added
removed
bzrlib/graph.py
