I've been trying to build a schedule generator for my school using topological sort, but am stuck dealing with classes that have prerequisites that can be taken concurrently. I was wondering if there was any clever way to modify topological sort to deal with these concurrent classes? For example, an intro to CS course can either be taken before a Data Structures course or at the same time as a Data Structures course. I'm trying to include the case where they are taken together.

CodePudding user response：

You could create a dummy node, combining the two courses together (assuming each course has low number of concurrent courses at most, as you will likely need all combination of them... Should work just fine if you have only one or two concurrent courses)

The prerequisites of the combined node will be the combined prerequisites of both courses, and all courses that have any prerequisite of one of these will have the dummy node as well.

As postprocessing, once topological sort has ended, you can cleanup the redundancies, and split dummy nodes back to the original courses.

That said, note that topological sort doesn't guarantee you to actually use this dummy node - even if it's possible, before using the original nodes. So there is no guarantee it will actually be used, unless you tie break in favor of them when possible.

CodePudding user response：

Can't mathematically guarantee it's correctness, but this slight modification should work.

Use the normal topological sorting with one difference. Assign all possible beginning nodes a value of 0. For each node that is queued, assign it value of parent node's value 1. That way, all nodes at a given value would ideally be parallel and can be picked together.

CodePudding user response：

Kahn's algorithm for topological sorting naturally produces a minimum length schedule with concurrency:

1. Make a dependency graph of all your courses
2. Select all courses with no dependencies. These can be taken concurrently.
3. Remove the selected courses from the graph.
4. If the graph is not empty, go back to (2)

Of course, students are limited in the number of courses they can take simultaneously, and the problem gets tricky when you also impose a limit on maximum concurrency. Deciding the best courses to take first, when too many courses are available, is an NP-hard problem. There are some heuristics you can try, though, like deferring the jobs with the shortest dependant depth.

CodePudding user response：

If you think about exactly what you want as output, it might clear out. For instance, if your desired output is a potential list of what courses to take which semester, then each vertex involved in the topological sort could be “course X on semester Y” rather than just “course X”. Then you'd get these edges, among many others:

• intro to CS on semester 1 → data structures on semester 1
• intro to CS on semester 1 → data structures on semester 2

This graph would be larger than if the vertices are just courses of course: the number of vertices is now the number of courses times the maximum number of semesters in your education. But in a realistic setting, it appears to me that it wouldn't be too much to handle.