← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: John Arbash Meinel
  • Date: 2009-06-15 17:00:30 UTC
  • mto: This revision was merged to the branch mainline in revision 4449.
  • Revision ID: john@arbash-meinel.com-20090615170030-p3am5qp19pstlu9x
Add a bit of discussion about why we would want to use linear dominators.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
97
97
        For any given node, the 'linear dominator' is an ancestor, such that
98
98
        all parents between this node and that one have a single parent, and a
99
99
        single child. So if A->B->C->D then B,C,D all have a linear dominator
100
 
        of A. Because there are no interesting siblings, we can quickly skip to
101
 
        the nearest dominator when doing comparisons.
 
100
        of A.
 
101
 
 
102
        There are two main benefits:
 
103
        1) When walking the graph, we can jump to the nearest linear dominator,
 
104
           rather than walking all of the nodes inbetween.
 
105
        2) When caching heads() results, dominators give the "same" results as
 
106
           their children. (If the dominator is a head, then the descendant is
 
107
           a head, if the dominator is not a head, then the child isn't
 
108
           either.)
102
109
        """
103
110
        def check_node(node):
104
111
            if node.parent_keys is None or len(node.parent_keys) != 1: