Question

Using the data structure concept of topological ordering, demonstrate using pseudocode (please don't provide the actual codings) how you can implement an operation to schedule picking during a delivery process in a warehouse.

Answer 1

Topological order can only be done on directed acyclic graph(DAG) where if directed edge (u,v) exist in graph G then vertex u will always come before vertex v in topological order.

Thus topological order gives an order of executing tasks by representing the tasks as directed graph with vertices represent task and edge represent task dependency and then perform the task as per topological order in which dependency is taken care by first performing independent tasks before dependent task.

Below is the pseudocode of using topological sort on delivery process.

SCHEDULE_ORDER(H,n) //H is the list of spot of picking and n is size of list

1. From task list (H,n) create a directed graph G(V,E) with vertices representing picking spot and directed edge (u,v) is created if spot u has to be covered before spot v.

//Now we will do topological sort as follows

2. Perfrom Depth-First-Search(DFS) on G and record the start and finish time of visiting vertices in G.

3. Now sort the vertices in G based on decreasing order of finish time, which is the required topological order.

4. If there is edge(u,v) such that finish_time(u) < finish_time(v) then this means graph G contains cycle and hence topological order does not exist.

5. Otherwise perform the task as per the topological order.

Thus topological order is obtain by performing DFS and then order the vertices in descending value of finish_time of visiting vertices.

Please comment for any clarification .