2
\$\begingroup\$

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);
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.