« back to all changes in this revision
Viewing changes to bzrlib/deprecated_graph.py
- browse files at revision 5718.9.1
- compare with another revision
- compare with revision 6017.1.2
- download diff
- download tarball
- view history from revision 5718.9.1
- Committer: Jelmer Vernooij
- Date: 2011-03-12 00:17:50 UTC
- mto: This revision was merged to the branch mainline in revision 5845.
- Revision ID: jelmer@canonical.com-20110312001750-4g4gkger050rrxok
Remove bzrlib.deprecated_graph.
- files removed:
- bzrlib/deprecated_graph.py
- files modified:
- bzrlib/revision.py
added
removed
bzrlib/deprecated_graph.py
1
# Copyright (C) 2005, 2008 Canonical Ltd
2
#
3
# This program is free software; you can redistribute it and/or modify
4
# it under the terms of the GNU General Public License as published by
5
# the Free Software Foundation; either version 2 of the License, or
6
# (at your option) any later version.
7
#
8
# This program is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU General Public License for more details.
12
#
13
# You should have received a copy of the GNU General Public License
14
# along with this program; if not, write to the Free Software
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
17
18
def max_distance(node, ancestors, distances, root_descendants):
19
"""Calculate the max distance to an ancestor.
20
Return None if not all possible ancestors have known distances"""
21
best = None
22
if node in distances:
23
best = distances[node]
24
for ancestor in ancestors[node]:
25
# skip ancestors we will never traverse:
26
if root_descendants is not None and ancestor not in root_descendants:
27
continue
28
# An ancestor which is not listed in ancestors will never be in
29
# distances, so we pretend it never existed.
30
if ancestor not in ancestors:
31
continue
32
if ancestor not in distances:
33
return None
34
if best is None or distances[ancestor]+1 > best:
35
best = distances[ancestor] + 1
36
return best
37
38
39
def node_distances(graph, ancestors, start, root_descendants=None):
40
"""Produce a list of nodes, sorted by distance from a start node.
41
This is an algorithm devised by Aaron Bentley, because applying Dijkstra
42
backwards seemed too complicated.
43
44
For each node, we walk its descendants. If all the descendant's ancestors
45
have a max-distance-to-start, (excluding ones that can never reach start),
46
we calculate their max-distance-to-start, and schedule their descendants.
47
48
So when a node's last parent acquires a distance, it will acquire a
49
distance on the next iteration.
50
51
Once we know the max distances for all nodes, we can return a list sorted
52
by distance, farthest first.
53
"""
54
distances = {start: 0}
55
lines = set([start])
56
while len(lines) > 0:
57
new_lines = set()
58
for line in lines:
59
line_descendants = graph[line]
60
for descendant in line_descendants:
61
distance = max_distance(descendant, ancestors, distances,
62
root_descendants)
63
if distance is None:
64
continue
65
distances[descendant] = distance
66
new_lines.add(descendant)
67
lines = new_lines
68
return distances
69
70
def nodes_by_distance(distances):
71
"""Return a list of nodes sorted by distance"""
72
def by_distance(n):
73
return distances[n],n
74
75
node_list = distances.keys()
76
node_list.sort(key=by_distance, reverse=True)
77
return node_list
78
79
def select_farthest(distances, common):
80
"""Return the farthest common node, or None if no node qualifies."""
81
node_list = nodes_by_distance(distances)
82
for node in node_list:
83
if node in common:
84
return node
85
86
def all_descendants(descendants, start):
87
"""Produce a set of all descendants of the start node.
88
The input is a map of node->list of descendants for a graph encompassing
89
start.
90
"""
91
result = set()
92
lines = set([start])
93
while len(lines) > 0:
94
new_lines = set()
95
for line in lines:
96
if line not in descendants:
97
continue
98
for descendant in descendants[line]:
99
if descendant in result:
100
continue
101
result.add(descendant)
102
new_lines.add(descendant)
103
lines = new_lines
104
return result
105
106
107
class Graph(object):
108
"""A graph object which can memoise and cache results for performance."""
109
110
def __init__(self):
111
super(Graph, self).__init__()
112
self.roots = set([])
113
self.ghosts = set([])
114
self._graph_ancestors = {}
115
self._graph_descendants = {}
116
117
def add_ghost(self, node_id):
118
"""Add a ghost to the graph."""
119
self.ghosts.add(node_id)
120
self._ensure_descendant(node_id)
121
122
def add_node(self, node_id, parent_ids):
123
"""Add node_id to the graph with parent_ids as its parents."""
124
if len(parent_ids) == 0:
125
self.roots.add(node_id)
126
self._graph_ancestors[node_id] = list(parent_ids)
127
self._ensure_descendant(node_id)
128
for parent in parent_ids:
129
self._ensure_descendant(parent)
130
self._graph_descendants[parent][node_id] = 1
131
132
def _ensure_descendant(self, node_id):
133
"""Ensure that a descendant lookup for node_id will work."""
134
if not node_id in self._graph_descendants:
135
self._graph_descendants[node_id] = {}
136
137
def get_ancestors(self):
138
"""Return a dictionary of graph node:ancestor_list entries."""
139
return dict(self._graph_ancestors.items())
140
141
def get_ancestry(self, node_id, topo_sorted=True):
142
"""Return the inclusive ancestors of node_id in topological order."""
143
# maybe optimise this ?
144
from bzrlib.tsort import topo_sort
145
result = {}
146
pending = set([node_id])
147
while len(pending):
148
current = pending.pop()
149
parents = self._graph_ancestors[current]
150
parents = [parent for parent in parents if parent not in self.ghosts]
151
result[current] = parents
152
for parent in parents:
153
if parent not in result and parent not in pending:
154
pending.add(parent)
155
if not topo_sorted:
156
return result.keys()
157
return topo_sort(result.items())
158
159
def get_descendants(self):
160
"""Return a dictionary of graph node:child_node:distance entries."""
161
return dict(self._graph_descendants.items())
Loggerhead is a web-based interface for Breezy
Version: 2.0.1