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 from the mobile storage rack during a delivery process in a warehouse.

Answer 1

Approach to Solve the problem
You can solve this problem in multiple ways, here are few of them.

Starting from the Source Vertex
Let us consider the above graph for demonstration purpose. Here is the steps we need to follow.

First we need to choose one of the source vertices and the obvious choice is among A and D, we choose A.
Delete all the outgoing edges from A, so we will delete (A,E) and (A,B).
Now choose among the available vertices with no incoming edges, we have D and E, we choose D here.
Delete all the outgoing edges from D, so we will delete (D,B).
Now choose among the available vertices with no incoming edges, we have E and B, we choose E here.
Delete all the outgoing edges from E, so we will delete (E,F) AND (E,G).
Now choose among the available vertices with no incoming edges, we have B and F, we choose B here.
Delete all the outgoing edges from B, so we will delete (B,C).
Now choose among the available vertices with no incoming edges, we have F, we choose F here.
Delete all the outgoing edges from F, so we will delete (F,G).
Now choose among the available vertices with no incoming edges, we have G, we choose G here.
Delete all the outgoing edges from G, so we will delete (G,C).
Now choose among the available vertices with no incoming edges, we have C, we choose C here.
Delete all the outgoing edges from C, so we will delete (C,H).
Now choose among the available vertices with no incoming edges, we have H, we choose H here.
There is no more connected vertices, hence we are done with the algorithm.
Here is an animation of the above steps which will help you understand the steps pictorially
ANIMATION

Starting from the Sink Vertex
You can perform the above set of operations from the sink vertex and arrive to one of the topological ordering by deleting the incoming edges to the sink vertex.
The approach and number of steps mostly remains the same.
Remember that the best way to delete the edges incoming or outgoing from a vertex is to delete the vertex itself.

Pseudo Code
For the purpose of the Pseudo code and the source code, we would prefer that the graph is given to us as a adjacency list, where each list contains all the nodes coming out of a given vertex. For more on Adjacency List, please refer to my tutorial on Basics of Graph Theory

Also, I would like to start from the sink as it is easier to identify all the sink vertices in an adjacency list representation.

topologicalOrdering(Graph G)
if G is NULL
return
for v in vertex set of G
if v.adjancencyList is EMPTY
Q.add(v)
while !Q.EMPTY
T <- Q.dequeue
print T
for u in vertex set of G
if u = T
u <- NULL
if u.adjacencyList contains T
u.adjacencyList.remove(T)
if u.adjacencyList is EMPTY
Q.add(u)

This is just to explain the idea behind the topological sort. We can definitely improve on the running time and get rid of inner loops to a great extent by choosing the underlying data structure carefully. May be if each vertex contains the list of vertices predecessor vertices, it will reduce the running time significantly.

Source Code
private void topologicalOrdering(List graph) {
if (graph == null)
return;
Queue topologicOrder = new ArrayDeque();
// identifying all the sink vertices
for (Vertex v : graph) {
if (v != null && v.adjacencyList == null || v.adjacencyList.size() == 0)
topologicOrder.add(v);
}
while (!topologicOrder.isEmpty()) {
Vertex currentSink = topologicOrder.remove();
System.out.print(currentSink.identifier + " ");
for (Vertex v : graph) {
if (v != null && v.equals(currentSink))
v = null;
else if (v != null && v.adjacencyList != null && v.adjacencyList.contains(currentSink)) {
v.adjacencyList.remove(currentSink);
if (v.adjacencyList.size() == 0)
topologicOrder.add(v);
}
}
}
}