Compute Load Factors in a Service Dependency DAG

Problem Statement

In a microservice ecosystem, an initial ingress request to an entrypoint service triggers a cascade of calls downstream. A service u may call a downstream dependency v multiple times per incoming request (or a fractional number of times, representing conditional branching). When multiple services depend on v, their request volumes converge.

Given a list of unique service names services, a list of directed dependency edges edges, and the name of an entry service, compute the total load factor for every service in the system when exactly 1.0 request enters the entry service.

Each edge is defined as a tuple (src, dst, multiplier), indicating that for every single request received by src, src sends multiplier requests to dst.

Rules:

• The entry service has an initial load factor of 1.0.
• Any service unreachable from entry receives 0.0 load.
• If a service has incoming calls from multiple reachable services, its total load is the sum of load(src) * multiplier across all incoming edges (src, dst) where src is reachable.
• Return the results as a list of tuples (service_name, load_factor) sorted in ascending lexicographical order by service_name.

Function Signature

def compute_load_factors(
    services: list[str],
    edges: list[tuple[str, str, float]],
    entry: str
) -> list[tuple[str, float]]:
    pass

Constraints

• 1 <= len(services) <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• All service names consist of lowercase alphanumeric characters and underscores ([a-z0-9_]).
• 0.0 <= multiplier <= 1000.0
• The graph is guaranteed to be a Directed Acyclic Graph (DAG).
• entry is guaranteed to be present in services.

Examples

Example 1

services = ["gateway", "auth", "users", "db"]
edges = [
    ("gateway", "auth", 1.0),
    ("gateway", "users", 2.0),
    ("auth", "db", 1.0),
    ("users", "db", 1.5)
]
entry = "gateway"

# Output:
# [("auth", 1.0), ("db", 4.0), ("gateway", 1.0), ("users", 2.0)]

Explanation: gateway starts with 1.0. It triggers 1.0 call to auth and 2.0 calls to users. auth calls db (1.0 * 1.0 = 1.0). users calls db (2.0 * 1.5 = 3.0). Total load on db = 1.0 + 3.0 = 4.0.

Example 2

services = ["gateway", "payment", "legacy_logger"]
edges = [
    ("gateway", "payment", 1.0),
    ("legacy_logger", "payment", 3.0)
]
entry = "gateway"

# Output:
# [("gateway", 1.0), ("legacy_logger", 0.0), ("payment", 1.0)]

Explanation: legacy_logger cannot be reached from gateway, so its load factor is 0.0, and it does not contribute to payment.

Edge Cases

• Isolated nodes not connected to any edges should receive 0.0 (unless the node is entry, which receives 1.0).
• Nodes upstream from entry or disjoint from entry's component must not propagate phantom load.
• Floating-point accumulation: answers within 1e-6 of the expected value are acceptable.