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
21
from bzrlib.branch import Branch
22
from bzrlib.errors import BzrCommandError, NoSuchRevision
23
from bzrlib.revision import NULL_REVISION
17
25
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
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:
30
111
mail_map = {'aaron.bentley@utoronto.ca' : 'Aaron Bentley',
31
112
'abentley@panoramicfeedback.com': 'Aaron Bentley',
106
188
return committer, message, nick, date
108
190
class Grapher(object):
109
192
def __init__(self, branch, other_branch=None):
110
193
object.__init__(self)
111
194
self.branch = branch
112
195
self.other_branch = other_branch
196
if other_branch is not None:
197
other_repo = other_branch.repository
198
revision_b = self.other_branch.last_revision()
202
self.graph = self.branch.repository.get_graph(other_repo)
113
203
revision_a = self.branch.last_revision()
114
if other_branch is not None:
115
branch.fetch(other_branch)
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)
124
self.root, self.ancestors, self.descendants = \
125
revision_graph(revision_a, branch.repository)
204
self.scan_graph(revision_a, revision_b)
128
205
self.n_history = branch.revision_history()
206
self.n_revnos = branch.get_revision_id_to_revno_map()
129
207
self.distances = node_distances(self.descendants, self.ancestors,
131
209
if other_branch is not None:
132
210
self.base = select_farthest(self.distances, self.common)
133
211
self.m_history = other_branch.revision_history()
134
new_graph = getattr(branch.repository, 'get_graph', lambda: None)()
135
if new_graph is None:
139
self.new_base = new_graph.find_unique_lca(revision_a,
141
self.lcas = new_graph.find_lca(revision_a, revision_b)
212
self.m_revnos = other_branch.get_revision_id_to_revno_map()
213
self.new_base = self.graph.find_unique_lca(revision_a,
215
self.lcas = self.graph.find_lca(revision_a, revision_b)
144
218
self.new_base = None
145
219
self.lcas = set()
146
220
self.m_history = []
223
def scan_graph(self, revision_a, revision_b):
224
a_ancestors = dict(self.graph.iter_ancestry([revision_a]))
225
self.ancestors = a_ancestors
226
self.root = NULL_REVISION
227
if revision_b is not None:
228
b_ancestors = dict(self.graph.iter_ancestry([revision_b]))
229
self.common = set(a_ancestors.keys())
230
self.common.intersection_update(b_ancestors)
231
self.ancestors.update(b_ancestors)
235
self.descendants = {}
237
for revision, parents in self.ancestors.iteritems():
238
self.descendants.setdefault(revision, [])
241
parents = [NULL_REVISION]
242
for parent in parents:
243
self.descendants.setdefault(parent, []).append(revision)
245
self.ancestors[ghost] = [NULL_REVISION]
248
def _get_revno_str(prefix, revno_map, revision_id):
250
revno = revno_map[revision_id]
253
return '%s%s' % (prefix, '.'.join(str(n) for n in revno))
148
255
def dot_node(self, node, num):
added
removed
graph.py
