← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/deprecated_graph.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2008-03-16 16:58:03 UTC
  • mfrom: (3224.3.1 news-typo)
  • Revision ID: pqm@pqm.ubuntu.com-20080316165803-tisoc9mpob9z544o
(Matt Nordhoff) Trivial NEWS typo fix

Show diffs side-by-side

added added

removed removed

Lines of Context:
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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
            assert line not in line_descendants, "%s refers to itself" % line
 
61
            for descendant in line_descendants:
 
62
                distance = max_distance(descendant, ancestors, distances,
 
63
                                        root_descendants)
 
64
                if distance is None:
 
65
                    continue
 
66
                distances[descendant] = distance
 
67
                new_lines.add(descendant)
 
68
        lines = new_lines
 
69
    return distances
 
70
 
 
71
def nodes_by_distance(distances):
 
72
    """Return a list of nodes sorted by distance"""
 
73
    def by_distance(n):
 
74
        return distances[n],n
 
75
 
 
76
    node_list = distances.keys()
 
77
    node_list.sort(key=by_distance, reverse=True)
 
78
    return node_list
 
79
 
 
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:
 
84
        if node in common:
 
85
            return node
 
86
 
 
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
 
90
    start.
 
91
    """
 
92
    result = set()
 
93
    lines = set([start])
 
94
    while len(lines) > 0:
 
95
        new_lines = set()
 
96
        for line in lines:
 
97
            if line not in descendants:
 
98
                continue
 
99
            for descendant in descendants[line]:
 
100
                if descendant in result:
 
101
                    continue
 
102
                result.add(descendant)
 
103
                new_lines.add(descendant)
 
104
        lines = new_lines
 
105
    return result
 
106
 
 
107
 
 
108
class Graph(object):
 
109
    """A graph object which can memoise and cache results for performance."""
 
110
 
 
111
    def __init__(self):
 
112
        super(Graph, self).__init__()
 
113
        self.roots = set([])
 
114
        self.ghosts = set([])
 
115
        self._graph_ancestors = {}
 
116
        self._graph_descendants = {}
 
117
 
 
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)
 
122
 
 
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
 
132
        
 
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] = {}
 
137
 
 
138
    def get_ancestors(self):
 
139
        """Return a dictionary of graph node:ancestor_list entries."""
 
140
        return dict(self._graph_ancestors.items())
 
141
 
 
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
 
146
        result = {}
 
147
        pending = set([node_id])
 
148
        while len(pending):
 
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:
 
155
                    pending.add(parent)
 
156
        if not topo_sorted:
 
157
            return result.keys()
 
158
        return topo_sort(result.items())
 
159
 
 
160
    def get_descendants(self):
 
161
        """Return a dictionary of graph node:child_node:distance entries."""
 
162
        return dict(self._graph_descendants.items())