@Test public void searchGraphWithNegativeCycles() { Set<TestVertex> vertexes = new HashSet<>(vertexes()); vertexes.add(Z); Set<TestEdge> edges = new HashSet<>(edges()); edges.add(new TestEdge(G, Z, 1.0)); edges.add(new TestEdge(Z, G, -2.0)); graph = new AdjacencyListsGraph<>(vertexes, edges); GraphPathSearch<TestVertex, TestEdge> search = graphSearch(); Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, H, weight, ALL_PATHS).paths(); assertEquals("incorrect paths count", 1, paths.size()); Path p = paths.iterator().next(); assertEquals("incorrect src", A, p.src()); assertEquals("incorrect dst", H, p.dst()); assertEquals("incorrect path length", 5, p.edges().size()); assertEquals("incorrect path cost", 5.0, p.cost(), 0.1); paths = search.search(graph, A, G, weight, ALL_PATHS).paths(); assertEquals("incorrect paths count", 0, paths.size()); paths = search.search(graph, A, null, weight, ALL_PATHS).paths(); printPaths(paths); assertEquals("incorrect paths count", 6, paths.size()); }
@Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, true); int max = graph.getVertexes().size() - 1; for (int i = 0; i < max; i++) { for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { result.relaxEdge(edge, result.cost(edge.src()), weight); } } } for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { if (result.relaxEdge(edge, result.cost(edge.src()), weight)) { result.removeVertex(edge.dst()); } } } result.buildPaths(); return result; }
BellmanFordGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, true); int max = graph.getVertexes().size() - 1; for (int i = 0; i < max; i++) { for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { result.relaxEdge(edge, result.cost(edge.src()), weight); } } } for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { if (result.relaxEdge(edge, result.cost(edge.src()), weight)) { result.removeVertex(edge.dst()); } } } result.buildPaths(); return result; } }
BellmanFordGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, true); int max = graph.getVertexes().size() - 1; for (int i = 0; i < max; i++) { for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { result.relaxEdge(edge, result.cost(edge.src()), weight); } } } for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { if (result.relaxEdge(edge, result.cost(edge.src()), weight)) { result.removeVertex(edge.dst()); } } } result.buildPaths(); return result; }  }
BellmanFordGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, true); int max = graph.getVertexes().size() - 1; for (int i = 0; i < max; i++) { for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { result.relaxEdge(edge, result.cost(edge.src()), weight); } } } for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { if (result.relaxEdge(edge, result.cost(edge.src()), weight)) { result.removeVertex(edge.dst()); } } } result.buildPaths(); return result; }  @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths); }
BellmanFordGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { checkArguments(graph, src, dst); DefaultResult result = new DefaultResult(src, dst, maxPaths); result.updateVertex(src, null, 0.0, true); int max = graph.getVertexes().size() - 1; for (int i = 0; i < max; i++) { for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { result.relaxEdge(edge, result.cost(edge.src()), weight); } } } for (E edge : graph.getEdges()) { if (result.hasCost(edge.src())) { if (result.relaxEdge(edge, result.cost(edge.src()), weight)) { result.removeVertex(edge.dst()); } } } result.buildPaths(); return result; }  @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths);  }