Tree example

class GraphNode<T> {
    T data
    Set<GraphNode> parents = []
    Set<GraphNode> children = []

    static GraphNode newRootNode() {
        new GraphNode(parents: emptySet())
    }

    void addParent(GraphNode parentNode) {
        parents << parentNode
    }

    void addParents(Iterable<GraphNode> parentNodes) {
        parents.addAll parentNodes
    }

    void addChild(GraphNode childNode) {
        children << childNode
    }

    void addChildren(Iterable<GraphNode> childNodes) {
        children.addAll childNodes
    }

    String toString() {
        new StringBuilder().with {
            append 'GraphNode(node: '
            append "${node.name}_${node.hashCode()}"
            append ', '
            append 'parents: '
            append "${parents*.node*.name}"
            append ', children: '
            append "${children*.node*.name}"
            append ')'
        }
    }
}

abstract class Graph {

    static trait NodeVisitor {
        void enter(GraphNode node) {}
        void visit(GraphNode node) {}
        void exit(GraphNode node) {}
    }

    /**
     * Visitor that detects cycles in graph structure during its traversal.
     */
    static class CycleDetector implements NodeVisitor {

        /**
         * Trail of the traversal.
         * Used for detecting cycles through searching duplicate nodes in the trail.
         */
        final Deque<GraphNode> trail = new LinkedList<>()

        /**
         * Add node to the trail if cycle is not detected.
         * @throws CyclicConnectionException if adding of this node to the trail introduces cycle
         */
        @Override
        void enter(GraphNode node) throws CyclicConnectionException {
            if (node in trail) { // cycle detected
                def cycle = []
                def peek
                while ((peek = trail.pop()) != node) { // while cycle origin not found
                    cycle << peek.data
                }
                cycle << node.data
                throw new CyclicConnectionException(cycle: cycle)
            }
            trail << node
        }

        /**
         * Remove node from the trail.
         */
        @Override
        void exit(GraphNode node) {
            trail.poll() // same as pop() without unchecked exception (just in case)
        }
    }

    private final Set<GraphNode> nodes = []
    private final GraphNode root = GraphNode.newRootNode()

    Graph(...domain data....) throws LinkException {
        buildGraph(domainData)
        def cycle = findCycle()
        if (cycle) {
            throw new CyclicConnectionException(cycle: cycle)
        }
    }

    protected abstract void buildGraph(...domain data....)

    /**
     * Find cycle in this graph.
     * @return list of nodes that form the cycle (sequence is preserved), empty list if no cycles were detected
     */
    @Ensures({ result != null })
    private List<Node> findCycle() {
        def cycleDetector = new CycleDetector()
        def cycle = []
        try {
            traverseDepthFirst([cycleDetector])
        } catch (CyclicConnectionException e) {
            cycle = e.cycle
        }
        return cycle
    }

    @Requires({ withVisitors != null })
    void traverseDepthFirst(Iterable<NodeVisitor> withVisitors) {
        visitNode(root, withVisitors)
    }

    /**
     * Visit node and all its children recursively in "depth-first" fashion.
     * Called first with root of the graph, traverses all the nodes.
     * @param node graph node to be visited
     * @param withVisitors visitors to be applied to the nodes
     */
    @Requires({ node && withVisitors != null })
    private void visitNode(GraphNode node, Iterable<NodeVisitor> withVisitors) {
        if (node != root) {
            withVisitors.each { it.enter node }
        }
        node.children.each { childNode -> visitNode childNode, withVisitors } // visit all children recursively first
        // after all children were visited, finish visiting this node
        if (node != root) {
            withVisitors.each { it.visit node }
            withVisitors.each { it.exit node }
        }
    }
}