Ok, so in topological sorting depending on the input data, there's usually multiple correct solutions for which order the graph can be "processed" so that all dependencies come before nodes that are "dependent" on them. However, I'm looking for a slightly different answer:
Suppose the following data:
a -> b and c -> d (a must come before b and c must come before d).
With just these two constraints we have multiple candidate solutions: (a b c d, a c d b, c a b d, etc). However, I'm looking to create a method of "grouping" these nodes so that after the processing of a group, all of the entries in the next group have their dependencies taken care of. For the above supposed data I'd be looking for a grouping like (a, c) (b, d). Within each group it doesn't matter which order the nodes are processed (a before c or b before d, etc and vice versa) just so long as group 1 (a, c) completes before any of group 2 (b, d) are processed.
The only additional catch would be that each node should be in the earliest group possible. Consider the following:
a -> b -> c
d -> e -> f
x -> y
A grouping scheme of (a, d) (b, e, x) (c, f, y) would technically be correct because x is before y, a more optimal solution would be (a, d, x) (b, e, y) (c, f) because having x in group 2 implies that x was dependent on some node in group 1.
Any ideas on how to go about doing this?
EDIT: I think I managed to slap together some solution code. Thanks to all those who helped!
// Topological sort
// Accepts: 2d graph where a [0 = no edge; non-0 = edge]
// Returns: 1d array where ea