Here is my attempt on implementing "Degrees of Wikipedia" (much faster version can be seen at degreesofwikipedia.com.It's basically an algorithm which tries to connect two unrelated Wikipedia pages by traversing the internal wikilinks they contain. This version in order to produce faster result doesn't look for the exact match, but just for the matching substring in the url, but that can be changed by editing one line, so it's not really an issue.
import re from collections import deque import requests from bs4 import BeautifulSoup class UrlNode: def __init__(self, url, prev): self.url = url self.prev = prev self.transform_url() def transform_url(self): if self.url.startswith("/wiki"): self.url = "https://en.wikipedia.org" + self.url def get_subject(self): return self.url.rsplit("/", 1).replace("_", " ") def is_wiki_url(url): url_pattern = r"^/wiki/[a-zA-Z0-9_\,.'-]+$" return re.match(url_pattern, url, re.I) def print_path(result): path =  distance = 0 while result is not None: path.append(result.get_subject()) distance += 1 result = result.prev path.reverse() print("DISTANCE:", distance) print(" -> ".join(path)) def crawl(start, query): print(" ==== WIKI CRAWLER === ") print("Searching for connnection between '", start, "' and '", query, "'", sep="") query = query.replace(" ", "_") start = "/wiki/" + start.replace(" ", "_") session = requests.session() visited_urls =  start_url = UrlNode(start, None) url_queue = deque() url_queue.append(start_url) while url_queue: url_node = url_queue.popleft() if url_node.url in visited_urls: continue visited_urls.append(url_node.url) print(url_node.url) req = session.get(url_node.url) bs = BeautifulSoup(req.text, 'html.parser') for link in bs.find_all('a'): if not link.has_attr("href"): continue if is_wiki_url(link["href"]) and link["href"] not in visited_urls: # print("\tFound: ", link["href"]) new_node = UrlNode(link["href"], url_node) if query in new_node.url: print("Total pages visited:", str(len(visited_urls))) return new_node url_queue.append(new_node) return None start = "Stack Overflow" query = "Banana" result = crawl(start, query) print_path(result)
This generates result:
Total pages visited: 1054 DISTANCE: 4 Stack Overflow -> Wiki -> University of California -> UC Santa Cruz Banana Slugs
My question is: how can I make this work faster? I welcome both algorithmic suggestions and various "hacks", e.g. requesting the mobile version of the page, which should load faster etc. Here I used breadth-first algorithm, which is very basic and I'm pretty sure better options exist.