Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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 }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement