b._.KnownGraph(object) : class documentation

Part of bzrlib._known_graph_py View In Hierarchy

This is a class which assumes we already know the full graph.
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
def __init__(self, parent_map, do_cache=True):
Create a new KnownGraph instance.
Parametersparent_mapA dictionary mapping key => parent_keys
def _initialize_nodes(self, parent_map):
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,
def _find_tails(self):
Undocumented
def _find_tips(self):
Undocumented
def _find_gdfo(self):
Undocumented
def add_node(self, key, parent_keys):
Add a new node to the graph.

If this fills in a ghost, then the gdfos of all children will be updated accordingly.

ParameterskeyThe node being added. If this is a duplicate, this is a no-op.
parent_keysThe parents of the given node.
ReturnsNone (should we return if this was a ghost, etc?)
def heads(self, keys):
Return the heads from amongst keys.

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.

ParameterskeysAn iterable of keys.
ReturnsA 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.
def topo_sort(self):
Return the nodes in topological order.

All parents must occur before all children.

def gc_sort(self):
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.
def merge_sort(self, tip_key):
Compute the merge sorted graph output.
def get_parent_keys(self, key):
Get the parents for a key

Returns a list containg the parents keys. If the key is a ghost, None is returned. A KeyError will be raised if the key is not in the graph.

ParameterskeysKey to check (eg revision_id)
ReturnsA list of parents
def get_child_keys(self, key):
Get the children for a key

Returns a list containg the children keys. A KeyError will be raised if the key is not in the graph.

ParameterskeysKey to check (eg revision_id)
ReturnsA list of children
API Documentation for Bazaar, generated by pydoctor at 2022-06-16 00:25:16.