Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Max White]

Unless you happened to get there before you went through all one hundred million, and that seems likely.

[Reelya]

Yes, but we're talking about search ALL links off each page, before deciding which route to take. How can you "find" the route when you're searching all the links in parallel?

This is the domain of search algorithms as seen in chess etc. Have you looked at how quickly modern supercomputers CPU and RAM gets swamped by even relatively simple games?

You can do depth-first or breadth-first search. My comment was in response to someone wishing that the program found shorter routes. i.e testing ALL routes even after one existing one is found (assuming you're using depth-first search). But with "depth first" you need to explore an unknown number of bad routes before finding the good route. And with breadth-first you search all links off each possible route in parallel until one of the routes is a winner. Both have pro's and con's.

If you want the "shortest route" as the person wishing for the Xefer algorithm to be improved did, then you have to keep searching even after a single route is found.

[Max White]

Unless you searched full breath before depth.
If you searched your entire tier X depth, then you can be sure that x + 1 will be longer, thus you can stop at the first result.

[Reelya]

Yes but that's likely to be minimum of 5 links, hence the 100 million routes i talked about. And '40' is just a guesstimate. Many pages will have more than 40 links.

Plus the memory needed to keep track of all the URLs for the various links and searching the database constantly to check that each new URL isn't on another page's path already, all for some lame web joke game.

[Qmarx]

Easiest just to start at philosophy and search backwards.

[Max White]

Yes but that's likely to be minimum of 5 links, hence the 100 million routes i talked about. And '40' is just a guesstimate. Many pages will have more than 40 links.

Plus the memory needed to keep track of all the URLs for the various links and searching the database constantly to check that each new URL isn't on another page's path already, all for some lame web joke game.

Persuading argument, would be very fun to test though...

Easiest just to start at philosophy and search backwards.

Good god man, are you trying to break the internet?

[Qmarx]

Good god man, are you trying to break the internet?

You'd only have to access each page on wikipedia once to build a database.  The algorithm would be pretty simple, too.  You'd have to go through the whole 31 gb data dump, but that shouldn't be that hard.

There's already an option for 'pages that link to this page', after all.

[Sensei]

Also: http://en.wikipedia.org/wiki/Michel_Folco
Ha! No links, eat that, theory!

I went on there and fixed it. Personally.

[Criptfeind]

Easiest just to start at philosophy and search backwards.

You would have the exact same issue. It gets exponentially bigger each time you don't get the link to it.

[PTTG??]

Try The Onion again.

[Max White]

I went on there and fixed it. Personally.

But now you are invoking the exception that proves the rule... Do you mean to imply that there are French writers that are not human?

[Qmarx]

Easiest just to start at philosophy and search backwards.

You would have the exact same issue. It gets exponentially bigger each time you don't get the link to it.

What do you mean by exponentially bigger? 

You're essentially building a tree iteratively starting from 'philosophy', right? 
All you're doing, then, is going through and building an array of articles, and which article they're attached to on the shortest path.  If you do breadth-first, you'll handle all of the articles in a non-descending order by degree of separation.  So find a link, check to see if it's in the array, if it isn't, add it to the end of the list and record what the article it's linked to (along with degree of separation if you like),


While towards the end (article 3.5 million or so) there might be a bit of slowdown when you start to check whether the article is already added, but I'm fairly certain there are algorithms that handle that sort of thing elegantly.

[Reelya]

Yes, but by going for a known target each time, the philosophy article, you can store heuristics on each URL reference (you've already needed to create a graph of the URLS links) which says the number of steps to philosophy. You can also look for "trunk" articles and avoid "leaves' in the graph.

That only needs to be done once, and all future searches could just follow the "path of least resistance" (just pick the link with lowest steps number) as in A* search.

With a "moving target" you'd need to work out a new set of heuristics for every search.

[JoshuaFH]

So what's the longest you could find? Mine is Arthur Tyndall at what I think is 30 steps.

EDIT: Holy moly. Tried just pasting the code for the image export, but the chunk for it's image location is 107,000 characters long, and I don't want to bother hosting it myself.

[Max White]

Swimming at the 1904 Summer Olympics – Men's 440 yard breaststroke
32 links.