StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I'm afraid what you're looking for is impossible, because thread-safety is a property of algorithms, not a property of data structures. Here's an example:</p> <p>Let's say your graph library has a main <code>Graph</code> class with a number of methods, all of which are <code>synchronized</code>. For example, <code>addVertex()</code>, <code>removeVertex()</code>, <code>addEdge()</code>, <code>removeEdge()</code>, etc. Let's also say that the <code>Vertex</code> class has some useful methods like <code>getAdjacentEdges()</code>, for example, also synchronized on the containing <code>Graph</code> instance.</p> <p>Now clearly because everything is synchronized, it's impossible to corrupt the data structure. For example, you'll never have a situation where <code>v.getAdjacentEdges()</code> gives you an edge that's not actually in the graph containing vertex <code>v</code>. The graph structure is always internally consistent thanks to its internal synchronization.</p> <p>However, your algorithms operating on the graph can still easily break. For example, let's say you write:</p> <pre><code>for (Edge e : v.getAdjacentEdges()) { g.removeEdge(e); } </code></pre> <p>The call to <code>getAdjacentEdges()</code> is atomic, as is each call to <code>removeEdge()</code> in the loop, but the algorithm itself is not. Another thread may add a new edge adjacent to <code>v</code> while this loop is running, or remove an edge, or whatever. To be safe, you still need a way of ensuring that the loop as a whole is atomic, and the graph itself cannot provide that.</p> <p>My best advice, I think, is to use JGraphT in combination with <a href="http://akka.io/docs/akka-1.0/stm-java.html" rel="nofollow">Akka's STM</a> implementation (or similar), so that you can write your algorithms without needing to determine ahead of time which objects will require locking. If you're not familiar with STM and its performance characteristics, <a href="http://en.wikipedia.org/wiki/Software_transactional_memory" rel="nofollow">Wikipedia's article on the topic</a> does a decent job of explaining.</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