Six Degrees of Wikipedia — Solver Engine

A high-performance "Six Degrees of Wikipedia" solver that finds the shortest path between any two Wikipedia articles through hyperlinks. The engine uses a Compressed Sparse Row (CSR) graph with Bidirectional BFS and Hub Labeling heuristics, exposed via a Python FastAPI service.

---

Architecture

graph TB
    subgraph Docker Compose
        direction TB
        Client["🌐 Client"]
        API["FastAPI<br/>(Python 3.11)"]
        Engine["wiki_engine<br/>(pybind11 C++17)"]
        Redis["Redis 7<br/>(LRU Cache)"]
        Data["📁 data/<br/>titles.tsv + edges.tsv"]

        Client -->|HTTP :8000| API
        API -->|pybind11| Engine
        API <-->|cache| Redis
        Engine -->|mmap| Data
    end

    subgraph C++ Engine
        direction LR
        CSR["CsrGraph<br/>(CSR storage)"]
        BFS["BidirectionalBfs"]
        Hub["HubLabeling"]
        Pool["ThreadPool"]

        BFS --> CSR
        Hub --> CSR
        BFS -.->|parallel| Pool
        Hub -.->|precompute| Pool
    end

    Engine --> CSR

Loading

Prerequisites

Docker (recommended)

• Docker ≥ 20.10
• Docker Compose ≥ 2.0

Local Development

• C++ Toolchain: GCC ≥ 10 / Clang ≥ 12 / MSVC ≥ 19.28 (C++17 support)
• CMake ≥ 3.20
• Python ≥ 3.9 with pip
• Git (for FetchContent dependencies)

---

Quick Start with Docker Compose

1. Prepare Data

# Download Wikipedia dumps and preprocess into TSV files
chmod +x scripts/download_dump.sh
./scripts/download_dump.sh ./data

Note: The full English Wikipedia dump is ~6 GB compressed. Preprocessing takes 30–60 minutes and requires ~16 GB RAM.

2. Start Services

docker compose up --build -d

This builds the C++ engine, starts the FastAPI server on port 8000, and a Redis cache on port 6379.

3. Query

curl "http://localhost:8000/api/path?source=Albert_Einstein&target=Pizza"

---

Local Development Setup

Build the C++ Engine

mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Debug -DBUILD_TESTING=ON
cmake --build . --parallel $(nproc)

Run Tests

cd build
ctest --output-on-failure

Install Python Dependencies

pip install -r api/requirements.txt

Run the API Server

# From the project root, with the built wiki_engine.so on PYTHONPATH
export PYTHONPATH="$(pwd)/build:${PYTHONPATH}"
uvicorn api.main:app --reload --host 0.0.0.0 --port 8000

---

API Documentation

GET /api/path

Find the shortest path between two Wikipedia articles.

Query Parameters:

Parameter	Type	Required	Description
source	string	✅	Source article title
target	string	✅	Target article title

Response:

{
  "source": "Albert_Einstein",
  "target": "Pizza",
  "found": true,
  "distance": 3,
  "path": [
    "Albert_Einstein",
    "Italy",
    "Italian_cuisine",
    "Pizza"
  ],
  "timing_ms": 12.4
}

Example — path not found:

{
  "source": "Some_Article",
  "target": "Nonexistent_Page",
  "found": false,
  "distance": -1,
  "path": [],
  "timing_ms": 1.2
}

GET /api/health

Health check endpoint.

curl http://localhost:8000/api/health

{
  "status": "ok",
  "graph_loaded": true,
  "num_articles": 6800000,
  "num_links": 190000000
}

---

Data Preparation

Automated (recommended)

./scripts/download_dump.sh ./data

Manual

1. Download from dumps.wikimedia.org:

   • enwiki-YYYYMMDD-page.sql.gz
   • enwiki-YYYYMMDD-pagelinks.sql.gz

2. Preprocess:

python3 scripts/preprocess_dump.py \
    --page-sql  data/enwiki-YYYYMMDD-page.sql.gz \
    --links-sql data/enwiki-YYYYMMDD-pagelinks.sql.gz \
    --output-dir data/

This produces:

• data/titles.tsv — page_id<TAB>page_title (~300 MB)
• data/edges.tsv — source_id<TAB>target_id (~3 GB)

---

Performance Characteristics

Metric	Value
Graph loading	~20 s (6.8M nodes, 190M edges)
Hub precomputation	~60 s (top-512 hubs)
Query latency (p50)	< 5 ms
Query latency (p99)	< 50 ms
Memory usage	~3.5 GB (CSR + hub labels)
Cache hit latency	< 1 ms (Redis)

The engine achieves sub-10ms median latency through:

• CSR storage: Cache-friendly, contiguous memory layout
• Bidirectional BFS: Explores from both ends, reducing search space exponentially
• Hub labeling: Pre-computed shortest paths through high-degree nodes enable O(1) lookups for common queries
• Thread pool: Parallel BFS frontiers for large graphs

---

Project Structure

Wikipedia_Solver/
├── CMakeLists.txt              # Top-level CMake build configuration
├── Dockerfile                  # Multi-stage Docker build
├── docker-compose.yml          # Full-stack orchestration
├── README.md                   # This file
├── include/                    # C++ headers
│   ├── csr_graph.h             #   CSR graph data structure
│   ├── bidirectional_bfs.h     #   Bidirectional BFS algorithm
│   ├── hub_labeling.h          #   Hub labeling heuristic
│   ├── thread_pool.h           #   Work-stealing thread pool
│   ├── graph_loader.h          #   TSV file → CsrGraph loader
│   └── path_result.h           #   Query result struct
├── src/                        # C++ sources
│   ├── csr_graph.cpp
│   ├── bidirectional_bfs.cpp
│   ├── hub_labeling.cpp
│   ├── thread_pool.cpp
│   ├── graph_loader.cpp
│   └── bindings.cpp            #   pybind11 Python bindings
├── api/                        # Python FastAPI service
│   ├── main.py                 #   Application entry point
│   ├── cache.py                #   Redis cache layer
│   ├── schemas.py              #   Pydantic models
│   ├── config.py               #   Environment configuration
│   └── requirements.txt        #   Python dependencies
├── tests/                      # C++ Google Test suites
│   ├── CMakeLists.txt
│   ├── test_csr_graph.cpp
│   ├── test_bidirectional_bfs.cpp
│   └── test_hub_labeling.cpp
├── scripts/                    # Data preparation scripts
│   ├── download_dump.sh        #   Download Wikipedia dumps
│   └── preprocess_dump.py      #   SQL dump → TSV conversion
└── data/                       # Graph data files (not committed)
    └── .gitkeep

---

License

MIT