0
\$\begingroup\$

(See the next iteration.) 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()));
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Deserves a void addEdge(DirectedGraphNode s, ~ d, double w). \$\endgroup\$ – greybeard Jan 9 '16 at 13:10
  • 1
    \$\begingroup\$ (Does Path belong in NC.graph.kshortest, or one level higher?) I'd like a decent Path.toString(). Trying to figure out whether JU.concurrent.CopyOnWriteArrayList (or its techniques) would be profitable, I'm failing to find why add(E e) copies instead of returning a "SubCOWList". (Coded addEdge as an instance member of Demo - not utterly convincing.) (Pity to see FibonacciHeap gone - the one part I liked the comment density of ;-) \$\endgroup\$ – greybeard Jan 9 '16 at 19:15
2
\$\begingroup\$

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).

Edit Here is my take:

DefaultKShortestPathFinder

import 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;
    }
}

AbstractKShortestPathFinder

import 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));
        }
    }
}

Edge

public 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.");
        }
    }

}

Path

import 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;
        }
    }

}

Graph

import 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();
    }

}

Demo

import 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());
        }
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.