← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: John Arbash Meinel
  • Date: 2008-07-13 04:06:16 UTC
  • mto: This revision was merged to the branch mainline in revision 3543.
  • Revision ID: john@arbash-meinel.com-20080713040616-fl43f8inkw19qj2l
Bring in the code to collapse linear portions of the graph.
Also, start handling when we get NULL_REVISION instead of a tuple key
from various apis.
We could probably handle it at a different level if we really wanted.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1444
1444
        """
1445
1445
        return self._keys
1446
1446
 
 
1447
 
 
1448
def collapse_linear_regions(parent_map):
 
1449
    """Collapse regions of the graph that are 'linear'.
 
1450
 
 
1451
    For example::
 
1452
 
 
1453
      A:[B], B:[C]
 
1454
 
 
1455
    can be collapsed by removing B and getting::
 
1456
 
 
1457
      A:[C]
 
1458
 
 
1459
    :param parent_map: A dictionary mapping children to their parents
 
1460
    :return: Another dictionary with 'linear' chains collapsed
 
1461
    """
 
1462
    # Note: this isn't a strictly minimal collapse. For example:
 
1463
    #   A
 
1464
    #  / \
 
1465
    # B   C
 
1466
    #  \ /
 
1467
    #   D
 
1468
    #   |
 
1469
    #   E
 
1470
    # Will not have 'D' removed, even though 'E' could fit. Also:
 
1471
    #   A
 
1472
    #   |    A
 
1473
    #   B => |
 
1474
    #   |    C
 
1475
    #   C
 
1476
    # A and C are both kept because they are edges of the graph. We *could* get
 
1477
    # rid of A if we wanted.
 
1478
    #   A
 
1479
    #  / \
 
1480
    # B   C
 
1481
    # |   |
 
1482
    # D   E
 
1483
    #  \ /
 
1484
    #   F
 
1485
    # Will not have any nodes removed, even though you do have an
 
1486
    # 'uninteresting' linear D->B and E->C
 
1487
    children = {}
 
1488
    for child, parents in parent_map.iteritems():
 
1489
        children.setdefault(child, [])
 
1490
        for p in parents:
 
1491
            children.setdefault(p, []).append(child)
 
1492
 
 
1493
    orig_children = dict(children)
 
1494
    removed = set()
 
1495
    result = dict(parent_map)
 
1496
    for node in parent_map:
 
1497
        parents = result[node]
 
1498
        if len(parents) == 1:
 
1499
            parent_children = children[parents[0]]
 
1500
            if len(parent_children) != 1:
 
1501
                # This is not the only child
 
1502
                continue
 
1503
            node_children = children[node]
 
1504
            if len(node_children) != 1:
 
1505
                continue
 
1506
            child_parents = result.get(node_children[0], None)
 
1507
            if child_parents is None:
 
1508
                import pdb; pdb.set_trace()
 
1509
            if len(child_parents) != 1:
 
1510
                # This is not its only parent
 
1511
                continue
 
1512
            assert child_parents[0] == node
 
1513
            # The child of this node only points at it, and the parent only has
 
1514
            # this as a child. remove this node, and join the others together
 
1515
            result[node_children[0]] = parents
 
1516
            children[parents[0]] = node_children
 
1517
            del result[node]
 
1518
            del children[node]
 
1519
            removed.add(node)
 
1520
 
 
1521
    return result