API docs for “bzrlib.deprecated

Line #	Kind	Name	Docs
18	Function	max_distance	Calculate the max distance to an ancestor.
39	Function	node_distances	Produce a list of nodes, sorted by distance from a start node.
70	Function	nodes_by_distance	Return a list of nodes sorted by distance
79	Function	select_farthest	Return the farthest common node, or None if no node qualifies.
86	Function	all_descendants	Produce a set of all descendants of the start node.
107	Class	Graph	A graph object which can memoise and cache results for performance.

def max_distance(node, ancestors, distances, root_descendants):

Calculate the max distance to an ancestor. Return None if not all possible ancestors have known distances

def node_distances(graph, ancestors, start, root_descendants=None):

Produce a list of nodes, sorted by distance from a start node. This is an algorithm devised by Aaron Bentley, because applying Dijkstra backwards seemed too complicated.

For each node, we walk its descendants. If all the descendant's ancestors have a max-distance-to-start, (excluding ones that can never reach start), we calculate their max-distance-to-start, and schedule their descendants.

So when a node's last parent acquires a distance, it will acquire a distance on the next iteration.

Once we know the max distances for all nodes, we can return a list sorted by distance, farthest first.

def nodes_by_distance(distances):

Return a list of nodes sorted by distance

def select_farthest(distances, common):

Return the farthest common node, or None if no node qualifies.

def all_descendants(descendants, start):

Produce a set of all descendants of the start node. The input is a map of node->list of descendants for a graph encompassing start.

Module b.deprecated_graph