@Test public void onePath() { setWeights(); Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D), of(new TestEdge(A, B, 1), new TestEdge(B, C, 1), new TestEdge(A, C, 4), new TestEdge(C, D, 1))); GraphPathSearch.Result<TestVertex, TestEdge> result = graphSearch().search(graph, A, D, weight, GraphPathSearch.ALL_PATHS); Set<Path<TestVertex, TestEdge>> paths = result.paths(); assertEquals("incorrect paths count", 1, paths.size()); DisjointPathPair<TestVertex, TestEdge> dpp = (DisjointPathPair<TestVertex, TestEdge>) paths.iterator().next(); assertEquals("incorrect disjoint paths count", 1, dpp.size()); }
@Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (weight == null) { weight = edge -> 1; } List<DisjointPathPair<V, E>> dpps = new ArrayList<>(); final EdgeWeight weightf = weight; DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS); DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS); Path<V, E> shortPath = null; if (firstDijkstraS.paths().size() == 0) { return firstDijkstraS; } for (Path p: firstDijkstraS.paths()) { shortPath = p; EdgeWeight<V, Edge<V>> modified = edge -> { if (classE().isInstance(edge)) { return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); } return 0; }; EdgeWeight<V, E> modified2 = edge -> weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); MutableGraph<V, Edge<V>> gt = mutableCopy(graph); Map<Edge<V>, E> revToEdge = new HashMap<>(); graph.getEdgesTo(src).forEach(gt::removeEdge); for (E edge: shortPath.edges()) { gt.removeEdge(edge); Edge<V> reverse = new Edge<V>() { final Edge<V> orig = edge; public V src() { return orig.dst(); } public V dst() { return orig.src(); } public String toString() { return "ReversedEdge " + "src=" + src() + " dst=" + dst(); } }; revToEdge.put(reverse, edge); gt.addEdge(reverse); } Result<V, Edge<V>> secondDijkstra; secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS); Path<V, Edge<V>> residualShortPath = null; if (secondDijkstra.paths().size() == 0) { dpps.add(new DisjointPathPair<V, E>(shortPath, null)); continue; } for (Path p2: secondDijkstra.paths()) { residualShortPath = p2; MutableGraph<V, E> roundTrip = mutableCopy(graph); List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList()); tmp.forEach(roundTrip::removeEdge); shortPath.edges().forEach(roundTrip::addEdge); if (residualShortPath != null) { for (Edge<V> edge: residualShortPath.edges()) { if (classE().isInstance(edge)) { roundTrip.addEdge((E) edge); } else { roundTrip.removeEdge(revToEdge.get(edge)); } } } DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS); Path<V, E> path1 = lastSearch.paths().iterator().next(); path1.edges().forEach(roundTrip::removeEdge); Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths(); Path<V, E> backup = null; if (bckpaths.size() != 0) { backup = bckpaths.iterator().next(); } dpps.add(new DisjointPathPair<>(path1, backup)); } } for (int i = dpps.size() - 1; i > 0; i--) { if (dpps.get(i).size() <= 1) { dpps.remove(i); } } return new Result<V, E>() { final DefaultResult search = firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); int paths = 0; for (DisjointPathPair<V, E> path: dpps) { pathsD.add((Path<V, E>) path); paths++; if (paths == maxPaths) { break; } } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; }
SuurballeGraphSearch extends DijkstraGraphSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (weight == null) { weight = edge -> 1; } List<DisjointPathPair<V, E>> dpps = new ArrayList<>(); final EdgeWeight weightf = weight; DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS); DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS); Path<V, E> shortPath = null; if (firstDijkstraS.paths().size() == 0) { return firstDijkstraS; } for (Path p: firstDijkstraS.paths()) { shortPath = p; EdgeWeight<V, Edge<V>> modified = edge -> { if (classE().isInstance(edge)) { return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); } return 0; }; EdgeWeight<V, E> modified2 = edge -> weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); MutableGraph<V, Edge<V>> gt = mutableCopy(graph); Map<Edge<V>, E> revToEdge = new HashMap<>(); graph.getEdgesTo(src).forEach(gt::removeEdge); for (E edge: shortPath.edges()) { gt.removeEdge(edge); Edge<V> reverse = new Edge<V>() { final Edge<V> orig = edge; public V src() { return orig.dst(); } public V dst() { return orig.src(); } public String toString() { return "ReversedEdge " + "src=" + src() + " dst=" + dst(); } }; revToEdge.put(reverse, edge); gt.addEdge(reverse); } Result<V, Edge<V>> secondDijkstra; secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS); Path<V, Edge<V>> residualShortPath = null; if (secondDijkstra.paths().size() == 0) { dpps.add(new DisjointPathPair<V, E>(shortPath, null)); continue; } for (Path p2: secondDijkstra.paths()) { residualShortPath = p2; MutableGraph<V, E> roundTrip = mutableCopy(graph); List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList()); tmp.forEach(roundTrip::removeEdge); shortPath.edges().forEach(roundTrip::addEdge); if (residualShortPath != null) { for (Edge<V> edge: residualShortPath.edges()) { if (classE().isInstance(edge)) { roundTrip.addEdge((E) edge); } else { roundTrip.removeEdge(revToEdge.get(edge)); } } } DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS); Path<V, E> path1 = lastSearch.paths().iterator().next(); path1.edges().forEach(roundTrip::removeEdge); Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths(); Path<V, E> backup = null; if (bckpaths.size() != 0) { backup = bckpaths.iterator().next(); } dpps.add(new DisjointPathPair<>(path1, backup)); } } for (int i = dpps.size() - 1; i > 0; i--) { if (dpps.get(i).size() <= 1) { dpps.remove(i); } } return new Result<V, E>() { final DefaultResult search = firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); int paths = 0; for (DisjointPathPair<V, E> path: dpps) { pathsD.add((Path<V, E>) path); paths++; if (paths == maxPaths) { break; } } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; } }
SuurballeGraphSearch extends DijkstraGraphSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (weight == null) { weight = edge -> 1; } List<DisjointPathPair<V, E>> dpps = new ArrayList<>(); final EdgeWeight weightf = weight; DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS); DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS); Path<V, E> shortPath = null; if (firstDijkstraS.paths().size() == 0) { return firstDijkstraS; } for (Path p: firstDijkstraS.paths()) { shortPath = p; EdgeWeight<V, Edge<V>> modified = edge -> { if (classE().isInstance(edge)) { return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); } return 0; }; EdgeWeight<V, E> modified2 = edge -> weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); MutableGraph<V, Edge<V>> gt = mutableCopy(graph); Map<Edge<V>, E> revToEdge = new HashMap<>(); graph.getEdgesTo(src).forEach(gt::removeEdge); for (E edge: shortPath.edges()) { gt.removeEdge(edge); Edge<V> reverse = new Edge<V>() { final Edge<V> orig = edge; public V src() { return orig.dst(); } public V dst() { return orig.src(); } public String toString() { return "ReversedEdge " + "src=" + src() + " dst=" + dst(); } }; revToEdge.put(reverse, edge); gt.addEdge(reverse); } Result<V, Edge<V>> secondDijkstra; secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS); Path<V, Edge<V>> residualShortPath = null; if (secondDijkstra.paths().size() == 0) { dpps.add(new DisjointPathPair<V, E>(shortPath, null)); continue; } for (Path p2: secondDijkstra.paths()) { residualShortPath = p2; MutableGraph<V, E> roundTrip = mutableCopy(graph); List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList()); tmp.forEach(roundTrip::removeEdge); shortPath.edges().forEach(roundTrip::addEdge); if (residualShortPath != null) { for (Edge<V> edge: residualShortPath.edges()) { if (classE().isInstance(edge)) { roundTrip.addEdge((E) edge); } else { roundTrip.removeEdge(revToEdge.get(edge)); } } } DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS); Path<V, E> path1 = lastSearch.paths().iterator().next(); path1.edges().forEach(roundTrip::removeEdge); Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths(); Path<V, E> backup = null; if (bckpaths.size() != 0) { backup = bckpaths.iterator().next(); } dpps.add(new DisjointPathPair<>(path1, backup)); } } for (int i = dpps.size() - 1; i > 0; i--) { if (dpps.get(i).size() <= 1) { dpps.remove(i); } } return new Result<V, E>() { final DefaultResult search = firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); int paths = 0; for (DisjointPathPair<V, E> path: dpps) { pathsD.add((Path<V, E>) path); paths++; if (paths == maxPaths) { break; } } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; }  }
SuurballeGraphSearch extends DijkstraGraphSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (weight == null) { weight = edge -> 1; } List<DisjointPathPair<V, E>> dpps = new ArrayList<>(); final EdgeWeight weightf = weight; DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS); DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS); Path<V, E> shortPath = null; if (firstDijkstraS.paths().size() == 0) { return firstDijkstraS; } for (Path p: firstDijkstraS.paths()) { shortPath = p; EdgeWeight<V, Edge<V>> modified = edge -> { if (classE().isInstance(edge)) { return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); } return 0; }; EdgeWeight<V, E> modified2 = edge -> weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); MutableGraph<V, Edge<V>> gt = mutableCopy(graph); Map<Edge<V>, E> revToEdge = new HashMap<>(); graph.getEdgesTo(src).forEach(gt::removeEdge); for (E edge: shortPath.edges()) { gt.removeEdge(edge); Edge<V> reverse = new Edge<V>() { final Edge<V> orig = edge; public V src() { return orig.dst(); } public V dst() { return orig.src(); } public String toString() { return "ReversedEdge " + "src=" + src() + " dst=" + dst(); } }; revToEdge.put(reverse, edge); gt.addEdge(reverse); } Result<V, Edge<V>> secondDijkstra; secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS); Path<V, Edge<V>> residualShortPath = null; if (secondDijkstra.paths().size() == 0) { dpps.add(new DisjointPathPair<V, E>(shortPath, null)); continue; } for (Path p2: secondDijkstra.paths()) { residualShortPath = p2; MutableGraph<V, E> roundTrip = mutableCopy(graph); List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList()); tmp.forEach(roundTrip::removeEdge); shortPath.edges().forEach(roundTrip::addEdge); if (residualShortPath != null) { for (Edge<V> edge: residualShortPath.edges()) { if (classE().isInstance(edge)) { roundTrip.addEdge((E) edge); } else { roundTrip.removeEdge(revToEdge.get(edge)); } } } DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS); Path<V, E> path1 = lastSearch.paths().iterator().next(); path1.edges().forEach(roundTrip::removeEdge); Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths(); Path<V, E> backup = null; if (bckpaths.size() != 0) { backup = bckpaths.iterator().next(); } dpps.add(new DisjointPathPair<>(path1, backup)); } } for (int i = dpps.size() - 1; i > 0; i--) { if (dpps.get(i).size() <= 1) { dpps.remove(i); } } return new Result<V, E>() { final DefaultResult search = firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); int paths = 0; for (DisjointPathPair<V, E> path: dpps) { pathsD.add((Path<V, E>) path); paths++; if (paths == maxPaths) { break; } } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; }  @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths); Class<?> classV(); Class<?> classE(); MutableGraph mutableCopy(Graph<V, E> graph); }
SuurballeGraphSearch extends DijkstraGraphSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (weight == null) { weight = edge -> 1; } List<DisjointPathPair<V, E>> dpps = new ArrayList<>(); final EdgeWeight weightf = weight; DefaultResult firstDijkstraS = (DefaultResult) super.search(graph, src, dst, weight, ALL_PATHS); DefaultResult firstDijkstra = (DefaultResult) super.search(graph, src, null, weight, ALL_PATHS); Path<V, E> shortPath = null; if (firstDijkstraS.paths().size() == 0) { return firstDijkstraS; } for (Path p: firstDijkstraS.paths()) { shortPath = p; EdgeWeight<V, Edge<V>> modified = edge -> { if (classE().isInstance(edge)) { return weightf.weight((E) (edge)) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); } return 0; }; EdgeWeight<V, E> modified2 = edge -> weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst()); MutableGraph<V, Edge<V>> gt = mutableCopy(graph); Map<Edge<V>, E> revToEdge = new HashMap<>(); graph.getEdgesTo(src).forEach(gt::removeEdge); for (E edge: shortPath.edges()) { gt.removeEdge(edge); Edge<V> reverse = new Edge<V>() { final Edge<V> orig = edge; public V src() { return orig.dst(); } public V dst() { return orig.src(); } public String toString() { return "ReversedEdge " + "src=" + src() + " dst=" + dst(); } }; revToEdge.put(reverse, edge); gt.addEdge(reverse); } Result<V, Edge<V>> secondDijkstra; secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS); Path<V, Edge<V>> residualShortPath = null; if (secondDijkstra.paths().size() == 0) { dpps.add(new DisjointPathPair<V, E>(shortPath, null)); continue; } for (Path p2: secondDijkstra.paths()) { residualShortPath = p2; MutableGraph<V, E> roundTrip = mutableCopy(graph); List<E> tmp = roundTrip.getEdges().stream().collect(Collectors.toList()); tmp.forEach(roundTrip::removeEdge); shortPath.edges().forEach(roundTrip::addEdge); if (residualShortPath != null) { for (Edge<V> edge: residualShortPath.edges()) { if (classE().isInstance(edge)) { roundTrip.addEdge((E) edge); } else { roundTrip.removeEdge(revToEdge.get(edge)); } } } DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS); Path<V, E> path1 = lastSearch.paths().iterator().next(); path1.edges().forEach(roundTrip::removeEdge); Set<Path<V, E>> bckpaths = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths(); Path<V, E> backup = null; if (bckpaths.size() != 0) { backup = bckpaths.iterator().next(); } dpps.add(new DisjointPathPair<>(path1, backup)); } } for (int i = dpps.size() - 1; i > 0; i--) { if (dpps.get(i).size() <= 1) { dpps.remove(i); } } return new Result<V, E>() { final DefaultResult search = firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); int paths = 0; for (DisjointPathPair<V, E> path: dpps) { pathsD.add((Path<V, E>) path); paths++; if (paths == maxPaths) { break; } } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; }  @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths); Class<?> classV(); Class<?> classE(); MutableGraph mutableCopy(Graph<V, E> graph);  }