Smallest and unique topological orders

Most directed acyclic graphs have many topological orders, so problems add a rule: return the smallest, the one that comes first when orders are compared number by number, or say whether only one order exists. Both questions turn on the moment in Kahn’s algorithm when more than one node is ready. The smallest order always takes the smallest ready node, which a min-heap hands out in O(log n) time. Unique topological orders are those in which that moment never comes: at every step exactly one node is ready.

Three problems: speakers, one order, and a ranking

Problem A: the smallest order. Speakers are numbered 0 to n − 1, and each pair (a, b) in before means that a speaks before b. Return the order that keeps every pair and comes first number by number, or [] if none does. Limits: up to 100,000 speakers and 200,000 pairs.

• smallest_order(6, [(3, 0), (4, 0), (5, 2), (2, 1)]) gives [3, 4, 0, 5, 2, 1]. Kahn’s queue gives [3, 4, 5, 0, 2, 1], which is valid but larger in the third place.
• With (1, 5) added, the pairs contain a loop: [].

Problem B: one order or several? Return the order if it is the only one, else nothing. The speakers’ pairs allow 40 orders; adding (3, 4) and (0, 5) leaves exactly one, [3, 4, 0, 5, 2, 1].

Problem C: sequence reconstruction. Referees report how some players of a tournament finished, each report a list in finishing order. Is the ranking seq of all n players the only one that keeps every report? With seq = [0, 1, 2, 3], the reports [0, 1, 3] and [1, 2, 3] say yes; [0, 1, 3] and [0, 2, 3] say no, since [0, 2, 1, 3] keeps both.

The brute force: test every order

Generate the orders of 0 to n − 1 in increasing order and test each one: the first that keeps every pair is the smallest, and counting all that do answers whether only one exists.

"""The brute force: try every order of the speakers, in increasing order, and test each against the constraints."""
from itertools import permutations


def valid(order, before):
    at = {v: i for i, v in enumerate(order)}
    return all(at[a] < at[b] for a, b in before)


def first_and_count(n, before):
    """The first valid order in increasing order, how many orders were tried to find it, and how many are valid."""
    first, tried, count = None, 0, 0
    for order in permutations(range(n)):  # permutations of 0..n-1 come out in increasing order
        if first is None:
            tried += 1
        if valid(order, before):
            count += 1
            if first is None:
                first = list(order)
    return first, tried, count


speakers = [(3, 0), (4, 0), (5, 2), (2, 1)]  # (a, b): speaker a speaks before speaker b
first, tried, count = first_and_count(6, speakers)
print(f"speakers: first valid order {first}, found after {tried} of 720 orders; {count} valid orders in all")
first, tried, count = first_and_count(6, speakers + [(3, 4), (0, 5)])
print(f"with 3 before 4 and 0 before 5 added: first {first}, {count} valid order")

print("\nTo show that only one order is valid, the brute force has to test every order:")
for n in (6, 7, 8, 9):
    first, tried, count = first_and_count(n, [(i, i + 1) for i in range(n - 1)])
    total = sum(1 for _ in permutations(range(n)))
    print(f"a chain of {n} speakers: {count} valid order among {total:,} tested")

speakers: first valid order [3, 4, 0, 5, 2, 1], found after 438 of 720 orders; 40 valid orders in all
with 3 before 4 and 0 before 5 added: first [3, 4, 0, 5, 2, 1], 1 valid order

To show that only one order is valid, the brute force has to test every order:
a chain of 6 speakers: 1 valid order among 720 tested
a chain of 7 speakers: 1 valid order among 5,040 tested
a chain of 8 speakers: 1 valid order among 40,320 tested
a chain of 9 speakers: 1 valid order among 362,880 tested

The smallest order of the speakers turns up after 438 of the 720 orders. Proving an order unique is worse, because every order must be tested: 362,880 for a chain of 9 speakers, and 20! ≈ 2.4 × 10¹⁸ for 20, while the limits allow 100,000.

What to notice

Kahn’s algorithm may take any ready node next, and all three problems are rules about that choice:

• A min-heap of ready nodes hands out the smallest one, which gives the smallest order.
• The uniqueness test stops as soon as two nodes are ready at once, so it finds unique topological orders in one run.
• Reconstruction checks that every two neighbours in the ranking appear side by side in some report.
• Putting small numbers early is a different rule: take the largest ready node of the reversed pairs.

The smallest order with a min-heap, step by step Pro: opens with a Pro, Premium or Ultimate pass