GraphUtil { public static Map<Node, Collection<Node>> getNodeMap( Set<Node> nodes, Map<Node, Collection<Edge>> edgeMap) { Deque<Edge> backtraceEdges = new LinkedList<>(); Set<Edge> cyclingEdges = new HashSet<>(); Set<Edge> resolvedEdges = new HashSet<>(); for (Collection<Edge> edges : edgeMap.values()) { for (Edge edge : edges) { _filterCyclingEdges( edge, edgeMap, backtraceEdges, cyclingEdges, resolvedEdges); } } Map<Node, Collection<Node>> nodeMap = new HashMap<>(); for (Edge edge : resolvedEdges) { Collection<Node> children = nodeMap.computeIfAbsent( edge.getFromNode(), node -> new HashSet<>()); Node toNode = edge.getToNode(); children.add(toNode); nodes.remove(toNode); } nodeMap.put(Node.ROOT_NODE, nodes); return nodeMap; }  static Map<Node, Collection<Node>> getNodeMap(
		Set<Node> nodes, Map<Node, Collection<Edge>> edgeMap);  }
@Test public void testIntersectingCycles() { Node node1 = new Node(1, 1); Node node2 = new Node(1, 2); Node node3 = new Node(1, 3); Node node4 = new Node(1, 4); Set<Node> nodes = new HashSet<>( Arrays.asList(node1, node2, node3, node4)); Map<Node, Collection<Node>> nodeMap = GraphUtil.getNodeMap( nodes, HashMapBuilder.<Node, Collection<Edge>>put( node1, Collections.singletonList(new Edge(node1, node2)) ).put( node2, Collections.singletonList(new Edge(node2, node3)) ).put( node3, Arrays.asList( new Edge(node3, node1), new Edge(node3, node2), new Edge(node3, node4)) ).put( node4, Collections.singletonList(new Edge(node4, node2)) ).build()); Assert.assertEquals( Collections.singleton(node3), nodeMap.remove(new Node(0, 0))); Assert.assertEquals( new HashSet<>(Arrays.asList(node1, node2, node4)), nodeMap.remove(node3)); Assert.assertEquals( Collections.singleton(node2), nodeMap.remove(node4)); Assert.assertTrue(nodeMap.toString(), nodeMap.isEmpty()); }
@Test public void testRoot() { Node node1 = new Node(1, 1); Node node2 = new Node(1, 2); Set<Node> nodes = new HashSet<>(Arrays.asList(node1, node2)); Map<Node, Collection<Node>> nodeMap = GraphUtil.getNodeMap( nodes, Collections.emptyMap()); Assert.assertEquals(nodeMap.toString(), 1, nodeMap.size()); Assert.assertEquals(nodes, nodeMap.get(new Node(0, 0))); }
@Test public void testSelfCycle() { Node node1 = new Node(1, 1); Map<Node, Collection<Node>> nodeMap = GraphUtil.getNodeMap( Collections.singleton(node1), Collections.singletonMap( node1, Collections.singletonList(new Edge(node1, node1)))); Assert.assertEquals( Collections.singleton(node1), nodeMap.remove(new Node(0, 0))); Assert.assertTrue(nodeMap.toString(), nodeMap.isEmpty()); }
@Test public void testSimpleCycle() { Node node1 = new Node(1, 1); Node node2 = new Node(1, 2); Set<Node> nodes = new HashSet<>(Arrays.asList(node1, node2)); Map<Node, Collection<Node>> nodeMap = GraphUtil.getNodeMap( nodes, HashMapBuilder.<Node, Collection<Edge>>put( node1, Collections.singletonList(new Edge(node1, node2)) ).put( node2, Collections.singletonList(new Edge(node2, node1)) ).build()); Assert.assertEquals( Collections.singleton(node2), nodeMap.remove(new Node(0, 0))); Assert.assertEquals( Collections.singleton(node1), nodeMap.remove(node2)); Assert.assertTrue(nodeMap.toString(), nodeMap.isEmpty()); }
@Test public void testTreeConverges() { Node node1 = new Node(1, 1); Node node2 = new Node(1, 2); Node node3 = new Node(1, 3); Node node4 = new Node(1, 4); Node node5 = new Node(1, 5); Set<Node> nodes = new HashSet<>( Arrays.asList(node1, node2, node3, node4, node5)); Map<Node, Collection<Node>> nodeMap = GraphUtil.getNodeMap( nodes, HashMapBuilder.<Node, Collection<Edge>>put( node1, Collections.singletonList(new Edge(node1, node2)) ).put( node2, Arrays.asList(new Edge(node2, node3), new Edge(node2, node4)) ).put( node3, Collections.singletonList(new Edge(node3, node4)) ).put( node4, Collections.singletonList(new Edge(node4, node5)) ).build()); Assert.assertEquals( Collections.singleton(node1), nodeMap.remove(new Node(0, 0))); Assert.assertEquals( Collections.singleton(node2), nodeMap.remove(node1)); Assert.assertEquals( new HashSet<>(Arrays.asList(node3, node4)), nodeMap.remove(node2)); Assert.assertEquals( Collections.singleton(node4), nodeMap.remove(node3)); Assert.assertEquals( Collections.singleton(node5), nodeMap.remove(node4)); Assert.assertTrue(nodeMap.toString(), nodeMap.isEmpty()); }