## Friday, April 6, 2012

### Prerequisites Problem aka Task Priority with Lexicographic Order

People who are familiar with TopCoder might have run into the problem "Prerequisites". I won't rewrite the complete statement here as it is exclusive property of TopCoder, but I'll give my own definition of it.
The problem statement is relatively simple: N tasks are given; each task depends on a set of tasks that must be performed before the given one. The time required to perform a task is irrelevant and the tasks must be performed one at a time. The requirement is to sort the tasks so that all the dependencies are satisfied. In case of ties (i.e., two or more tasks could be performed at the same time), the tasks must be sorted according to a given lexicographic criterion (e.g., in alphabetical order). It's assumed that there are no conflicts between dependencies, i.e., the sorted list always exists and is unique.
By analyzing the structure of the input data, we easily recognize a directed acyclic graph (DAG) in which each task is a vertex and each edge represents a dependency of a task from another (A depends on B if and only if that there is an edge going from B to A). The requested solution is a particular topological sorting of the graph (examples of algorithms used for topological sorting are Kahn's algorithm or DFS). However, enforcing the lexicographic order to tied tasks requires complex topological sorting algorithms.
An interesting and very intuitive solution can be devised by applying the greedy strategy: always making the choice that looks best at the moment. This approach works if the problem has optimal substructure and I'll do my best to explain that it does in this case. Since there are no dependency conflicts (i.e., no cycles), there must be one or more tasks with no dependencies at all (no incoming edges). Once we found all of these tasks, we can sort them according to the lexicographic order to decide which one must be performed first. We append the first task in this sorted set to the output list. This first task will also be removed from the graph together with all its outgoing edges (i.e., the dependencies of all the other tasks from it: since this task is performed first, we can ignore all these dependencies). At this point we are left with one sub-problem that's absolutely analogous to the previous one (here's the optimal substructure!) and we can proceed to solve it as we did before, appending to the output list one task per sub-problem.
Follows a java implementation of this algorithm. There are N tasks. For simplicity, the tasks are identified by their name only. The input is composed of N strings. Each string is in the form "TASK: DEP1 DEP2 ... ", where "TASK" is the name of a task and "DEP1", "DEP2", etc. are its dependencies (there can be zero up to N-1). Each task will always appear only once as the head of the string.
`````` import java.util.Collections;
import java.util.Iterator;
import java.util.regex.Pattern;
// this array will contain the sorted tasks
int index = 0;
// create a list of tasks and populate it
// find elements with no dependency, add them to the list of
if (c.hasNoDependencies()) {
// we can remove it from the list of tasks since it will
it.remove();
}
}
Collections.sort(independentList);
// poll the first independent task and store it into the return
// array
// remove the dependencies to the task we just processed
a.removeDependency(c.toString());
}
// store the remaining tasks in the list of independent tasks into the
// output array. note that they are already properly sorted
while (!independentList.isEmpty())
}
private final Pattern splitPattern = Pattern.compile("\\s");
private String[] getTokens(String s) {
return splitPattern.split(s);
}
private final String name;
@Override
public String toString() {
return name;
}
@Override
public boolean equals(Object o) {
if (o == null)
return false;
if (this == o)
return true;
return name.equals(c.name);
}
return false;
}
String[] tokens = getTokens(c);
name = tokens.substring(0, tokens.length() - 1);
for (int i = 1; i < tokens.length; i++) {
}
}
public boolean hasNoDependencies() {
return dependencies.isEmpty();
}
public boolean removeDependency(String s) {
return dependencies.remove(s);
}