@Test public void testSingleNode() { final MutableUndirectedGraph<String> g = new MutableUndirectedGraph<>(); g.addNode("a"); final UndirectedGraph<String> mst = BoruvkaKruskal.compute(g, (edge) -> 0); assertEquals(1, mst.nodes().size()); assertEquals(0, mst.edges().size()); }
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);  }