This snippet is about computing \$k\$ shortest paths in a directed graph using this algorithm.I would like to hear about API design, naming/coding conventions, and so on.My implementation follows:DefaultKShortestPathFinder.java:package net.coderodde.graph.kshortest.support;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>. *  * @author Rodion rodde Efremov * @version 1.6 (Jan 9, 2016) */public class DefaultKShortestPathFinder 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<Path> paths = new ArrayList<>(k);        Map<DirectedGraphNode, Integer> countMap = new HashMap<>();        Queue<Path> HEAP = new PriorityQueue<>();        HEAP.add(new Path(weightFunction, source));        while (!HEAP.isEmpty() && countMap.getOrDefault(target, 0) < k) {            Path currentPath = HEAP.remove();            DirectedGraphNode endNode = currentPath.getEndNode();            countMap.put(endNode, countMap.getOrDefault(endNode, 0) + 1);            if (endNode.equals(target)) {                paths.add(currentPath);            }            if (countMap.get(endNode) <= k) {                for (DirectedGraphNode child : endNode.children()) {                    Path path = currentPath.append(child);                    HEAP.add(path);                }            }        }        return paths;    }}AbstractKShortestPathFinder.java:package net.coderodde.graph.kshortest;import java.util.List;import net.coderodde.graph.DirectedGraphNode;import net.coderodde.graph.DirectedGraphWeightFunction;/** * This abstract class defines the API for {@code k}-shortest path algorithms. *  * @author Rodion rodde Efremov * @version 1.6 (Jan 9, 2016) */public abstract class AbstractKShortestPathFinder {    public abstract List<Path>         findShortestPaths(DirectedGraphNode source,                           DirectedGraphNode target,                           DirectedGraphWeightFunction weightFunction,                           int k);    protected void checkK(int k) {        if (k < 1) {            throw new IllegalArgumentException(                    The value of k is too small:  + k + ,  +                    should be at least 1.);        }    }}Path.java:package net.coderodde.graph.kshortest;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Objects;import net.coderodde.graph.DirectedGraphNode;import net.coderodde.graph.DirectedGraphWeightFunction;/** * This class implements a graph path. *  * @author Rodion rodde Efremov * @version 1.6 (Jan 9, 2016) */public class Path implements Comparable<Path> {    private final DirectedGraphWeightFunction weightFunction;    private final List<DirectedGraphNode> nodeList = new ArrayList<>();    private double totalCost;    public Path(DirectedGraphWeightFunction weightFunction,                DirectedGraphNode source) {        Objects.requireNonNull(weightFunction,                                The input weight function is null.);        Objects.requireNonNull(source, The input source node is null.);        this.weightFunction = weightFunction;        nodeList.add(source);    }    private Path(Path path, DirectedGraphNode node) {        this.weightFunction = path.weightFunction;        this.nodeList.addAll(path.nodeList);        this.nodeList.add(node);        int listLength = nodeList.size();        this.totalCost += weightFunction.get(nodeList.get(listLength - 2),                                             nodeList.get(listLength - 1));    }    public Path append(DirectedGraphNode node) {        return new Path(this, node);    }    public DirectedGraphNode getEndNode() {        return nodeList.get(nodeList.size() - 1);    }    /**     * Returns the number of nodes in this path.     *      * @return the path length in nodes.     */    public int size() {        return nodeList.size();    }    public List<DirectedGraphNode> getNodeList() {        return Collections.<DirectedGraphNode>unmodifiableList(nodeList);    }    public double pathCost() {        return totalCost;    }    @Override    public int compareTo(Path o) {        return Double.compare(totalCost, o.totalCost);    }}DirectedGraphNode.java:package net.coderodde.graph;import java.util.Collections;import java.util.LinkedHashSet;import java.util.Objects;import java.util.Set;/** * This class implements a directed graph node. *  * @author Rodion rodde Efremov * @version 1.6 (Jan 9, 2016) */public class DirectedGraphNode {    private final int id;    private final Set<DirectedGraphNode> children = new LinkedHashSet<>();    private final Set<DirectedGraphNode> parents  = new LinkedHashSet<>();    private final Set<DirectedGraphNode> childrenWrapper =             Collections.<DirectedGraphNode>unmodifiableSet(children);    private final Set<DirectedGraphNode> parentsWrapper  =             Collections.<DirectedGraphNode>unmodifiableSet(parents);    public DirectedGraphNode(int id) {        this.id = id;    }    public void addChild(DirectedGraphNode child) {        Objects.requireNonNull(child, The child node is null.);        children.add(child);        child.parents.add(this);    }    public Set<DirectedGraphNode> children() {        return childrenWrapper;    }    public Set<DirectedGraphNode> parents() {        return parentsWrapper;    }    @Override    public int hashCode() {        return Integer.hashCode(id);    }    @Override    public boolean equals(Object o) {        if (!(o instanceof DirectedGraphNode)) {            return false;        }        return id == ((DirectedGraphNode) o).id;    }    @Override    public String toString() {        return [DirectedGraphNode  + id + ];    }}DirectedGraphWeightFunction.java:package net.coderodde.graph;import java.util.HashMap;import java.util.Map;/** * This class implements a weight function for directed graphs. *  * @author Rodion rodde Efremov * @version 1.6 (Jan 9, 2016) */public class DirectedGraphWeightFunction {    private final Map<DirectedGraphNode,                       Map<DirectedGraphNode, Double>> map = new HashMap<>();    public void put(DirectedGraphNode tail,                    DirectedGraphNode head,                     double weight) {        checkWeight(weight);        map.putIfAbsent(tail, new HashMap<>());        map.get(tail).put(head, weight);    }    public double get(DirectedGraphNode tail, DirectedGraphNode head) {        return map.get(tail).get(head);    }    private void checkWeight(double weight) {        if (Double.isNaN(weight)) {            throw new IllegalArgumentException(The weight is NaN.);        }        if (weight < 0.0) {            throw new IllegalArgumentException(The weight is negative.);        }    }}Demo.java:import java.util.Arrays;import java.util.List;import net.coderodde.graph.DirectedGraphNode;import net.coderodde.graph.DirectedGraphWeightFunction;import net.coderodde.graph.kshortest.Path;import net.coderodde.graph.kshortest.support.DefaultKShortestPathFinder;public class Demo {    public static void main(String[] args) {        demo1();    }    private static void demo1() {        //    1    4        //  /  \  / \        // 0    3    6        //  \  / \  /        //   2    5        DirectedGraphNode a = new DirectedGraphNode(0);         DirectedGraphNode b = new DirectedGraphNode(1);         DirectedGraphNode c = new DirectedGraphNode(2);         DirectedGraphNode d = new DirectedGraphNode(3);         DirectedGraphNode e = new DirectedGraphNode(4);         DirectedGraphNode f = new DirectedGraphNode(5);         DirectedGraphNode g = new DirectedGraphNode(6);         // The edges above the line 0 - 6 have weight of 1.0.        // The edges below the line 0 - 6 have weight of 2.0        DirectedGraphWeightFunction weightFunction =                 new DirectedGraphWeightFunction();        a.addChild(b); weightFunction.put(a, b, 1);        a.addChild(c); weightFunction.put(a, c, 2);        b.addChild(d); weightFunction.put(b, d, 1);        c.addChild(d); weightFunction.put(c, d, 2);        d.addChild(e); weightFunction.put(d, e, 1);        d.addChild(f); weightFunction.put(d, f, 2);        e.addChild(g); weightFunction.put(e, g, 1);        f.addChild(g); weightFunction.put(f, g, 2);        List<Path> paths = new DefaultKShortestPathFinder()                .findShortestPaths(a, g, weightFunction, 3);        for (Path path : paths) {            System.out.println(Arrays.toString(path.getNodeList().toArray()));        }    }}
k-shortest path algorithm in Java
java;algorithm;pathfinding
I can't find much to critisize here. You could use static import (e.g. for Objects.requirenNonNull) and String.format.I find it a little bit strange to have no graph type which holds both nodes and edges, just nodes and the weight function. It would be easy to get out of sync between nodes and weights in your demo (e.g. when making a copy-and-paste error).EditHere is my take:DefaultKShortestPathFinderimport java.util.*;import static java.util.Objects.requireNonNull;public class DefaultKShortestPathFinder<V> implements AbstractKShortestPathFinder<V> {    @Override    public List<Path<V>> findShortestPaths(V source, V target, Graph<V> graph, int k) {        requireNonNull(source, The source node is null.);        requireNonNull(target, The target node is null.);        requireNonNull(graph, The graph is null.);        checkK(k);        List<Path<V>> paths = new ArrayList<>(k);        Map<V, Integer> countMap = new HashMap<>();        Queue<Path<V>> HEAP = new PriorityQueue<>(                Comparator.comparingDouble(Path::pathCost));        HEAP.add(new Path<>(source));        while (!HEAP.isEmpty() && countMap.getOrDefault(target, 0) < k) {            Path<V> currentPath = HEAP.remove();            V endNode = currentPath.getEndNode();            countMap.put(endNode, countMap.getOrDefault(endNode, 0) + 1);            if (endNode.equals(target)) {                paths.add(currentPath);            }            if (countMap.get(endNode) <= k) {                for (Edge<V> edge : graph.get(endNode)) {                    Path<V> path = currentPath.append(edge);                    HEAP.add(path);                }            }        }        return paths;    }}AbstractKShortestPathFinderimport java.util.List;public interface AbstractKShortestPathFinder<V> {    List<Path<V>> findShortestPaths(V source, V target, Graph<V> graph, int k);    default void checkK(int k) {        if (k < 1) {            throw new IllegalArgumentException(                    String.format(The value of k is too small: %d, should be at least 1., k));        }    }}Edgepublic class Edge<V> {    public final V from;    public final V to;    public final double weight;    public Edge(V from, V to, double weight) {        this.from = from;        this.to = to;        this.weight = weight;        if (Double.isNaN(weight)) {            throw new IllegalArgumentException(The weight is NaN.);        }        if (weight < 0.0) {            throw new IllegalArgumentException(The weight is negative.);        }    }}Pathimport java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Objects;import static java.lang.String.format;public class Path<V> {    private final V node;    private final double totalCost;    public Path(V source) {        Objects.requireNonNull(source, The input source node is null.);        node = source;        totalCost = 0.0;    }    private Path(V node, double totalCost) {        this.node = node;        this.totalCost = totalCost;    }    public Path<V> append(Edge<V> edge) {        if (!node.equals(edge.from)) {            throw new IllegalArgumentException(format(The edge %s doesn't extend the path %s, edge, this.getNodeList()));        }        return new NonEmptyPath<>(this, edge);    }    public V getEndNode() {        return node;    }    public List<V> getNodeList() {        return new ArrayList<>();    }    public double pathCost() {        return totalCost;    }    private static class NonEmptyPath<V> extends Path<V> {        private final Path<V> predecessor;        public NonEmptyPath(Path<V> path, Edge<V> edge) {            super(edge.to, path.totalCost + edge.weight);            predecessor = path;        }        @Override        public List<V> getNodeList() {            LinkedList<V> result = new LinkedList<>();            Path<V> path = this;            while(path instanceof NonEmptyPath) {                result.addFirst(path.node);                path = ((NonEmptyPath<V>) path).predecessor;            }            result.addFirst(path.node);            return result;        }    }}Graphimport java.util.*;import static java.lang.String.*;public class Graph<V> {    //could be replaced by http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Table.html    private Map<V,Map<V,Edge<V>>> vertexEdgeMap = new HashMap<>();    @SafeVarargs    public Graph(Edge<V> ... edges) {        for (Edge<V> edge : edges) {            addEdge(edge);        }    }    private void addEdge(Edge<V> edge) {        vertexEdgeMap.putIfAbsent(edge.from, new HashMap<>());        Map<V, Edge<V>> fromMap = vertexEdgeMap.get(edge.from);        if(fromMap.containsKey(edge.to)) {            throw new IllegalArgumentException(format(Edge between %s and %s was added twice, edge.from, edge.to));        }        fromMap.put(edge.to, edge);    }    public Edge<V> get(V from, V to) {        return vertexEdgeMap.get(from).get(to);    }    public Collection<Edge<V>> get(V from) {        return vertexEdgeMap.getOrDefault(from, Collections.emptyMap()).values();    }}Demoimport java.util.List;public class Demo {    public static void main(String[] args) {        demo1();    }    private static void demo1() {        //    b    e        //  /  \  / \        // a    d    g        //  \  / \  /        //   c    f        // The edges above the line a - g have weight of 1.0.        // The edges below the line a - g have weight of 2.0        Graph<Character> graph = new Graph<>(                new Edge<>('a', 'b', 1.0),                new Edge<>('a', 'c', 2.0),                new Edge<>('b', 'd', 1.0),                new Edge<>('c', 'd', 2.0),                new Edge<>('d', 'e', 1.0),                new Edge<>('d', 'f', 2.0),                new Edge<>('e', 'g', 1.0),                new Edge<>('e', 'f', 2.0)        );        List<Path<Character>> paths = new DefaultKShortestPathFinder<Character>()                .findShortestPaths('a', 'g', graph, 3);        for (Path<Character> path : paths) {            System.out.println(path.getNodeList() +   + path.pathCost());        }    }}