Fixed an infinite loop bug in Suurballe graph path search.
Triggered by three edges between two vertices.
More work needed to address the remaining issues in the class implementation.
Change-Id: Ice1fa85f1b9213680e063e362db4d734d212f6f0
diff --git a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
index a5f3878..01f17efa 100644
--- a/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/AbstractGraphPathSearch.java
@@ -279,9 +279,12 @@
while (edges.hasNext()) {
E edge = edges.next();
boolean isLast = !edges.hasNext();
- DefaultMutablePath<V, E> pendingPath = isLast ? path : new DefaultMutablePath<>(path);
- pendingPath.insertEdge(edge);
- frontier.add(pendingPath);
+ // Exclude any looping paths
+ if (!isInPath(edge, path)) {
+ DefaultMutablePath<V, E> pendingPath = isLast ? path : new DefaultMutablePath<>(path);
+ pendingPath.insertEdge(edge);
+ frontier.add(pendingPath);
+ }
}
}
}
@@ -291,6 +294,18 @@
}
}
+ /**
+ * Indicates whether or not the specified edge source is already visited
+ * in the specified path.
+ *
+ * @param edge edge to test
+ * @param path path to test
+ * @return true if the edge.src() is a vertex in the path already
+ */
+ private boolean isInPath(E edge, DefaultMutablePath<V, E> path) {
+ return path.edges().stream().anyMatch(e -> edge.src().equals(e.dst()));
+ }
+
// Returns the first vertex of the specified path. This is either the source
// of the first edge or, if there are no edges yet, the given destination.
private V firstVertex(Path<V, E> path, V dst) {
diff --git a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
index f097b6b..f3d0e62 100644
--- a/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
+++ b/utils/misc/src/main/java/org/onlab/graph/SuurballeGraphSearch.java
@@ -16,6 +16,8 @@
package org.onlab.graph;
+import com.google.common.collect.Sets;
+
import java.util.ArrayList;
import java.util.Set;
import java.util.List;
@@ -34,13 +36,20 @@
@Override
public Result<V, E> search(Graph<V, E> graph, V src, V dst,
EdgeWeight<V, E> weight, int maxPaths) {
+ // FIXME: This method needs to be refactored as it is difficult to follow and debug.
+ // FIXME: There is a defect here triggered by 3+ edges between the same vertices,
+ // which makes an attempt to produce looping paths. Protection against
+ // this was added to AbstractGraphPathSearch, but the root issue remains here.
+
+ // FIXME: There is a defect here where not all paths are truly disjoint.
+ // This class needs to filter its own results to make sure that the
+ // paths are indeed disjoint. Temporary fix for this is provided, but
+ // the issue needs to be addressed through refactoring.
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);
@@ -50,49 +59,37 @@
if (firstDijkstraS.paths().size() == 0) {
return firstDijkstraS;
}
+
+ DisjointPathResult result = new DisjointPathResult(firstDijkstra, src, dst, maxPaths);
+
for (Path p: firstDijkstraS.paths()) {
shortPath = p;
//transforms the graph so tree edges have 0 weight
- 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> modified = edge ->
+ edge instanceof ReverseEdge ? 0 :
+ weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
EdgeWeight<V, E> modified2 = edge ->
weightf.weight(edge) + firstDijkstra.cost(edge.src()) - firstDijkstra.cost(edge.dst());
//create a residual graph g' by removing all src vertices and reversing 0 length path edges
- MutableGraph<V, Edge<V>> gt = mutableCopy(graph);
+ MutableGraph<V, E> gt = mutableCopy(graph);
- Map<Edge<V>, E> revToEdge = new HashMap<>();
+ Map<E, 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);
+ Edge<V> reverse = new ReverseEdge<V>(edge);
+ revToEdge.put((E) reverse, edge);
+ gt.addEdge((E) reverse);
}
//rerun dijkstra on the temporary graph to get a second path
- Result<V, Edge<V>> secondDijkstra;
- secondDijkstra = new DijkstraGraphSearch<V, Edge<V>>().search(gt, src, dst, modified, ALL_PATHS);
+ Result<V, E> secondDijkstra = new DijkstraGraphSearch<V, E>()
+ .search(gt, src, dst, modified, ALL_PATHS);
- Path<V, Edge<V>> residualShortPath = null;
+ Path<V, E> residualShortPath = null;
if (secondDijkstra.paths().size() == 0) {
- dpps.add(new DisjointPathPair<V, E>(shortPath, null));
+ result.dpps.add(new DisjointPathPair<>(shortPath, null));
continue;
}
@@ -109,85 +106,123 @@
if (residualShortPath != null) {
for (Edge<V> edge: residualShortPath.edges()) {
- if (classE().isInstance(edge)) {
- roundTrip.addEdge((E) edge);
- } else {
+ if (edge instanceof ReverseEdge) {
roundTrip.removeEdge(revToEdge.get(edge));
+ } else {
+ roundTrip.addEdge((E) edge);
}
}
}
//Actually build the final result
DefaultResult lastSearch = (DefaultResult) super.search(roundTrip, src, dst, weight, ALL_PATHS);
- Path<V, E> path1 = lastSearch.paths().iterator().next();
- path1.edges().forEach(roundTrip::removeEdge);
+ Path<V, E> primary = lastSearch.paths().iterator().next();
+ primary.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();
- }
+ Set<Path<V, E>> backups = super.search(roundTrip, src, dst, weight, ALL_PATHS).paths();
- 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) {
+ // Find first backup path that does not share any nodes with the primary
+ for (Path<V, E> backup : backups) {
+ if (isDisjoint(primary, backup)) {
+ result.dpps.add(new DisjointPathPair<>(primary, backup));
break;
}
}
- return pathsD;
}
- public Map<V, Double> costs() {
- return search.costs();
+ }
+
+ for (int i = result.dpps.size() - 1; i > 0; i--) {
+ if (result.dpps.get(i).size() <= 1) {
+ result.dpps.remove(i);
}
- public Map<V, Set<E>> parents() {
- return search.parents();
- }
- };
+ }
+
+ result.buildPaths();
+ return result;
}
- private Class<?> clazzV;
-
- public Class<?> classV() {
- return clazzV;
+ private boolean isDisjoint(Path<V, E> a, Path<V, E> b) {
+ return Sets.intersection(vertices(a), vertices(b)).isEmpty();
}
- private Class<?> clazzE;
-
- public Class<?> classE() {
- return clazzE;
+ private Set<V> vertices(Path<V, E> p) {
+ Set<V> set = new HashSet<>();
+ p.edges().forEach(e -> set.add(e.src()));
+ set.remove(p.src());
+ return set;
}
+
/**
* Creates a mutable copy of an immutable graph.
*
* @param graph immutable graph
* @return mutable copy
*/
- public MutableGraph mutableCopy(Graph<V, E> graph) {
- clazzV = graph.getVertexes().iterator().next().getClass();
- clazzE = graph.getEdges().iterator().next().getClass();
- return new MutableAdjacencyListsGraph<V, E>(graph.getVertexes(), graph.getEdges());
+ private MutableGraph<V, E> mutableCopy(Graph<V, E> graph) {
+ return new MutableAdjacencyListsGraph<>(graph.getVertexes(), graph.getEdges());
+ }
+
+ private static final class ReverseEdge<V extends Vertex> extends AbstractEdge<V> {
+ private ReverseEdge(Edge<V> edge) {
+ super(edge.dst(), edge.src());
+ }
+
+ @Override
+ public String toString() {
+ return "ReversedEdge " + "src=" + src() + " dst=" + dst();
+ }
+ }
+
+ // Auxiliary result for disjoint path search
+ private final class DisjointPathResult implements AbstractGraphPathSearch.Result<V, E> {
+
+ private final Result<V, E> searchResult;
+ private final V src, dst;
+ private final int maxPaths;
+ private final List<DisjointPathPair<V, E>> dpps = new ArrayList<>();
+ private final Set<Path<V, E>> disjointPaths = new HashSet<>();
+
+ private DisjointPathResult(Result<V, E> searchResult, V src, V dst, int maxPaths) {
+ this.searchResult = searchResult;
+ this.src = src;
+ this.dst = dst;
+ this.maxPaths = maxPaths;
+ }
+
+ @Override
+ public V src() {
+ return src;
+ }
+
+ @Override
+ public V dst() {
+ return dst;
+ }
+
+ @Override
+ public Set<Path<V, E>> paths() {
+ return disjointPaths;
+ }
+
+ private void buildPaths() {
+ int paths = 0;
+ for (DisjointPathPair<V, E> path: dpps) {
+ disjointPaths.add(path);
+ paths++;
+ if (paths == maxPaths) {
+ break;
+ }
+ }
+ }
+
+ @Override
+ public Map<V, Set<E>> parents() {
+ return searchResult.parents();
+ }
+
+ @Override
+ public Map<V, Double> costs() {
+ return searchResult.costs();
+ }
}
}