Compute Effective Letter Permissions in a DAG

Problem Statement

In an access control system represented by a Directed Acyclic Graph (DAG), nodes represent security principals or resources, and directed edges (u, v) indicate that v is a descendant of u (i.e., v inherits access privileges from u).

Each node may define:

• Explicit allows: A set of lowercase English letters representing permissions granted at this node.
• Explicit disallows: A set of lowercase English letters representing permissions denied locally at this node.

Inheritance and Permission Rules

1. Propagation of Allows: A permission letter c is available to node v if c is explicitly allowed by v itself or by any of v's ancestors.
2. Local Disallows: An explicit disallow on a node v removes that letter from v's effective permissions. Disallow settings are strictly local—they do not propagate to descendants and do not prevent descendants from inheriting the permission from ancestors.
3. Effective Permissions: For any node v, its effective permissions are the set of letters available to v (via inheritance or its own explicit allows) minus v's explicit disallows.

Write a function to return the effective permissions for all nodes. The result must be a list of (node, permissions) pairs sorted lexicographically by node, with each permissions string sorted alphabetically.

Function Signature

def compute_effective_permissions(
    nodes: list[str],
    edges: list[tuple[str, str]],
    allows: dict[str, str],
    disallows: dict[str, str]
) -> list[tuple[str, str]]:
    pass

Input and Output Format

• Input:
  • nodes: A list of unique strings representing node identifiers.
  • edges: A list of pairs (u, v) representing a directed edge from parent u to child v.
  • allows: A dictionary mapping node IDs to strings of unique lowercase letters ('a'-'z'). If a node is missing from the dictionary, it has no explicit allows.
  • disallows: A dictionary mapping node IDs to strings of unique lowercase letters ('a'-'z'). If a node is missing, it has no explicit disallows.
• Output:
  • A list of tuples (node_id, effective_permissions) where effective_permissions is a string of sorted unique lowercase letters.
  • The list must be sorted in ascending lexicographical order by node_id.

Constraints

• 1 <= len(nodes) <= 10^4
• 0 <= len(edges) <= 2 * 10^4
• Node IDs are non-empty alphanumeric strings.
• The given graph is guaranteed to be a Directed Acyclic Graph (DAG).
• All permission characters are lowercase English letters ('a' to 'z').

Examples

Example 1

nodes = ["A", "B", "C"]
edges = [("A", "B"), ("B", "C")]
allows = {"A": "rw", "B": "x"}
disallows = {"B": "w"}

# Output:
# [("A", "rw"), ("B", "rx"), ("C", "rwx")]

Explanation:

• A: Inherits nothing. Allows 'r', 'w'. No disallow. Effective: "rw".
• B: Inherits 'r', 'w' from A; explicitly allows 'x'. Disallows 'w'. Effective: {'r', 'w', 'x'} - {'w'} = {'r', 'x'} -> "rx".
• C: Inherits 'r', 'w' from ancestor A, and 'x' from ancestor B. B's disallow of 'w' is local and does not affect C. Effective: "rwx".

Example 2

nodes = ["U", "V", "W"]
edges = [("U", "W"), ("V", "W")]
allows = {"U": "a", "V": "b", "W": "c"}
disallows = {"W": "b"}

# Output:
# [("U", "a"), ("V", "b"), ("W", "ac")]

Explanation:

• W has two parents: U and V. It inherits 'a' and 'b', and allows 'c'. Since W locally disallows 'b', its effective set is {'a', 'c'} -> "ac".