@Test public void testExample1() { final String[] nodes = {"1", "2", "3", "4"}; final FloydWarshallOutput<String> output = calculate( nodes, new Object[][]{ new Object[]{"1", "2", 1}, new Object[]{"2", "3", 2}, new Object[]{"3", "4", 3}, new Object[]{"4", "1", 4}, new Object[]{"4", "2", 7} } ); assertNoPath(output, "1", "XXX"); assertNoPath(output, "1", "XXX"); assertNoPath(output, "XXX", "1"); assertNoPath(output, "XXX", "XXX"); assertNoPath(output, "XXX", "YYY"); assertShortestPath(output, "1", "1", 0, Arrays.asList("1")); assertShortestPath(output, "1", "2", 1, Arrays.asList("1", "2")); assertShortestPath(output, "1", "3", 3, Arrays.asList("1", "2", "3")); assertShortestPath(output, "1", "4", 6, Arrays.asList("1", "2", "3", "4")); assertShortestPath(output, "2", "1", 9, Arrays.asList("2", "3", "4", "1")); assertShortestPath(output, "2", "2", 0, Arrays.asList("2")); assertShortestPath(output, "2", "3", 2, Arrays.asList("2", "3")); assertShortestPath(output, "2", "4", 5, Arrays.asList("2", "3", "4")); assertShortestPath(output, "3", "1", 7, Arrays.asList("3", "4", "1")); assertShortestPath(output, "3", "2", 8, Arrays.asList("3", "4", "2")); assertShortestPath(output, "3", "3", 0, Arrays.asList("3")); assertShortestPath(output, "3", "4", 3, Arrays.asList("3", "4")); assertShortestPath(output, "4", "1", 4, Arrays.asList("4", "1")); assertShortestPath(output, "4", "2", 5, Arrays.asList("4", "1", "2")); assertShortestPath(output, "4", "3", 7, Arrays.asList("4", "1", "2", "3")); assertShortestPath(output, "4", "4", 0, Arrays.asList("4")); }
public static <N, E> FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter) { final List<N> nodes = new ArrayList<>(graph.nodes()); final FloydWarshallMatrix<Integer, N> matrix = new FloydWarshallMatrix<>(nodes.size()); for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final N xNode = nodes.get(iX); final N yNode = nodes.get(iY); if (iX == iY) { matrix.setMinimumDistance(iX, iY, 0); matrix.setPredecessor(iX, iY, xNode); } else { final E edge = graph.edgeIncidentWithNodes(xNode, yNode); if (edge != null) { final int distance = weighter.applyAsInt(edge); matrix.setMinimumDistance(iX, iY, distance); matrix.setPredecessor(iX, iY, xNode); } } } } for (int iDetour = 0; iDetour < matrix.size(); iDetour++) { for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final Optional<Integer> detourPart1 = matrix.get(iX, iDetour); final Optional<Integer> detourPart2 = matrix.get(iDetour, iY); if (detourPart1.isPresent() && detourPart2.isPresent()) { final int detourDistance = detourPart1.get() + detourPart2.get(); final Optional<Integer> currentDistance = matrix.get(iX, iY); if (!currentDistance.isPresent() || detourDistance < currentDistance.get()) { final N detourNode = nodes.get(iDetour); matrix.setMinimumDistance(iX, iY, detourDistance); matrix.setPredecessor(iX, iY, detourNode); } } } } } return new FloydWarshallOutput<N>() { @Override public Optional<Integer> getMinimalDistance(final N a, final N b) { final int iA = nodes.indexOf(a); final int iB = nodes.indexOf(b); if (iA == -1 || iB == -1) { return Optional.empty(); } return matrix.get(iA, iB); } @Override public Optional<List<N>> getShortestPath(final N a, final N b) { final int iTarget = nodes.indexOf(a); int iStart = nodes.indexOf(b); if (iStart == -1 || iTarget == -1) { return Optional.empty(); } final List<N> result = new LinkedList<>(); while (true) { result.add(nodes.get(iStart)); if (iStart == iTarget) { Collections.reverse(result); return Optional.of(result); } final Optional<N> parent = matrix.getParent(iTarget, iStart); if (parent.isPresent()) { iStart = nodes.indexOf(parent.get()); } else { return Optional.empty(); } } } }; }
FloydWarshall { public static <N, E> FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter) { final List<N> nodes = new ArrayList<>(graph.nodes()); final FloydWarshallMatrix<Integer, N> matrix = new FloydWarshallMatrix<>(nodes.size()); for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final N xNode = nodes.get(iX); final N yNode = nodes.get(iY); if (iX == iY) { matrix.setMinimumDistance(iX, iY, 0); matrix.setPredecessor(iX, iY, xNode); } else { final E edge = graph.edgeIncidentWithNodes(xNode, yNode); if (edge != null) { final int distance = weighter.applyAsInt(edge); matrix.setMinimumDistance(iX, iY, distance); matrix.setPredecessor(iX, iY, xNode); } } } } for (int iDetour = 0; iDetour < matrix.size(); iDetour++) { for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final Optional<Integer> detourPart1 = matrix.get(iX, iDetour); final Optional<Integer> detourPart2 = matrix.get(iDetour, iY); if (detourPart1.isPresent() && detourPart2.isPresent()) { final int detourDistance = detourPart1.get() + detourPart2.get(); final Optional<Integer> currentDistance = matrix.get(iX, iY); if (!currentDistance.isPresent() || detourDistance < currentDistance.get()) { final N detourNode = nodes.get(iDetour); matrix.setMinimumDistance(iX, iY, detourDistance); matrix.setPredecessor(iX, iY, detourNode); } } } } } return new FloydWarshallOutput<N>() { @Override public Optional<Integer> getMinimalDistance(final N a, final N b) { final int iA = nodes.indexOf(a); final int iB = nodes.indexOf(b); if (iA == -1 || iB == -1) { return Optional.empty(); } return matrix.get(iA, iB); } @Override public Optional<List<N>> getShortestPath(final N a, final N b) { final int iTarget = nodes.indexOf(a); int iStart = nodes.indexOf(b); if (iStart == -1 || iTarget == -1) { return Optional.empty(); } final List<N> result = new LinkedList<>(); while (true) { result.add(nodes.get(iStart)); if (iStart == iTarget) { Collections.reverse(result); return Optional.of(result); } final Optional<N> parent = matrix.getParent(iTarget, iStart); if (parent.isPresent()) { iStart = nodes.indexOf(parent.get()); } else { return Optional.empty(); } } } }; } }
FloydWarshall { public static <N, E> FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter) { final List<N> nodes = new ArrayList<>(graph.nodes()); final FloydWarshallMatrix<Integer, N> matrix = new FloydWarshallMatrix<>(nodes.size()); for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final N xNode = nodes.get(iX); final N yNode = nodes.get(iY); if (iX == iY) { matrix.setMinimumDistance(iX, iY, 0); matrix.setPredecessor(iX, iY, xNode); } else { final E edge = graph.edgeIncidentWithNodes(xNode, yNode); if (edge != null) { final int distance = weighter.applyAsInt(edge); matrix.setMinimumDistance(iX, iY, distance); matrix.setPredecessor(iX, iY, xNode); } } } } for (int iDetour = 0; iDetour < matrix.size(); iDetour++) { for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final Optional<Integer> detourPart1 = matrix.get(iX, iDetour); final Optional<Integer> detourPart2 = matrix.get(iDetour, iY); if (detourPart1.isPresent() && detourPart2.isPresent()) { final int detourDistance = detourPart1.get() + detourPart2.get(); final Optional<Integer> currentDistance = matrix.get(iX, iY); if (!currentDistance.isPresent() || detourDistance < currentDistance.get()) { final N detourNode = nodes.get(iDetour); matrix.setMinimumDistance(iX, iY, detourDistance); matrix.setPredecessor(iX, iY, detourNode); } } } } } return new FloydWarshallOutput<N>() { @Override public Optional<Integer> getMinimalDistance(final N a, final N b) { final int iA = nodes.indexOf(a); final int iB = nodes.indexOf(b); if (iA == -1 || iB == -1) { return Optional.empty(); } return matrix.get(iA, iB); } @Override public Optional<List<N>> getShortestPath(final N a, final N b) { final int iTarget = nodes.indexOf(a); int iStart = nodes.indexOf(b); if (iStart == -1 || iTarget == -1) { return Optional.empty(); } final List<N> result = new LinkedList<>(); while (true) { result.add(nodes.get(iStart)); if (iStart == iTarget) { Collections.reverse(result); return Optional.of(result); } final Optional<N> parent = matrix.getParent(iTarget, iStart); if (parent.isPresent()) { iStart = nodes.indexOf(parent.get()); } else { return Optional.empty(); } } } }; }  }
FloydWarshall { public static <N, E> FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter) { final List<N> nodes = new ArrayList<>(graph.nodes()); final FloydWarshallMatrix<Integer, N> matrix = new FloydWarshallMatrix<>(nodes.size()); for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final N xNode = nodes.get(iX); final N yNode = nodes.get(iY); if (iX == iY) { matrix.setMinimumDistance(iX, iY, 0); matrix.setPredecessor(iX, iY, xNode); } else { final E edge = graph.edgeIncidentWithNodes(xNode, yNode); if (edge != null) { final int distance = weighter.applyAsInt(edge); matrix.setMinimumDistance(iX, iY, distance); matrix.setPredecessor(iX, iY, xNode); } } } } for (int iDetour = 0; iDetour < matrix.size(); iDetour++) { for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final Optional<Integer> detourPart1 = matrix.get(iX, iDetour); final Optional<Integer> detourPart2 = matrix.get(iDetour, iY); if (detourPart1.isPresent() && detourPart2.isPresent()) { final int detourDistance = detourPart1.get() + detourPart2.get(); final Optional<Integer> currentDistance = matrix.get(iX, iY); if (!currentDistance.isPresent() || detourDistance < currentDistance.get()) { final N detourNode = nodes.get(iDetour); matrix.setMinimumDistance(iX, iY, detourDistance); matrix.setPredecessor(iX, iY, detourNode); } } } } } return new FloydWarshallOutput<N>() { @Override public Optional<Integer> getMinimalDistance(final N a, final N b) { final int iA = nodes.indexOf(a); final int iB = nodes.indexOf(b); if (iA == -1 || iB == -1) { return Optional.empty(); } return matrix.get(iA, iB); } @Override public Optional<List<N>> getShortestPath(final N a, final N b) { final int iTarget = nodes.indexOf(a); int iStart = nodes.indexOf(b); if (iStart == -1 || iTarget == -1) { return Optional.empty(); } final List<N> result = new LinkedList<>(); while (true) { result.add(nodes.get(iStart)); if (iStart == iTarget) { Collections.reverse(result); return Optional.of(result); } final Optional<N> parent = matrix.getParent(iTarget, iStart); if (parent.isPresent()) { iStart = nodes.indexOf(parent.get()); } else { return Optional.empty(); } } } }; }  static FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter); }
FloydWarshall { public static <N, E> FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter) { final List<N> nodes = new ArrayList<>(graph.nodes()); final FloydWarshallMatrix<Integer, N> matrix = new FloydWarshallMatrix<>(nodes.size()); for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final N xNode = nodes.get(iX); final N yNode = nodes.get(iY); if (iX == iY) { matrix.setMinimumDistance(iX, iY, 0); matrix.setPredecessor(iX, iY, xNode); } else { final E edge = graph.edgeIncidentWithNodes(xNode, yNode); if (edge != null) { final int distance = weighter.applyAsInt(edge); matrix.setMinimumDistance(iX, iY, distance); matrix.setPredecessor(iX, iY, xNode); } } } } for (int iDetour = 0; iDetour < matrix.size(); iDetour++) { for (int iX = 0; iX < matrix.size(); iX++) { for (int iY = 0; iY < matrix.size(); iY++) { final Optional<Integer> detourPart1 = matrix.get(iX, iDetour); final Optional<Integer> detourPart2 = matrix.get(iDetour, iY); if (detourPart1.isPresent() && detourPart2.isPresent()) { final int detourDistance = detourPart1.get() + detourPart2.get(); final Optional<Integer> currentDistance = matrix.get(iX, iY); if (!currentDistance.isPresent() || detourDistance < currentDistance.get()) { final N detourNode = nodes.get(iDetour); matrix.setMinimumDistance(iX, iY, detourDistance); matrix.setPredecessor(iX, iY, detourNode); } } } } } return new FloydWarshallOutput<N>() { @Override public Optional<Integer> getMinimalDistance(final N a, final N b) { final int iA = nodes.indexOf(a); final int iB = nodes.indexOf(b); if (iA == -1 || iB == -1) { return Optional.empty(); } return matrix.get(iA, iB); } @Override public Optional<List<N>> getShortestPath(final N a, final N b) { final int iTarget = nodes.indexOf(a); int iStart = nodes.indexOf(b); if (iStart == -1 || iTarget == -1) { return Optional.empty(); } final List<N> result = new LinkedList<>(); while (true) { result.add(nodes.get(iStart)); if (iStart == iTarget) { Collections.reverse(result); return Optional.of(result); } final Optional<N> parent = matrix.getParent(iTarget, iStart); if (parent.isPresent()) { iStart = nodes.indexOf(parent.get()); } else { return Optional.empty(); } } } }; }  static FloydWarshallOutput calculate(final Graph<N, E> graph, final ToIntFunction<E> weighter);  }