2
\$\begingroup\$

In the \$k\$-shortest path problem, we are searching for (at most) \$k\$ distinct, shortest paths connecting two given terminal nodes. You can see the previous version here. This implementation, however, represents the intermediate paths in the open list as linked lists so that extending such a path by one node runs in \$\Theta(1)\$ time. My code is below:

net.coderodde.graph.kshortest.impl.FasterDefaultShortestPathFinder

package net.coderodde.graph.kshortest.impl;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import net.coderodde.graph.DirectedGraphNode;
import net.coderodde.graph.DirectedGraphWeightFunction;
import net.coderodde.graph.kshortest.AbstractKShortestPathFinder;
import net.coderodde.graph.kshortest.Path;

/**
 * This class implements a rather simple k-shortest path algorithm from
 * <a href="https://en.wikipedia.org/wiki/K_shortest_path_routing#Algorithm">
 * Wikipedia
 * </a>. This version improves 
 * {@link net.coderodde.graph.kshortest.impl.DefaultKShortestPathFinder} via 
 * using linked lists of nodes as the paths.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jun 4, 2019)
 */
public class FasterDefaultKShortestPathFinder 
        extends AbstractKShortestPathFinder {

    @Override
    public List<Path>
         findShortestPaths(DirectedGraphNode source, 
                           DirectedGraphNode target,
                           DirectedGraphWeightFunction weightFunction, 
                           int k) {
        Objects.requireNonNull(source, "The source node is null.");
        Objects.requireNonNull(target, "The target node is null.");
        Objects.requireNonNull(weightFunction,
                               "The weight function is null.");
        checkK(k);

        List<LinkedPathNode> linkedPathTails = new ArrayList<>(k);
        Map<DirectedGraphNode, Integer> countMap = new HashMap<>();
        Queue<LinkedPathNode> HEAP = new PriorityQueue<>();

        HEAP.add(new LinkedPathNode(weightFunction, source));

        while (!HEAP.isEmpty() && countMap.getOrDefault(target, 0) < k) {
            LinkedPathNode currentPath = HEAP.remove();
            DirectedGraphNode endNode = currentPath.getTailNode();
            countMap.put(endNode, countMap.getOrDefault(endNode, 0) + 1);

            if (endNode.equals(target)) {
                linkedPathTails.add(currentPath);
            }

            if (countMap.get(endNode) <= k) {
                for (DirectedGraphNode child : endNode.children()) {
                    HEAP.add(currentPath.append(child));
                }
            }
        }

        return convertListOfLinkedPathsToPaths(linkedPathTails);
    }

    private static final List<Path> 
        convertListOfLinkedPathsToPaths(
                List<LinkedPathNode> linkedPathTails) {
        List<Path> paths = new ArrayList<>(linkedPathTails.size());

        for (LinkedPathNode linkedPathNode : linkedPathTails) {
            paths.add(linkedPathNode.toPath());
        }

        return paths;
    }
}

net.coderodde.graph.kshortest.impl.LinkedPathNode

package net.coderodde.graph.kshortest.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import net.coderodde.graph.DirectedGraphWeightFunction;
import java.util.Objects;
import net.coderodde.graph.DirectedGraphNode;
import net.coderodde.graph.kshortest.Path;

/**
 * This class represents a path in a graph. The only difference between 
 * {@link net.coderodde.graph.kshortest.Path} is that this class implements the
 * path as a linked list of graph nodes. This arrangement allows us to extend 
 * any given path by one graph node in constant time.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jun 4, 2019)
 */
final class LinkedPathNode implements Comparable<LinkedPathNode> {

    private final DirectedGraphWeightFunction weightFunction;
    private final DirectedGraphNode node;
    private final LinkedPathNode previousLinkedPathNode;
    private double totalCost;

    public LinkedPathNode(DirectedGraphWeightFunction weightFunction,
                   DirectedGraphNode node) {
        this.weightFunction =
                Objects.requireNonNull(
                        weightFunction,
                        "The input weight function is null.");

        this.node = Objects.requireNonNull(node, "The input node is null.");
        this.totalCost = 0.0;
        this.previousLinkedPathNode = null;
    }

    LinkedPathNode(LinkedPathNode path, DirectedGraphNode node) {
        this.weightFunction = path.weightFunction;
        this.node = node;
        this.previousLinkedPathNode = path;
        this.totalCost += weightFunction.get(previousLinkedPathNode.node, node);
    }

    LinkedPathNode append(DirectedGraphNode node) {
        return new LinkedPathNode(this, node);
    }

    LinkedPathNode getPreviousLinkedPathNode() {
        return this.previousLinkedPathNode;
    }

    DirectedGraphNode getTailNode() {
        return this.node;
    }

    Path toPath() {
        List<DirectedGraphNode> path = new ArrayList<>();
        LinkedPathNode node = this;

        while (node != null) {
            path.add(node.node);
            node = node.previousLinkedPathNode;
        }

        Collections.<DirectedGraphNode>reverse(path);
        return new Path(path, this.weightFunction);
    }

    @Override
    public int compareTo(LinkedPathNode o) {
        return Double.compare(totalCost, o.totalCost);
    }
}

Critique request

I would love to hear comments about naming conventions, maintainability and readability, but please tell me anything that comes to mind.

Miscellany

See this project for all the missing Java files.

\$\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.