@Test public void testParentSubGraph() { DAG<Integer> dag = DAG.of(1, 2, 3); dag.add(4, 2, 3); dag.add(5, 4, 2); dag.add(6, 5, 3); DAG<Integer> oneSubgraph = dag.parentSubGraph(1); assertEquals(1, oneSubgraph.size()); Node<Integer> one = Iterables.getOnlyElement(oneSubgraph.getRoots()); assertEquals(new Integer(1), one.get()); assertEquals(0, one.getParents().size()); assertEquals(0, one.getChildren().size()); assertTrue(oneSubgraph.getLeafs().contains(new Node<>(1))); assertTrue(oneSubgraph.getRoots().contains(new Node<>(1))); DAG<Integer> sixSubgraph = dag.parentSubGraph(6); assertEquals(5, sixSubgraph.size()); Node<Integer> six = Iterables.getOnlyElement(sixSubgraph.getLeafs()); assertEquals(six, sixSubgraph.getNode(6)); assertEquals(new Integer(6), six.get()); assertEquals(2, six.getParents().size()); assertTrue(six.getParents().contains(new Node<>(5))); assertTrue(six.getParents().contains(new Node<>(3))); Node<Integer> five = sixSubgraph.getNode(5); assertEquals(2, five.getParents().size()); assertTrue(five.getParents().contains(new Node<>(2))); assertTrue(five.getParents().contains(new Node<>(4))); assertEquals(1, five.getChildren().size()); Node<Integer> four = sixSubgraph.getNode(4); assertEquals(2, four.getParents().size()); assertTrue(four.getParents().contains(new Node<>(2))); assertTrue(four.getParents().contains(new Node<>(3))); assertEquals(1, four.getChildren().size()); Node<Integer> three = sixSubgraph.getNode(3); assertEquals(0, three.getParents().size()); assertEquals(2, three.getChildren().size()); assertTrue(three.getChildren().contains(new Node<>(6))); assertTrue(three.getChildren().contains(new Node<>(4))); Node<Integer> two = sixSubgraph.getNode(2); assertEquals(0, two.getParents().size()); assertEquals(2, two.getChildren().size()); assertTrue(two.getChildren().contains(new Node<>(5))); assertTrue(two.getChildren().contains(new Node<>(4))); DAG<Integer> fiveSubgraph = dag.parentSubGraph(5); assertEquals(4, fiveSubgraph.size()); five = Iterables.getOnlyElement(fiveSubgraph.getLeafs()); assertEquals(five, fiveSubgraph.getNode(5)); assertEquals(new Integer(5), five.get()); assertEquals(2, five.getParents().size()); assertTrue(five.getParents().contains(new Node<>(2))); assertTrue(five.getParents().contains(new Node<>(4))); four = fiveSubgraph.getNode(4); assertEquals(2, four.getParents().size()); assertTrue(four.getParents().contains(new Node<>(2))); assertTrue(four.getParents().contains(new Node<>(3))); assertEquals(1, four.getChildren().size()); three = fiveSubgraph.getNode(3); assertEquals(0, three.getParents().size()); assertEquals(1, three.getChildren().size()); assertTrue(three.getChildren().contains(new Node<>(4))); two = fiveSubgraph.getNode(2); assertEquals(0, two.getParents().size()); assertEquals(2, two.getChildren().size()); assertTrue(two.getChildren().contains(new Node<>(5))); assertTrue(two.getChildren().contains(new Node<>(4))); }
public DAG<T> parentSubGraph(T elem) { DAG<T> ret = new DAG<>(); LinkedHashSet<Node<T>> nodeList = new LinkedHashSet<>(); LinkedList<Node<T>> notYetAdded = new LinkedList<>(); notYetAdded.add(getNode(elem)); while (!notYetAdded.isEmpty()) { Node<T> node = notYetAdded.pollLast(); nodeList.remove(node); nodeList.add(node); notYetAdded.addAll(node.parents); } LinkedList<Node<T>> reversedNodes = new LinkedList<>(); for (Node<T> n : nodeList) { reversedNodes.addFirst(n); } for (Node<T> node : reversedNodes) { List<T> parents = node.parents .stream().map(n -> n.value) .collect(Collectors.toList()); ret.add(node.value, parents); } return ret; }
DAG { public DAG<T> parentSubGraph(T elem) { DAG<T> ret = new DAG<>(); LinkedHashSet<Node<T>> nodeList = new LinkedHashSet<>(); LinkedList<Node<T>> notYetAdded = new LinkedList<>(); notYetAdded.add(getNode(elem)); while (!notYetAdded.isEmpty()) { Node<T> node = notYetAdded.pollLast(); nodeList.remove(node); nodeList.add(node); notYetAdded.addAll(node.parents); } LinkedList<Node<T>> reversedNodes = new LinkedList<>(); for (Node<T> n : nodeList) { reversedNodes.addFirst(n); } for (Node<T> node : reversedNodes) { List<T> parents = node.parents .stream().map(n -> n.value) .collect(Collectors.toList()); ret.add(node.value, parents); } return ret; } }
DAG { public DAG<T> parentSubGraph(T elem) { DAG<T> ret = new DAG<>(); LinkedHashSet<Node<T>> nodeList = new LinkedHashSet<>(); LinkedList<Node<T>> notYetAdded = new LinkedList<>(); notYetAdded.add(getNode(elem)); while (!notYetAdded.isEmpty()) { Node<T> node = notYetAdded.pollLast(); nodeList.remove(node); nodeList.add(node); notYetAdded.addAll(node.parents); } LinkedList<Node<T>> reversedNodes = new LinkedList<>(); for (Node<T> n : nodeList) { reversedNodes.addFirst(n); } for (Node<T> node : reversedNodes) { List<T> parents = node.parents .stream().map(n -> n.value) .collect(Collectors.toList()); ret.add(node.value, parents); } return ret; } private  DAG(); }
DAG { public DAG<T> parentSubGraph(T elem) { DAG<T> ret = new DAG<>(); LinkedHashSet<Node<T>> nodeList = new LinkedHashSet<>(); LinkedList<Node<T>> notYetAdded = new LinkedList<>(); notYetAdded.add(getNode(elem)); while (!notYetAdded.isEmpty()) { Node<T> node = notYetAdded.pollLast(); nodeList.remove(node); nodeList.add(node); notYetAdded.addAll(node.parents); } LinkedList<Node<T>> reversedNodes = new LinkedList<>(); for (Node<T> n : nodeList) { reversedNodes.addFirst(n); } for (Node<T> node : reversedNodes) { List<T> parents = node.parents .stream().map(n -> n.value) .collect(Collectors.toList()); ret.add(node.value, parents); } return ret; } private  DAG(); static DAG<T> empty(); @SuppressWarnings("unchecked") static DAG<T> of(T ...rootElements); static DAG<T> of(Iterable<T> rootElements); @SafeVarargs final DAG<T> add(T elem, T... parents); DAG<T> add(T elem, List<T> parents); Node<T> getNode(T elem); Collection<Node<T>> getRoots(); Collection<Node<T>> getLeafs(); DAG<T> parentSubGraph(T elem); int size(); Stream<T> nodes(); Stream<Node<T>> traverse(); @Override String toString(); }
DAG { public DAG<T> parentSubGraph(T elem) { DAG<T> ret = new DAG<>(); LinkedHashSet<Node<T>> nodeList = new LinkedHashSet<>(); LinkedList<Node<T>> notYetAdded = new LinkedList<>(); notYetAdded.add(getNode(elem)); while (!notYetAdded.isEmpty()) { Node<T> node = notYetAdded.pollLast(); nodeList.remove(node); nodeList.add(node); notYetAdded.addAll(node.parents); } LinkedList<Node<T>> reversedNodes = new LinkedList<>(); for (Node<T> n : nodeList) { reversedNodes.addFirst(n); } for (Node<T> node : reversedNodes) { List<T> parents = node.parents .stream().map(n -> n.value) .collect(Collectors.toList()); ret.add(node.value, parents); } return ret; } private  DAG(); static DAG<T> empty(); @SuppressWarnings("unchecked") static DAG<T> of(T ...rootElements); static DAG<T> of(Iterable<T> rootElements); @SafeVarargs final DAG<T> add(T elem, T... parents); DAG<T> add(T elem, List<T> parents); Node<T> getNode(T elem); Collection<Node<T>> getRoots(); Collection<Node<T>> getLeafs(); DAG<T> parentSubGraph(T elem); int size(); Stream<T> nodes(); Stream<Node<T>> traverse(); @Override String toString();  }