Aaron Kruglikov | 07d8038 | 2015-12-07 16:54:37 -0800 | [diff] [blame] | 1 | /* |
Brian O'Connor | 5ab426f | 2016-04-09 01:19:45 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Laboratory |
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 |
| 43 | public Result<V, E> search(Graph<V, E> graph, V src, V dst, EdgeWeight<V, E> weight, int maxPaths) { |
| 44 | checkNotNull(src); |
| 45 | checkNotNull(dst); |
| 46 | //The modified edge weight removes any need to modify the original graph |
| 47 | InnerEdgeWeighter modifiedWeighter = new InnerEdgeWeighter(checkNotNull(weight)); |
| 48 | checkArgument(maxPaths > 0); |
| 49 | Graph<V, E> originalGraph = checkNotNull(graph); |
| 50 | //the result contains the set of eventual results |
| 51 | InnerOrderedResult result = new InnerOrderedResult(src, dst, maxPaths); |
| 52 | ArrayList<Path<V, E>> resultPaths = new ArrayList<>(maxPaths); |
| 53 | ArrayList<Path<V, E>> potentialPaths = Lists.newArrayList(); |
| 54 | |
| 55 | DijkstraGraphSearch<V, E> dijkstraSearch = new DijkstraGraphSearch<>(); |
| 56 | Set<Path<V, E>> dijkstraResults = dijkstraSearch.search(originalGraph, src, dst, modifiedWeighter, 1).paths(); |
| 57 | //Checks if the dst was reachable |
| 58 | if (dijkstraResults.size() == 0) { |
| 59 | log.warn("No path was found."); |
| 60 | return result; |
| 61 | } |
| 62 | //If it was reachable adds the first shortest path to the set of results |
| 63 | resultPaths.add(dijkstraResults.iterator().next()); |
| 64 | |
| 65 | for (int k = 1; k < maxPaths; k++) { |
| 66 | |
| 67 | for (int i = 0; i < (resultPaths.get(k - 1).edges().size() - 1); i++) { |
| 68 | V spurNode = resultPaths.get(k - 1).edges().get(i).src(); |
| 69 | List<E> rootPathEdgeList = resultPaths.get(k - 1).edges().subList(0, i); |
| 70 | |
| 71 | for (Path<V, E> path : resultPaths) { |
| 72 | if (edgeListsAreEqual(rootPathEdgeList, path.edges().subList(0, i))) { |
| 73 | modifiedWeighter.removedEdges.add(path.edges().get(i)); |
| 74 | } |
| 75 | } |
| 76 | |
| 77 | //Effectively remove all nodes from the source path |
| 78 | for (E edge : rootPathEdgeList) { |
| 79 | originalGraph.getEdgesFrom(edge.src()).forEach(e -> modifiedWeighter.removedEdges.add(e)); |
| 80 | originalGraph.getEdgesTo(edge.src()).forEach(e -> modifiedWeighter.removedEdges.add(e)); |
| 81 | } |
| 82 | |
| 83 | dijkstraResults = dijkstraSearch.search(originalGraph, spurNode, dst, modifiedWeighter, 1).paths(); |
| 84 | if (dijkstraResults.size() != 0) { |
| 85 | Path<V, E> spurPath = dijkstraResults.iterator().next(); |
| 86 | List<E> totalPath = new ArrayList<>(rootPathEdgeList); |
| 87 | spurPath.edges().forEach(e -> totalPath.add(e)); |
| 88 | //The following line must use the original weighter not the modified weighter because the modified |
| 89 | //weighter will count -1 values used for modifying the graph and return an inaccurate cost. |
| 90 | potentialPaths.add(new DefaultPath<V, E>(totalPath, |
| 91 | calculatePathCost(weight, totalPath))); |
| 92 | } |
| 93 | |
| 94 | //Restore all removed paths and nodes |
| 95 | modifiedWeighter.removedEdges.clear(); |
| 96 | } |
| 97 | if (potentialPaths.isEmpty()) { |
| 98 | break; |
| 99 | } |
| 100 | potentialPaths.sort(new InnerPathComparator()); |
| 101 | resultPaths.add(potentialPaths.get(0)); |
| 102 | potentialPaths.remove(0); |
| 103 | } |
| 104 | result.pathSet.addAll(resultPaths); |
| 105 | |
| 106 | return result; |
| 107 | } |
| 108 | //Edge list equality is judges by shared endpoints, and shared endpoints should be the same |
| 109 | private boolean edgeListsAreEqual(List<E> edgeListOne, List<E> edgeListTwo) { |
| 110 | if (edgeListOne.size() != edgeListTwo.size()) { |
| 111 | return false; |
| 112 | } |
| 113 | E edgeOne; |
| 114 | E edgeTwo; |
| 115 | for (int i = 0; i < edgeListOne.size(); i++) { |
| 116 | edgeOne = edgeListOne.get(i); |
| 117 | edgeTwo = edgeListTwo.get(i); |
| 118 | if (!edgeOne.equals(edgeTwo)) { |
| 119 | return false; |
| 120 | } |
| 121 | } |
| 122 | return true; |
| 123 | } |
| 124 | |
| 125 | private Double calculatePathCost(EdgeWeight<V, E> weighter, List<E> edges) { |
| 126 | Double totalCost = 0.0; |
| 127 | for (E edge : edges) { |
| 128 | totalCost += weighter.weight(edge); |
| 129 | } |
| 130 | return totalCost; |
| 131 | } |
| 132 | |
| 133 | /** |
| 134 | * Weights edges to make them inaccessible if set, otherwise returns the result of the original EdgeWeight. |
| 135 | */ |
| 136 | private class InnerEdgeWeighter implements EdgeWeight<V, E> { |
| 137 | |
| 138 | private Set<E> removedEdges = Sets.newConcurrentHashSet(); |
| 139 | private EdgeWeight<V, E> innerEdgeWeight; |
| 140 | |
| 141 | public InnerEdgeWeighter(EdgeWeight<V, E> weight) { |
| 142 | this.innerEdgeWeight = weight; |
| 143 | } |
| 144 | |
| 145 | @Override |
| 146 | public double weight(E edge) { |
| 147 | if (removedEdges.contains(edge)) { |
| 148 | //THIS RELIES ON THE LOCAL DIJKSTRA ALGORITHM AVOIDING NEGATIVES |
| 149 | return -1; |
| 150 | } else { |
| 151 | return innerEdgeWeight.weight(edge); |
| 152 | } |
| 153 | } |
| 154 | } |
| 155 | |
| 156 | /** |
| 157 | * A result modified to return paths ordered according to the provided comparator. |
| 158 | */ |
| 159 | protected class InnerOrderedResult extends DefaultResult { |
| 160 | |
| 161 | private TreeSet<Path<V, E>> pathSet = new TreeSet<>(new InnerPathComparator()); |
| 162 | |
| 163 | public InnerOrderedResult(V src, V dst) { |
| 164 | super(src, dst); |
| 165 | } |
| 166 | |
| 167 | public InnerOrderedResult(V src, V dst, int maxPaths) { |
| 168 | super(src, dst, maxPaths); |
| 169 | } |
| 170 | |
| 171 | @Override |
| 172 | public Set<Path<V, E>> paths() { |
| 173 | return ImmutableSet.copyOf(pathSet); |
| 174 | } |
| 175 | } |
| 176 | |
| 177 | /** |
| 178 | * Provides a comparator to order the set of paths. |
| 179 | */ |
| 180 | private class InnerPathComparator implements Comparator<Path<V, E>> { |
| 181 | |
| 182 | @Override |
| 183 | public int compare(Path<V, E> pathOne, Path<V, E> pathTwo) { |
| 184 | int comparisonValue = Double.compare(pathOne.cost(), pathTwo.cost()); |
| 185 | if (comparisonValue != 0) { |
| 186 | return comparisonValue; |
| 187 | } else if (edgeListsAreEqual(pathOne.edges(), pathTwo.edges())) { |
| 188 | return 0; |
| 189 | } else { |
| 190 | return 1; |
| 191 | } |
| 192 | } |
| 193 | } |
| 194 | } |