4 ms·
I think this is going to be extremely computationally intensive. One of the big performance wins I got when designing the search algorithm[1] was visiting as fe
by jwngr 9y ago
I think this is going to be extremely computationally intensive. One of the big performance wins I got when designing the search algorithm[1] was visiting as few nodes in the graph as possible (which I did via a bi-directional breadth-first search). To find the most distant node, I'd need to traverse the entire graph, which consists of almost 6 million nodes. It can be done, but it would take minutes, hours, days, ...
[1] https://github.com/jwngr/sdow/blob/a2699dc95d884ec64a46416307bebd9c58f76412/sdow/breadth_first_search.py#L36 https://github.com/jwngr/sdow/blob/a2699dc95d884ec64a4641630...
- AstralStorm 9y agoNot too expensive, you can use parallel IDDFS to get a good approximation quickly. (Especially if you pick a good heuristic to follow links.) Challenging part is keeping track of already visited pages to break cycles - some variant of a Bloom filter will help.