How to sort the keys of a dictionary in Python? : <p>I have a dictionary whose keys are integers, but when iterating over it I would like the integers to appear in a non-sorted order. In a simple example this seems to work with an <a href="https://docs.python.org/2/library/collections.html#collections.OrderedDict" rel="nofollow noreferrer">OrderedDict</a>:</p>

<pre><code>In [16]: d3 = OrderedDict({k: k+1 for k in [3, 2, 1]})

In [17]: for k, v in d3.items():
    ...:     print(k, v)
    ...:     
3 4
2 3
1 2
</code></pre>

<p>However, in my 'real' application this is not working as expected. I'm trying to identify the strongly connected components (SCCs) of a directed graph. In my <code>Graph</code> class, I'm in the process of writing the <code>strongly_connected_component</code> method:</p>

<pre><code>import pytest
import collections


class Node(object):
    def __init__(self):
        self.color = 'white'
        self.parent = None
        self.d = None           # Discovery time
        self.f = None           # Finishing time


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.nodes = self.initialize_nodes()
        self.adj = self.initialize_adjacency_list()

    def initialize_nodes(self, node_indices=None):
        if node_indices is None:
            node_indices = sorted(list(set(node for edge in self.edges for node in edge)))
        return collections.OrderedDict({node_index: Node() for node_index in node_indices})

    def initialize_adjacency_list(self):
        A = {node: [] for node in self.nodes}
        for edge in self.edges:
            u, v = edge
            A[u].append(v)
        return A

    def dfs(self):
        self.time = 0
        for u, node in self.nodes.items():
            if node.color == 'white':
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.time += 1
        self.nodes[u].d = self.time
        self.nodes[u].color = 'gray'
        for v in self.adj[u]:
            if self.nodes[v].color == 'white':
                self.nodes[v].parent = u
                self.dfs_visit(v)
        self.nodes[u].color = 'black'
        self.time += 1
        self.nodes[u].f = self.time

    @staticmethod
    def transpose(edges):
        return [(v,u) for (u,v) in edges]

    def strongly_connected_components(self):
        self.dfs()
        finishing_times = {u: node.f for u, node in self.nodes.items()}
        # print(finishing_times)
        self.__init__(self.transpose(self.edges))
        node_indices = sorted(finishing_times, key=self.nodes.get, reverse=True)
        # print(node_indices)
        self.nodes = self.initialize_nodes(node_indices)
        # print(self.nodes)
</code></pre>

<p>In order to verify that the <code>dfs</code> method is working, I reproduced the following example from Cormen et al., <em>Introduction to Algorithms</em>:</p>

<p><a href="https://i.stack.imgur.com/Om6KP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Om6KP.png" alt="enter image description here"></a></p>

<p>where I've replaced the node labels <em>u</em> through <em>z</em> with the numbers <code>1</code> through <code>6</code>, respectively. The following test,</p>

<pre><code>def test_dfs():
    '''This example is taken from Cormen et al., Introduction to Algorithms (3rd ed.), Figure 22.4'''
    edges = [(1,2), (1,4), (4,2), (5,4), (2,5), (3,5), (3,6), (6,6)]
    graph = Graph(edges)
    graph.dfs()

    print("\n")
    for index, node in graph.nodes.items():
        print index, node.__dict__
</code></pre>

<p>prints</p>

<pre><code>1 {'color': 'black', 'd': 1, 'parent': None, 'f': 8}
2 {'color': 'black', 'd': 2, 'parent': 1, 'f': 7}
3 {'color': 'black', 'd': 9, 'parent': None, 'f': 12}
4 {'color': 'black', 'd': 4, 'parent': 5, 'f': 5}
5 {'color': 'black', 'd': 3, 'parent': 2, 'f': 6}
6 {'color': 'black', 'd': 10, 'parent': 3, 'f': 11}
</code></pre>

<p>which is readily seen to correspond with Figure 22.4(p) from the book. In order to compute the SCCs, I have to implement the following pseudocode:</p>

<p><a href="https://i.stack.imgur.com/4BBaP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4BBaP.png" alt="enter image description here"></a></p>

<p>In my <code>strongly_connected_components</code> method, I order the <code>node_indices</code> by finishing time in reverse order. Since it is initialized as an <code>OrderedDict</code> in the <code>initialize_nodes</code> methods, I would expect the following test to pass:</p>

<pre><code>def test_strongly_connected_components():
    edges = [(1,2), (1,4), (4,2), (5,4), (2,5), (3,5), (3,6), (6,6)]
    graph = Graph(edges)
    graph.strongly_connected_components()
    assert graph.nodes.keys() == [3, 2, 1, 4, 6, 5]


if __name__ == "__main__":
    pytest.main([__file__, "-s"])
</code></pre>

<p>since <code>[3, 2, 1, 4, 6, 5]</code> is the reverse order in which the nodes were 'finished' in the depth-first search. However, this test fails:</p>

<pre><code>=================================== FAILURES ===================================
______________________ test_strongly_connected_components ______________________

    def test_strongly_connected_components():
        edges = [(1,2), (1,4), (4,2), (5,4), (2,5), (3,5), (3,6), (6,6)]
        graph = Graph(edges)
        graph.strongly_connected_components()
&gt;       assert graph.nodes.keys() == [3, 2, 1, 4, 6, 5]
E    assert [1, 2, 3, 4, 5, 6] == [3, 2, 1, 4, 6, 5]
E      At index 0 diff: 1 != 3
E      Use -v to get the full diff

scc.py:94: AssertionError
</code></pre>

<p>Why do the keys not remain in the order specified in the initialization of the <code>OrderedDict</code>?</p>
