@Test public void onePath() { setDefaultWeights(); TestEdge aB = new TestEdge(A, B, 1); TestEdge bC = new TestEdge(B, C, 1); TestEdge aD = new TestEdge(A, D, 1); TestEdge dC = new TestEdge(D, C, 1); Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D), of(aB, bC, aD, dC)); Map<TestEdge, Integer> riskProfile = new HashMap<>(); riskProfile.put(aB, 0); riskProfile.put(bC, 0); riskProfile.put(aD, 1); riskProfile.put(dC, 0); SrlgGraphSearch<TestVertex, TestEdge> search = new SrlgGraphSearch<>(2, riskProfile); Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths(); System.out.println(paths); assertTrue("no disjoint path pairs found", paths.size() == 0); }
@Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (maxPaths == ALL_PATHS) { maxPaths = POPSIZE; } if (useSuurballe) { return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS); } if (weight == null) { weight = edge -> 1; } checkArguments(graph, src, dst); orig = graph; this.src = src; this.dst = dst; this.weight = weight; List<Subset> best = new GAPopulation<Subset>() .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups])); Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>(); for (Subset s: best) { dpps.addAll(s.buildPaths()); } Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>() .search(orig, src, dst, weight, 1); return new Result<V, E>() { final DefaultResult search = (DefaultResult) firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); for (DisjointPathPair<V, E> path: dpps) { pathsD.add(path); } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; }
SrlgGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (maxPaths == ALL_PATHS) { maxPaths = POPSIZE; } if (useSuurballe) { return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS); } if (weight == null) { weight = edge -> 1; } checkArguments(graph, src, dst); orig = graph; this.src = src; this.dst = dst; this.weight = weight; List<Subset> best = new GAPopulation<Subset>() .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups])); Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>(); for (Subset s: best) { dpps.addAll(s.buildPaths()); } Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>() .search(orig, src, dst, weight, 1); return new Result<V, E>() { final DefaultResult search = (DefaultResult) firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); for (DisjointPathPair<V, E> path: dpps) { pathsD.add(path); } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; } }
SrlgGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (maxPaths == ALL_PATHS) { maxPaths = POPSIZE; } if (useSuurballe) { return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS); } if (weight == null) { weight = edge -> 1; } checkArguments(graph, src, dst); orig = graph; this.src = src; this.dst = dst; this.weight = weight; List<Subset> best = new GAPopulation<Subset>() .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups])); Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>(); for (Subset s: best) { dpps.addAll(s.buildPaths()); } Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>() .search(orig, src, dst, weight, 1); return new Result<V, E>() { final DefaultResult search = (DefaultResult) firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); for (DisjointPathPair<V, E> path: dpps) { pathsD.add(path); } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; } SrlgGraphSearch(int groups, Map<E, Integer> grouping);  SrlgGraphSearch(Map<E, Object> grouping); }
SrlgGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (maxPaths == ALL_PATHS) { maxPaths = POPSIZE; } if (useSuurballe) { return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS); } if (weight == null) { weight = edge -> 1; } checkArguments(graph, src, dst); orig = graph; this.src = src; this.dst = dst; this.weight = weight; List<Subset> best = new GAPopulation<Subset>() .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups])); Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>(); for (Subset s: best) { dpps.addAll(s.buildPaths()); } Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>() .search(orig, src, dst, weight, 1); return new Result<V, E>() { final DefaultResult search = (DefaultResult) firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); for (DisjointPathPair<V, E> path: dpps) { pathsD.add(path); } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; } SrlgGraphSearch(int groups, Map<E, Integer> grouping);  SrlgGraphSearch(Map<E, Object> grouping); @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths); }
SrlgGraphSearch extends AbstractGraphPathSearch<V, E> { @Override public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { if (maxPaths == ALL_PATHS) { maxPaths = POPSIZE; } if (useSuurballe) { return new SuurballeGraphSearch<V, E>().search(graph, src, dst, weight, ALL_PATHS); } if (weight == null) { weight = edge -> 1; } checkArguments(graph, src, dst); orig = graph; this.src = src; this.dst = dst; this.weight = weight; List<Subset> best = new GAPopulation<Subset>() .runGA(ITERATIONS, POPSIZE, maxPaths, new Subset(new boolean[numGroups])); Set<DisjointPathPair> dpps = new HashSet<DisjointPathPair>(); for (Subset s: best) { dpps.addAll(s.buildPaths()); } Result<V, E> firstDijkstra = new DijkstraGraphSearch<V, E>() .search(orig, src, dst, weight, 1); return new Result<V, E>() { final DefaultResult search = (DefaultResult) firstDijkstra; public V src() { return src; } public V dst() { return dst; } public Set<Path<V, E>> paths() { Set<Path<V, E>> pathsD = new HashSet<>(); for (DisjointPathPair<V, E> path: dpps) { pathsD.add(path); } return pathsD; } public Map<V, Double> costs() { return search.costs(); } public Map<V, Set<E>> parents() { return search.parents(); } }; } SrlgGraphSearch(int groups, Map<E, Integer> grouping);  SrlgGraphSearch(Map<E, Object> grouping); @Override Result<V, E> search(Graph<V, E> graph, V src, V dst,
                               EdgeWeight<V, E> weight, int maxPaths);  }