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 OrderedDict:
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
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 Graph class, I'm in the process of writing the strongly_connected_component method:
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)
In order to verify that the dfs method is working, I reproduced the following example from Cormen et al., Introduction to Algorithms:
where I've replaced the node labels u through z with the numbers 1 through 6, respectively. The following test,
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__
prints
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}
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:
In my strongly_connected_components method, I order the node_indices by finishing time in reverse order. Since it is initialized as an OrderedDict in the initialize_nodes methods, I would expect the following test to pass:
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"])
since [3, 2, 1, 4, 6, 5] is the reverse order in which the nodes were 'finished' in the depth-first search. However, this test fails:
=================================== 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()
> 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
Why do the keys not remain in the order specified in the initialization of the OrderedDict?
