StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I recently implemented this algorithm. I started with the approach you have shown, but it didn't scale to graphs of 20+ million nodes. The solution I ended up with is based on <a href="http://www.brpreiss.com/books/opus4/html/page558.html#SECTION0017331000000000000000" rel="nofollow">the approach detailed here</a>. </p> <p>You can think of it as computing the height of each node, and then the result is a group of each node at a given height.</p> <p>Consider the graph:</p> <p>A -> X</p> <p>B -> X</p> <p>X -> Y</p> <p>X -> Z</p> <p>So the desired output is (A,B), (X), (Y, Z)</p> <p>The basic approach is to find everything with nothing using it(A,B in this example). All of these are at height 0.</p> <p>Now remove A and B from the graph, find anything that now has nothing using it(now X in this example). So X is at height 1.</p> <p>Remove X from the graph, find anything that now has nothing using it(now Y,Z in this example). so Y,Z are at height 2.</p> <p>You can make an optimization by realizing the fact that you don't need to store bidirectional edges for everything or actually remove anything from your graph, you only need to know the number of things pointing to a node and the nodes you know are at the next height.</p> <p>So for this example at the start:</p> <ul> <li>0 things use 1</li> <li>0 things use 2</li> <li>2 things use X (1 and 2)</li> <li>1 things use Y,Z (X)</li> </ul> <p>When you visit a node, decrease the number of each of the nodes it points to, if that number goes to zero, you know that node is at the next height.</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