ASSIGNED - bug 358697: [Subsystems] DAG interface and implementation https://bugs.eclipse.org/bugs/show_bug.cgi?id=358697 - DirectedAcyclicGraph and GraphNode ready for contribution.

6 files changed, 1704 insertions, 0 deletions

diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
new file mode 100644
index 0000000..12e4391
--- a/dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/DirectedAcyclicGraph.java
@@ -0,0 +1,54 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.List;
+
+/**
+ * {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
+ * to each other in a way that it is impossible to start at a node n and follow a child relationship that loops back to
+ * n. The DAG may have multiple root nodes (nodes with no parents) and nodes may share children.
+ * <p />
+ * Once created a root node can become a non-root node by adding the node as a child to another node. This can be done
+ * by calling the method addChild on a node. All nodes of a DAG are reachable from its root nodes.
+ * 
+ * <strong>Concurrent Semantics</strong><br />
+ * 
+ * Implementations of this interface may or may not be thread safe.
+ * 
+ * @param <V> type of values in the {@link GraphNode}s.
+ */
+public interface DirectedAcyclicGraph<V> {
+
+    /**
+     * Create a new {@link GraphNode} and add it to this {@link DirectedAcyclicGraph}'s root nodes. The value is not
+     * copied.
+     * 
+     * @param value of the node to create
+     * @return a node with the given value
+     */
+    GraphNode<V> createRootNode(V value);
+
+    /**
+     * Removes the occurrence of the given {@link GraphNode} from this {@link DirectedAcyclicGraph}'s root nodes.
+     * Returns <code>true</code> if the node was found and removed, otherwise <code>false</code>.
+     * 
+     * <strong>Note</strong>: Removal is only allowed if the root node has no children.
+     * 
+     * @param node the node to remove
+     * @throws IllegalArgumentException if the given node is not a root node (the node has one or more parents)
+     * @throws IllegalArgumentException if the given node has children
+     * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+     * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
+     * @see java.util.List#remove
+     */
+    boolean deleteRootNode(GraphNode<V> node);
+
+    /**
+     * Returns a list of this {@link DirectedAcyclicGraph}'s root nodes (not copies of the nodes). If the graph has no
+     * root nodes (and is therefore empty), returns an empty list. Never returns <code>null</code>.
+     * 
+     * @return this graph's root nodes
+     */
+    List<GraphNode<V>> getRootNodes();
+
+}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java
new file mode 100644
index 0000000..598e51c
--- a/dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/GraphNode.java
@@ -0,0 +1,160 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.List;
+
+/**
+ * {@link GraphNode} is a node in a {@link DirectedAcyclicGraph}. Each node has a value.
+ * <p />
+ * 
+ * <strong>Concurrent Semantics</strong><br />
+ * 
+ * Implementations of this interface may or may not be thread safe.
+ * 
+ * @param <V> type of values in the graph nodes.
+ */
+public interface GraphNode<V> {
+
+    /**
+     * {@link DirectedAcyclicGraphVisitor} is used to visit a node and, at the option of the visitor, its subgraphs
+     * recursively. <strong>Note</strong>: Shared nodes are only visited once.
+     * <p />
+     * 
+     * <strong>Concurrent Semantics</strong><br />
+     * 
+     * Implementations of this interface should be thread safe when used with a thread safe
+     * <code>DirectedAcyclicGraph</code> implementation.
+     * 
+     * @param <V> type of values in graph nodes
+     */
+    interface DirectedAcyclicGraphVisitor<V> {
+
+        /**
+         * Visits the given {@link GraphNode}. The return value determines whether or not any subgraphs of the given
+         * node are visited.
+         * 
+         * @param node the <code>GraphNode</code> to be visited
+         * @return <code>true</code> if and only if the subgraphs of the given node should be visited.
+         */
+        boolean visit(GraphNode<V> node);
+
+    }
+
+    /**
+     * An <code>ExceptionThrowingDirectedAcyclicGraphVisitor</code> is used to visit a node and, at the option of the
+     * visitor, its subgraphs recursively if the {@link #visit(GraphNode)} implementation needs to be able to throw a
+     * checked {@link Exception}. <strong>Note</strong>: Shared nodes are only visited once.
+     * <p />
+     * 
+     * <strong>Concurrent Semantics</strong><br />
+     * 
+     * Implementations of this interface should be thread safe when used with a thread safe
+     * <code>DirectedAcyclicGraph</code> implementation.
+     * 
+     * @param <V> type of values in graph nodes
+     * @param <E> type of exceptions possibly thrown
+     */
+    interface ExceptionThrowingDirectedAcyclicGraphVisitor<V, E extends Exception> {
+
+        /**
+         * Visits the given {@link GraphNode}. The return value determines whether or not any subgraphs of the given
+         * node are visited.
+         * 
+         * @param node the <code>GraphNode</code> to be visited
+         * @throws E if an error occurs when visiting the given node
+         * @return <code>true</code> if and only if the subgraphs of the given node should be visited.
+         */
+        boolean visit(GraphNode<V> node) throws E;
+
+    }
+
+    /**
+     * Returns the node's value. If there is no value associated with this node, returns <code>null</code>.
+     * 
+     * @return the value, which may be <code>null</code>
+     */
+    V getValue();
+
+    /**
+     * Returns a list of this node's children (not copies of the children). If the node has no children, returns an
+     * empty list. Never returns <code>null</code> .
+     * 
+     * @return this node's children
+     */
+    List<GraphNode<V>> getChildren();
+
+    /**
+     * Adds the given node as child to this node. The child node is <strong>not</strong> copied.
+     * 
+     * @param child the node to add
+     * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+     * @throws IllegalArgumentException if the given node is already a child of this node.
+     */
+    void addChild(GraphNode<V> child);
+
+    /**
+     * Removes the occurrence of the given node from this node's children. Returns <code>true</code> if the child was
+     * found and removed, otherwise <code>false</code>.
+     * 
+     * @param child the node to remove
+     * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+     * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
+     * @see java.util.List#remove
+     */
+    boolean removeChild(GraphNode<V> child);
+
+    /**
+     * Returns a list of this node's parents (not copies of the parents). If this node does not have any parents,
+     * returns an empty list. Never returns <code>null</code>.
+     * 
+     * @return this node's parents
+     */
+    List<GraphNode<V>> getParents();
+
+    /**
+     * Traverse this {@link GraphNode} in preorder (see below) and call the visit method of the given
+     * {@link DirectedAcyclicGraphVisitor} at each node. The visitor determines whether the subgraphs of each visited
+     * node should also be visited. <strong>Note</strong>: Shared nodes are only visited once.
+     * <p/>
+     * Preorder traversal visits the node and then visits, in preorder, each subgraph of the node.
+     * 
+     * @param visitor a {@link DirectedAcyclicGraphVisitor}
+     */
+    void visit(DirectedAcyclicGraphVisitor<V> visitor);
+
+    /**
+     * Traverse this {@link GraphNode} in preorder (see below) and call the visit method of the given
+     * {@link ExceptionThrowingDirectedAcyclicGraphVisitor} at each node. The visitor determines whether the subgraph of
+     * each visited node should also be visited. <strong>Note</strong>: Shared nodes are only visited once.
+     * <p/>
+     * Preorder traversal visits the node and then visits, in preorder, each subgraph of the node.
+     * 
+     * @param <E> type of exception possibly thrown
+     * @param visitor a {@link ExceptionThrowingDirectedAcyclicGraphVisitor}
+     * @throws E if an error occurs when visiting the node
+     */
+    <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor) throws E;
+
+    /**
+     * Returns the number of nodes in the subgraph of this node. The subgraph includes the node itself as the only root
+     * node.
+     * 
+     * <p />
+     * <strong>Note</strong>: Nodes may be shared and shared nodes are counted only once.
+     * 
+     * <p />
+     * If there are more than <tt>Integer.MAX_VALUE</tt> nodes, the return value is undefined and the user should seek
+     * professional help.
+     * 
+     * @return the number of nodes in the subgraph
+     */
+    int size();
+
+    /**
+     * Check if this node is a root node (a node without parents).
+     * 
+     * @return <code>true</code> if the node has no parents. Otherwise <code>false</code>.
+     */
+    boolean isRootNode();
+
+}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
new file mode 100644
index 0000000..7b827c8
--- a/dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeDirectedAcyclicGraph.java
@@ -0,0 +1,161 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * {@link DirectedAcyclicGraph} is a set of {@link GraphNode}s with a parent child relationship. The nodes are connected
+ * to each other in a way that it is impossible to start at a node n and follow a child relationship that loops back to
+ * n. The DAG may have multiple root nodes (nodes with no parents) and nodes may share children.
+ * <p />
+ * Once created a root node can become a non-root node by adding the node as a child to another node. This can be done
+ * by calling the method addChild on a node. All nodes of a DAG are reachable from its root nodes.
+ * 
+ * <strong>Concurrent Semantics</strong><br />
+ * 
+ * This class is thread safe.
+ * 
+ * @param <V> type of values in the graph
+ */
+public class ThreadSafeDirectedAcyclicGraph<V> implements DirectedAcyclicGraph<V> {
+
+    private final Object monitor = new Object();
+
+    private static final Object tieMonitor = new Object();
+
+    private final List<ThreadSafeGraphNode<V>> nodes = new ArrayList<ThreadSafeGraphNode<V>>();
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public ThreadSafeGraphNode<V> createRootNode(V value) {
+        synchronized (this.monitor) {
+            ThreadSafeGraphNode<V> node = new ThreadSafeGraphNode<V>(value, this.monitor);
+            this.nodes.add(node);
+            return node;
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean deleteRootNode(GraphNode<V> node) {
+        assertTypeAndMembership(node);
+        synchronized (this.monitor) {
+            Assert.isTrue(node.getChildren().isEmpty(), "Cannot delete node '%s'. Node has children. Please remove the children first.", node);
+            Assert.isTrue(node.getParents().isEmpty(),
+                "Cannot delete node '%s'. Node is still in use. Please remove it from the other node(s) first.", node);
+            boolean removed = this.nodes.remove(node);
+            return removed;
+        }
+    }
+
+    private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
+        Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
+        ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
+        Assert.isTrue(concreteChild.belongsToSameGraph(this.monitor), "The node '%s' does not belong to the graph '%s'", concreteChild, this);
+        return concreteChild;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public List<GraphNode<V>> getRootNodes() {
+        List<GraphNode<V>> rootNodes = new ArrayList<GraphNode<V>>();
+        synchronized (this.monitor) {
+            for (GraphNode<V> node : this.nodes) {
+                if (node.isRootNode()) {
+                    rootNodes.add(node);
+                }
+            }
+            return rootNodes;
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String toString() {
+        StringBuffer result = new StringBuffer();
+        result.append("<");
+        synchronized (this.monitor) {
+            boolean first = true;
+            for (GraphNode<V> child : getRootNodes()) {
+                if (!first) {
+                    result.append(", ");
+                }
+                result.append(child.toString());
+                first = false;
+            }
+        }
+        result.append(">");
+        return result.toString();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public int hashCode() {
+        synchronized (this.monitor) {
+            final int prime = 31;
+            int result = 1;
+            result = prime * result + this.nodes.hashCode();
+            return result;
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj == null) {
+            return false;
+        }
+        if (getClass() != obj.getClass()) {
+            return false;
+        }
+        ThreadSafeDirectedAcyclicGraph<V> other = (ThreadSafeDirectedAcyclicGraph<V>) obj;
+        int thisHash = System.identityHashCode(this);
+        int otherHash = System.identityHashCode(other);
+        if (thisHash < otherHash) {
+            synchronized (this.monitor) {
+                synchronized (other.monitor) {
+                    if (!this.nodes.equals(other.nodes)) {
+                        return false;
+                    }
+                }
+            }
+        } else if (thisHash > otherHash) {
+            synchronized (other.monitor) {
+                synchronized (this.monitor) {
+                    if (!this.nodes.equals(other.nodes)) {
+                        return false;
+                    }
+                }
+            }
+        } else {
+            synchronized (tieMonitor) {
+                synchronized (this.monitor) {
+                    synchronized (other.monitor) {
+                        if (!this.nodes.equals(other.nodes)) {
+                            return false;
+                        }
+                    }
+                }
+            }
+        }
+        return true;
+    }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java
new file mode 100644
index 0000000..7b7a221
--- a/dev/null
+++ b/org.eclipse.virgo.util.common/src/main/java/org/eclipse/virgo/util/common/ThreadSafeGraphNode.java
@@ -0,0 +1,382 @@
+
+package org.eclipse.virgo.util.common;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+/**
+ * {@link GraphNode} is a node in a {@link DirectedAcyclicGraph}. Each node has a value.
+ * <p />
+ * 
+ * <strong>Concurrent Semantics</strong><br />
+ * 
+ * This class is thread safe.
+ * 
+ * @param <V> type of values in the graph
+ */
+class ThreadSafeGraphNode<V> implements GraphNode<V> {
+
+    private final V value;
+
+    private final Object monitor;
+
+    private static final Object tieMonitor = new Object();
+
+    private final List<ThreadSafeGraphNode<V>> children = new ArrayList<ThreadSafeGraphNode<V>>();
+
+    private final List<ThreadSafeGraphNode<V>> parents = new ArrayList<ThreadSafeGraphNode<V>>();
+
+    /**
+     * Construct a {@link ThreadSafeGraphNode} with the given value, which may be <code>null</code>.
+     * 
+     * @param value the value of the node, which may be <code>null</code>
+     * @param monitor the shared monitor of the graph
+     */
+    ThreadSafeGraphNode(V value, Object monitor) {
+        this.value = value;
+        this.monitor = monitor;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public V getValue() {
+        return this.value;
+    }
+
+    /**
+     * Returns a list of this node's children (not copies of the children). If the node has no children, returns an
+     * empty list. Never returns <code>null</code> .
+     * <p/>
+     * The returned list is synchronized to preserve thread safety, but may still result in
+     * ConcurrentModificationException being thrown.
+     * 
+     * @return this node's children
+     */
+    @Override
+    public List<GraphNode<V>> getChildren() {
+        synchronized (this.monitor) {
+            return new SynchronizedList<GraphNode<V>>(this.children, this.monitor);
+        }
+    }
+
+    /**
+     * Adds the given node as child to this node. The child node is <strong>not</strong> copied.
+     * 
+     * @param child the node to add
+     * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+     * @throws IllegalArgumentException if the given node is already a child of this node.
+     * @throws IllegalArgumentException if the given node is not a {@link ThreadSafeGraphNode}.
+     */
+    @Override
+    public void addChild(GraphNode<V> child) {
+        ThreadSafeGraphNode<V> concreteChild = assertTypeAndMembership(child);
+        synchronized (this.monitor) {
+            Assert.isFalse(this.children.contains(child), "The node '%s' is already a child of '%s'", child, this);
+            doCycleCheck(concreteChild);
+            this.children.add(concreteChild);
+            concreteChild.parents.add(this);
+        }
+    }
+
+    private ThreadSafeGraphNode<V> assertTypeAndMembership(GraphNode<V> child) {
+        Assert.isInstanceOf(ThreadSafeGraphNode.class, child, "A child must be of type %s.", this.getClass().getName());
+        ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
+        Assert.isTrue(belongsToSameGraph(concreteChild), "The node '%s' does not belong to the same graph as '%s'", concreteChild, this);
+        return concreteChild;
+    }
+
+    private boolean belongsToSameGraph(ThreadSafeGraphNode<V> other) {
+        return this.monitor == other.monitor;
+    }
+
+    protected boolean belongsToSameGraph(Object monitor) {
+        return this.monitor == monitor;
+    }
+
+    // check for cycles when adding a new child to a parent (is this node a descendant of the new child?).
+    private void doCycleCheck(GraphNode<V> child) {
+        synchronized (this.monitor) {
+            DescendentChecker<V> descendentChecker = new DescendentChecker<V>(this);
+            child.visit(descendentChecker);
+            Assert.isFalse(descendentChecker.isDescendent(), "Can't add '%s'. This node is a descendent of the new child.", child);
+        }
+    }
+
+    /**
+     * Removes the occurrence of the given node from this node's children. Returns <code>true</code> if the child was
+     * found and removed, otherwise <code>false</code>.
+     * 
+     * @param child the node to remove
+     * @throws IllegalArgumentException if the given node does not belong to the same {@link DirectedAcyclicGraph}.
+     * @throws IllegalArgumentException if the given node is not a {@link ThreadSafeGraphNode}.
+     * @return <code>true</code> if the node was removed successfully, otherwise <code>false</code>.
+     * @see java.util.List#remove
+     */
+    @Override
+    public boolean removeChild(GraphNode<V> child) {
+        ThreadSafeGraphNode<V> concreteChild = assertTypeAndMembership(child);
+        synchronized (this.monitor) {
+            boolean removed = this.children.remove(concreteChild);
+            if (removed) {
+                removeParent(child, this);
+            }
+            return removed;
+        }
+    }
+
+    /*
+     * All the children in this.children share this.monitor.
+     */
+    private void removeParent(GraphNode<V> child, GraphNode<V> parent) {
+        synchronized (this.monitor) {
+            if (child instanceof ThreadSafeGraphNode<?>) {
+                ThreadSafeGraphNode<V> concreteChild = (ThreadSafeGraphNode<V>) child;
+                concreteChild.parents.remove(parent);
+            }
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public void visit(DirectedAcyclicGraphVisitor<V> visitor) {
+        visitInternal(visitor, new HashMap<ThreadSafeGraphNode<V>, Boolean>());
+    }
+
+    private void visitInternal(DirectedAcyclicGraphVisitor<V> visitor, Map<ThreadSafeGraphNode<V>, Boolean> visitedFlags) {
+        if (visitedFlags.containsKey(this)) {
+            return;
+        }
+        visitedFlags.put(this, Boolean.TRUE);
+        if (visitor.visit(this)) {
+            for (int i = 0; i < numChildren(); i++) {
+                ThreadSafeGraphNode<V> nextChild = getChild(i);
+                if (nextChild != null) {
+                    nextChild.visitInternal(visitor, visitedFlags);
+                } else {
+                    break;
+                }
+            }
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor) throws E {
+        visitInternal(visitor, new HashMap<ThreadSafeGraphNode<V>, Boolean>());
+    }
+
+    private <E extends Exception> void visitInternal(ExceptionThrowingDirectedAcyclicGraphVisitor<V, E> visitor,
+        Map<ThreadSafeGraphNode<V>, Boolean> visitedFlags) throws E {
+        if (visitedFlags.containsKey(this)) {
+            return;
+        }
+        visitedFlags.put(this, Boolean.TRUE);
+        if (visitor.visit(this)) {
+            for (int i = 0; i < numChildren(); i++) {
+                ThreadSafeGraphNode<V> nextChild = getChild(i);
+                if (nextChild != null) {
+                    nextChild.visitInternal(visitor, visitedFlags);
+                } else {
+                    break;
+                }
+            }
+        }
+    }
+
+    private ThreadSafeGraphNode<V> getChild(int i) {
+        synchronized (this.monitor) {
+            try {
+                return this.children.get(i);
+            } catch (IndexOutOfBoundsException e) {
+                return null;
+            }
+        }
+    }
+
+    private int numChildren() {
+        synchronized (this.monitor) {
+            return this.children.size();
+        }
+    }
+
+    private static class DescendentChecker<V> implements DirectedAcyclicGraphVisitor<V> {
+
+        private final ThreadSafeGraphNode<V> prospect;
+
+        private boolean descendent = false;
+
+        public DescendentChecker(ThreadSafeGraphNode<V> prospect) {
+            this.prospect = prospect;
+        }
+
+        @Override
+        public boolean visit(GraphNode<V> node) {
+            if (this.descendent) {
+                return false;
+            }
+            if (this.prospect == node) {
+                this.descendent = true;
+                return false;
+            }
+            return true;
+        }
+
+        public boolean isDescendent() {
+            return this.descendent;
+        }
+
+    }
+
+    private static class SizeVisitor<V> implements DirectedAcyclicGraphVisitor<V> {
+
+        private int size;
+
+        @Override
+        public boolean visit(GraphNode<V> dag) {
+            this.size += 1;
+            return true;
+        }
+
+        public int getSize() {
+            return this.size;
+        }
+    };
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public int size() {
+        SizeVisitor<V> sizeVisitor = new SizeVisitor<V>();
+        visit(sizeVisitor);
+        return sizeVisitor.getSize();
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public int hashCode() {
+        synchronized (this.monitor) {
+            final int prime = 31;
+            int result = 1;
+            result = prime * result + this.children.hashCode();
+            result = prime * result + (this.value == null ? 0 : this.value.hashCode());
+            return result;
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    // TODO TSGN.equals regards nodes as equal which have different sets of parents.
+    // TODO TSGN.equals regards distinct nodes with no children (no parents once the todo above is fixed) and the same
+    // value as equal. These nodes were created separately, possibly even from distinct DAGs as currently coded.
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj == null) {
+            return false;
+        }
+        if (getClass() != obj.getClass()) {
+            return false;
+        }
+        ThreadSafeGraphNode<V> other = (ThreadSafeGraphNode<V>) obj;
+        int thisHash = System.identityHashCode(this);
+        int otherHash = System.identityHashCode(other);
+        if (thisHash < otherHash) {
+            synchronized (this.monitor) {
+                synchronized (other.monitor) {
+                    if (!this.children.equals(other.children)) {
+                        return false;
+                    }
+                }
+            }
+        } else if (thisHash > otherHash) {
+            synchronized (other.monitor) {
+                synchronized (this.monitor) {
+                    if (!this.children.equals(other.children)) {
+                        return false;
+                    }
+                }
+            }
+        } else {
+            synchronized (tieMonitor) {
+                synchronized (this.monitor) {
+                    synchronized (other.monitor) {
+                        if (!this.children.equals(other.children)) {
+                            return false;
+                        }
+                    }
+                }
+            }
+        }
+        if (this.value == null) {
+            if (other.value != null) {
+                return false;
+            }
+        } else if (!this.value.equals(other.value)) {
+            return false;
+        }
+        return true;
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public String toString() {
+        StringBuffer result = new StringBuffer();
+        result.append(this.value != null ? this.value : "null").append("<");
+        synchronized (this.monitor) {
+            boolean first = true;
+            for (ThreadSafeGraphNode<V> child : this.children) {
+                if (!first) {
+                    result.append(", ");
+                }
+                result.append(child.toString());
+                first = false;
+            }
+        }
+        result.append(">");
+        return result.toString();
+    }
+
+    /**
+     * Returns a list of this graph's parents (not copies of the parents). If the graph has no parents, returns an empty
+     * list. Never returns <code>null</code> .
+     * <p/>
+     * The returned list is synchronized to preserve thread safety, but may still result in
+     * ConcurrentModificationException being thrown.
+     * 
+     * @return this graph's parents
+     */
+    // TODO TSGN.getParents share its monitor with return values of getParents and getChildren. It feels as if the user
+    // might get some surprising deadlocks.
+    @Override
+    public List<GraphNode<V>> getParents() {
+        synchronized (this.monitor) {
+            return new SynchronizedList<GraphNode<V>>(this.parents, this.monitor);
+        }
+    }
+
+    /**
+     * {@inheritDoc}
+     */
+    @Override
+    public boolean isRootNode() {
+        return this.parents.isEmpty();
+    }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java
new file mode 100644
index 0000000..69e36f0
--- a/dev/null
+++ b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeAcyclicDirectedGraphTests.java
@@ -0,0 +1,346 @@
+/*******************************************************************************
+ * Copyright (c) 2008, 2010 VMware Inc.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *   VMware Inc. - initial contribution
+ *******************************************************************************/
+
+package org.eclipse.virgo.util.common;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.concurrent.CyclicBarrier;
+
+import org.junit.Before;
+import org.junit.Test;
+
+public class ThreadSafeAcyclicDirectedGraphTests {
+
+    private DirectedAcyclicGraph<String> graph;
+
+    private static DirectedAcyclicGraph<String> getDAG() {
+        return getDAG("We");
+    }
+
+    private static DirectedAcyclicGraph<String> getDAG(String rootValue) {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        // shared nodes
+        GraphNode<String> lo = graph.createRootNode("Lo");
+        GraphNode<String> fi = graph.createRootNode("Fi");
+
+        // We.add(Pa)
+        GraphNode<String> we = graph.createRootNode("We");
+        GraphNode<String> pa = graph.createRootNode("Pa");
+        we.addChild(pa);
+        // Pa.add(Cr)
+        GraphNode<String> cr = graph.createRootNode("Cr");
+        pa.addChild(cr);
+        // Cr.add(B1,Lo,Fi)
+        cr.addChild(graph.createRootNode("B1"));
+        cr.addChild(lo);
+        cr.addChild(fi);
+
+        // Pa.add(Cu)
+        GraphNode<String> cu = graph.createRootNode("Cu");
+        pa.addChild(cu);
+        cu.addChild(graph.createRootNode("B2"));
+        cu.addChild(lo);
+        cu.addChild(fi);
+
+        // Pa.add(B3)
+        pa.addChild(graph.createRootNode("B3"));
+        // Pa.add(Lo)
+        pa.addChild(lo);
+
+        return graph;
+    }
+
+    @Before
+    public void setUp() {
+        this.graph = getDAG();
+    }
+
+    @Test
+    public void testEmptyGraph() throws Exception {
+        DirectedAcyclicGraph<String> emptyGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        assertNotNull(emptyGraph);
+        assertNotNull(emptyGraph.getRootNodes());
+        assertEquals("<>", emptyGraph.toString());
+        assertTrue(emptyGraph.getRootNodes().isEmpty());
+    }
+
+    @Test
+    public void testGraphWithSingleRootNode() throws Exception {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> rootNode = smallGraph.createRootNode("root");
+
+        assertEquals("<root<>>", smallGraph.toString());
+        assertEquals(1, smallGraph.getRootNodes().size());
+
+        smallGraph.deleteRootNode(rootNode);
+
+        assertEquals(0, smallGraph.getRootNodes().size());
+    }
+
+    @Test
+    public void testGraphWithSingleNullRootNode() throws Exception {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> rootNode = smallGraph.createRootNode(null);
+
+        assertEquals("<null<>>", smallGraph.toString());
+        assertEquals(1, smallGraph.getRootNodes().size());
+
+        smallGraph.deleteRootNode(rootNode);
+
+        assertEquals(0, smallGraph.getRootNodes().size());
+    }
+
+    @Test
+    public void testGraphWithOnlyChildren() throws Exception {
+        DirectedAcyclicGraph<String> onlyChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> rootNode = onlyChildGraph.createRootNode("root");
+        assertEquals("<root<>>", onlyChildGraph.toString());
+        assertEquals(1, onlyChildGraph.getRootNodes().size());
+
+        GraphNode<String> child = onlyChildGraph.createRootNode("child");
+        rootNode.addChild(child);
+        assertEquals("<root<child<>>>", onlyChildGraph.toString());
+
+        GraphNode<String> grandchild = onlyChildGraph.createRootNode("grandchild");
+        child.addChild(grandchild);
+        assertEquals("<root<child<grandchild<>>>>", onlyChildGraph.toString());
+        assertEquals(1, onlyChildGraph.getRootNodes().size());
+
+        assertTrue(child.removeChild(grandchild));
+        onlyChildGraph.deleteRootNode(grandchild);
+        assertTrue(rootNode.removeChild(child));
+        onlyChildGraph.deleteRootNode(child);
+        onlyChildGraph.deleteRootNode(rootNode);
+        assertEquals(0, onlyChildGraph.getRootNodes().size());
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testDirectCycle() throws Exception {
+        DirectedAcyclicGraph<Integer> smallGraph = new ThreadSafeDirectedAcyclicGraph<Integer>();
+        GraphNode<Integer> root = smallGraph.createRootNode(Integer.valueOf(42));
+
+        root.addChild(root);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testParentNodeIsNotADescendantOfTheNewChild() throws Exception {
+        DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> rootNode = dag.createRootNode("root");
+        GraphNode<String> child = dag.createRootNode("child");
+
+        rootNode.addChild(child);
+        child.addChild(rootNode);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testParentIsNotADescendantOfTheNewChildDistanceTwo() throws Exception {
+        DirectedAcyclicGraph<String> dag = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> rootNode = dag.createRootNode("root");
+
+        GraphNode<String> child = dag.createRootNode("child");
+        rootNode.addChild(child);
+        GraphNode<String> child2 = dag.createRootNode("child2");
+        rootNode.addChild(child2);
+        GraphNode<String> grandchild = dag.createRootNode("grandchild");
+        child.addChild(grandchild);
+
+        grandchild.addChild(rootNode);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testDeleteRootNodeFromOtherGraph() {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> r1 = smallGraph.createRootNode("R1");
+
+        this.graph.deleteRootNode(r1);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testDeleteRootNodeOfWrongType() {
+        this.graph.deleteRootNode(new ThreadSafeGraphNodeTests.NoopGraphNode());
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testDeleteRootNodeWithChildren() {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> r1 = smallGraph.createRootNode("R1");
+        GraphNode<String> c1 = smallGraph.createRootNode("C1");
+        r1.addChild(c1);
+
+        this.graph.deleteRootNode(r1);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testDeleteNonRootNode() {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> r1 = smallGraph.createRootNode("R1");
+        GraphNode<String> c1 = smallGraph.createRootNode("C1");
+        r1.addChild(c1);
+
+        this.graph.deleteRootNode(c1);
+    }
+
+    @Test
+    public void testAddSharedChildWithMultipleThreads() throws Exception {
+
+        final DirectedAcyclicGraph<String> sharedChildGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        final int THREAD_COUNT = 150;
+        final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
+        final GraphNode<String> sharedChild = sharedChildGraph.createRootNode("shared child");
+        assertEquals(0, sharedChild.getParents().size());
+        assertEquals(1, sharedChildGraph.getRootNodes().size());
+
+        class AddChildThread extends Thread {
+
+            private final int counter;
+
+            public AddChildThread(int counter) {
+                this.counter = counter;
+            }
+
+            @Override
+            public void run() {
+                try {
+                    barrier.await(); // 1
+                    GraphNode<String> root = sharedChildGraph.createRootNode("root" + this.counter);
+                    root.addChild(sharedChild);
+                    barrier.await(); // 2
+                    barrier.await();
+                    assertTrue(root.removeChild(sharedChild));
+                    barrier.await(); // 3
+                    barrier.await();
+                    sharedChildGraph.deleteRootNode(root);
+                    barrier.await();
+                } catch (Exception e) {
+                    fail();
+                }
+            }
+        }
+
+        for (int i = 0; i < THREAD_COUNT; i++) {
+            new AddChildThread(i).start();
+        }
+        barrier.await(); // 1 - wait for all threads to be ready
+        barrier.await(); // 2 - wait for all threads to create and add the nodes
+        assertEquals(THREAD_COUNT, sharedChild.getParents().size());
+        assertEquals(THREAD_COUNT, sharedChildGraph.getRootNodes().size());
+        barrier.await(); //
+        barrier.await(); // 3 - wait for all threads to be finish
+        assertEquals(0, sharedChild.getParents().size());
+        assertEquals(THREAD_COUNT + 1, sharedChildGraph.getRootNodes().size());
+        barrier.await(); // wait for all threads to be finish
+        assertEquals(0, sharedChild.getParents().size());
+    }
+
+    @Test
+    public void testGraphWithSharedNodes() throws Exception {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> r1 = smallGraph.createRootNode("R1");
+        GraphNode<String> c1 = smallGraph.createRootNode("C1");
+        GraphNode<String> c2 = smallGraph.createRootNode("C2");
+        smallGraph.createRootNode("C3");
+        assertEquals(4, smallGraph.getRootNodes().size());
+        assertEquals("<R1<>, C1<>, C2<>, C3<>>", smallGraph.toString());
+
+        r1.addChild(c1);
+        assertEquals(3, smallGraph.getRootNodes().size());
+        r1.addChild(c2);
+        assertEquals(2, smallGraph.getRootNodes().size());
+        assertEquals("<R1<C1<>, C2<>>, C3<>>", smallGraph.toString());
+
+        GraphNode<String> r2 = smallGraph.createRootNode("R2");
+        assertEquals(3, smallGraph.getRootNodes().size());
+        assertEquals("<R1<C1<>, C2<>>, C3<>, R2<>>", smallGraph.toString());
+
+        r2.addChild(c1);
+        assertEquals(3, smallGraph.getRootNodes().size());
+        assertEquals("<R1<C1<>, C2<>>, C3<>, R2<C1<>>>", smallGraph.toString());
+    }
+
+    @Test
+    public void testDisassembleGraphWithSharedNodes() throws Exception {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> r1 = smallGraph.createRootNode("R1");
+        GraphNode<String> c1 = smallGraph.createRootNode("C1");
+        GraphNode<String> c2 = smallGraph.createRootNode("C2");
+        GraphNode<String> c3 = smallGraph.createRootNode("C3");
+        r1.addChild(c1);
+        r1.addChild(c2);
+        GraphNode<String> r2 = smallGraph.createRootNode("R2");
+        r2.addChild(c1);
+        assertEquals("<R1<C1<>, C2<>>, C3<>, R2<C1<>>>", smallGraph.toString());
+        assertEquals(3, smallGraph.getRootNodes().size());
+
+        // remove shared node
+        assertTrue(r2.removeChild(c1));
+        assertEquals("<R1<C1<>, C2<>>, C3<>, R2<>>", smallGraph.toString());
+        assertEquals(3, smallGraph.getRootNodes().size());
+        assertTrue(r1.removeChild(c2));
+        assertEquals(4, smallGraph.getRootNodes().size());
+        assertTrue(r1.removeChild(c1));
+        assertEquals(5, smallGraph.getRootNodes().size());
+        assertEquals("<R1<>, C1<>, C2<>, C3<>, R2<>>", smallGraph.toString());
+        assertTrue(smallGraph.deleteRootNode(r2));
+        assertEquals(4, smallGraph.getRootNodes().size());
+        assertEquals("<R1<>, C1<>, C2<>, C3<>>", smallGraph.toString());
+        assertTrue(smallGraph.deleteRootNode(r1));
+        assertEquals(3, smallGraph.getRootNodes().size());
+        assertEquals("<C1<>, C2<>, C3<>>", smallGraph.toString());
+        smallGraph.deleteRootNode(smallGraph.getRootNodes().get(0));
+        assertEquals(2, smallGraph.getRootNodes().size());
+        assertEquals("<C2<>, C3<>>", smallGraph.toString());
+        assertTrue(smallGraph.deleteRootNode(c2));
+        assertEquals(1, smallGraph.getRootNodes().size());
+        assertTrue(smallGraph.deleteRootNode(c3));
+        assertTrue(smallGraph.getRootNodes().isEmpty());
+    }
+
+    @Test
+    public void testRemovalOfAnAlreadyRemovedRootNode() throws Exception {
+        DirectedAcyclicGraph<String> smallGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> r1 = smallGraph.createRootNode("R1");
+
+        assertTrue(smallGraph.deleteRootNode(r1));
+
+        assertFalse(smallGraph.deleteRootNode(r1));
+    }
+
+    @Test
+    public void testHashCodeEquals() {
+        assertFalse(this.graph.equals(null));
+
+        assertFalse(this.graph.equals(new Object()));
+
+        DirectedAcyclicGraph<String> graph2 = getDAG();
+        assertEquals(this.graph.hashCode(), graph2.hashCode());
+        assertEquals(this.graph, this.graph);
+        assertEquals(graph2, this.graph);
+        assertEquals(this.graph, graph2);
+
+        DirectedAcyclicGraph<String> g1 = new ThreadSafeDirectedAcyclicGraph<String>();
+        assertFalse(this.graph.equals(g1));
+        assertFalse(g1.equals(this.graph));
+
+        assertTrue(new ThreadSafeDirectedAcyclicGraph<String>().equals(new ThreadSafeDirectedAcyclicGraph<String>()));
+    }
+
+}
diff --git a/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
new file mode 100644
index 0000000..8c9dc76
--- a/dev/null
+++ b/org.eclipse.virgo.util.common/src/test/java/org/eclipse/virgo/util/common/ThreadSafeGraphNodeTests.java
@@ -0,0 +1,601 @@
+/*******************************************************************************
+ * Copyright (c) 2008, 2010 VMware Inc.
+ * All rights reserved. This program and the accompanying materials
+ * are made available under the terms of the Eclipse Public License v1.0
+ * which accompanies this distribution, and is available at
+ * http://www.eclipse.org/legal/epl-v10.html
+ *
+ * Contributors:
+ *   VMware Inc. - initial contribution
+ *******************************************************************************/
+
+package org.eclipse.virgo.util.common;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.concurrent.CyclicBarrier;
+
+import org.eclipse.virgo.util.common.GraphNode.DirectedAcyclicGraphVisitor;
+import org.eclipse.virgo.util.common.GraphNode.ExceptionThrowingDirectedAcyclicGraphVisitor;
+import org.junit.Test;
+
+public class ThreadSafeGraphNodeTests {
+
+    private static void add(List<String> l, String... s) {
+        for (String string : s) {
+            l.add(string);
+        }
+    }
+
+    private static final List<String> EXPECTED_VISITS = new ArrayList<String>();
+
+    static {
+        add(EXPECTED_VISITS, "We", "Pa", "Cr", "B1", "Lo", "Fi", "Cu", "B2", "B3");
+    }
+
+    private GraphNode<String> buildTestGraphAndReturnRootNode() {
+        return buildTestGraphAndReturnRootNode(new ThreadSafeDirectedAcyclicGraph<String>());
+    }
+
+    private GraphNode<String> buildTestGraphAndReturnRootNode(DirectedAcyclicGraph<String> graph) {
+        return buildTestGraphAndReturnRootNode(graph, "We");
+    }
+
+    private GraphNode<String> buildTestGraphAndReturnRootNode(DirectedAcyclicGraph<String> graph, String rootValue) {
+        GraphNode<String> top = graph.createRootNode(rootValue);
+
+        // shared nodes
+        GraphNode<String> lo = graph.createRootNode("Lo");
+        GraphNode<String> fi = graph.createRootNode("Fi");
+
+        // We.add(Pa)
+        top.addChild(graph.createRootNode("Pa"));
+        GraphNode<String> pa = top.getChildren().get(0);
+        // Pa.add(Cr)
+        pa.addChild(graph.createRootNode("Cr"));
+        GraphNode<String> cr = pa.getChildren().get(0);
+        cr.addChild(graph.createRootNode("B1"));
+        cr.addChild(lo);
+        cr.addChild(fi);
+
+        // Pa.add(Cu)
+        pa.addChild(graph.createRootNode("Cu"));
+        GraphNode<String> cu = pa.getChildren().get(1);
+        cu.addChild(graph.createRootNode("B2"));
+        cu.addChild(lo);
+        cu.addChild(fi);
+
+        // Pa.add(B3)
+        pa.addChild(graph.createRootNode("B3"));
+        // Pa.add(Lo)
+        pa.addChild(lo);
+
+        return top;
+    }
+
+    private GraphNode<String> addFluffyToGraph(DirectedAcyclicGraph<String> graph) {
+        GraphNode<String> body = graph.createRootNode("Fluffy's body");
+        for (int i = 0; i < 3; i++) {
+            GraphNode<String> head = graph.createRootNode("head " + i);
+            head.addChild(body);
+        }
+        return body;
+    }
+
+    @Test
+    public void testEmptyNode() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> nullGraph = graph.createRootNode(null);
+
+        assertNull(nullGraph.getValue());
+        assertEquals("null<>", nullGraph.toString());
+    }
+
+    @Test
+    public void testDepthTwo() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> root = graph.createRootNode("root");
+
+        root.addChild(graph.createRootNode("C1"));
+        root.addChild(graph.createRootNode("C2"));
+
+        assertEquals("root<C1<>, C2<>>", root.toString());
+    }
+
+    @Test
+    public void testDepthThree() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> we = graph.createRootNode("We");
+        GraphNode<String> pa = graph.createRootNode("Pa");
+        GraphNode<String> cr = graph.createRootNode("Cr");
+
+        we.addChild(pa);
+        pa.addChild(cr);
+
+        assertEquals("We<Pa<Cr<>>>", we.toString());
+    }
+
+    @Test
+    public void testToString() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        assertEquals("null<>", graph.createRootNode(null).toString());
+
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        assertEquals("We<Pa<Cr<B1<>, Lo<>, Fi<>>, Cu<B2<>, Lo<>, Fi<>>, B3<>, Lo<>>>", top.toString());
+    }
+
+    @Test
+    public void testHashCodeEquals() {
+        DirectedAcyclicGraph<String> graphA = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> topA = graphA.createRootNode("root");
+
+        assertFalse(topA.equals(null));
+        assertFalse(topA.equals(new Object()));
+
+        DirectedAcyclicGraph<String> graphB = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> topB = graphB.createRootNode("root");
+
+        assertEquals(topA.hashCode(), topB.hashCode());
+        assertEquals(topB.hashCode(), topA.hashCode());
+
+        assertEquals(topA, topB);
+        assertEquals(topB, topA);
+
+        GraphNode<String> t1 = graphA.createRootNode("a");
+        {
+            GraphNode<String> a = t1;
+            assertFalse(topA.equals(a));
+            assertFalse(a.equals(topA));
+        }
+
+        {
+            GraphNode<String> a = graphA.createRootNode(null);
+            a.hashCode();
+            assertFalse(topA.equals(a));
+            assertFalse(a.equals(topA));
+        }
+
+        assertTrue(graphA.createRootNode(null).equals(graphA.createRootNode(null)));
+        assertFalse(graphA.createRootNode(null).equals(graphA.createRootNode("a")));
+        assertFalse(graphA.createRootNode("a").equals(graphA.createRootNode(null)));
+
+        GraphNode<String> t2 = graphA.createRootNode("b");
+        assertFalse(t1.equals(t2));
+        assertFalse(t2.equals(t1));
+    }
+
+    @Test
+    public void testSize() {
+        GraphNode<String> top = buildTestGraphAndReturnRootNode();
+
+        // (+1) Web shop application
+        // (+1) Payment application
+        // (+1) Credit card application
+        // (+3) B1, Logging Bundle, Financial Utils (Lo and Fi first time)
+        // (+1) Currency conversion application
+        // (+1) B2, Logging Bundle, Financial Utils (B2 only)
+        // (+1) B3
+        // (+0) Logging Bundle
+        assertEquals(9, top.size());
+    }
+
+    @Test
+    public void testSizeWithNullNodes() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> graphWithNullNodes = graph.createRootNode("with null values");
+        assertEquals(1, graphWithNullNodes.size());
+
+        graphWithNullNodes.addChild(graph.createRootNode("first"));
+        assertEquals(2, graphWithNullNodes.size());
+
+        graphWithNullNodes.addChild(graph.createRootNode(null));
+        assertEquals(3, graphWithNullNodes.size());
+
+        graphWithNullNodes.addChild(graph.createRootNode("third"));
+        assertEquals(4, graphWithNullNodes.size());
+    }
+
+    @Test
+    public void testSizeWithMultipleRoots() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> fluffy = addFluffyToGraph(graph);
+
+        assertEquals(1, fluffy.size());
+
+        List<GraphNode<String>> parents = fluffy.getParents();
+        for (GraphNode<String> parent : parents) {
+            assertEquals(2, parent.size());
+        }
+    }
+
+    @Test
+    public void testChildren() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        List<GraphNode<String>> children = top.getChildren();
+        assertEquals(1, children.size());
+        GraphNode<String> newChild = graph.createRootNode("newChild");
+
+        top.addChild(newChild);
+        assertEquals(2, children.size());
+        assertEquals(newChild, children.get(1));
+    }
+
+    @Test
+    public void testDAGWithNoChilds() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        GraphNode<String> solo = graph.createRootNode("solo");
+
+        assertNotNull(solo.getChildren());
+        assertTrue(solo.getChildren().isEmpty());
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testInstanceOfChild() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> child = new NoopGraphNode();
+
+        graph.createRootNode("foo").addChild(child);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testDuplicateInsertionOfAChild() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        buildTestGraphAndReturnRootNode(graph);
+
+        GraphNode<String> node = graph.getRootNodes().get(0);
+        GraphNode<String> child = graph.createRootNode("child");
+
+        node.addChild(child);
+        node.addChild(child);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testAddChildFromOtherDAG() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        DirectedAcyclicGraph<String> secondGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> alienNode = secondGraph.createRootNode("alien");
+
+        top.addChild(alienNode);
+    }
+
+    @Test
+    public void testAddSharedChild() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> cr = graph.createRootNode("cr");
+        GraphNode<String> cu = graph.createRootNode("cu");
+        GraphNode<String> lo = graph.createRootNode("lo");
+
+        cr.addChild(lo);
+        cu.addChild(lo);
+
+        assertEquals(2, lo.getParents().size());
+        assertTrue(lo.getParents().contains(cr));
+        assertTrue(lo.getParents().contains(cu));
+
+        // Ensure parents are correctly set up in both root nodes.
+        checkParents(Collections.singletonList(cr));
+        checkParents(Collections.singletonList(cu));
+    }
+
+    @Test
+    public void testAddSharedChildWithMultipleThreads() throws Exception {
+
+        final int THREAD_COUNT = 150;
+        final CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT + 1);
+        final DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        final GraphNode<String> sharedChild = graph.createRootNode("shared child");
+
+        class AddChildThread extends Thread {
+
+            private final int counter;
+
+            public AddChildThread(int counter) {
+                this.counter = counter;
+            }
+
+            @Override
+            public void run() {
+                try {
+                    barrier.await();
+                    GraphNode<String> root = graph.createRootNode("root" + this.counter);
+                    root.addChild(sharedChild);
+                    barrier.await();
+                } catch (Exception e) {
+                    fail();
+                }
+            }
+        }
+
+        for (int i = 0; i < THREAD_COUNT; i++) {
+            new AddChildThread(i).start();
+        }
+        barrier.await(); // wait for all threads to be ready
+        barrier.await(); // wait for all threads to be finish
+
+        assertEquals(THREAD_COUNT, sharedChild.getParents().size());
+    }
+
+    private void checkParents(List<GraphNode<String>> parents) {
+        for (GraphNode<String> parent : parents) {
+            List<GraphNode<String>> children = parent.getChildren();
+            for (GraphNode<String> child : children) {
+                assertTrue(child.getParents().contains(parent));
+                checkParents(Collections.singletonList(child));
+            }
+        }
+    }
+
+    @Test
+    public void testChildrenListModification() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        List<GraphNode<String>> children = top.getChildren();
+        assertEquals(1, children.size());
+
+        GraphNode<String> newChild = buildTestGraphAndReturnRootNode(graph, "newChild");
+        children.add(newChild);
+        assertEquals(2, children.size());
+        assertEquals(newChild, children.get(1));
+    }
+
+    @Test
+    public void testGetValue() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        assertEquals("We", top.getValue());
+    }
+
+    @Test
+    public void testRemoveChild() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        List<GraphNode<String>> children = top.getChildren();
+        assertTrue(top.removeChild(children.get(0)));
+
+        assertEquals(1, top.size());
+        assertFalse(top.removeChild(buildTestGraphAndReturnRootNode(graph, "unknownChild")));
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testRemoveWrongInstanceOfChild() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> child = new NoopGraphNode();
+
+        graph.createRootNode("foo").removeChild(child);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void testRemoveChildFromOtherDAG() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        DirectedAcyclicGraph<String> secondGraph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> alienNode = secondGraph.createRootNode("alien");
+
+        top.removeChild(alienNode);
+    }
+
+    @Test
+    public void testParent() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        List<GraphNode<String>> children = top.getChildren();
+        assertNotNull(top.getParents());
+        assertTrue(top.getParents().isEmpty());
+
+        GraphNode<String> child = children.get(0);
+        assertEquals(Collections.singletonList(top), child.getParents());
+        assertSame(top, child.getParents().get(0));
+
+        top.removeChild(child);
+        assertNotNull(child.getParents());
+        assertTrue(child.getParents().isEmpty());
+    }
+
+    @Test
+    public void testNormalVisit() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
+        top.visit(visitor);
+        assertTrue(EXPECTED_VISITS.equals(visitor.getVisited()));
+    }
+
+    @Test
+    public void testSkippedVisit() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
+        GraphNode<String> t = graph.createRootNode("-");
+        t.visit(visitor);
+        List<String> visited = visitor.getVisited();
+
+        assertEquals(1, visited.size());
+        assertEquals("-", visited.get(0));
+    }
+
+    @Test
+    public void testPartiallySkippedVisit() {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        TestDirectedAcyclicGraphVisitor visitor = new TestDirectedAcyclicGraphVisitor();
+        top.addChild(graph.createRootNode("-"));
+        GraphNode<String> t = top.getChildren().get(1);
+        t.addChild(graph.createRootNode("foo"));
+        t.addChild(graph.createRootNode("bar"));
+        assertEquals(12, top.size());
+
+        top.visit(visitor);
+
+        assertEquals(10, visitor.getVisited().size());
+    }
+
+    @Test
+    public void testNormalExceptionVisit() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+        top.visit(visitor);
+
+        assertEquals(EXPECTED_VISITS, visitor.getVisited());
+    }
+
+    @Test
+    public void testSkippedExceptionVisit() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+
+        TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+        GraphNode<String> t = graph.createRootNode("-");
+        t.visit(visitor);
+
+        List<String> visited = visitor.getVisited();
+        assertEquals(1, visited.size());
+        assertEquals("-", visited.get(0));
+    }
+
+    @Test
+    public void testPartiallySkippedDueToStopExceptionVisit() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+        top.addChild(graph.createRootNode("-"));
+        GraphNode<String> t = top.getChildren().get(1);
+        t.addChild(graph.createRootNode("foo"));
+        t.addChild(graph.createRootNode("bar"));
+        assertEquals(12, top.size());
+
+        top.visit(visitor);
+
+        assertEquals(10, visitor.getVisited().size());
+    }
+
+    @Test(expected = Exception.class)
+    public void testPartiallySkippedDueToExceptionExceptionVisit() throws Exception {
+        DirectedAcyclicGraph<String> graph = new ThreadSafeDirectedAcyclicGraph<String>();
+        GraphNode<String> top = buildTestGraphAndReturnRootNode(graph);
+
+        TestExceptionThrowingDirectedAcyclicGraphVisitor visitor = new TestExceptionThrowingDirectedAcyclicGraphVisitor();
+        top.addChild(graph.createRootNode("*"));
+        GraphNode<String> t = top.getChildren().get(1);
+        t.addChild(graph.createRootNode("foo"));
+        t.addChild(graph.createRootNode("bar"));
+
+        assertEquals(12, top.size());
+        try {
+            top.visit(visitor);
+        } finally {
+            assertEquals(10, visitor.getVisited().size());
+        }
+    }
+
+    private static class TestDirectedAcyclicGraphVisitor implements DirectedAcyclicGraphVisitor<String> {
+
+        private final List<String> visited = new ArrayList<String>();
+
+        @Override
+        public boolean visit(GraphNode<String> dag) {
+            String value = dag.getValue();
+            this.visited.add(value);
+            return !value.startsWith("-");
+        }
+
+        public List<String> getVisited() {
+            return this.visited;
+        }
+    }
+
+    private static class TestExceptionThrowingDirectedAcyclicGraphVisitor implements ExceptionThrowingDirectedAcyclicGraphVisitor<String, Exception> {
+
+        private final List<String> visited = new ArrayList<String>();
+
+        @Override
+        public boolean visit(GraphNode<String> dag) throws Exception {
+            String value = dag.getValue();
+            this.visited.add(value);
+            if (value.startsWith("*")) {
+                throw new Exception();
+            }
+            return !value.startsWith("-");
+        }
+
+        public List<String> getVisited() {
+            return this.visited;
+        }
+    }
+
+    protected static class NoopGraphNode implements GraphNode<String> {
+
+        @Override
+        public void visit(DirectedAcyclicGraphVisitor<String> visitor) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public <E extends Exception> void visit(ExceptionThrowingDirectedAcyclicGraphVisitor<String, E> visitor) throws E {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public void addChild(GraphNode<String> child) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public int size() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean removeChild(GraphNode<String> child) {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public List<GraphNode<String>> getChildren() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public List<GraphNode<String>> getParents() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public String getValue() {
+            throw new UnsupportedOperationException();
+        }
+
+        @Override
+        public boolean isRootNode() {
+            throw new UnsupportedOperationException();
+        }
+
+    }
+
+}