← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2009-08-13 21:30:07 UTC
  • mfrom: (4577.3.2 1.18-topo_sort)
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090813213007-4wqkou02fo0tegay
Bring in the optimized tsort code.

It turns out we needed a way to detect that there was graph cycles.
The easiest way to do it, is by noticing that we end up with a node
that has no gdfo. That means it has a parent that was not reached
before the child was reached, when walking from nodes with no known parents.
I'm 90% sure that this is correct, but arguably it should be detected
when creating the KnownGraph, and not during topo_sort.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_pyx.pyx
45
45
    void Py_INCREF(object)
46
46
 
47
47
 
48
 
from bzrlib import revision
 
48
from bzrlib import errors, revision
49
49
 
50
50
cdef object NULL_REVISION
51
51
NULL_REVISION = revision.NULL_REVISION
52
52
 
53
53
 
 
54
def topo_sort(graph):
 
55
    cdef Py_ssize_t last_tip, pos
 
56
    cdef PyObject *temp_key, *temp_value
 
57
 
 
58
    graph = dict(graph)
 
59
    # this is the stack storing on which the sorted nodes are pushed.
 
60
    node_name_stack = []
 
61
 
 
62
    # count the number of children for every node in the graph
 
63
    num_children = dict.fromkeys(graph.iterkeys(), 0)
 
64
    pos = 0
 
65
    while PyDict_Next(graph, &pos, NULL, &temp_value):
 
66
        parents = <object>temp_value
 
67
        for parent in parents: # pretty sure this is a tuple
 
68
            temp_value = PyDict_GetItem(num_children, parent)
 
69
            if temp_value != NULL: # Ignore ghosts
 
70
                n = (<object>temp_value) + 1
 
71
                PyDict_SetItem(num_children, parent, n)
 
72
    # keep track of nodes without children in a separate list
 
73
    tips = []
 
74
    pos = 0
 
75
    while PyDict_Next(num_children, &pos, &temp_key, &temp_value):
 
76
        value = <object>temp_value
 
77
        if value == 0:
 
78
            node_name = <object>temp_key
 
79
            PyList_Append(tips, node_name)
 
80
 
 
81
    graph_pop = graph.pop
 
82
    last_tip = len(tips) - 1
 
83
    while last_tip >= 0:
 
84
        # pick a node without a child and add it to the stack.
 
85
        temp_key = PyList_GET_ITEM(tips, last_tip)
 
86
        node_name = <object>temp_key
 
87
        last_tip -= 1
 
88
        PyList_Append(node_name_stack, node_name)
 
89
 
 
90
        # the parents of the node lose it as a child; if it was the last
 
91
        # child, add the parent to the list of childless nodes.
 
92
        parents = graph_pop(node_name)
 
93
        for parent in parents:
 
94
            temp_value = PyDict_GetItem(num_children, parent)
 
95
            if temp_value == NULL:
 
96
                # Ghost parent, skip it
 
97
                continue
 
98
            n = (<object>temp_value) - 1
 
99
            PyDict_SetItem(num_children, parent, n)
 
100
            if n == 0:
 
101
                last_tip += 1
 
102
                if PyList_GET_SIZE(tips) > last_tip:
 
103
                    Py_INCREF(parent)
 
104
                    PyList_SetItem(tips, last_tip, parent)
 
105
                else:
 
106
                    PyList_Append(tips, parent)
 
107
 
 
108
    # if there are still nodes left in the graph,
 
109
    # that means that there is a cycle
 
110
    if graph:
 
111
        raise errors.GraphCycleError(graph)
 
112
 
 
113
    # the nodes where pushed on the stack child first, so this list needs to be
 
114
    # reversed before returning it.
 
115
    node_name_stack.reverse()
 
116
    return node_name_stack
 
117
 
 
118
 
54
119
cdef class _KnownGraphNode:
55
120
    """Represents a single object in the known graph."""
56
121
 
337
402
        return heads
338
403
 
339
404
    def topo_sort(self):
340
 
        cdef _KnownGraphNode node, parent
341
 
        from bzrlib import tsort
342
 
        as_parent_map = {}
343
 
        for node in self._nodes.itervalues():
344
 
            if node.parents is None:
345
 
                continue
346
 
            parent_keys = []
347
 
            for parent in node.parents:
348
 
                parent_keys.append(parent.key)
349
 
            as_parent_map[node.key] = parent_keys
350
 
        return tsort.topo_sort(as_parent_map)
 
405
        """Return the nodes in topological order.
 
406
 
 
407
        All parents must occur before all children.
 
408
        """
 
409
        # This is, for the most part, the same iteration order that we used for
 
410
        # _find_gdfo, consider finding a way to remove the duplication
 
411
        # In general, we find the 'tails' (nodes with no parents), and then
 
412
        # walk to the children. For children that have all of their parents
 
413
        # yielded, we queue up the child to be yielded as well.
 
414
        cdef _KnownGraphNode node
 
415
        cdef _KnownGraphNode child
 
416
        cdef PyObject *temp
 
417
        cdef Py_ssize_t pos
 
418
        cdef int replace
 
419
        cdef Py_ssize_t last_item
 
420
 
 
421
        pending = self._find_tails()
 
422
        if PyList_GET_SIZE(pending) == 0 and len(self._nodes) > 0:
 
423
            raise errors.GraphCycleError(self._nodes)
 
424
 
 
425
        topo_order = []
 
426
 
 
427
        last_item = PyList_GET_SIZE(pending) - 1
 
428
        while last_item >= 0:
 
429
            # Avoid pop followed by push, instead, peek, and replace
 
430
            # timing shows this is 930ms => 770ms for OOo
 
431
            node = _get_list_node(pending, last_item)
 
432
            last_item = last_item - 1
 
433
            if node.parents is not None:
 
434
                # We don't include ghost parents
 
435
                PyList_Append(topo_order, node.key)
 
436
            for pos from 0 <= pos < PyList_GET_SIZE(node.children):
 
437
                child = _get_list_node(node.children, pos)
 
438
                if child.gdfo == -1:
 
439
                    # We know we have a graph cycle because a node has a parent
 
440
                    # which we couldn't find
 
441
                    raise errors.GraphCycleError(self._nodes)
 
442
                child.seen = child.seen + 1
 
443
                if child.seen == PyTuple_GET_SIZE(child.parents):
 
444
                    # All parents of this child have been yielded, queue this
 
445
                    # one to be yielded as well
 
446
                    last_item = last_item + 1
 
447
                    if last_item < PyList_GET_SIZE(pending):
 
448
                        Py_INCREF(child) # SetItem steals a ref
 
449
                        PyList_SetItem(pending, last_item, child)
 
450
                    else:
 
451
                        PyList_Append(pending, child)
 
452
                    # We have queued this node, we don't need to track it
 
453
                    # anymore
 
454
                    child.seen = 0
 
455
        # We started from the parents, so we don't need to do anymore work
 
456
        return topo_order