Part of bzrlib._known_graph_py View In Hierarchy
Method | __init__ | Create a new KnownGraph instance. |
Method | add_node | Add a new node to the graph. |
Method | heads | Return the heads from amongst keys. |
Method | topo_sort | Return the nodes in topological order. |
Method | gc_sort | Return a reverse topological ordering which is 'stable'. |
Method | merge_sort | Compute the merge sorted graph output. |
Method | get_parent_keys | Get the parents for a key |
Method | get_child_keys | Get the children for a key |
Method | _initialize_nodes | Populate self._nodes. |
Method | _find_tails | Undocumented |
Method | _find_tips | Undocumented |
Method | _find_gdfo | Undocumented |
Parameters | parent_map | A dictionary mapping key => parent_keys |
Populate self._nodes. After this has finished: - self._nodes will have an entry for every entry in parent_map. - ghosts will have a parent_keys = None, - all nodes found will also have .child_keys populated with all known child_keys,
If this fills in a ghost, then the gdfos of all children will be updated accordingly.
Parameters | key | The node being added. If this is a duplicate, this is a no-op. |
parent_keys | The parents of the given node. | |
Returns | None (should we return if this was a ghost, etc?) |
This is done by searching the ancestries of each key. Any key that is reachable from another key is not returned; all the others are.
This operation scales with the relative depth between any two keys. It uses gdfo to avoid walking all ancestry.
Parameters | keys | An iterable of keys. |
Returns | A set of the heads. Note that as a set there is no ordering information. Callers will need to filter their input to create order if they need it. |
All parents must occur before all children.
Return a reverse topological ordering which is 'stable'. There are a few constraints: 1) Reverse topological (all children before all parents) 2) Grouped by prefix 3) 'stable' sorting, so that we get the same result, independent of machine, or extra data. To do this, we use the same basic algorithm as topo_sort, but when we aren't sure what node to access next, we sort them lexicographically.