@Test public void testRegularCase() { final Map<UndirectedGraph.Edge<String>, Integer> w = new HashMap<>(); final MutableUndirectedGraph<String> g = new MutableUndirectedGraph<>(); Arrays.asList("a", "b", "c", "d", "e", "f").forEach(g::addNode); w.put(g.addEdge("a", "b"), 5); w.put(g.addEdge("b", "d"), 2); w.put(g.addEdge("b", "f"), 3); w.put(g.addEdge("b", "c"), 1); w.put(g.addEdge("b", "e"), 3); w.put(g.addEdge("d", "f"), 9); w.put(g.addEdge("d", "e"), 1); final UndirectedGraph<String> mst = BoruvkaKruskal.compute(g, w::get); assertEquals(6, mst.nodes().size()); assertEquals(5, mst.edges().size()); assertTrue(mst.isSuccessor("a", "b")); assertTrue(mst.isSuccessor("b", "c")); assertTrue(mst.isSuccessor("b", "d")); assertTrue(mst.isSuccessor("b", "f")); assertTrue(mst.isSuccessor("d", "e")); assertEquals(12, mst.edges().stream().mapToInt(w::get).sum()); }
public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final List<UndirectedGraph.Edge<N>> sortedEdges = graph .edges() .stream() .sorted(Comparator.comparingInt(weighter)) .collect(Collectors.toList()); final MutableUndirectedGraph<N> minimumSpanningTree = new MutableUndirectedGraph<>(); graph.nodes().forEach(minimumSpanningTree::addNode); sortedEdges .stream() .filter(edge -> !isReachable(minimumSpanningTree, edge.either(), edge.another())) .forEach(edge -> minimumSpanningTree.addEdge(edge.either(), edge.another())); return minimumSpanningTree; }
BoruvkaKruskal { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final List<UndirectedGraph.Edge<N>> sortedEdges = graph .edges() .stream() .sorted(Comparator.comparingInt(weighter)) .collect(Collectors.toList()); final MutableUndirectedGraph<N> minimumSpanningTree = new MutableUndirectedGraph<>(); graph.nodes().forEach(minimumSpanningTree::addNode); sortedEdges .stream() .filter(edge -> !isReachable(minimumSpanningTree, edge.either(), edge.another())) .forEach(edge -> minimumSpanningTree.addEdge(edge.either(), edge.another())); return minimumSpanningTree; } }
BoruvkaKruskal { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final List<UndirectedGraph.Edge<N>> sortedEdges = graph .edges() .stream() .sorted(Comparator.comparingInt(weighter)) .collect(Collectors.toList()); final MutableUndirectedGraph<N> minimumSpanningTree = new MutableUndirectedGraph<>(); graph.nodes().forEach(minimumSpanningTree::addNode); sortedEdges .stream() .filter(edge -> !isReachable(minimumSpanningTree, edge.either(), edge.another())) .forEach(edge -> minimumSpanningTree.addEdge(edge.either(), edge.another())); return minimumSpanningTree; }  }
BoruvkaKruskal { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final List<UndirectedGraph.Edge<N>> sortedEdges = graph .edges() .stream() .sorted(Comparator.comparingInt(weighter)) .collect(Collectors.toList()); final MutableUndirectedGraph<N> minimumSpanningTree = new MutableUndirectedGraph<>(); graph.nodes().forEach(minimumSpanningTree::addNode); sortedEdges .stream() .filter(edge -> !isReachable(minimumSpanningTree, edge.either(), edge.another())) .forEach(edge -> minimumSpanningTree.addEdge(edge.either(), edge.another())); return minimumSpanningTree; }  static UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter); }
BoruvkaKruskal { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final List<UndirectedGraph.Edge<N>> sortedEdges = graph .edges() .stream() .sorted(Comparator.comparingInt(weighter)) .collect(Collectors.toList()); final MutableUndirectedGraph<N> minimumSpanningTree = new MutableUndirectedGraph<>(); graph.nodes().forEach(minimumSpanningTree::addNode); sortedEdges .stream() .filter(edge -> !isReachable(minimumSpanningTree, edge.either(), edge.another())) .forEach(edge -> minimumSpanningTree.addEdge(edge.either(), edge.another())); return minimumSpanningTree; }  static UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter);  }