Same-Domain Web Crawl (BFS)

Problem Statement

You are building a focused web crawler. Given a starting URL start_url and an interface HtmlFetcher, implement a breadth-first search (BFS) crawler that visits accessible pages and returns a list of crawled URLs in the order they were first visited.

The crawler must adhere to the following rules:

1. Same-Domain Only: Only crawl URLs that have the exact same hostname/domain as start_url. For example, if start_url is "https://anthropic.com/research", you should crawl "https://anthropic.com/careers", but not "https://news.anthropic.com" or "https://example.com".
2. URL Normalization:
   • Strip URL fragments (anything from # onwards). For example, https://anthropic.com/about#team should be normalized to https://anthropic.com/about.
   • Do not alter query parameters or paths otherwise.
3. Deduplication: Do not fetch or visit the same normalized URL more than once.
4. Traversal Order: Traverse the link graph level-by-level using Breadth-First Search (BFS).
5. Page Limit: Stop crawling once you have fetched max_pages unique URLs, or when no more same-domain links are available in the queue.

Interface

class HtmlFetcher:
    def get_urls(self, url: str) -> list[str]:
        """Returns raw link URLs found on the given page."""
        pass

def crawl(start_url: str, fetcher: HtmlFetcher, max_pages: int = 50) -> list[str]:
    pass

Constraints

• 1 <= max_pages <= 1000
• start_url is a valid, well-formed HTTP/HTTPS URL.
• HtmlFetcher.get_urls(url) will return valid HTTP/HTTPS URLs as strings.
• You may use standard library modules such as urllib.parse.

Examples

Example 1

# Graph:
# "http://example.com/" -> ["http://example.com/a", "http://other.com/", "http://example.com/b"]
# "http://example.com/a" -> ["http://example.com/c", "http://example.com/#top"]
# "http://example.com/b" -> []
# "http://example.com/c" -> []

fetcher = MockFetcher(...) # with graph above
crawl("http://example.com/", fetcher, max_pages=10)
# Output: ["http://example.com/", "http://example.com/a", "http://example.com/b", "http://example.com/c"]

Explanation: http://other.com/ is skipped because its domain does not match example.com. http://example.com/#top normalizes to http://example.com/, which was already visited.

Example 2

# Graph:
# "https://site.org/start" -> ["https://site.org/1", "https://site.org/2"]
# "https://site.org/1" -> ["https://site.org/3"]
# "https://site.org/2" -> ["https://site.org/4"]

fetcher = MockFetcher(...) 
crawl("https://site.org/start", fetcher, max_pages=3)
# Output: ["https://site.org/start", "https://site.org/1", "https://site.org/2"]

Explanation: Crawling stops immediately once max_pages (3) is reached, without calling fetcher.get_urls on subsequent items in the queue.