Introduction

A plain topological sort orders items so every prerequisite appears before the item that depends on it. The grouped version adds another rule: items belonging to the same group should appear together, or at least respect a group-level ordering as well. That turns one DAG problem into two related DAGs that have to stay consistent.

Why Grouping Changes the Problem

In an ordinary DAG, each node is independent except for edges. Grouping introduces structure above the node level. For example, tasks may belong to teams, build steps may belong to modules, or lessons may belong to chapters.

If the requirement is that grouped items stay contiguous, then you cannot simply topologically sort all items and hope for a good result. Dependencies can cross group boundaries, so you need a strategy that orders groups first and items second.

A useful mental model is:

• Build an item graph for dependencies between individual items.
• Build a group graph for dependencies induced by cross-group edges.
• Topologically sort the groups.
• Within each group, topologically sort that group's items.

This is the core idea behind many accepted solutions to grouped-ordering problems.

Two-Level Topological Sort

Suppose item a in group G1 must come before item b in group G2. That single edge implies both:

• 'a must precede b in the item graph.'
• 'G1 must precede G2 in the group graph.'

Once you compute indegrees for both layers, Kahn's algorithm works well.

1from collections import defaultdict, deque
2
3
4def topo(nodes, edges):
5    graph = defaultdict(list)
6    indegree = {node: 0 for node in nodes}
7
8    for u, v in edges:
9        graph[u].append(v)
10        indegree[v] += 1
11
12    queue = deque([node for node in nodes if indegree[node] == 0])
13    order = []
14
15    while queue:
16        node = queue.popleft()
17        order.append(node)
18        for nxt in graph[node]:
19            indegree[nxt] -= 1
20            if indegree[nxt] == 0:
21                queue.append(nxt)
22
23    return order if len(order) == len(nodes) else None

The helper returns None if a cycle exists.

A Grouped Example

The next example keeps groups contiguous. Each item belongs to a group, and before_items[i] lists prerequisites for item i.

1from collections import defaultdict
2
3
4def grouped_topo_sort(n, group, before_items):
5    next_group_id = max(group) + 1 if group else 0
6
7    for i in range(n):
8        if group[i] == -1:
9            group[i] = next_group_id
10            next_group_id += 1
11
12    item_nodes = list(range(n))
13    group_nodes = list(range(next_group_id))
14    item_edges = []
15    group_edges = set()
16    items_in_group = defaultdict(list)
17
18    for item, grp in enumerate(group):
19        items_in_group[grp].append(item)
20
21    for item in range(n):
22        for prev in before_items[item]:
23            item_edges.append((prev, item))
24            if group[prev] != group[item]:
25                group_edges.add((group[prev], group[item]))
26
27    group_order = topo(group_nodes, list(group_edges))
28    if group_order is None:
29        return None
30
31    item_order = topo(item_nodes, item_edges)
32    if item_order is None:
33        return None
34
35    ordered_items_by_group = defaultdict(list)
36    for item in item_order:
37        ordered_items_by_group[group[item]].append(item)
38
39    result = []
40    for grp in group_order:
41        result.extend(ordered_items_by_group[grp])
42    return result
43
44
45n = 8
46group = [0, 0, 1, 1, -1, 2, 2, -1]
47before_items = [[], [0], [1], [2], [1], [3], [5], [4, 6]]
48print(grouped_topo_sort(n, group, before_items))

Ungrouped items are assigned unique synthetic groups so the algorithm can treat everything uniformly.

When This Approach Works

This two-level approach works when the grouping rule is hierarchical: every item belongs to exactly one group, and the goal is to order groups plus the items within them. It is especially useful for package builds, deployment phases, curriculum ordering, and batch jobs.

It is less suitable when items may belong to multiple groups or when the grouping rule is soft rather than strict. In those cases, you are solving a different optimization problem, not just a DAG ordering problem.

Detecting Impossible Inputs

A grouped topological sort can fail for two independent reasons.

First, the item graph may contain a cycle, such as a -> b -> c -> a. Second, the group graph may contain a cycle induced by cross-group prerequisites even if no single group contains a cycle internally.

That is why checking only one graph is not enough. You must validate both layers.

Common Pitfalls

The biggest mistake is to topologically sort items once and then try to rearrange the result into groups afterward. That can silently break dependency constraints.

Another common bug is forgetting to create synthetic groups for ungrouped items. Leaving them all in a single placeholder bucket can force unrelated nodes together and create false constraints.

It is also easy to double-count cross-group edges. Using a set for group edges prevents inflated indegrees and avoids incorrect cycle detection.

Summary

• Grouped topological sort is usually a two-level DAG problem.
• Cross-group item edges imply dependencies in the group graph.
• Kahn's algorithm works well for both item and group ordering.
• Assign unique groups to ungrouped items if contiguity matters.
• Validate both the item graph and the group graph for cycles.