def order_upgrades(self, upgrades, history=None):
        """Order upgrades according to their dependencies.

        (topological sort using
        Kahn's algorithm - http://en.wikipedia.org/wiki/Topological_sorting).

        :param upgrades: Dict of upgrades
        :param history: Dict of applied upgrades
        """
        history = history or {}
        graph_incoming, graph_outgoing = self._create_graph(upgrades, history)

        # Removed already applied upgrades (assumes all dependencies prior to
        # this upgrade has been applied).
        for node_id in six.iterkeys(history):
            start_nodes = [node_id, ]
            while start_nodes:
                node = start_nodes.pop()
                # Remove from direct dependents
                try:
                    for d in graph_outgoing[node]:
                        graph_incoming[d] = [x for x in graph_incoming[d]
                                             if x != node]
                except KeyError:
                    warnings.warn("Ghost upgrade %s detected" % node)

                # Remove all prior dependencies
                if node in graph_incoming:
                    # Get dependencies, remove node, and recursively
                    # remove all dependencies.
                    depends_on = graph_incoming[node]

                    # Add dependencies to check
                    for d in depends_on:
                        graph_outgoing[d] = [x for x in graph_outgoing[d]
                                             if x != node]
                        start_nodes.append(d)

                    del graph_incoming[node]

        # Check for missing dependencies
        for node_id, depends_on in six.iteritems(graph_incoming):
            for d in depends_on:
                if d not in graph_incoming:
                    raise RuntimeError("Upgrade %s depends on an unknown"
                                       " upgrade %s" % (node_id, d))

        # Nodes with no incoming edges
        start_nodes = [x for x in six.iterkeys(graph_incoming)
                       if len(graph_incoming[x]) == 0]
        topo_order = []

        while start_nodes:
            # Append node_n to list (it has no incoming edges)
            node_n = start_nodes.pop()
            topo_order.append(node_n)

            # For each node m with and edge from n to m
            for node_m in graph_outgoing[node_n]:
                # Remove the edge n to m
                graph_incoming[node_m] = [x for x in graph_incoming[node_m]
                                          if x != node_n]
                # If m has no incoming edges, add it to start_nodes.
                if not graph_incoming[node_m]:
                    start_nodes.append(node_m)

        for node, edges in six.iteritems(graph_incoming):
            if edges:
                raise RuntimeError("The upgrades have at least one cyclic "
                                   "dependency involving %s." % node)

        return map(lambda x: upgrades[x], topo_order)
Order upgrades according to their dependencies.

        (topological sort using
        Kahn's algorithm - http://en.wikipedia.org/wiki/Topological_sorting).

        :param upgrades: Dict of upgrades
        :param history: Dict of applied upgrades