I just wrote some code for doing a topological sort in Python, given a undirected graph.
G = {
7: [11, 8],
5: [11],
3: [8, 10],
11: [2, 9],
8: [9],
2: [],
9: [],
10: []
}
class GraphException(Exception):
def __init__(self, str):
pass
def has_incoming_edges(g, a_node):
"""
Return True if it has incoming edges,
False otherwise.
"""
for each_node in g:
if a_node in g[each_node]:
return True
return False
def remove_edge(g, start, end):
"""
Removes the edge start->end in g.
"""
edges = g[start]
edges.pop(edges.index(end))
def edges_exist(g):
for each_node in g:
if g[each_node]: return True
return False
def do_topsort(g):
S = [] # list of all nodes that have no incoming nodes
L = [] # topordering
for each_node in G:
if not has_incoming_edges(g, each_node):
S.append(each_node)
while S:
a_node = S.pop(0)
print "Popping", a_node
L.append(a_node)
x = g[a_node]
#TODO NEVER ITERATE ON A LIST AND REMOVE FROM IT AT
# THE SAME TIME
backup = g[a_node]
for each_connected in backup:
print ">>>", backup
print "Removing edge", a_node, each_connected
# Remove the edge from a_node to each_connected
remove_edge(g, a_node, each_connected)
print g
if not has_incoming_edges(g, each_connected):
print "Adding", each_connected
S.append(each_connected)
if edges_exist(g):
print g
print L
raise GraphException("Graph has cycles")
return L
def main():
global G
topsort = do_topsort(G)
print topsort
if __name__ == '__main__':
main()
The output I obtain from this code is as follows :-
Popping 3
>>> [8, 10]
Removing edge 3 8
{2: [], 3: [10], 5: [11], 7: [11, 8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Popping 5
>>> [11]
Removing edge 5 11
{2: [], 3: [10], 5: [], 7: [11, 8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Popping 7
>>> [11, 8]
Removing edge 7 11
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [2, 9]}
Adding 11
Popping 11
>>> [2, 9]
Removing edge 11 2
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [9]}
Adding 2
Popping 2
{2: [], 3: [10], 5: [], 7: [8], 8: [9], 9: [], 10: [], 11: [9]}
[3, 5, 7, 11, 2]
Traceback (most recent call last):
File "topsort.py", line 80, in <module>
main()
File "topsort.py", line 76, in main
topsort = do_topsort(G)
File "topsort.py", line 71, in do_topsort
raise GraphException("Graph has cycles")
__main__.GraphException
Notice that in the output there is a line Popping 7. It indicates that 7 is the node being processed in the for loop for each_connected in backup:. We can see that 7 is connected to both 11 and 8. However, the loop seems to be running only once and removing the edge 7-11. Node 8 does not seem to be processed. What am I doing wrong?
