StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>There is no particular algorithm that will help you optimise the construction of a graph from scratch. One way or another, you are going to have to visit each node at least once. Whether you do this <a href="http://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow noreferrer">depth first</a> or <a href="http://en.wikipedia.org/wiki/Breadth-first_search" rel="nofollow noreferrer">breadth first</a> is irrelevant from a speed perspective. <a href="https://stackoverflow.com/users/40180/theran">Theran</a> correctly points out in a comment below that breadth-first search, by exploring nearer nodes first, may give you a more useful graph immediately, before the whole graph is completed; this may or may not be a concern for you. He also notes that the neatest version of depth-first search is implemented using recursion, which could potentially be a problem for you. Note that recursion is not required, however; you can add incompletely explored nodes to a stack and process them linearly if you wish.</p> <p>If you do a simple existence check for new nodes (O(1) if you use a hash for lookup), then cycles will not be a problem at all. Cycles are only a concern if you do not store the complete graph. You can optimise searches through the graph, but the construction step itself will always take linear time.</p> <p>I agree with other posters that the size of your graph should not be a problem. 250,000 is not very large!</p> <p>Regarding concurrent execution; the graph is updated by all threads, so it needs to be a synchronised data structure. Since this is Python, you can make use of the <a href="http://docs.python.org/library/queue.html" rel="nofollow noreferrer">Queue</a> module to store new links still to be processed by your threads.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload