14
14
# You should have received a copy of the GNU General Public License
15
15
# along with this program; if not, write to the Free Software
16
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17
from bzrtools import short_committer
18
from dotgraph import Node, dot_output, invoke_dot, invoke_dot_aa, NoDot, NoRsvg
19
from dotgraph import RSVG_OUTPUT_TYPES, DOT_OUTPUT_TYPES, Edge, invoke_dot_html
20
from bzrlib.branch import Branch
21
from bzrlib.errors import BzrCommandError, NoCommonRoot, NoSuchRevision
22
from bzrlib.graph import node_distances, select_farthest
23
from bzrlib.revision import combined_graph, revision_graph
24
from bzrlib.revision import MultipleRevisionSources
21
from bzrlib.branch import Branch
22
from bzrlib.errors import BzrCommandError, NoSuchRevision
23
from bzrlib.revision import NULL_REVISION
25
from bzrtools import short_committer
26
from dotgraph import (
40
def max_distance(node, ancestors, distances, root_descendants):
41
"""Calculate the max distance to an ancestor.
42
Return None if not all possible ancestors have known distances"""
45
best = distances[node]
46
for ancestor in ancestors[node]:
47
# skip ancestors we will never traverse:
48
if root_descendants is not None and ancestor not in root_descendants:
50
# An ancestor which is not listed in ancestors will never be in
51
# distances, so we pretend it never existed.
52
if ancestor not in ancestors:
54
if ancestor not in distances:
56
if best is None or distances[ancestor]+1 > best:
57
best = distances[ancestor] + 1
61
def node_distances(graph, ancestors, start, root_descendants=None):
62
"""Produce a list of nodes, sorted by distance from a start node.
63
This is an algorithm devised by Aaron Bentley, because applying Dijkstra
64
backwards seemed too complicated.
66
For each node, we walk its descendants. If all the descendant's ancestors
67
have a max-distance-to-start, (excluding ones that can never reach start),
68
we calculate their max-distance-to-start, and schedule their descendants.
70
So when a node's last parent acquires a distance, it will acquire a
71
distance on the next iteration.
73
Once we know the max distances for all nodes, we can return a list sorted
74
by distance, farthest first.
76
distances = {start: 0}
81
line_descendants = graph[line]
82
for descendant in line_descendants:
83
distance = max_distance(descendant, ancestors, distances,
87
distances[descendant] = distance
88
new_lines.add(descendant)
93
def nodes_by_distance(distances):
94
"""Return a list of nodes sorted by distance"""
98
node_list = distances.keys()
99
node_list.sort(key=by_distance, reverse=True)
103
def select_farthest(distances, common):
104
"""Return the farthest common node, or None if no node qualifies."""
105
node_list = nodes_by_distance(distances)
106
for node in node_list:
111
30
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
112
31
'abentley@panoramicfeedback.com': 'Aaron Bentley',
113
32
'abentley@lappy' : 'Aaron Bentley',
187
106
return committer, message, nick, date
189
108
class Grapher(object):
191
109
def __init__(self, branch, other_branch=None):
192
110
object.__init__(self)
193
111
self.branch = branch
194
112
self.other_branch = other_branch
113
revision_a = self.branch.last_revision()
195
114
if other_branch is not None:
196
other_repo = other_branch.repository
115
branch.fetch(other_branch)
197
116
revision_b = self.other_branch.last_revision()
118
self.root, self.ancestors, self.descendants, self.common = \
119
combined_graph(revision_a, revision_b,
120
self.branch.repository)
121
except bzrlib.errors.NoCommonRoot:
122
raise bzrlib.errors.NoCommonAncestor(revision_a, revision_b)
201
self.graph = self.branch.repository.get_graph(other_repo)
202
revision_a = self.branch.last_revision()
203
self.scan_graph(revision_a, revision_b)
124
self.root, self.ancestors, self.descendants = \
125
revision_graph(revision_a, branch.repository)
204
128
self.n_history = branch.revision_history()
205
self.n_revnos = branch.get_revision_id_to_revno_map()
206
129
self.distances = node_distances(self.descendants, self.ancestors,
208
131
if other_branch is not None:
209
132
self.base = select_farthest(self.distances, self.common)
210
133
self.m_history = other_branch.revision_history()
211
self.m_revnos = other_branch.get_revision_id_to_revno_map()
212
self.new_base = self.graph.find_unique_lca(revision_a,
214
self.lcas = self.graph.find_lca(revision_a, revision_b)
219
136
self.m_history = []
222
def scan_graph(self, revision_a, revision_b):
223
a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
224
self.ancestors = a_ancestors
225
self.root = NULL_REVISION
226
if revision_b is not None:
227
b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
228
self.common = set(a_ancestors.keys())
229
self.common.intersection_update(b_ancestors)
230
self.ancestors.update(b_ancestors)
234
self.descendants = {}
236
for revision, parents in self.ancestors.iteritems():
237
self.descendants.setdefault(revision, [])
240
parents = [NULL_REVISION]
241
for parent in parents:
242
self.descendants.setdefault(parent, []).append(revision)
244
self.ancestors[ghost] = [NULL_REVISION]
247
def _get_revno_str(prefix, revno_map, revision_id):
249
revno = revno_map[revision_id]
252
return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
254
138
def dot_node(self, node, num):
333
207
node_relations = []
336
exceptions = self.lcas.union([self.base, self.new_base])
337
210
visible_ancestors = compact_ancestors(self.descendants,
211
self.ancestors, (self.base,))
341
visible_ancestors = {}
342
for revision, parents in self.ancestors.iteritems():
343
visible_ancestors[revision] = dict((p, 0) for p in parents)
213
visible_ancestors = self.ancestors
344
214
if max_distance is not None:
345
215
min_distance = max(self.distances.values()) - max_distance
346
visible_ancestors = dict((n, p) for n, p in
347
visible_ancestors.iteritems() if
348
self.distances[n] >= min_distance)
216
visible_ancestors = dict((n, p) for n, p in visible_ancestors.iteritems() if
217
self.distances[n] >= min_distance)
349
218
for node, parents in visible_ancestors.iteritems():
350
219
if node not in dot_nodes:
351
220
dot_nodes[node] = self.dot_node(node, num)
353
for parent, skipped in parents.iteritems():
222
if visible_ancestors is self.ancestors:
223
parent_iter = ((f, 0) for f in parents)
225
parent_iter = (f for f in parents.iteritems())
226
for parent, skipped in parent_iter:
354
227
if parent not in dot_nodes:
355
228
dot_nodes[parent] = self.dot_node(parent, num)
added
removed
graph.py
