[cvigoe]

Love the idea, and it’s brilliantly executed! Well done.

Perhaps I misinterpreted the concept of “degrees of separation”, but I was expecting the site to tell me how to start at page X and get to page Y with the min number of clicks. If you wanted to achieve this, it doesn’t strike me as appropriate to use Bidirectional BFS but IANAL.

I did notice that someone pointed out that they get different results by swapping the order of X and Y. This seems pretty surprising?

Well done again!

[jwngr]

Thanks, glad you enjoyed it!

> I was expecting the site to tell me how to start at page X and get to page Y with the min number of clicks.

Yup, this is exactly what the site does, and a bi-directional BFS is an efficient way to do it. The special thing about my bi-directional BFS is that I follow outgoing links when searching from the source page while following incoming links when searching from the target page[1].

> I did notice that someone pointed out that they get different results by swapping the order of X and Y. This seems pretty surprising?

This is expected, because it is a directed graph, with the links on Wikipedia being in one direction. Just because page A links to page B doesn't mean page B links to page A.

[1] https://github.com/jwngr/sdow/blob/master/sdow/breadth_first...

[cvigoe]

I just realized what my confusion was over!

https://www.sixdegreesofwikipedia.com/?source=Carnegie%20Mel...

I was looking at the results of going from CMU to my little secondary school in Dublin, Ireland. I saw the results and saw that the last page before my Irish school was "College" and assumed it must be wrong, because how could my tiny secondary school be on the Wikipedia page for "College"? But alas, I was wrong!! I just checked and turns out it IS on the college wiki page!

I also assumed you were looking at outgoing links for both X and Y - that explains a lot.

I am super interested in this, but I have never done any graph theory or searching/planning (I'm EE) - how did you build up all of the incoming links for each wiki page? Are you storing all of this? How much data is that? Thanks for the reply!

[jwngr]

Check out an earlier comment I made[1] which has some information about this. It also includes links to the relevant code, which is all open source.

[1] https://news.ycombinator.com/item?id=16469260