1
# Copyright (C) 2005, 2008 Canonical Ltd
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
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"""
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:
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:
32
if ancestor not in distances:
34
if best is None or distances[ancestor]+1 > best:
35
best = distances[ancestor] + 1
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.
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.
48
So when a node's last parent acquires a distance, it will acquire a
49
distance on the next iteration.
51
Once we know the max distances for all nodes, we can return a list sorted
52
by distance, farthest first.
54
distances = {start: 0}
59
line_descendants = graph[line]
60
assert line not in line_descendants, "%s refers to itself" % line
61
for descendant in line_descendants:
62
distance = max_distance(descendant, ancestors, distances,
66
distances[descendant] = distance
67
new_lines.add(descendant)
71
def nodes_by_distance(distances):
72
"""Return a list of nodes sorted by distance"""
76
node_list = distances.keys()
77
node_list.sort(key=by_distance, reverse=True)
80
def select_farthest(distances, common):
81
"""Return the farthest common node, or None if no node qualifies."""
82
node_list = nodes_by_distance(distances)
83
for node in node_list:
87
def all_descendants(descendants, start):
88
"""Produce a set of all descendants of the start node.
89
The input is a map of node->list of descendants for a graph encompassing
97
if line not in descendants:
99
for descendant in descendants[line]:
100
if descendant in result:
102
result.add(descendant)
103
new_lines.add(descendant)
109
"""A graph object which can memoise and cache results for performance."""
112
super(Graph, self).__init__()
114
self.ghosts = set([])
115
self._graph_ancestors = {}
116
self._graph_descendants = {}
118
def add_ghost(self, node_id):
119
"""Add a ghost to the graph."""
120
self.ghosts.add(node_id)
121
self._ensure_descendant(node_id)
123
def add_node(self, node_id, parent_ids):
124
"""Add node_id to the graph with parent_ids as its parents."""
125
if len(parent_ids) == 0:
126
self.roots.add(node_id)
127
self._graph_ancestors[node_id] = list(parent_ids)
128
self._ensure_descendant(node_id)
129
for parent in parent_ids:
130
self._ensure_descendant(parent)
131
self._graph_descendants[parent][node_id] = 1
133
def _ensure_descendant(self, node_id):
134
"""Ensure that a descendant lookup for node_id will work."""
135
if not node_id in self._graph_descendants:
136
self._graph_descendants[node_id] = {}
138
def get_ancestors(self):
139
"""Return a dictionary of graph node:ancestor_list entries."""
140
return dict(self._graph_ancestors.items())
142
def get_ancestry(self, node_id, topo_sorted=True):
143
"""Return the inclusive ancestors of node_id in topological order."""
144
# maybe optimise this ?
145
from bzrlib.tsort import topo_sort
147
pending = set([node_id])
149
current = pending.pop()
150
parents = self._graph_ancestors[current]
151
parents = [parent for parent in parents if parent not in self.ghosts]
152
result[current] = parents
153
for parent in parents:
154
if parent not in result and parent not in pending:
158
return topo_sort(result.items())
160
def get_descendants(self):
161
"""Return a dictionary of graph node:child_node:distance entries."""
162
return dict(self._graph_descendants.items())
added
removed
bzrlib/deprecated_graph.py
