Created a shortest path finder that must pass via sets of intermediary edges (either one in each set counts as a pass) in order.
Primarily I would like to know if there are logical fallacies in the ShortestPathViaFinder. I built it as a label-based breadth first search.
Made for Java 7.
Example: in the graph with vertexes A-E and edges 1-6 (with cost 1-6 also):
1-B-4
/ \
A-2-C-5-E
\ /
3-D-6
Searching A - E via { { 2 , 3 } , { 5 , 6 } } should give the result { 2 , 5 } since that path is cheaper than { 3 , 6 } even though that is also a valid path (as is { 2 , 5 , 6 , 6 } and { 3 , 3 , 1 , 4 , 5 , 5 } etc).
Graph / Vertex / Edge cannot be changed as they are already in use.
ShortestPathViaFinder.java
import java.util.*;
public class ShortestPathViaFinder<V, E> {
/**
* Finds a path between from and to passing at least one item in each via list in order.
* @param graph The graph, must have positive lengths.
* @param from Starting node.
* @param via List of intermediary edges that must be visited in order,
* any one of the items in the interior list will fulfill the visited status.
* @param to End node.
* @return List of edges describing best path or null if no valid path found.
*/
public List<E> visitEdges(final Graph<V, E> graph, V from, List<List<E>> via, V to) {
final VisitedNodes visitedNodes = new VisitedNodes(graph);
final VisitsNode startNode = visitedNodes.visits(from);
final VisitsLabel startLabel = startNode.addLabel(0, 0, null, null);
PriorityQueue<VisitsLabel> labels = new PriorityQueue<>(11,
new Comparator<VisitsLabel>() {
@Override
public int compare(VisitsLabel o1, VisitsLabel o2) {
return Double.compare(o1.cost, o2.cost);
}
}
);
labels.add(startLabel);
double best = Double.MAX_VALUE;
VisitsLabel bestSolution = null;
while (!labels.isEmpty() && labels.peek().cost < best) {
final VisitsLabel label = labels.poll();
for (Edge<E, V> edge : label.owner.outgoingEdges) {
VisitsNode visitsNode = visitedNodes.visits(edge.getDestination().getRef());
int visits = label.visits;
if (visits < via.size() && via.get(visits).contains(edge.getRef())) {
++visits;
}
final VisitsLabel visitsLabel = visitsNode.addLabel(label.cost + edge.getLength(), visits, label, edge);
if (visitsLabel != null) {
labels.add(visitsLabel);
if (visits == via.size() && edge.getDestination().getRef().equals(to)) {
bestSolution = visitsLabel;
best = bestSolution.cost;
}
}
}
}
if (bestSolution == null) {
return null;
}
VisitsLabel tail = bestSolution;
LinkedList<E> edges = new LinkedList<>();
while (tail.ingoingEdge != null) {
edges.addFirst(tail.ingoingEdge.getRef());
tail = tail.previousLabel;
}
return edges;
}
private class VisitedNodes {
final Graph<V, E> graph;
final Map<V, VisitsNode> visitedNodes = new HashMap<>();
VisitedNodes(Graph<V, E> graph) {
this.graph = graph;
}
VisitsNode visits(V node) {
VisitsNode visitsNode = visitedNodes.get(node);
if (visitsNode == null) {
visitsNode = new VisitsNode(node, graph.getVertex(node).getOutgoingEdges());
visitedNodes.put(node, visitsNode);
}
return visitsNode;
}
}
private class VisitsNode {
final V node;
final List<VisitsLabel> labels = new LinkedList<>();
final Collection<Edge<E, V>> outgoingEdges;
VisitsNode(V node, Collection<Edge<E, V>> outgoingEdges) {
this.node = node;
this.outgoingEdges = outgoingEdges;
}
VisitsLabel addLabel(double cost, int visits, VisitsLabel previousLabel, Edge<E, V> ingoingEdge) {
final Iterator<VisitsLabel> labelIterator = labels.iterator();
boolean better = false;
while (labelIterator.hasNext()) {
final VisitsLabel label = labelIterator.next();
if (label.dominated(cost, visits)) {
labelIterator.remove();
} else if (label.worse(cost, visits)) {
better = true;
}
}
if (labels.isEmpty() || better) {
final VisitsLabel newLabel = new VisitsLabel(cost, visits, this, previousLabel, ingoingEdge);
labels.add(newLabel);
return newLabel;
}
return null;
}
}
private class VisitsLabel {
final double cost;
final int visits;
final VisitsNode owner;
final VisitsLabel previousLabel;
final Edge<E, V> ingoingEdge;
VisitsLabel(double cost, int visits, VisitsNode owner, VisitsLabel previousLabel, Edge<E, V> ingoingEdge) {
this.cost = cost;
this.visits = visits;
this.owner = owner;
this.ingoingEdge = ingoingEdge;
this.previousLabel = previousLabel;
}
boolean dominated(double cost, int visits) {
return this.costlier(cost) && this.visits <= visits;
}
boolean worse(double cost, int visits) {
return this.costlier(cost) || this.visits < visits;
}
private boolean costlier(double cost) {
return this.cost > cost;
}
}
}
Graph.java
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.Map;
public class Graph<V, E> {
private Map<V, Vertex<V, E>> vertices = new LinkedHashMap<>();
private Map<E, Edge<E, V>> edges = new LinkedHashMap<>();
public Vertex<V, E> buildVertex(V ref) {
if (!vertices.containsKey(ref)) {
vertices.put(ref, newVertex(ref));
}
return vertices.get(ref);
}
// Create edge and vertices
public Graph<V, E> buildEdge(E ref, V refSource, V refDestination, double length) {
if (!edges.containsKey(ref)) {
Vertex<V, E> source = buildVertex(refSource);
Vertex<V, E> destination = buildVertex(refDestination);
Edge<E, V> edge = newEdge(ref, source, destination, length);
edges.put(ref, edge);
}
return this;
}
// Assume vertices have already been added (with buildVertex)
public Graph<V, E> addEdge(E ref, V refSource, V refDestination, double length) {
if (!edges.containsKey(ref)) {
Vertex<V, E> source = getVertex(refSource);
Vertex<V, E> destination = getVertex(refDestination);
Edge<E, V> edge = Graphs.newEdge(ref, source, destination, length);
edges.put(ref, edge);
}
return this;
}
// lightweight version - no checks performed and vertices must be given
public Graph<V, E> addEdge(E ref, Vertex<V, E> source, Vertex<V, E> destination, double length) {
edges.put(ref, Graphs.newEdge(ref, source, destination, length));
return this;
}
public Vertex<V, E> getVertex(V ref) {
return vertices.get(ref);
}
public Collection<Vertex<V, E>> getVertices() {
return vertices.values();
}
public Collection<Edge<E, V>> getEdges() {
return edges.values();
}
public Edge<E, V> getEdge(E ref) {
return edges.get(ref);
}
protected Vertex<V, E> newVertex(V refSource) {
return Graphs.newVertex(refSource);
}
protected Edge<E, V> newEdge(E ref, Vertex<V, E> source, Vertex<V, E> destination, double length) {
return Graphs.newEdge(ref, source, destination, length);
}
}
Vertex.java
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.Set;
public class Vertex<V, E> {
private final V ref;
private final Set<Edge<E, V>> outgoingEdges = new LinkedHashSet<>();
private final Set<Edge<E, V>> incomingEdges = new LinkedHashSet<>();
public Vertex(V ref) {
this.ref = ref;
}
public V getRef() {
return ref;
}
public Collection<Edge<E, V>> getIncomingEdges() {
return incomingEdges;
}
public Collection<Edge<E, V>> getOutgoingEdges() {
return outgoingEdges;
}
public void addIncomingEdge(Edge<E, V> edge) {
incomingEdges.add(edge);
}
public void addOutgoingEdge(Edge<E, V> edge) {
outgoingEdges.add(edge);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Vertex vertex = (Vertex) o;
//noinspection RedundantIfStatement
if (ref != null ? !ref.equals(vertex.ref) : vertex.ref != null) return false;
return true;
}
@Override
public int hashCode() {
return getRef().hashCode();
}
@Override
public String toString() {
return ref.toString();
}
}
Edge.java
public class Edge<E, V> {
private final E ref;
private final Vertex<V, E> source;
private final Vertex<V, E> destination;
private final double length;
public Edge(E ref, Vertex<V, E> source, Vertex<V, E> destination, double length) {
this.ref = ref;
this.source = source;
this.destination = destination;
this.length = length;
}
public E getRef() {
return ref;
}
public Vertex<V, E> getDestination() {
return destination;
}
public Vertex<V, E> getSource() {
return source;
}
public double getLength() {
return length;
}
@Override
public String toString() {
return source + "->" + destination;
}
}
TestShortestPathViaFinder.java
import org.junit.Test;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import static org.junit.Assert.assertEquals;
public class TestShortestPathViaFinder {
@Test
public void testSingle() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
;
final List<List<Integer>> edges = Collections.singletonList(Collections.singletonList(1));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"B"
);
assertEquals(Collections.singletonList(1), visits);
}
@Test
public void testTrivial() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
.buildEdge(2, "B", "C", 1)
.buildEdge(3, "C", "D", 1)
;
final List<List<Integer>> edges = Collections.singletonList(Collections.singletonList(2));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"D"
);
assertEquals(Arrays.asList(1, 2, 3), visits);
}
@Test
public void testTrivialTwoVia() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
.buildEdge(2, "B", "C", 1)
.buildEdge(3, "C", "D", 1)
;
final List<List<Integer>> edges = Arrays.asList(Collections.singletonList(2), Collections.singletonList(3));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"D"
);
assertEquals(Arrays.asList(1, 2, 3), visits);
}
@Test
public void testLoop() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
.buildEdge(2, "B", "C", 1)
.buildEdge(3, "C", "D", 1)
.buildEdge(4, "D", "A", 1)
;
final List<List<Integer>> edges = Collections.singletonList(Collections.singletonList(2));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"D"
);
assertEquals(Arrays.asList(1, 2, 3), visits);
}
@Test
public void testFullLoop() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
.buildEdge(2, "B", "C", 1)
.buildEdge(3, "C", "D", 1)
.buildEdge(4, "D", "A", 1)
;
final List<List<Integer>> edges = Arrays.asList(Collections.singletonList(1), Collections.singletonList(2), Collections.singletonList(3), Collections.singletonList(4));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"A"
);
assertEquals(Arrays.asList(1, 2, 3, 4), visits);
}
@Test
public void testForked() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
.buildEdge(2, "B", "C", 2)
.buildEdge(3, "B", "D", 1)
.buildEdge(4, "C", "E", 1)
.buildEdge(5, "D", "E", 1)
.buildEdge(6, "E", "F", 1)
;
final List<List<Integer>> edges = Collections.singletonList(Arrays.asList(3, 4));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"F"
);
assertEquals(Arrays.asList(1, 3, 5, 6), visits);
}
@Test
public void testGoingBack() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(10, "A", "B", 1)
.buildEdge(20, "B", "C", 1)
.buildEdge(21, "C", "B", 1)
.buildEdge(30, "B", "D", 1)
.buildEdge(31, "D", "B", 1)
.buildEdge(40, "C", "E", 1)
.buildEdge(41, "E", "C", 1)
.buildEdge(50, "D", "E", 1)
.buildEdge(51, "E", "D", 1)
.buildEdge(60, "E", "F", 1)
;
final List<List<Integer>> edges = Arrays.asList(Arrays.asList(50, 51), Arrays.asList(40, 41));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"F"
);
assertEquals(Arrays.asList(10, 30, 50, 41, 40, 60), visits);
}
@Test
public void testCheapest() {
final Graph<String, Integer> graph = new Graph<>();
graph
.buildEdge(1, "A", "B", 1)
.buildEdge(2, "B", "C", 2)
.buildEdge(3, "B", "D", 1)
.buildEdge(4, "C", "E", 1)
.buildEdge(5, "D", "E", 5)
.buildEdge(6, "E", "F", 1)
;
final List<List<Integer>> edges = Arrays.asList(Arrays.asList(2,3), Arrays.asList(4, 5));
final List<Integer> visits = new ShortestPathViaFinder<String, Integer>()
.visitEdges(
graph,
"A",
edges,
"F"
);
assertEquals(Arrays.asList(1, 2, 4, 6), visits);
}
}
