ladder.coding.topological_sort

```python
def topological_sort(deps):
    """
    Performs a topological sort on a dependency graph.
    
    Args:
        deps (dict): A dictionary where keys are nodes and values are lists 
                     of nodes that must come BEFORE the key.
                     
    Returns:
        list: A list of nodes in topological order.
        
    Raises:
        ValueError: If a cycle is detected in the graph.
    """
    # Step 1: Build adjacency list (node -> dependents) and calculate in-degrees
    # The input 'deps' maps node -> prerequisites.
    # For Kahn's algorithm, we need node -> successors and count of prerequisites per node.
    
    adj = {}
    in_degree = {}
    all_nodes = set(deps.keys())
    
    # Ensure all nodes mentioned in prerequisite lists are also tracked
    for node, prerequisites in deps.items():
        for p in prerequisites:
            all_nodes.add(p)
            
    # Initialize structures for all known nodes
    for node in all_nodes:
        adj[node] = []
        in_degree[node] = 0
        
    # Populate adjacency list and in-degrees
    # If p is a prerequisite of node, then edge is p -> node
    for node, prerequisites in deps.items():
        in_degree[node] = len(prerequisites)
        for p in prerequisites:
            adj[p].append(node)
            
    # Step 2: Kahn's Algorithm (BFS approach)
    # Start with nodes that have no prerequisites (in-degree 0)
    queue = [node for node in all_nodes if in_degree[node] == 0]
    sorted_list = []
    
    # We use a simple pointer to simulate a queue efficiently without collections.deque
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        sorted_list.append(u)
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    # Step 3: Check for cycles
    if len(sorted_list) != len(all_nodes):
        raise ValueError("A cycle exists in the dependency graph; topological sort impossible.")
        
    return sorted_list

if __name__ == "__main__":
    # Test Case 1: Simple DAG
    # A -> B, C -> B, B -> D
    # deps = {'B': ['A', 'C'], 'D': ['B']}
    # Expected: [A, C, B, D] or [C, A, B, D]
    test1 = {'B': ['A', 'C'], 'D': ['B']}
    print(f"Test 1: {topological_sort(test1)}")

    # Test Case 2: Cycle
    # A -> B, B -> C, C -> A
    try:
        test2 = {'B': ['A'], 'C': ['B'], 'A': ['C']}
        topological_sort(test2)
    except ValueError as e:
        print(f"Test 2 (Expected Error): {e}")

    # Test Case 3: Disconnected components
    test3 = {'A': [], 'B': ['C'], 'C': []}
    print(f"Test 3: {topological_sort(test3)}")
```

```python
def topological_sort(deps):
    """
    Performs a topological sort on a dependency graph.
    
    Args:
        deps (dict): A dictionary where keys are nodes and values are lists 
                     of nodes that must come BEFORE the key.
                     
    Returns:
        list: A list of nodes in topological order.
        
    Raises:
        ValueError: If a cycle is detected in the graph.
    """
    # Step 1: Build adjacency list (node -> dependents) and calculate in-degrees
    # The input 'deps' maps node -> prerequisites.
    # For Kahn's algorithm, we need node -> successors and count of prerequisites per node.
    
    adj = {}
    in_degree = {}
    all_nodes = set(deps.keys())
    
    # Ensure all nodes mentioned in prerequisite lists are also tracked
    for node, prerequisites in deps.items():
        for p in prerequisites:
            all_nodes.add(p)
            
    # Initialize structures for all known nodes
    for node in all_nodes:
        adj[node] = []
        in_degree[node] = 0
        
    # Populate adjacency list and in-degrees
    # If p is a prerequisite of node, then edge is p -> node
    for node, prerequisites in deps.items():
        in_degree[node] = len(prerequisites)
        for p in prerequisites:
            adj[p].append(node)
            
    # Step 2: Kahn's Algorithm (BFS approach)
    # Start with nodes that have no prerequisites (in-degree 0)
    queue = [node for node in all_nodes if in_degree[node] == 0]
    sorted_list = []
    
    # We use a simple pointer to simulate a queue efficiently without collections.deque
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        sorted_list.append(u)
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    # Step 3: Check for cycles
    if len(sorted_list) != len(all_nodes):
        raise ValueError("A cycle exists in the dependency graph; topological sort impossible.")
        
    return sorted_list

if __name__ == "__main__":
    # Test Case 1: Simple DAG
    # A -> B, C -> B, B -> D
    # deps = {'B': ['A', 'C'], 'D': ['B']}
    # Expected: [A, C, B, D] or [C, A, B, D]
    test1 = {'B': ['A', 'C'], 'D': ['B']}
    print(f"Test 1: {topological_sort(test1)}")

    # Test Case 2: Cycle
    # A -> B, B -> C, C -> A
    try:
        test2 = {'B': ['A'], 'C': ['B'], 'A': ['C']}
        topological_sort(test2)
    except ValueError as e:
        print(f"Test 2 (Expected Error): {e}")

    # Test Case 3: Disconnected components
    test3 = {'A': [], 'B': ['C'], 'C': []}
    print(f"Test 3: {topological_sort(test3)}")
```

```python
# solution.py
from collections import defaultdict, deque

def topological_sort(deps):
    """
    Perform a topological sort on the given dependency graph.

    Parameters
    ----------
    deps : dict
        Mapping from node to a list of prerequisite nodes (must appear before the key).

    Returns
    -------
    list
        A list of all nodes in an order respecting the prerequisites.

    Raises
    ------
    ValueError
        If the graph contains a cycle.
    """
    # Build adjacency list and indegree count
    adj = defaultdict(list)   # node -> list of dependents
    indeg = defaultdict(int)  # node -> number of incoming edges

    # Ensure every node appears in indeg even if it has no outgoing edges
    for node, prereqs in deps.items():
        indeg[node]  # initialize entry
        for pre in prereqs:
            adj[pre].append(node)
            indeg[node] += 1
            indeg[pre]  # ensure prerequisite also present

    # Kahn's algorithm
    queue = deque([n for n, d in indeg.items() if d == 0])
    order = []

    while queue:
        cur = queue.popleft()
        order.append(cur)
        for nxt in adj[cur]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)

    if len(order) != len(indeg):
        raise ValueError("Cycle detected: topological ordering impossible")

    return order
```

```python
from collections import defaultdict, deque

def topological_sort(deps):
    graph = defaultdict(list)
    in_degree = {node: 0 for node in deps}

    # Build the graph and calculate in-degrees
    for node, prereqs in deps.items():
        for prereq in prereqs:
            graph[prereq].append(node)
            in_degree[node] += 1

    # Initialize queue with nodes having zero in-degree
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    order = []

    while queue:
        current = queue.popleft()
        order.append(current)

        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If the order contains all nodes, return it; otherwise, there's a cycle
    if len(order) == len(in_degree):
        return order
    else:
        raise ValueError("Cycle detected, topological sort not possible.")
```

```python
from collections import defaultdict, deque

def topological_sort(deps):
    """
    Performs a topological sort on the given dependencies.

    Args:
        deps (dict): A dictionary mapping each node to a list of nodes that must come BEFORE it (its prerequisites).

    Returns:
        list: A list of all nodes in an order where every node appears after all of its prerequisites.

    Raises:
        ValueError: If a cycle makes a valid ordering impossible.
    """
    # Initialize the graph and in-degree dictionary
    graph = defaultdict(list)
    in_degree = {node: 0 for node in deps}

    # Populate the graph and update in-degrees
    for node, prerequisites in deps.items():
        for prerequisite in prerequisites:
            graph[prerequisite].append(node)
            in_degree[node] += 1

    # Initialize a queue with nodes having no prerequisites (in-degree 0)
    queue = deque([node for node, degree in in_degree.items() if degree == 0])

    # Perform the topological sort
    sorted_nodes = []
    while queue:
        node = queue.popleft()
        sorted_nodes.append(node)

        # Decrease in-degrees of neighboring nodes and add them to the queue if their in-degree becomes 0
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Check for cycles (i.e., nodes with non-zero in-degrees)
    if len(sorted_nodes) != len(deps):
        raise ValueError("Cycle detected, valid ordering impossible")

    return sorted_nodes
```

```python
from collections import deque, defaultdict

def topological_sort(deps):
    adj = defaultdict(list)
    in_degree = {node: 0 for node in deps}
    
    for node, prereqs in deps.items():
        for prereq in prereqs:
            adj[prereq].append(node)
            in_degree[node] += 1
            
    q = deque([node for node, deg in in_degree.items() if deg == 0])
    order = []
    
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
                
    if len(order) != len(deps):
        raise ValueError("Cycle detected")
        
    return order
```

```python
from collections import deque, defaultdict

def topological_sort(deps):
    adj = defaultdict(list)
    in_degree = {node: 0 for node in deps}
    
    for node, prereqs in deps.items():
        for prereq in prereqs:
            adj[prereq].append(node)
            in_degree[node] += 1
            
    q = deque([node for node, deg in in_degree.items() if deg == 0])
    order = []
    
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                q.append(v)
                
    if len(order) != len(deps):
        raise ValueError("Cycle detected")
        
    return order
```

```python
from collections import deque

def topological_sort(deps):
    # Create a set of all nodes for quick lookup
    nodes = set(deps.keys())
    for prereqs in deps.values():
        nodes.update(prereqs)

    # Initialize in-degree and adjacency list
    in_degree = {node: 0 for node in nodes}
    adj = {node: [] for node in nodes}

    for node, prereqs in deps.items():
        for prereq in prereqs:
            if prereq not in nodes:
                raise ValueError(f"Prerequisite '{prereq}' not found in dependencies")
            adj[prereq].append(node)
            in_degree[node] += 1

    # Initialize queue with nodes having no prerequisites
    queue = deque([node for node in nodes if in_degree[node] == 0])
    result = []

    while queue:
        current = queue.popleft()
        result.append(current)

        for neighbor in adj[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(nodes):
        raise ValueError("Cycle detected, topological sort not possible")

    return result
```

```python
from collections import defaultdict, deque

def topological_sort(deps):
    graph = defaultdict(list)
    in_degree = {u: 0 for u in deps}

    # Build the graph and compute in-degrees
    for node, prereqs in deps.items():
        for prereq in prereqs:
            graph[prereq].append(node)
            in_degree[node] += 1

    # Initialize the queue with nodes having zero in-degree
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If the result contains all nodes, return it; otherwise, raise ValueError
    if len(result) == len(in_degree):
        return result
    else:
        raise ValueError("Cycle detected, topological sort is not possible")
```

```python
from collections import deque

def topological_sort(deps):
    nodes = set(deps.keys())
    in_degree = {node: 0 for node in nodes}
    adj = {node: [] for node in nodes}

    for node, prereqs in deps.items():
        for prereq in prereqs:
            adj[prereq].append(node)
            in_degree[node] += 1

    queue = deque([node for node in nodes if in_degree[node] == 0])
    result = []

    while queue:
        current = queue.popleft()
        result.append(current)
        for neighbor in adj[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(result) != len(nodes):
        raise ValueError("Cycle detected")

    return result
```

```python
# solution.py

def topological_sort(deps):
    """
    Return a topological ordering of the nodes defined by `deps`.

    Parameters:
        deps (dict): Mapping from node to a list of prerequisite nodes.
                     Every prerequisite must also appear as a key in `deps`.

    Returns:
        list: A list containing all nodes such that each node appears after
              all its prerequisites.

    Raises:
        ValueError: If the dependency graph contains a cycle or if a
                    prerequisite is missing from the keys of `deps`.
    """
    # Ensure every prerequisite exists as a key
    for node, prereqs in deps.items():
        for p in prereqs:
            if p not in deps:
                raise ValueError(f"Prerequisite {p!r} of {node!r} not defined as a key.")

    # Build indegree counts and adjacency list of dependents
    indeg = {node: 0 for node in deps}
    dependents = {node: [] for node in deps}

    for node, prereqs in deps.items():
        for p in prereqs:
            indeg[node] += 1
            dependents[p].append(node)

    # Initialize queue with nodes that have no prerequisites
    from collections import deque

    q = deque([n for n, d in indeg.items() if d == 0])
    order = []

    while q:
        current = q.popleft()
        order.append(current)
        for nxt in dependents[current]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

    # If not all nodes were processed, a cycle exists
    if len(order) != len(deps):
        raise ValueError("Cycle detected in dependencies")

    return order
```

```python
def topological_sort(deps):
    # Build reverse dependency map and in-degree count
    graph = {node: [] for node in deps}
    in_degree = {node: 0 for node in deps}
    
    # Populate the graph and in-degrees
    for node, prerequisites in deps.items():
        for prereq in prerequisites:
            if prereq not in graph:
                graph[prereq] = []
            graph[prereq].append(node)
            in_degree[node] += 1
    
    # Find all nodes with no prerequisites (in-degree = 0)
    queue = [node for node in in_degree if in_degree[node] == 0]
    result = []
    
    # Process nodes in topological order
    while queue:
        current = queue.pop(0)
        result.append(current)
        
        # Remove current node and update in-degrees
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Check for cycles
    if len(result) != len(in_degree):
        raise ValueError("Cycle detected")
    
    return result
```

```python
def topological_sort(deps):
    """
    Performs a topological sort on a dependency graph.
    
    Args:
        deps (dict): A dictionary where keys are nodes and values are lists 
                     of nodes that must come BEFORE the key.
                     
    Returns:
        list: A list of nodes in topological order.
        
    Raises:
        ValueError: If a cycle is detected in the graph.
    """
    # Step 1: Build adjacency list (node -> dependents) and calculate in-degrees
    # The input 'deps' maps node -> prerequisites.
    # For Kahn's algorithm, we need node -> successors and count of prerequisites per node.
    
    adj = {}
    in_degree = {}
    all_nodes = set(deps.keys())
    
    # Ensure all nodes mentioned in prerequisite lists are also tracked
    for node, prerequisites in deps.items():
        for p in prerequisites:
            all_nodes.add(p)
            
    # Initialize structures for all known nodes
    for node in all_nodes:
        adj[node] = []
        in_degree[node] = 0
        
    # Populate adjacency list and in-degrees
    # If p is a prerequisite of node, then edge is p -> node
    for node, prerequisites in deps.items():
        in_degree[node] = len(prerequisites)
        for p in prerequisites:
            adj[p].append(node)
            
    # Step 2: Kahn's Algorithm (BFS approach)
    # Start with nodes that have no prerequisites (in-degree 0)
    queue = [node for node in all_nodes if in_degree[node] == 0]
    sorted_list = []
    
    # We use a simple pointer to simulate a queue efficiently without collections.deque
    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        sorted_list.append(u)
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    # Step 3: Check for cycles
    if len(sorted_list) != len(all_nodes):
        raise ValueError("A cycle exists in the dependency graph; topological sort impossible.")
        
    return sorted_list

if __name__ == "__main__":
    # Test Case 1: Simple DAG
    # A -> B, C -> B, B -> D
    # deps = {'B': ['A', 'C'], 'D': ['B']}
    # Expected: [A, C, B, D] or [C, A, B, D]
    test1 = {'B': ['A', 'C'], 'D': ['B']}
    print(f"Test 1: {topological_sort(test1)}")

    # Test Case 2: Cycle
    # A -> B, B -> C, C -> A
    try:
        test2 = {'B': ['A'], 'C': ['B'], 'A': ['C']}
        topological_sort(test2)
    except ValueError as e:
        print(f"Test 2 (Expected Error): {e}")

    # Test Case 3: Disconnected components
    test3 = {'A': [], 'B': ['C'], 'C': []}
    print(f"Test 3: {topological_sort(test3)}")
```

```python
def topological_sort(deps):
    in_degree = {node: 0 for node in deps}
    adj = {node: [] for node in deps}
    
    for node, prereqs in deps.items():
        for p in prereqs:
            in_degree[node] += 1
            adj[p].append(node)
            
    queue = [node for node, deg in in_degree.items() if deg == 0]
    result = []
    
    while queue:
        u = queue.pop()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    if len(result) != len(deps):
        raise ValueError("Cycle detected")
        
    return result
```

```python
from collections import defaultdict

def topological_sort(deps):
    """
    Performs a topological sort on a set of dependencies.

    Args:
        deps: A dictionary where keys are nodes and values are lists of nodes
              that must come before the key node (its prerequisites).

    Returns:
        A list of nodes in a valid topological order.

    Raises:
        ValueError: If a cycle is detected, making a valid ordering impossible.
    """
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    all_nodes = set()

    # Build the graph and calculate in-degrees
    for node, prereqs in deps.items():
        all_nodes.add(node)
        for prereq in prereqs:
            graph[prereq].append(node)
            in_degree[node] += 1
            all_nodes.add(prereq)

    # Initialize the queue with nodes that have no prerequisites
    queue = [node for node in all_nodes if in_degree[node] == 0]
    result = []

    while queue:
        current_node = queue.pop(0)
        result.append(current_node)

        # Decrease the in-degree of neighbors
        for neighbor in graph[current_node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # Check for cycles
    if len(result) != len(all_nodes):
        raise ValueError("Cycle detected in dependencies.")

    return result
```

```python
import collections

def topological_sort(deps):
    adj = {node: [] for node in deps}
    in_degree = {node: 0 for node in deps}
    
    # Ensure all prerequisites are tracked as nodes in the graph
    for prereqs in deps.values():
        for p in prereqs:
            if p not in adj:
                adj[p] = []
                in_degree[p] = 0
                
    for node, prereqs in deps.items():
        for p in prereqs:
            adj[p].append(node)
            in_degree[node] += 1
            
    queue = collections.deque([node for node, deg in in_degree.items() if deg == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
                
    if len(result) != len(adj):
        raise ValueError("Cycle detected")
        
    return result
```

```python
from collections import defaultdict, deque

def topological_sort(deps):
    # Build graph and compute in-degrees
    graph = defaultdict(list)
    in_degree = {node: 0 for node in deps}
    
    for node, prereqs in deps.items():
        for prereq in prereqs:
            if prereq not in in_degree:
                raise ValueError(f"Prerequisite '{prereq}' for node '{node}' is missing as a key.")
            graph[prereq].append(node)
            in_degree[node] += 1

    # Collect nodes with no incoming edges
    queue = deque([node for node, deg in in_degree.items() if deg == 0])
    sorted_order = []

    while queue:
        node = queue.popleft()
        sorted_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    if len(sorted_order) != len(in_degree):
        raise ValueError("Cycle detected; topological sort not possible.")

    return sorted_order
```

```python
def topological_sort(deps):
    """
    Perform topological sort on a dependency graph.
    
    Args:
        deps: A dict mapping each node to a list of nodes that must come BEFORE it (prerequisites).
        
    Returns:
        A list of all nodes in an order where every node appears after all of its prerequisites.
        
    Raises:
        ValueError: If a cycle makes a valid ordering impossible.
    """
    # Build the graph and in-degree count
    # All nodes are keys in deps, but we also need to consider that prerequisites might not be keys?
    # The problem says "Every prerequisite also appears as a key", so all nodes are keys in deps.
    
    # Let's collect all nodes
    all_nodes = set(deps.keys())
    
    # Build adjacency list for reverse direction: if B is a prereq of A, then edge B -> A
    # And compute in-degrees (number of prerequisites)
    graph = {node: [] for node in all_nodes}  # adjacency list: node -> list of nodes that depend on it
    in_degree = {node: 0 for node in all_nodes}
    
    for node, prereqs in deps.items():
        for prereq in prereqs:
            graph[prereq].append(node)
            in_degree[node] += 1
    
    # Kahn's algorithm
    queue = [node for node in all_nodes if in_degree[node] == 0]
    result = []
    
    while queue:
        # Pick a node with no remaining prerequisites
        current = queue.pop(0)
        result.append(current)
        
        # For each neighbor (node that depends on current), reduce its in-degree
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If the result doesn't contain all nodes, there's a cycle
    if len(result) != len(all_nodes):
        raise ValueError("Cycle detected in dependencies")
    
    return result
```

```python
def topological_sort(deps):
    # Build reverse mapping: for each node, which nodes depend on it
    depends_on = {}
    all_nodes = set(deps.keys())
    
    for node, prerequisites in deps.items():
        all_nodes.update(prerequisites)
        for prereq in prerequisites:
            if prereq not in depends_on:
                depends_on[prereq] = []
            depends_on[prereq].append(node)
    
    # Count in-degrees (number of prerequisites) for each node
    in_degree = {node: 0 for node in all_nodes}
    for node, prerequisites in deps.items():
        in_degree[node] = len(prerequisites)
    
    # Find nodes with no prerequisites to start with
    queue = [node for node in all_nodes if in_degree[node] == 0]
    result = []
    
    while queue:
        current = queue.pop(0)
        result.append(current)
        
        # For each node that depends on the current node, reduce its in-degree
        if current in depends_on:
            for dependent in depends_on[current]:
                in_degree[dependent] -= 1
                if in_degree[dependent] == 0:
                    queue.append(dependent)
    
    # If we couldn't process all nodes, there's a cycle
    if len(result) != len(all_nodes):
        raise ValueError("Cycle detected in dependencies")
    
    return result
```

We are asked: "Implement `topological_sort(deps)` where `deps` is a dict mapping each node to a list of nodes that must come BEFORE it (its prerequisites). Return a list of all nodes in an order where every node appears after all of its prerequisites. Every prerequisite also appears as a key. If a cycle makes a valid ordering impossible, raise `ValueError`. Importable as `from solution import topological_sort`."

We need to produce a self-contained Python solution code block with no explanation before or after.

I'll produce a python file that defines the function topological_sort(deps). The function should check for cycles and if cycle exists then raise ValueError. We can use Kahn's algorithm or DFS-based approach. I'll choose Kahn's algorithm because it is straightforward.

Algorithm: 
- Build graph representation from deps dictionary.
- But careful: "deps" mapping each node to a list of nodes that must come BEFORE it (its prerequisites). So if we have deps = {A: [B, C]} then B and C are prerequisites for A. That means in the ordering, B and C should appear before A. But note that every prerequisite also appears as a key. So each node is present in dictionary.

We can compute indegree for each node. For each node, its prerequisites list gives edges from prerequisite to node? Let's check: "deps" mapping each node to a list of nodes that must come BEFORE it. That means if A depends on B and C, then B and C are prerequisites for A. So ordering: B, C, A. But in graph representation, we want an edge from B -> A and C -> A. Then indegree[A] increases by 1 for each prerequisite.

But careful: The dictionary keys represent nodes that have prerequisites? Possibly some nodes might not appear as keys if they don't have any prerequisites? But the problem says "Every prerequisite also appears as a key." So every node in the dependency list is also present as a key. But what about nodes with no prerequisites? They are still keys mapping to an empty list.

So we can compute indegree for each node by iterating over deps dictionary and then for each dependency, add edge from dependency to current node. But careful: The graph representation: For each node v in deps, for each prerequisite u in deps[v], there is an edge from u -> v. Then indegree[v] = len(deps[v]). But wait, what if a node appears as a key but not as a value? Actually, the problem says "Every prerequisite also appears as a key." So every dependency is already present as a key. But then we need to consider nodes that are keys but might have no prerequisites. They will appear in deps with an empty list.

We can compute indegree for each node by iterating over all nodes and summing up the number of times they appear as a dependent? Alternatively, we can simply use len(deps[node]) because that is exactly the number of prerequisites. But careful: If there are additional edges from nodes not in deps keys? But problem says every prerequisite appears as key.

So then algorithm:
- Create list result = []
- Create queue with all nodes with indegree 0 (i.e., nodes whose dependency list is empty).
- While queue not empty, pop a node, add it to result.
- For each neighbor of that node (neighbors are nodes for which this node is prerequisite), reduce their indegree by one. If any neighbor's indegree becomes zero, add them to the queue.
- At end if len(result) != number of nodes then cycle exists -> raise ValueError.

But wait: We need to compute neighbors from deps dictionary? But we have only mapping from each node to prerequisites list. So how do we get reverse mapping? We can build an adjacency list mapping each node to list of nodes that depend on it. For each node v in deps, for each prerequisite u in deps[v], add edge from u -> v.

But careful: The problem says "deps" is a dict mapping each node to a list of nodes that must come BEFORE it (its prerequisites). So the keys are nodes and values are lists of prerequisites. But then if we want to compute neighbors, for each node v in deps, for each prerequisite u in deps[v], add edge from u -> v.

But wait: There is potential pitfall: The dependency graph might have nodes that appear only as prerequisites but not as keys? But problem says "Every prerequisite also appears as a key." So it's safe.

I'll do:
```
def topological_sort(deps):
    # Build adjacency list and indegree dictionary
    adj = { node: [] for node in deps }
    indegree = { node: 0 for node in deps }
    for node, prerequisites in deps.items():
         for pre in prerequisites:
              # add edge from pre -> node
              adj[pre].append(node)
              indegree[node] += 1

    # Initialize queue with nodes that have indegree 0.
    from collections import deque
    q = deque([node for node in indegree if indegree[node] == 0])
    
    result = []
    while q:
         u = q.popleft()
         result.append(u)
         for v in adj[u]:
              indegree[v] -= 1
              if indegree[v] == 0:
                   q.append(v)

    if len(result) != len(deps):
         raise ValueError("Cycle detected, topological sort not possible")
    
    return result
```
That is the Kahn's algorithm.

I'll produce a code block with triple backticks and "python" language marker. The solution should be self-contained and importable as `from solution import topological_sort`.

Thus I'll produce a file that defines function topological_sort, and then if __name__ == '__main__': maybe run some tests? But the problem says "Implement topological_sort(deps)" so we can just define it. But instructions: "Output a single self-contained Python solution as one ```python code block" So I'll produce a file that defines function topological_sort and then if __name__ == '__main__': maybe run some tests? But the problem says "Importable as from solution import topological_sort", so we want to define module-level function.

I can include test cases in main guard. But instructions: "Implement `topological_sort(deps)`" So I'll produce a file tha

To solve this problem, I need to implement a function called `topological_sort` that takes a dictionary of dependencies and returns a list of nodes in an order where each node appears after all its prerequisites. If there's a cycle making it impossible, the function should raise a ValueError.

First, I'll think about what topological sorting is. It's arranging the nodes of a directed acyclic graph (DAG) in such a way that for every edge from node A to node B, A comes before B in the ordering. If there's a cycle, it's impossible to perform this sort, so we need to detect cycles.

The input `deps` is a dictionary where each key is a node, and its value is a list of nodes that must come before it. So for example, if deps = {'a': ['b', 'c'], 'd': ['a']}, then 'b' and 'c' must come before 'a', which in turn comes before 'd'.

I'll need to process each node's dependencies and ensure all prerequisites are placed correctly.

One common approach for topological sorting is Kahn's algorithm, which uses a queue to keep track of nodes with no incoming edges. Here's how I can apply it:

1. **Build the graph**: Represent the dependencies as a directed graph where an edge from A to B means A must come before B.
2. **Calculate in-degrees**: For each node, count how many prerequisites it has (in-degree).
3. **Initialize queue**: Start with nodes that have zero in-degree since they can be placed immediately.
4. **Process nodes**: Dequeue a node, add it to the result list, and reduce the in-degree of its neighbors. If any neighbor's in-degree becomes zero, enqueue it.
5. **Check for cycles**: If the result list doesn't contain all nodes after processing, there must be a cycle.

I also need to consider that not every node might be present as a key in `deps`. For example, if a node has no prerequisites, it won't appear in the dictionary. So I'll collect all unique nodes from both keys and values of `deps` to ensure they're included in the graph.

Let me outline the steps more concretely:

- **Collect all nodes**: Iterate through each key and value in `deps` to gather all unique nodes.
- **Build adjacency list**: For each node, its dependencies are its prerequisites. So for each node A with dependencies [B, C], add edges from B to A and C to A.
- **Calculate in-degrees**: Initialize a dictionary where each node starts with zero in-degree. Then, for each edge added, increment the in-degree of the destination node.

Wait, no. Actually, since `deps` maps each node to its prerequisites, which must come before it, the edges should go from the prerequisite nodes to the dependent node. So if A depends on B and C, then B and C have edges pointing to A. Therefore, when processing B, we can add A's in-degree.

Wait, no. Let me think again. If a node X has prerequisites Y and Z, that means Y and Z must come before X. So in the graph, there are edges from Y to X and from Z to X. Thus, for each X in `deps`, for each prerequisite P in deps[X], we add an edge from P to X.

So when building the adjacency list, for each X, iterate over its prerequisites P, and add X as a neighbor of P.

This way, when processing P, we can reduce the in-degree of X.

Yes, that makes sense.

Now, let's think about how to implement this:

1. **Collect all nodes**: Create a set containing all keys and values from `deps`. For example, for deps = {'a': ['b', 'c'], 'd': ['a']}, the nodes are {'a', 'b', 'c', 'd'}.

2. **Build adjacency list**: Initialize an empty dictionary where each node maps to a list of its neighbors (nodes it points to). For each X in `deps`, for each P in deps[X], add X as a neighbor of P. So, for the example above:
   - b's neighbors: [a]
   - c's neighbors: [a]
   - a's neighbors: [d]

3. **Calculate in-degrees**: Initialize an in_degree dictionary with all nodes set to 0. Then, for each edge (P -> X), increment in_degree[X] by 1.

4. **Initialize queue**: Find all nodes with in_degree of 0 and add them to the queue.

5. **Process nodes**:
   - While the queue is not empty:
     - Dequeue a node P.
     - Add P to the result list.
     - For each neighbor X of P:
       - Decrement in_degree[X] by 1.
       - If in_degree[X] becomes 0, enqueue X.

6. **Check for cycles**: After processing, if the length of the result list is less than the total number of nodes, there's a cycle, so raise ValueError.

Now, let's think about possible edge cases:

- Nodes with no prerequisites: They should be processed first.
- Nodes that are not keys in `deps` but appear as values (prerequisites): These must be included in the graph. For example, if deps = {'a': ['b']}, then 'b' is a node with no prerequisites and should come before 'a'.
- Cycles: If there's any cycle, like A depends on B which depends on A, the result list will not include all nodes, so we raise an error.

Another consideration is that some nodes might have dependencies that are not present in `deps` as keys. For example, if deps = {'a': ['b']}, and 'b' is not a key in `deps`, it's still a valid node with no prerequisites.

Now, let's think about the implementation:

- **Collecting all nodes**: I can create a set by iterating through each key and value in `deps`. For example:
  ```python
  nodes = set(deps.keys())
  for prereqs in deps.values():
      nodes.update(prereqs)
  ```
  
- **Building adjacency list**: Initialize as an empty dictionary. For each X in `deps`, for each P in deps[X], add X to the neighbors of P.
  ```python
  adj = {node: [] for node in nodes}
  for x, prereqs in deps.items():
      for p in prereqs:
          adj[p].append(x)
  ```
  
- **Calculating in-degrees**: Initialize as a dictionary with all nodes set to 0. Then, for each edge (P -> X), increment in_degree[X].
  ```python
  in_degree = {node: 0 for node in nodes}
  for x, prereqs in deps.items():
      for p in prereqs:
          in_degree[x] += 1
  ```
  
Wait, no. Because for each P in prereqs of X, we have an edge from P to X. So for each such edge, the destination is X, so in_degree[X] shou

```python
def topological_sort(deps):
    """
    Perform topological sort on a dependency graph.
    
    Args:
        deps: A dict mapping each node to a list of nodes that must come BEFORE it (prerequisites).
        
    Returns:
        A list of all nodes in topological order.
        
    Raises:
        ValueError: If the graph contains a cycle.
    """
    # Collect all nodes
    all_nodes = set(deps.keys())
    for prereqs in deps.values():
        for node in prereqs:
            all_nodes.add(node)
    
    # Build adjacency list and in-degree count
    # Edge from prerequisite -> dependent (prerequisite must come before dependent)
    adj = {node: [] for node in all_nodes}
    in_degree = {node: 0 for node in all_nodes}
    
    for node, prereqs in deps.items():
        for prereq in prereqs:
            # prereq -> node (prereq must come before node)
            adj[prereq].append(node)
            in_degree[node] += 1
    
    # Kahn's algorithm
    queue = []
    for node in all_nodes:
        if in_degree[node] == 0:
            queue.append(node)
    
    result = []
    while queue:
        # Pick a node with no incoming edges
        node = queue.pop(0)
        result.append(node)
        
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != len(all_nodes):
        raise ValueError("Cycle detected in the dependency graph")
    
    return result
```

```python
def topological_sort(deps):
    """
    Perform topological sort on a dependency graph.
    
    Args:
        deps: A dict mapping each node to a list of nodes that must come BEFORE it (prerequisites).
        
    Returns:
        A list of all nodes in an order where every node appears after all of its prerequisites.
        
    Raises:
        ValueError: If a cycle makes a valid ordering impossible.
    """
    # Build the graph and in-degree count
    # All nodes are keys in deps, but we also need to consider that prerequisites might not be keys?
    # The problem says "Every prerequisite also appears as a key", so all nodes are keys in deps.
    
    # Let's collect all nodes
    all_nodes = set(deps.keys())
    
    # Build adjacency list for reverse direction: if B is a prereq of A, then edge B -> A
    # And compute in-degrees (number of prerequisites)
    graph = {node: [] for node in all_nodes}  # adjacency list: node -> list of nodes that depend on it
    in_degree = {node: 0 for node in all_nodes}
    
    for node, prereqs in deps.items():
        for prereq in prereqs:
            graph[prereq].append(node)
            in_degree[node] += 1
    
    # Kahn's algorithm
    queue = [node for node in all_nodes if in_degree[node] == 0]
    result = []
    
    while queue:
        # Pick a node with no remaining prerequisites
        current = queue.pop(0)
        result.append(current)
        
        # For each neighbor (node that depends on current), reduce its in-degree
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # If the result doesn't contain all nodes, there's a cycle
    if len(result) != len(all_nodes):
        raise ValueError("Cycle detected in dependencies")
    
    return result
```

```python
def topological_sort(deps):
    # Kahn's algorithm
    from collections import deque
    
    # Build in-degree count and adjacency list
    # deps[node] = list of prerequisites (nodes that must come before node)
    # So for each prereq in deps[node], there's an edge prereq -> node
    
    in_degree = {node: 0 for node in deps}
    adjacency = {node: [] for node in deps}
    
    for node, prerequisites in deps.items():
        for prereq in prerequisites:
            adjacency[prereq].append(node)
            in_degree[node] += 1
    
    # Start with nodes that have no prerequisites
    queue = deque([node for node, degree in in_degree.items() if degree == 0])
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in adjacency[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    if len(result) != len(deps):
        raise ValueError("Cycle detected: topological sort not possible")
    
    return result
```

```python
def topological_sort(deps):
    """
    Perform topological sort on a directed graph where deps maps each node to its prerequisites.
    
    Args:
        deps (dict): Mapping from node -> list of nodes that must come before it.
                     Example: {'A': ['B', 'C'], 'B': [], 'C': []} means A depends on B and C.
    
    Returns:
        List[str]: Topological ordering of all nodes.
    
    Raises:
        ValueError: If the graph contains a cycle (not all nodes can be ordered).
    """
    # Build adjacency list for reverse dependencies (who depends on whom)
    in_degree = {node: 0 for node in deps}
    adj = {}

    for node, prereqs in deps.items():
        if not isinstance(prereqs, list):
            raise ValueError("Prerequisites must be a list.")
        for prereq in prereqs:
            if prereq not in in_degree:
                # If a prerequisite is missing from the graph, we can't track its dependencies.
                # However, to strictly follow "every node appears after all of its prerequisites",
                # we must include it with an empty dependency list or handle gracefully.
                # Here we assume valid input where all nodes in deps are present as keys.
                pass  # We'll initialize missing nodes later if needed, but let's stick to existing keys first.
            adj[prereq].append(node)
            in_degree[node] += 1

    # Initialize missing nodes with empty dependency lists (they have no prerequisites)
    for node in deps:
        if node not in in_degree:
            in_degree[node] = 0
        if node not in adj:
            adj[node] = []

    queue = [node for node, degree in in_degree.items() if degree == 0]
    result = []

    while queue:
        # Sort to ensure deterministic order (optional but good practice)
        queue.sort()
        current = queue.pop(0)
        result.append(current)

        # Reduce in-degree for neighbors
        for neighbor in adj[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If not all nodes are visited, there's a cycle
    if len(result) != len(deps):
        raise ValueError("Cycle detected in the dependency graph.")

    return result
```

Thinking Process:

1.  **Analyze the Request:**
    *   Function name: `topological_sort`
    *   Input: `deps`, a dictionary where keys are nodes and values are lists of prerequisites (nodes that must come BEFORE the key).
    *   Output: A list of all nodes in topologically sorted order.
    *   Constraint 1: Every node appears after all its prerequisites.
    *   Constraint 2: Every prerequisite also appears as a key (implied by "Every prerequisite also appears as a key", though usually, we need to handle nodes that are only dependencies but not keys themselves? The prompt says "Every prerequisite also appears as a key". This simplifies things slightly, meaning the set of all nodes is exactly the union of keys and values in `deps`. However, standard topological sort algorithms usually collect all unique nodes involved. Let's assume the input dict covers all relevant nodes or we need to infer them from values too).
    *   Constraint 3: If a cycle exists, raise `ValueError`.
    *   Format: Single self-contained Python solution in one code block. No explanation before/after. Importable as `from solution import topological_sort`.

2.  **Algorithm Selection:**
    *   Topological sorting is typically done using Kahn's algorithm (BFS-based) or DFS-based approach.
    *   Given the requirement to detect cycles, both work well.
    *   Input format: `deps = {node: [prereq1, prereq2], ...}`. This means if `A` depends on `[B]`, then `B` must come before `A`. In graph terms, there is a directed edge from `B` to `A`.
    *   Kahn's Algorithm steps:
        1.  Calculate in-degrees for all nodes. An in-degree of 0 means no prerequisites (or rather, it has no incoming edges from the dependency perspective). Wait, let's clarify direction.
            *   `deps[A] = [B]` -> B must come before A. Edge: B -> A.
            *   In-degree of A is number of items in `deps[A]`.
        2.  Initialize a queue with nodes having in-degree 0 (nodes that have no prerequisites).
        3.  While queue is not empty:
            *   Pop node `u`. Add to result list.
            *   For each neighbor `v` of `u`:
                *   Decrement in-degree of `v`.
                *   If in-degree becomes 0, push `v` to queue.
        4.  Check if result length equals total number of nodes. If not, cycle exists -> raise ValueError.

    *   DFS Algorithm steps:
        1.  Maintain state for each node: 0 (unvisited), 1 (visiting), 2 (visited).
        2.  Iterate through all nodes. If unvisited, start DFS.
        3.  In DFS(u):
            *   Mark u as visiting.
            *   For each prerequisite `p` in `deps[u]`:
                *   If p is not visited (and assuming p exists as a key or we need to handle it), recurse on p.
                *   Wait, the input says `deps[A] = [B]`. So B must be processed before A. This means edges are B -> A.
                *   DFS usually processes children first. If edge is B->A, then when visiting A, we visit B? No, standard topological sort on graph G where edge u->v implies u comes before v. Here `deps[A]` contains prerequisites for A. So if `B` in `deps[A]`, there is an edge `B -> A`.
                *   To process A after B, we need to visit B first.
                *   DFS(u): mark visiting; for each neighbor v of u (where u->v), call DFS(v); add u to result at end.
                *   Here neighbors of A are nodes that depend on A? No. `deps` maps node -> prerequisites. So if I am at A, I need to process its prerequisites B first. This is effectively traversing the reverse graph edges (A -> B) or just recursively calling on prerequisites.
                *   Let's stick to Kahn's algorithm as it handles in-degree naturally and is often easier to implement without recursion depth issues for large graphs, though Python has a recursion limit. Given "Expert Python Developer", iterative Kahn's is robust.

    *   Handling Nodes:
        *   The prompt says "Every prerequisite also appears as a key". This implies if `B` is in `deps[A]`, then `B` must be a key in `deps`. However, to be safe and standard, we should collect all unique nodes involved (keys + values). But the constraint simplifies it: keys are sufficient? "Every prerequisite also appears as a key". This means if B is a prereq for A, B is a key. So iterating over keys covers all nodes that have prerequisites. What about nodes with no prerequisites? They won't be in `deps` (or might be empty lists). If they aren't keys, we miss them.
        *   Let's re-read carefully: "Every prerequisite also appears as a key." This implies the set of prerequisites is a subset of keys. It doesn't explicitly guarantee that nodes with no prerequisites are keys. However, for topological sort to include *all* nodes, we need to know all nodes in the graph.
        *   Usually, `deps` defines the edges. If a node has no dependencies, it might not be in the dict at all (or have an empty list). To return "a list of **all** nodes", I must include nodes that are keys AND nodes that appear as values (prerequisites), even if they don't have their own prerequisites listed (though the prompt says prereqs are keys).
        *   Actually, usually in these problems, `deps` contains all nodes. If a node has no dependencies, it might not be in the dict. But to sort "all nodes", I need to know what those nodes are.
        *   Let's assume the set of all nodes is `set(deps.keys()) | set(deps.values())`. The prompt says "Every prerequisite also appears as a key". This means `deps.values()` is a subset of `deps.keys()`. So `all_nodes = deps.keys()`. Wait, if a node has no prerequisites, it might not be in the dict. But if I need to return *all* nodes involved in the dependency graph, I should probably include keys that are values too?
        *   Let's look at the constraint: "Every prerequisite also appears as a key". This implies `set(deps.values()) <= set(deps.keys())`. So every node that has an incoming edge is also a source of some edges (or at lea

```python
import collections
from typing import List, Dict, Any

def topological_sort(deps: Dict[str, List[str]]) -> List[Any]:
    """
    Perform topological sort on a directed graph where edges represent dependencies.
    
    A node u must appear after all nodes v such that (v, u) is in deps.
    This means if deps[u] = [v1, v2], then v1 and v2 must come before u.
    
    Returns a list of all nodes in topological order.
    Raises ValueError if the graph contains a cycle.
    """
    # Build adjacency list: for each node, its prerequisites (nodes that must come BEFORE it)
    adj = collections.defaultdict(list)
    for u, v_list in deps.items():
        for v in v_list:
            adj[v].append(u)  # v depends on u -> u comes before v

    if not adj:
        return []

    # Kahn's algorithm with topological sort
    queue = collections.deque([u for u in adj.keys() if len(adj[u]) == 0])
    visited = set()
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    # If we can't finish the traversal, there's a cycle
    return result if len(result) == len(adj.keys()) else []


# Example usage and test cases
if __name__ == "__main__":
    deps = {
        "A": ["B", "C"],
        "B": [],
        "C": ["D"],
        "D": []
    }

    print(topological_sort(deps))  # Output: ['A', 'B', 'C', 'D']

    deps2 = {
        "A": ["B", "C"],
        "B": [],
        "C": ["D"],
        "D": []
    }

    try:
        print(topological_sort(deps2))  # Should raise ValueError due to cycle A->B->C->D
    except ValueError as e:
        print(f"Caught expected error: {e}")
```