Type-Level Topological Sort in TypeScript

This challenge asks you to implement a topological sort algorithm entirely at the TypeScript type level. This means the input will be a type representing a directed acyclic graph (DAG), and the output will be a type representing a valid topological ordering of its nodes. Type-level topological sort is useful for verifying dependency orderings in code, ensuring correct build sequences, or enforcing structural constraints in complex type systems.

Problem Description

You need to create a TypeScript type, let's call it TopologicalSort<T>, which takes a type T representing a directed acyclic graph (DAG) and returns a type representing a valid topological ordering of its nodes.

The input type T will represent the graph's structure. We'll define a convention for this input type:

• T will be an object type where keys represent node names (as string literals).
• The value associated with each key will be a tuple of string literals representing the nodes that the key node depends on (its prerequisites).

For example, a node 'A' that depends on 'B' and 'C' would be represented as: { A: ['B', 'C'], ... }

A valid topological sort is a linear ordering of nodes such that for every directed edge from node u to node v, u comes before v in the ordering. Since we're working with dependencies (where a node depends on its prerequisites), this means all prerequisites of a node must appear before that node in the output tuple.

Key Requirements:

1. Type-Level Computation: All logic must be implemented using TypeScript's type inference and conditional types. No runtime JavaScript code is allowed for the sorting itself.
2. Input Format: The input T will be an object type where keys are string literals representing node names, and values are tuples of string literals representing their dependencies.
3. Output Format: The output should be a tuple of string literals representing a valid topological ordering.
4. DAG Assumption: The input graph is guaranteed to be a Directed Acyclic Graph (DAG). You do not need to handle cycles.
5. Completeness: The output tuple must contain all unique nodes present in the input graph.
6. Correctness: The ordering must be valid. For any node X appearing in the output tuple at index i, all its dependencies must appear at indices j < i.

Important Considerations:

• Node Identification: Nodes are identified by their string literal names.
• Dependency Resolution: The core of the problem is identifying nodes that have no unmet dependencies and can be added to the sorted list.

Examples

Example 1: Simple Linear Dependency

// Input graph: A depends on B, B depends on C
type Graph1 = {
  A: ['B'];
  B: ['C'];
  C: [];
};

// Expected Output: ['C', 'B', 'A']
// Explanation: C has no dependencies. Once C is placed, B has no unmet dependencies and can be placed.
// Once B is placed, A has no unmet dependencies and can be placed.

Example 2: Multiple Dependencies and Independent Nodes

// Input graph:
// D depends on B, C
// C depends on A
// B depends on A
// A depends on nothing
// E depends on nothing
type Graph2 = {
  A: [];
  B: ['A'];
  C: ['A'];
  D: ['B', 'C'];
  E: [];
};

// Expected Output (one possible valid ordering): ['A', 'E', 'B', 'C', 'D']
// Or: ['E', 'A', 'C', 'B', 'D']
// Explanation: A and E can be placed first as they have no dependencies.
// Once A is placed, B and C can be placed.
// Once B and C are placed, D can be placed.

Example 3: More Complex Dependencies

// Input graph:
// F depends on D, E
// E depends on B
// D depends on A, C
// C depends on A
// B depends on A
// A depends on nothing
type Graph3 = {
  A: [];
  B: ['A'];
  C: ['A'];
  D: ['A', 'C'];
  E: ['B'];
  F: ['D', 'E'];
};

// Expected Output (one possible valid ordering): ['A', 'B', 'C', 'E', 'D', 'F']
// Explanation: A has no dependencies and is placed first.
// Then B and C can be placed (order between B and C can vary).
// Once B is placed, E can be placed.
// Once A and C are placed, D can be placed.
// Once D and E are placed, F can be placed.

Constraints

• The input graph will always be a Directed Acyclic Graph (DAG).
• Node names are represented by string literals.
• Dependencies are represented by tuples of string literals.
• The output tuple must contain all nodes from the input graph.
• The number of nodes in the graph will not exceed 10 for practical type-checking limits in TypeScript.
• The depth of dependencies will not exceed 10.

Notes

This problem requires a recursive approach at the type level. You'll likely need helper types to:

• Extract all unique nodes from the graph.
• Determine which nodes have no unmet dependencies.
• Recursively build the sorted tuple.

Think about how to model "remaining dependencies" and how to identify nodes that are "ready" to be added to the sorted list. The key is to simulate the iterative process of topological sort within the type system. You might find it helpful to create types that can filter or transform tuples of node names.