- Sometimes graphs represent a list of tasks, with the edges representing a dependency
- Look the first graph in the supplement
- This represents the way someone gets dressed (not me, I don't use ties or jackets, and soon perhaps not socks!)
- You need to put your pants on before your shoes
- And it doesn't matter when you put your watch on.
- We can use Topological Sort to produce such an ordering.
- It is important that there are no directed cycles (a->b->c->a)
- The topological sort can not be done in this case.
- The DFS will produce the DFS tree that has no cycles.
- The first idea is to use Depth-First-Search to form the DFS graph.
- We can then use the finish time to determine the tasks that must be done first.
-
TOPLOGICAL-SORT(G)
- call DFS(G)
- As each vertex finishes, insert it into a list L
- Return L
-
- Graphviz again
digraph G {
TIME [label=<TIME: 0>, shape="box"]
L[label="L: ", shape="BOX"]
undershorts[label=<undershorts<br/>0/0> style="filled", color="lightblue" ]
pants[label=<pants<br/>0/0> style="filled", color="lightblue" ]
socks[label=<socks<br/>0/0> style="filled", color="lightblue" ]
watch[label=<watch<br/>0/0> style="filled", color="lightblue" ]
shoes[label=<shoes<br/>0/0> style="filled", color="lightblue" ]
shirt[label=<shirt<br/>0/0> style="filled", color="lightblue" ]
belt[label=<belt<br/>0/0> style="filled", color="lightblue" ]
tie[label=<tie<br/>0/0> style="filled", color="lightblue" ]
jacket[label=<jacket<br/>0/0> style="filled", color="lightblue" ]
undershorts->pants
undershorts->shoes
pants->shoes
pants->belt
belt->jacket
shirt->belt
shirt->tie
tie->jacket
socks->shoes
watch
// pants->undershorts [color=red]
}
- Or finished:
digraph G {
// start with shirt
undershorts[label=<undershorts<br/>11/16> style="filled", color="grey" ]
pants[label=<pants<br/>12/15> style="filled", color="grey" ]
socks[label=<socks<br/>17/18> style="filled", color="grey" ]
watch[label=<watch<br/>9/10> style="filled", color="grey" ]
shoes[label=<shoes<br/>13/14> style="filled", color="grey" ]
shirt[label=<shirt<br/>1/8> style="filled", color="grey" ]
belt[label=<belt<br/>6/7> style="filled", color="grey" ]
tie[label=<tie<br/>2/5> style="filled", color="grey" ]
jacket[label=<jacket<br/>3/4> style="filled", color="grey" ]
TIME [label=<TIME: 18>, shape="box"]
L[label="L: socks undershorts pants shoes watch shirt belt tie jacket", shape="BOX"]
undershorts->pants
undershorts->shoes
pants->shoes
pants->belt
belt->jacket
shirt->belt
shirt->tie
tie->jacket
socks->shoes
watch
// pants->undershorts [color=red]
}
- Wikipedia has a second one:
Kahn's algorithm, 1962
KHAN-TOPO(G)
- L ← {} // an empty list
- // make S the set of all vertexes with no incoming edges
- S ← {v | v ∈ G.V and there is no e = (x,v) ∈ G.E}
- While S is not empty do
- remove a node n from S
- add n to L
- for v ∈ Adj(n)
- remove (v,n) from G
- if v has no other incoming edges
- insert m into S
- If G.V ≠ {}
- return error (the graph has a cycle)
- else
- return l