Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Foundation |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | package org.onlab.graph; |
| 17 | |
| 18 | import com.google.common.collect.ImmutableSet; |
| 19 | import com.google.common.collect.Lists; |
| 20 | import com.google.common.collect.Sets; |
| 21 | import org.slf4j.Logger; |
| 22 | |
| 23 | import java.util.ArrayList; |
| 24 | import java.util.Comparator; |
| 25 | import java.util.List; |
| 26 | import java.util.Set; |
| 27 | import java.util.TreeSet; |
| 28 | |
| 29 | import static com.google.common.base.Preconditions.checkArgument; |
| 30 | import static com.google.common.base.Preconditions.checkNotNull; |
| 31 | import static org.slf4j.LoggerFactory.getLogger; |
| 32 | |
| 33 | /** |
| 34 | * Runs K shortest paths algorithm on a provided directed graph. Returns results in the form of an |
| 35 | * InnerOrderedResult so iteration through the returned paths will return paths in ascending order according to the |
| 36 | * provided EdgeWeight. |
| 37 | */ |
| 38 | public class KShortestPathsSearch<V extends Vertex, E extends Edge<V>> extends AbstractGraphPathSearch<V, E> { |
| 39 | |
| 40 | private final Logger log = getLogger(getClass()); |
| 41 | |
| 42 | @Override |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 43 | protected Result<V, E> internalSearch(Graph<V, E> graph, V src, V dst, EdgeWeigher<V, E> weigher, int maxPaths) { |
| 44 | //The modified edge weigher removes any need to modify the original graph |
| 45 | InnerEdgeWeigher modifiedWeighter = new InnerEdgeWeigher(checkNotNull(weigher)); |
Aaron Kruglikov | f6aed99 | 2016-11-08 15:16:03 -0800 | [diff] [blame] | 46 | checkArgument(maxPaths != ALL_PATHS, "KShortestPath search cannot" + |
| 47 | "be used with ALL_PATHS."); |
| 48 | checkArgument(maxPaths > 0, "The max number of paths must be greater" + |
| 49 | " than 0"); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 50 | Graph<V, E> originalGraph = checkNotNull(graph); |
| 51 | //the result contains the set of eventual results |
| 52 | InnerOrderedResult result = new InnerOrderedResult(src, dst, maxPaths); |
| 53 | ArrayList<Path<V, E>> resultPaths = new ArrayList<>(maxPaths); |
| 54 | ArrayList<Path<V, E>> potentialPaths = Lists.newArrayList(); |
| 55 | |
| 56 | DijkstraGraphSearch<V, E> dijkstraSearch = new DijkstraGraphSearch<>(); |
| 57 | Set<Path<V, E>> dijkstraResults = dijkstraSearch.search(originalGraph, src, dst, modifiedWeighter, 1).paths(); |
| 58 | //Checks if the dst was reachable |
Jon Hall | cbd1b39 | 2017-01-18 20:15:44 -0800 | [diff] [blame] | 59 | if (dijkstraResults.isEmpty()) { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 60 | log.warn("No path was found."); |
| 61 | return result; |
| 62 | } |
| 63 | //If it was reachable adds the first shortest path to the set of results |
| 64 | resultPaths.add(dijkstraResults.iterator().next()); |
| 65 | |
| 66 | for (int k = 1; k < maxPaths; k++) { |
| 67 | |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 68 | for (int i = 0; i < resultPaths.get(k - 1).edges().size(); i++) { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 69 | V spurNode = resultPaths.get(k - 1).edges().get(i).src(); |
| 70 | List<E> rootPathEdgeList = resultPaths.get(k - 1).edges().subList(0, i); |
| 71 | |
| 72 | for (Path<V, E> path : resultPaths) { |
Koosha | 1525c45 | 2016-10-28 18:25:19 +0330 | [diff] [blame] | 73 | if (path.edges().size() >= i && edgeListsAreEqual(rootPathEdgeList, path.edges().subList(0, i))) { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 74 | modifiedWeighter.removedEdges.add(path.edges().get(i)); |
| 75 | } |
| 76 | } |
| 77 | |
| 78 | //Effectively remove all nodes from the source path |
| 79 | for (E edge : rootPathEdgeList) { |
| 80 | originalGraph.getEdgesFrom(edge.src()).forEach(e -> modifiedWeighter.removedEdges.add(e)); |
| 81 | originalGraph.getEdgesTo(edge.src()).forEach(e -> modifiedWeighter.removedEdges.add(e)); |
| 82 | } |
| 83 | |
| 84 | dijkstraResults = dijkstraSearch.search(originalGraph, spurNode, dst, modifiedWeighter, 1).paths(); |
Jon Hall | cbd1b39 | 2017-01-18 20:15:44 -0800 | [diff] [blame] | 85 | if (!dijkstraResults.isEmpty()) { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 86 | Path<V, E> spurPath = dijkstraResults.iterator().next(); |
| 87 | List<E> totalPath = new ArrayList<>(rootPathEdgeList); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 88 | spurPath.edges().forEach(totalPath::add); |
| 89 | //The following line must use the original weigher not the modified weigher because the modified |
| 90 | //weigher will count -1 values used for modifying the graph and return an inaccurate cost. |
Yuta HIGUCHI | c5a088c | 2017-03-30 19:07:07 -0700 | [diff] [blame] | 91 | potentialPaths.add(new DefaultPath<>(totalPath, |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 92 | calculatePathCost(weigher, totalPath))); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 93 | } |
| 94 | |
| 95 | //Restore all removed paths and nodes |
| 96 | modifiedWeighter.removedEdges.clear(); |
| 97 | } |
| 98 | if (potentialPaths.isEmpty()) { |
| 99 | break; |
| 100 | } |
| 101 | potentialPaths.sort(new InnerPathComparator()); |
| 102 | resultPaths.add(potentialPaths.get(0)); |
| 103 | potentialPaths.remove(0); |
| 104 | } |
| 105 | result.pathSet.addAll(resultPaths); |
| 106 | |
| 107 | return result; |
| 108 | } |
| 109 | //Edge list equality is judges by shared endpoints, and shared endpoints should be the same |
| 110 | private boolean edgeListsAreEqual(List<E> edgeListOne, List<E> edgeListTwo) { |
| 111 | if (edgeListOne.size() != edgeListTwo.size()) { |
| 112 | return false; |
| 113 | } |
| 114 | E edgeOne; |
| 115 | E edgeTwo; |
| 116 | for (int i = 0; i < edgeListOne.size(); i++) { |
| 117 | edgeOne = edgeListOne.get(i); |
| 118 | edgeTwo = edgeListTwo.get(i); |
| 119 | if (!edgeOne.equals(edgeTwo)) { |
| 120 | return false; |
| 121 | } |
| 122 | } |
| 123 | return true; |
| 124 | } |
| 125 | |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 126 | private Weight calculatePathCost(EdgeWeigher<V, E> weighter, List<E> edges) { |
| 127 | Weight totalCost = weighter.getInitialWeight(); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 128 | for (E edge : edges) { |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 129 | totalCost = totalCost.merge(weighter.weight(edge)); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 130 | } |
| 131 | return totalCost; |
| 132 | } |
| 133 | |
| 134 | /** |
| 135 | * Weights edges to make them inaccessible if set, otherwise returns the result of the original EdgeWeight. |
| 136 | */ |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 137 | private final class InnerEdgeWeigher implements EdgeWeigher<V, E> { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 138 | |
| 139 | private Set<E> removedEdges = Sets.newConcurrentHashSet(); |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 140 | private EdgeWeigher<V, E> innerEdgeWeigher; |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 141 | |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 142 | private InnerEdgeWeigher(EdgeWeigher<V, E> weigher) { |
| 143 | this.innerEdgeWeigher = weigher; |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 144 | } |
| 145 | |
| 146 | @Override |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 147 | public Weight weight(E edge) { |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 148 | if (removedEdges.contains(edge)) { |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 149 | return innerEdgeWeigher.getNonViableWeight(); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 150 | } |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 151 | return innerEdgeWeigher.weight(edge); |
| 152 | } |
| 153 | |
| 154 | @Override |
| 155 | public Weight getInitialWeight() { |
| 156 | return innerEdgeWeigher.getInitialWeight(); |
| 157 | } |
| 158 | |
| 159 | @Override |
| 160 | public Weight getNonViableWeight() { |
| 161 | return innerEdgeWeigher.getNonViableWeight(); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 162 | } |
| 163 | } |
| 164 | |
| 165 | /** |
| 166 | * A result modified to return paths ordered according to the provided comparator. |
| 167 | */ |
| 168 | protected class InnerOrderedResult extends DefaultResult { |
| 169 | |
| 170 | private TreeSet<Path<V, E>> pathSet = new TreeSet<>(new InnerPathComparator()); |
| 171 | |
| 172 | public InnerOrderedResult(V src, V dst) { |
| 173 | super(src, dst); |
| 174 | } |
| 175 | |
| 176 | public InnerOrderedResult(V src, V dst, int maxPaths) { |
| 177 | super(src, dst, maxPaths); |
| 178 | } |
| 179 | |
| 180 | @Override |
| 181 | public Set<Path<V, E>> paths() { |
| 182 | return ImmutableSet.copyOf(pathSet); |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | /** |
| 187 | * Provides a comparator to order the set of paths. |
| 188 | */ |
| 189 | private class InnerPathComparator implements Comparator<Path<V, E>> { |
| 190 | |
| 191 | @Override |
| 192 | public int compare(Path<V, E> pathOne, Path<V, E> pathTwo) { |
Andrey Komarov | 2398d96 | 2016-09-26 15:11:23 +0300 | [diff] [blame] | 193 | int comparisonValue = pathOne.cost().compareTo(pathTwo.cost()); |
Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 194 | if (comparisonValue != 0) { |
| 195 | return comparisonValue; |
| 196 | } else if (edgeListsAreEqual(pathOne.edges(), pathTwo.edges())) { |
| 197 | return 0; |
| 198 | } else { |
| 199 | return 1; |
| 200 | } |
| 201 | } |
| 202 | } |
| 203 | } |