SequenceForwardOrder { protected void assignDepth() { resetNodeInfo(); NodeData input = findInput(); input.depth = 0; List<NodeData> layer = new ArrayList<>(); List<NodeData> nextLayer = new ArrayList<>(); layer.addAll(input.next); for (int i = 0; i < input.next.size(); i++) { NodeData c = input.next.get(i); if( c.depth == Integer.MAX_VALUE ) { c.depth = 1; } else { throw new RuntimeException("Input node connects to a child node more than once! "+c.node.name); } } int depth = 1; while( !layer.isEmpty() ) { nextLayer.clear(); for (int i = 0; i < layer.size(); i++) { NodeData n = layer.get(i); for (int j = 0; j < n.next.size(); j++) { NodeData c = n.next.get(j); if( c.depth == Integer.MAX_VALUE ) { boolean allAssigned = true; for (int k = 0; k < c.previous.size(); k++) { if( c.previous.get(k).depth == Integer.MAX_VALUE ) { allAssigned = false; break; } } if( allAssigned ) { c.depth = depth + 1; nextLayer.add(c); } } } for (int j = 0; j < n.previous.size(); j++) { NodeData c = n.previous.get(j); if( c.depth == Integer.MAX_VALUE ) { throw new RuntimeException("An input to this node has not been traversed. Cycle or other graph error. "+c.node.name); } } } List<NodeData> tmp = layer; layer = nextLayer; nextLayer = tmp; depth++; } } SequenceForwardOrder(List<Node<?,?>> list ); List<Node<?,?>> putIntoForwardOrder();  }
@Test public void assignDepth_line() { for (int length = 1; length < 4; length++) { List<Node> ordered = createLineSequence(length); List<Node> shuffled = new ArrayList<>(ordered); Collections.shuffle(shuffled,rand); SequenceForwardOrder alg = new SequenceForwardOrder((List)shuffled); alg.assignDepth(); for (int j = 0; j < length; j++) { SequenceForwardOrder.NodeData d = alg.sequence.get(j); int expected = ordered.indexOf(d.node); assertEquals(expected,d.depth); } } }
@Test public void assignDepth_forked() { List<Node> ordered = createBranchA(); SequenceForwardOrder alg = new SequenceForwardOrder((List)ordered); alg.assignDepth(); assertEquals(0,alg.sequence.get(0).depth); assertEquals(1,alg.sequence.get(1).depth); assertEquals(1,alg.sequence.get(2).depth); assertEquals(2,alg.sequence.get(3).depth); assertEquals(3,alg.sequence.get(4).depth); assertEquals(4,alg.sequence.get(5).depth); }