Compute trigger counts in a DAG

You are given a directed acyclic graph (DAG) that represents trigger dependencies between tasks.

• Each node represents a task.
• There is exactly one entry node.
• When a node is triggered once, it immediately triggers each of its outgoing neighbors once.
• A node may have multiple incoming edges; its total trigger count is the sum of triggers from all its parents.
• The entry node is triggered exactly once initially.

Your job is to compute how many times each node is triggered.

Input

• A list of directed edges edges, where each edge is a pair (u, v) meaning there is an edge u -> v.
• A designated entry node ID.
• You may assume:
  • The graph is acyclic.
  • All nodes that appear in edges are valid nodes.
  • Node IDs can be strings or integers (you can pick a representation and document it).

Example:

• Nodes: A, B, C, D, E, F
• Edges:
  • A -> B
  • B -> C
  • B -> D
  • C -> D
  • D -> E
  • D -> F
  • E -> F
• Entry node: A

Trigger propagation:

• A is triggered once (given).
• B is triggered once (from A).
• C is triggered once (from B).
• D is triggered twice (once from B, once from C).
• E is triggered twice (both from D).
• F is triggered four times (twice from D, twice from E).

So the result is something equivalent to:

A: 1
B: 1
C: 1
D: 2
E: 2
F: 4

Task

Implement a function in Python with a signature such as:

def count_triggers(edges, entry):
    """Return a mapping from node to its trigger count."""

The function should:

• Validate that all reachable nodes from entry are handled.
• Run efficiently for graphs with up to around 10^5 nodes and 10^5 edges.

You may assume there are no cycles in the input graph.

Compute Trigger Counts in a DAG

Constraints

• 0 <= len(edges) <= 10^5
• The graph is acyclic
• Node IDs are strings or integers
• Only nodes reachable from entry should be included in the result
• The solution should run in O(V + E) time, where V is the number of nodes and E is the number of edges

Hints

1. The trigger count of a node is the sum of the trigger counts of its parents. In a DAG, this is equivalent to counting paths from the entry node.
2. Process only the reachable part of the graph in topological order so every parent contributes before its child is finalized.