StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It really depends on what algorithms you need to implement, there is no silver bullet (and that's shouldn't be a surprise... the general rule about programming is that there's no general rule ;-) ).</p> <p>I often end up representing directed multigraphs using node/edge structures with pointers... more specifically:</p> <pre><code>struct Node { ... payload ... Link *first_in, *last_in, *first_out, *last_out; }; struct Link { ... payload ... Node *from, *to; Link *prev_same_from, *next_same_from, *prev_same_to, *next_same_to; }; </code></pre> <p>In other words each node has a doubly-linked list of incoming links and a doubly-linked list of outgoing links. Each link knows <code>from</code> and <code>to</code> nodes and is at the same time in two different doubly-linked lists: the list of all links coming out from the same <code>from</code> node and the list of all links arriving at the same <code>to</code> node.</p> <p>The pointers <code>prev_same_from</code> and <code>next_same_from</code> are used when following the chain of all the links coming out <strong>from</strong> the same node; the pointers <code>prev_same_to</code> and <code>next_same_to</code> are instead used when managing the chain of all the links pointing <strong>to</strong> the same node.</p> <p><a href="https://i.stack.imgur.com/xfq8f.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/xfq8f.png" alt="Data structure diagram"></a></p> <p>It's a lot of pointer twiddling (so unless you love pointers just forget about this) but query and update operations are efficient; for example adding a node or a link is O(1), removing a link is O(1) and removing a node x is O(deg(x)).</p> <p>Of course depending on the problem, payload size, graph size, graph density this approach can be way overkilling or too much demanding for memory (in addition to payload you've 4 pointers per node and 6 pointers per link).</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