@Test public void testSingleEdge() { final Map<UndirectedGraph.Edge<String>, Integer> w = new HashMap<>(); final MutableUndirectedGraph<String> g = new MutableUndirectedGraph<>(); g.addNode("a"); g.addNode("b"); w.put(g.addEdge("a", "b"), 10); final UndirectedGraph<String> mst = JarnikPrim.compute(g, w::get); assertEquals(2, mst.nodes().size()); assertEquals(1, mst.edges().size()); assertTrue(mst.isSuccessor("a", "b")); assertEquals(10, mst.edges().stream().mapToInt(w::get).sum()); }
public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final MutableUndirectedGraph<N> result = new MutableUndirectedGraph<>(); if (!graph.nodes().isEmpty()) { result.addNode(graph.nodes().iterator().next()); while (result.nodes().size() < graph.nodes().size()) { final Optional<UndirectedGraph.Edge<N>> edgeToAddMaybe = graph .edges() .stream() .filter(edge -> { final N eitherNode = edge.either(); final N anotherNode = edge.another(); boolean p1 = result.nodes().contains(eitherNode) && !result.nodes().contains(anotherNode); boolean p2 = result.nodes().contains(anotherNode) && !result.nodes().contains(eitherNode); return p1 || p2; }) .min(Comparator.comparingInt(weighter)); if (!edgeToAddMaybe.isPresent()) { throw new IllegalArgumentException("Graph is not strongly connected."); } final N eitherNode = edgeToAddMaybe.get().either(); final N anotherNode = edgeToAddMaybe.get().another(); if (!result.nodes().contains(eitherNode)) { result.addNode(eitherNode); } if (!result.nodes().contains(anotherNode)) { result.addNode(anotherNode); } result.addEdge(eitherNode, anotherNode); } } return result; }
JarnikPrim { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final MutableUndirectedGraph<N> result = new MutableUndirectedGraph<>(); if (!graph.nodes().isEmpty()) { result.addNode(graph.nodes().iterator().next()); while (result.nodes().size() < graph.nodes().size()) { final Optional<UndirectedGraph.Edge<N>> edgeToAddMaybe = graph .edges() .stream() .filter(edge -> { final N eitherNode = edge.either(); final N anotherNode = edge.another(); boolean p1 = result.nodes().contains(eitherNode) && !result.nodes().contains(anotherNode); boolean p2 = result.nodes().contains(anotherNode) && !result.nodes().contains(eitherNode); return p1 || p2; }) .min(Comparator.comparingInt(weighter)); if (!edgeToAddMaybe.isPresent()) { throw new IllegalArgumentException("Graph is not strongly connected."); } final N eitherNode = edgeToAddMaybe.get().either(); final N anotherNode = edgeToAddMaybe.get().another(); if (!result.nodes().contains(eitherNode)) { result.addNode(eitherNode); } if (!result.nodes().contains(anotherNode)) { result.addNode(anotherNode); } result.addEdge(eitherNode, anotherNode); } } return result; } }
JarnikPrim { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final MutableUndirectedGraph<N> result = new MutableUndirectedGraph<>(); if (!graph.nodes().isEmpty()) { result.addNode(graph.nodes().iterator().next()); while (result.nodes().size() < graph.nodes().size()) { final Optional<UndirectedGraph.Edge<N>> edgeToAddMaybe = graph .edges() .stream() .filter(edge -> { final N eitherNode = edge.either(); final N anotherNode = edge.another(); boolean p1 = result.nodes().contains(eitherNode) && !result.nodes().contains(anotherNode); boolean p2 = result.nodes().contains(anotherNode) && !result.nodes().contains(eitherNode); return p1 || p2; }) .min(Comparator.comparingInt(weighter)); if (!edgeToAddMaybe.isPresent()) { throw new IllegalArgumentException("Graph is not strongly connected."); } final N eitherNode = edgeToAddMaybe.get().either(); final N anotherNode = edgeToAddMaybe.get().another(); if (!result.nodes().contains(eitherNode)) { result.addNode(eitherNode); } if (!result.nodes().contains(anotherNode)) { result.addNode(anotherNode); } result.addEdge(eitherNode, anotherNode); } } return result; }  }
JarnikPrim { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final MutableUndirectedGraph<N> result = new MutableUndirectedGraph<>(); if (!graph.nodes().isEmpty()) { result.addNode(graph.nodes().iterator().next()); while (result.nodes().size() < graph.nodes().size()) { final Optional<UndirectedGraph.Edge<N>> edgeToAddMaybe = graph .edges() .stream() .filter(edge -> { final N eitherNode = edge.either(); final N anotherNode = edge.another(); boolean p1 = result.nodes().contains(eitherNode) && !result.nodes().contains(anotherNode); boolean p2 = result.nodes().contains(anotherNode) && !result.nodes().contains(eitherNode); return p1 || p2; }) .min(Comparator.comparingInt(weighter)); if (!edgeToAddMaybe.isPresent()) { throw new IllegalArgumentException("Graph is not strongly connected."); } final N eitherNode = edgeToAddMaybe.get().either(); final N anotherNode = edgeToAddMaybe.get().another(); if (!result.nodes().contains(eitherNode)) { result.addNode(eitherNode); } if (!result.nodes().contains(anotherNode)) { result.addNode(anotherNode); } result.addEdge(eitherNode, anotherNode); } } return result; }  static UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter); }
JarnikPrim { public static <N> UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter) { final MutableUndirectedGraph<N> result = new MutableUndirectedGraph<>(); if (!graph.nodes().isEmpty()) { result.addNode(graph.nodes().iterator().next()); while (result.nodes().size() < graph.nodes().size()) { final Optional<UndirectedGraph.Edge<N>> edgeToAddMaybe = graph .edges() .stream() .filter(edge -> { final N eitherNode = edge.either(); final N anotherNode = edge.another(); boolean p1 = result.nodes().contains(eitherNode) && !result.nodes().contains(anotherNode); boolean p2 = result.nodes().contains(anotherNode) && !result.nodes().contains(eitherNode); return p1 || p2; }) .min(Comparator.comparingInt(weighter)); if (!edgeToAddMaybe.isPresent()) { throw new IllegalArgumentException("Graph is not strongly connected."); } final N eitherNode = edgeToAddMaybe.get().either(); final N anotherNode = edgeToAddMaybe.get().another(); if (!result.nodes().contains(eitherNode)) { result.addNode(eitherNode); } if (!result.nodes().contains(anotherNode)) { result.addNode(anotherNode); } result.addEdge(eitherNode, anotherNode); } } return result; }  static UndirectedGraph<N> compute(final UndirectedGraph<N> graph, final ToIntFunction<UndirectedGraph.Edge<N>> weighter);  }