Traverse All Reachable Pages With Parallel BFS

Problem Statement

You are tasked with building a web crawler that traverses all web pages reachable from a given start_url. Fetching a webpage over the network is high-latency, so your crawler must issue fetch requests concurrently while guaranteeing a deterministic discovery order.

You are provided an interface Fetcher:

class Fetcher:
    def get_links(self, url: str) -> list[str]:
        """Returns the list of outgoing URLs from `url`.
        Raises an Exception if the network request fails.
        """
        pass

Implement the function crawl(start_url: str, fetcher: Fetcher, max_concurrency: int) -> list[str].

Requirements

1. Deterministic Level-Order Traversal: Return URLs in breadth-first search (BFS) order. Level 0 contains [start_url]. Level k contains all newly discovered, unvisited URLs directly reachable from pages in Level k - 1. Within each level, URLs must be ordered lexicographically.
2. Cycles and Duplicates: Each unique URL must be fetched at most once and must appear in the output list exactly once.
3. Concurrency: At most max_concurrency calls to fetcher.get_links should be active at any given moment.
4. Fault Tolerance: If fetcher.get_links(url) raises an exception, treat that page as having no outgoing links. The failed URL itself should still be included in the output list.

Function Signature

def crawl(start_url: str, fetcher: Fetcher, max_concurrency: int = 4) -> list[str]:
    pass

Examples

Example 1

Graph Structure:

• "pageA" -> ["pageC", "pageB"]
• "pageB" -> ["pageD"]
• "pageC" -> ["pageD", "pageA"]
• "pageD" -> []

Input:

start_url = "pageA"
max_concurrency = 2

Output:

["pageA", "pageB", "pageC", "pageD"]

Explanation:

• Level 0: ["pageA"]
• Level 1: ["pageB", "pageC"] (sorted lexicographically)
• Level 2: ["pageD"] ("pageA" is already visited)

Example 2

Graph Structure:

• "root" -> ["child1", "child2"]
• "child1" raises a TimeoutError
• "child2" -> ["leaf"]

Input:

start_url = "root"
max_concurrency = 4

Output:

["root", "child1", "child2", "leaf"]

Constraints

• 1 <= total reachable pages <= 10,000
• 1 <= max_concurrency <= 64
• URL strings consist of printable ASCII characters with length between 1 and 256.