Graph Traversal Implementation

EasyPython

Problem

Guardian Life models dependencies between internal services as a directed graph. Given a starting service and a destination service, determine whether the destination is reachable by following one-way dependency edges.

Implement can_reach(graph, start, target) using breadth-first search or depth-first search. The graph is represented as an adjacency list, where each key is a service name and its value is a list of directly dependent services. Return true if target can be reached from start, including when both names are the same. Return false when no path exists.

Formal Specification

Input: graph, a dictionary mapping strings to lists of strings; start and target, service-name strings.
Output: A boolean indicating whether a directed path exists from start to target.
The graph may contain cycles, self-loops, disconnected services, and services that appear only as neighbors.

Constraints

1 <= number of services <= 10^5
0 <= number of directed edges <= 2 * 10^5
Service names are non-empty strings
The graph may contain cycles, self-loops, disconnected services, and repeated edges

Function Signature

def can_reach(graph, start, target):

Formal Specification

Input: graph, a dictionary mapping strings to lists of strings; start and target, service-name strings.
Output: A boolean indicating whether a directed path exists from start to target.
The graph may contain cycles, self-loops, disconnected services, and services that appear only as neighbors.