Example
A topological ordering, or a topological sort, orders the vertices in a directed acyclic graph on a line, i.e. in a list, such that all directed edges go from left to right. Such an ordering cannot exist if the graph contains a directed cycle because there is no way that you can keep going right on a line and still return back to where you started from.
Formally, in a graph G = (V, E), then a linear ordering of all its
vertices is such that if G contains an edge (u, v) ∈ Efrom vertex u to vertex v then u precedes v in the ordering.
It is important to note that each DAG has at least one topological sort.
There are known algorithms for constructing a topological ordering of any DAG in linear time, one example is:
- Call
depth_first_search(G)to compute finishing timesv.ffor each vertexv - As each vertex is finished, insert it into the front of a linked list
- the linked list of vertices, as it is now sorted.
A topological sort can be performed in ϴ(V + E) time, since the
depth-first search algorithm takes ϴ(V + E) time and it takes Ω(1)
(constant time) to insert each of |V| vertices into the front of
a linked list.
Many applications use directed acyclic graphs to indicate precedences among events. We use topological sorting so that we get an ordering to process each vertex before any of its successors.
Vertices in a graph may represent tasks to be performed and the edges
may represent constraints that one task must be performed before
another; a topological ordering is a valid sequence to perform the
tasks set of tasks described in V.
Problem instance and its solution
Let a vertice v describe a Task(hours_to_complete: int), i. e. Task(4) describes a Task that takes 4 hours to complete, and an edge e describe a Cooldown(hours: int) such that Cooldown(3) describes a duration of time to cool down after a completed task.
Let our graph be called dag (since it is a directed acyclic graph), and let it contain 5 vertices:
A <- dag.add_vertex(Task(4));
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3));
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));
where we connect the vertices with directed edges such that the graph is acyclic,
// A ---> C ----+
// | | |
// v v v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));
then there are three possible topological orderings between A and E,
A -> B -> D -> EA -> C -> D -> EA -> C -> E
