Part of bzrlib

Topological sorting routines.

Function | topo_sort | Topological sort a graph. |

Class | TopoSorter | No class docstring; 3/3 methods documented |

Function | merge_sort | Topological sort a graph which groups merges. |

Class | MergeSorter | No class docstring; 5/5 methods documented |

def
topo_sort(graph):

Topological sort a graph.

graph -- sequence of pairs of node->parents_list.

The result is a list of node names, such that all parents come before their children.

node identifiers can be any hashable object, and are typically strings.

This function has the same purpose as the TopoSorter class, but uses a different algorithm to sort the graph. That means that while both return a list with parents before their child nodes, the exact ordering can be different.

topo_sort is faster when the whole list is needed, while when iterating over a part of the list, TopoSorter.iter_topo_order should be used.

def
merge_sort(graph, branch_tip, mainline_revisions=None, generate_revno=False):

Topological sort a graph which groups merges.

Node identifiers can be any hashable object, and are typically strings.

Parameters | graph | sequence of pairs of node->parents_list. |

branch_tip | the tip of the branch to graph. Revisions not reachable from branch_tip are not included in the output. | |

mainline_revisions | If not None this forces a mainline to be used rather than synthesised from the graph. This must be a valid path through some part of the graph. If the mainline does not cover all the revisions, output stops at the start of the old revision listed in the mainline revisions list. The order for this parameter is oldest-first. | |

generate_revno | Optional parameter controlling the generation of revision number sequences in the output. See the output description of the MergeSorter docstring for details. | |

Unknown Field: result | See the MergeSorter docstring for details. |