Graphs: Topological Ordering

Source

Table of Contents

Beginning

# python
from functools import partial

# this project
from bowling.data_structures.graphs.depth_first_search import (
    DFSVertex,
    DepthFirstSearch,
    DirectedGraph)

Middle

underpants = DFSVertex("underpants")
pants = DFSVertex("pants")
belt = DFSVertex("belt")
socks = DFSVertex("socks")
watch = DFSVertex("watch")
shoes = DFSVertex("shoes")
shirt = DFSVertex("shirt")
tie = DFSVertex("tie")
jacket = DFSVertex("jacket")

graph = DirectedGraph()

graph.add(underpants, pants)
graph.add(underpants, shoes)
graph.add(socks, shoes)
graph.add(pants, shoes)
graph.add(pants, belt)
graph.add(shirt, belt)
graph.add(shirt, tie)
graph.add(tie, jacket)
graph.add(belt, jacket)
graph.vertices.add(watch)

search = DepthFirstSearch(graph)
search()

topologically_sorted = reversed(sorted(graph.vertices, key=lambda v: v.finished))
for node in topologically_sorted:
    predecessor = node.predecessor.identifier if node.predecessor is not None else "None"
    print(f"{node.identifier} \tfinished: {node.finished}\t predecessor: {predecessor}")

watch   finished: 18     predecessor: None
shirt   finished: 16     predecessor: None
tie     finished: 15     predecessor: shirt
socks   finished: 12     predecessor: None
underpants      finished: 10     predecessor: None
pants   finished: 9      predecessor: underpants
belt    finished: 8      predecessor: pants
jacket  finished: 7      predecessor: belt
shoes   finished: 4      predecessor: pants

This differs from the CLRS solution. The ordering depends on the order in which the edges are encountered (in this case it means the order in which the edges are added to the graph) so the sort won't always be the same. The important feature is that no item later in the list needs to come before any that precede it.