def order_upgrades(self, upgrades, history=None):
        history = history or {}
        graph_incoming, graph_outgoing = self._create_graph(upgrades, history)
        for node_id in six.iterkeys(history):
            start_nodes = [node_id, ]
            while start_nodes:
                node = start_nodes.pop()
                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)
                if node in graph_incoming:
                    depends_on = graph_incoming[node]
                    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]
        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))
        start_nodes = [x for x in six.iterkeys(graph_incoming)
                       if len(graph_incoming[x]) == 0]
        topo_order = []
        while start_nodes:
            node_n = start_nodes.pop()
            topo_order.append(node_n)
            for node_m in graph_outgoing[node_n]:
                graph_incoming[node_m] = [x for x in graph_incoming[node_m]
                                          if x != node_n]
                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)