Wikiroute

Returns the Six Degrees of Separation path between two Wikipedia articles.

Algorithm

Single-directional BFS

        Depth = 0        →        S
        Depth = 1        →       ○○○
        Depth = 2        →      ○○○○○
        Depth = 3        →     ○○○○○○○
        Depth = 4        →    ○○○○○○○○○
        Depth = 5        →   ○○○○○○○○○○○
        Depth = 6        →  ○○○○○○○○○○○○○

Time complexity: O(b^6)

Bidirectional BFS

From Start Side: From Goal Side:

  From Start Side:              From Goal Side:

        S                           G
       ○○○                        ○○○
      ○○○○○                      ○○○○○
     ○○○○○○○                    ○○○○○○○
        ↓                          ↑
        ↓←←←←←←←←←←→→→→→→→→→→→→→→↑
            Meet in the middle!

Time complexity: O(b^3 + b^3) = O(2b^3)

Setup

1. Download Wikipedia dump files

make download-all DATE=20250301

2. Generate parsed data

make generate-all

Run the application

docker compose up