Advertisement
dburyak

Tree example

Jun 28th, 2019
713
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Groovy 4.18 KB | None | 0 0
  1. class GraphNode<T> {
  2.     T data
  3.     Set<GraphNode> parents = []
  4.     Set<GraphNode> children = []
  5.  
  6.     static GraphNode newRootNode() {
  7.         new GraphNode(parents: emptySet())
  8.     }
  9.  
  10.     void addParent(GraphNode parentNode) {
  11.         parents << parentNode
  12.     }
  13.  
  14.     void addParents(Iterable<GraphNode> parentNodes) {
  15.         parents.addAll parentNodes
  16.     }
  17.  
  18.     void addChild(GraphNode childNode) {
  19.         children << childNode
  20.     }
  21.  
  22.     void addChildren(Iterable<GraphNode> childNodes) {
  23.         children.addAll childNodes
  24.     }
  25.  
  26.     String toString() {
  27.         new StringBuilder().with {
  28.             append 'GraphNode(node: '
  29.             append "${node.name}_${node.hashCode()}"
  30.             append ', '
  31.             append 'parents: '
  32.             append "${parents*.node*.name}"
  33.             append ', children: '
  34.             append "${children*.node*.name}"
  35.             append ')'
  36.         }
  37.     }
  38. }
  39.  
  40. abstract class Graph {
  41.  
  42.     static trait NodeVisitor {
  43.         void enter(GraphNode node) {}
  44.         void visit(GraphNode node) {}
  45.         void exit(GraphNode node) {}
  46.     }
  47.  
  48.     /**
  49.      * Visitor that detects cycles in graph structure during its traversal.
  50.      */
  51.     static class CycleDetector implements NodeVisitor {
  52.  
  53.         /**
  54.          * Trail of the traversal.
  55.          * Used for detecting cycles through searching duplicate nodes in the trail.
  56.          */
  57.         final Deque<GraphNode> trail = new LinkedList<>()
  58.  
  59.         /**
  60.          * Add node to the trail if cycle is not detected.
  61.          * @throws CyclicConnectionException if adding of this node to the trail introduces cycle
  62.          */
  63.         @Override
  64.         void enter(GraphNode node) throws CyclicConnectionException {
  65.             if (node in trail) { // cycle detected
  66.                 def cycle = []
  67.                 def peek
  68.                 while ((peek = trail.pop()) != node) { // while cycle origin not found
  69.                     cycle << peek.data
  70.                 }
  71.                 cycle << node.data
  72.                 throw new CyclicConnectionException(cycle: cycle)
  73.             }
  74.             trail << node
  75.         }
  76.  
  77.         /**
  78.          * Remove node from the trail.
  79.          */
  80.         @Override
  81.         void exit(GraphNode node) {
  82.             trail.poll() // same as pop() without unchecked exception (just in case)
  83.         }
  84.     }
  85.  
  86.     private final Set<GraphNode> nodes = []
  87.     private final GraphNode root = GraphNode.newRootNode()
  88.  
  89.     Graph(...domain data....) throws LinkException {
  90.         buildGraph(domainData)
  91.         def cycle = findCycle()
  92.         if (cycle) {
  93.             throw new CyclicConnectionException(cycle: cycle)
  94.         }
  95.     }
  96.  
  97.     protected abstract void buildGraph(...domain data....)
  98.  
  99.     /**
  100.      * Find cycle in this graph.
  101.      * @return list of nodes that form the cycle (sequence is preserved), empty list if no cycles were detected
  102.      */
  103.     @Ensures({ result != null })
  104.     private List<Node> findCycle() {
  105.         def cycleDetector = new CycleDetector()
  106.         def cycle = []
  107.         try {
  108.             traverseDepthFirst([cycleDetector])
  109.         } catch (CyclicConnectionException e) {
  110.             cycle = e.cycle
  111.         }
  112.         return cycle
  113.     }
  114.  
  115.     @Requires({ withVisitors != null })
  116.     void traverseDepthFirst(Iterable<NodeVisitor> withVisitors) {
  117.         visitNode(root, withVisitors)
  118.     }
  119.  
  120.     /**
  121.      * Visit node and all its children recursively in "depth-first" fashion.
  122.      * Called first with root of the graph, traverses all the nodes.
  123.      * @param node graph node to be visited
  124.      * @param withVisitors visitors to be applied to the nodes
  125.      */
  126.     @Requires({ node && withVisitors != null })
  127.     private void visitNode(GraphNode node, Iterable<NodeVisitor> withVisitors) {
  128.         if (node != root) {
  129.             withVisitors.each { it.enter node }
  130.         }
  131.         node.children.each { childNode -> visitNode childNode, withVisitors } // visit all children recursively first
  132.         // after all children were visited, finish visiting this node
  133.         if (node != root) {
  134.             withVisitors.each { it.visit node }
  135.             withVisitors.each { it.exit node }
  136.         }
  137.     }
  138. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement