102
102
new_lines.add(descendant)
103
103
lines = new_lines
108
"""A graph object which can memoise and cache results for performance."""
111
super(Graph, self).__init__()
113
self.ghosts = set([])
114
self._graph_ancestors = {}
115
self._graph_descendants = {}
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)
122
def add_node(self, node_id, parent_ids):
123
"""Add node_id to the graph with parent_ids as its parents."""
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
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] = {}
137
def get_ancestors(self):
138
"""Return a dictionary of graph node:ancestor_list entries."""
139
return dict(self._graph_ancestors.items())
141
def get_descendants(self):
142
"""Return a dictionary of graph node:child_node:distance entries."""
143
return dict(self._graph_descendants.items())
added
removed
bzrlib/graph.py
