1
\$\begingroup\$

Part 1/3

Part 3/3

I have this library for performing shortest path queries on dags (directed acyclic graphs). This post presents the shortest path algorithms and the topological sorters. Two algorithms for topologically sorting the graph nodes are compared:

  • com.github.coderodde.graph.impl.DFSTopologicalSorter (See this; implemented iteratively in order not to cause StackOverflowError.)
  • com.github.coderodde.graph.impl.KahnsTopologicalSorter (See the Kahn's algorithm.)

The two actual shortest path algorithms:

  • NaivePreprocessingDagShortestPathQueryRunner, follows the text books on shortest path search in dags,
  • IndexingPreprocessingDagShortestPathQueryRunner, same as above, but with a minor tweak: we compute in \$\Theta(N)\$ a map (call it \$\mu\$ mapping dag nodes to their appearance index in the topologically sorted list \$L\$). Now, in order to find a shortest path from \$s\$ to \$t\$, we compute two indices: \$f = \mu(s)\$ and \$e = \mu(t)\$; if \$f > e\$, there is no path from \$s\$ to \$t\$, and we stop before doing any search; constant time. If, however, \$f \leq e\$, we restrict the search to that range of nodes whose indices are in the range \$[f, e]\$ instead of going through the entire \$L\$. Clearly, assuming the average out-degree is \$d\$, the running time is \$\mathcal{O}(d(\mu(t) - \mu(s)))\$.

Below is the code:

com.github.coderodde.graph.TopologicalSortChecker.java:

package com.github.coderodde.graph;

import com.github.coderodde.graph.impl.DirectedGraph;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * This class contains a static method for checking whether the input node list
 * is topologically sorted.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 16, 2022)
 * @since 1.6 (Jul 16, 2022)
 */
public final class TopologicalSortChecker {

    /**
     * Checks whether the input node list is in topological order.
     * 
     * @param graph the graph.
     * @param nodes the node list to check.
     * @return {@code true} if and only if the input node list is in 
     *         topological order.
     */
    public static boolean isTopologicallySorted(DirectedGraph graph,
                                                List<Integer> nodes) {
        Objects.requireNonNull(nodes);
        Map<Integer, Integer> indices = getIndexMap(nodes); 

        for (Integer node : nodes) {
            if (!isValidNodePosition(graph, node, indices)) {
                return false;
            }
        }

        return true;
    }

    /**
     * Returns the map mapping each node to its appearance index in the 
     * {@code nodes} list.
     * 
     * @param nodes the node list from which to compute the index map.
     * @return the node-to-index map.
     */
    private static Map<Integer, Integer> getIndexMap(List<Integer> nodes) {
        Map<Integer, Integer> map = new HashMap<>(nodes.size());

        for (int index = 0; index < nodes.size(); index++) {
            map.put(nodes.get(index), index);
        }

        return map;
    }

    /**
     * Checks that there is no parents of {@code node} on the right of 
     * {@code node}, and that there is no children of {@code node} on the left
     * of {@code node}.
     * 
     * @param graph the target graph.
     * @param node the node to check.
     * @param indexMap the map mapping nodes to their appearance indices.
     * @return {@code true} if and only if the {@code node} is in valid 
     *         position.
     */
    private static boolean isValidNodePosition(DirectedGraph graph,
                                               Integer node, 
                                               Map<Integer, Integer> indexMap) {
        Integer nodeIndex = indexMap.get(node);

        for (Integer parent : graph.getParentsOf(node)) {
            // >= in the condition in order to fail on self-loops:
            if (indexMap.get(parent) >= nodeIndex) {
                return false;
            }
        }

        for (Integer child : graph.getChildrenOf(node)) {
            if (indexMap.get(child) < nodeIndex) {
                return false;
            }
        }

        return true;
    }
}

com.github.coderodde.graph.TopologicalSorter.java:

package com.github.coderodde.graph;

import com.github.coderodde.graph.impl.DirectedGraph;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * This interface defines the API for topological sorters.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 15, 2022)
 * @since 1.6 (Jul 15, 2022)
 */
public interface TopologicalSorter {

    /**
     * Attempts to sort the input graph topologically. If the input graph 
     * contains cycles, an instance of {@link GraphContainsCyclesException} is
     * thrown.
     * 
     * @param graph the graph to sort.
     * @return a list of nodes in topological order.
     * @throws GraphContainsCyclesException if the input graph contains cycles.
     */
    List<Integer> sort(DirectedGraph graph) throws GraphContainsCyclesException;

    /**
     * Removes and returns a node from a set of nodes.
     * 
     * @param set the set to remove from.
     * @return a node.
     */
    default Integer removeNodeFromSet(Set<Integer> set) {
        Iterator<Integer> iterator = set.iterator();
        Integer node = iterator.next();
        iterator.remove();
        return node;
    }

    /**
     * Loads the index map from {@code nodeList} to {@code indexMap}.
     * 
     * @param nodeList the (topologically sorted) list of nodes.
     * @param indexMap the target map mapping nodes to their appearance indices
     *                 in {@code nodeList}.
     */
    default void loadIndexMap(List<Integer> nodeList, 
                              Map<Integer, Integer> indexMap) {
        for (int index = 0; index < nodeList.size(); index++) {
            indexMap.put(nodeList.get(index), index);
        }
    }
}

com.github.coderodde.graph.sp.AbstractGraphPreprocessor.java:

package com.github.coderodde.graph.sp;

import com.github.coderodde.graph.TopologicalSorter;
import com.github.coderodde.graph.impl.DirectedGraph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * This abstract class defines the common facilities for graph preprocessor 
 * implementations.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 19, 2022)
 * @since 1.6 (Jul 19, 2022)
 */
public abstract class AbstractGraphPreprocessor {

    private static final long UNSET_PREPROCESSING_DURATION = -1L;

    protected final List<Integer> topologicallySortedNodes;
    protected final Map<Integer, Integer> indexMap;
    protected long preprocessingDuration = UNSET_PREPROCESSING_DURATION;
    protected final DirectedGraph graph;

    public AbstractGraphPreprocessor(DirectedGraph graph) {
        this.graph = Objects.requireNonNull(graph);
        this.topologicallySortedNodes = new ArrayList<>(graph.size());
        this.indexMap = new HashMap<>(graph.size());
    }

    public abstract void preprocessGraph();

    protected void preprocessGraph(TopologicalSorter topologicalSorter) {
        long startTime = System.currentTimeMillis();

        topologicallySortedNodes.clear();
        topologicallySortedNodes.addAll(topologicalSorter.sort(graph));
        topologicalSorter.loadIndexMap(topologicallySortedNodes, indexMap);

        long endTime = System.currentTimeMillis();
        long duration = endTime - startTime;

        this.preprocessingDuration = duration;
    }

    public List<Integer> getTopologicallySortedNodes() {
        return topologicallySortedNodes;
    }

    public Map<Integer, Integer> getIndexMap() {
        return indexMap;
    }

    public long getPreprocessingDuration() {
        if (preprocessingDuration == UNSET_PREPROCESSING_DURATION) {
            throw new IllegalStateException("Preprocessing was not run.");
        }

        return preprocessingDuration;
    }

    protected void computeIndexMap() {
        for (int index = 0; index < topologicallySortedNodes.size(); index++) {
            indexMap.put(topologicallySortedNodes.get(index), index);
        }
    }
}

com.github.coderodde.graph.sp.AbstractDagShortestPathQueryRunner.java:

package com.github.coderodde.graph.sp;

import com.github.coderodde.graph.impl.DirectedGraph;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * This abstract class defines the common facilities for the shortest path query
 * runner implementations.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 19, 2022)
 * @since 1.6 (Jul 19, 2022)
 */
public abstract class AbstractDagShortestPathQueryRunner {

    protected final DirectedGraph graph;
    protected final AbstractGraphPreprocessor graphPreprocessor;

    protected long expectedGraphModCount = -1L;

    public AbstractDagShortestPathQueryRunner(
            DirectedGraph graph,
            AbstractGraphPreprocessor graphPreprocessor) {
        this.graph = Objects.requireNonNull(graph);
        this.graphPreprocessor = graphPreprocessor;
    }

    public abstract long getPreprocessingDuration();

    public abstract DirectedGraph.Path queryShortestPath(Integer sourceNode,
                                                         Integer targetNode);

    @Override
    public String toString() {
        return getClass().getSimpleName() 
                + "[" 
                + graphPreprocessor.getClass().getSimpleName() 
                + "]";
    }

    /**
     * Reconstructs the shortest path.
     * 
     * @param targetNode the target node in the target graph.
     * @param parentMap  the map mapping each node to its predecessor.
     * @return the shortest path.
     */
    protected DirectedGraph.Path 
        tracebackPath(Integer targetNode, 
                      Map<Integer, Integer> parentMap) {

        List<Integer> pathList = new ArrayList<>();
        Integer node = targetNode;

        while (node != null) {
            pathList.add(node);
            node = parentMap.get(node);
        }

        Collections.reverse(pathList);
        return new DirectedGraph.Path(graph, pathList);
    }

    protected void checkSourceNode(Integer sourceNode) {
        if (!graph.hasNode(sourceNode)) {
            throw new IllegalArgumentException(
                    "The source node (" 
                            + sourceNode 
                            + ") is not in the graph.");
        }
    }

    protected void checkTargetNode(Integer targetNode) {   
        if (!graph.hasNode(targetNode)) {
            throw new IllegalArgumentException(
                    "The target node (" 
                            + targetNode 
                            + ") is not in the graph.");
        }
    }
}

com.github.coderodde.graph.sp.impl.IndexingPreprocessingDagShortestPathQueryRunner.java:

package com.github.coderodde.graph.sp.impl;

import com.github.coderodde.graph.PathDoesNotExistException;
import com.github.coderodde.graph.impl.DirectedGraph;
import com.github.coderodde.graph.sp.AbstractDagShortestPathQueryRunner;
import com.github.coderodde.graph.sp.AbstractGraphPreprocessor;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * This class implements a method for running the shortest path queries in dags.
 * This implementation uses a simple speed-up technique: all the node in the 
 * topologically sorted list {@code L} are mapped to their respective appearance 
 * indices in the sorted list. Now, if the source node is {@code s} and the 
 * target node is {@code t}, and the map is {@code m}, the search traverses 
 * only the range {@code L[m(s) ... m(t)]}.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 19, 2022)
 * @since 1.6 (Jul 19, 2022)
 */
public class IndexingPreprocessingDagShortestPathQueryRunner 
        extends AbstractDagShortestPathQueryRunner {

    private final List<Integer> topologicallySortedNodes = new ArrayList<>();
    private final Map<Integer, Integer> indexMap = new HashMap<>();

    /**
     * Constructs the preprocessing shortest path query provider.
     * 
     * @param graph             the graph in which to run the shortest path 
     *                          search.
     * @param graphPreprocessor the graph preprocessor.
     */
    public IndexingPreprocessingDagShortestPathQueryRunner(
            DirectedGraph graph,
            AbstractGraphPreprocessor graphPreprocessor) {
        super(graph, graphPreprocessor);
    }

    @Override
    public DirectedGraph.Path queryShortestPath(Integer sourceNode, 
                                                Integer targetNode) {
        checkGraphDirtyStatus();

        checkSourceNode(sourceNode);
        checkTargetNode(targetNode);

        Map<Integer, Double> costMap = new HashMap<>();
        Map<Integer, Integer> parentMap = new HashMap<>();

        costMap.put(sourceNode, 0.0);
        parentMap.put(sourceNode, null);

        int sourceIndex = indexMap.get(sourceNode);
        int targetIndex = indexMap.get(targetNode);

        for (int i = sourceIndex; i <= targetIndex; i++) {
            Integer node = topologicallySortedNodes.get(i);

            if (!costMap.containsKey(node)) {
                continue;
            }

            if (node.equals(targetNode)) {
                return tracebackPath(node, parentMap);
            }

            for (Integer child : graph.getChildrenOf(node)) {
                if (!costMap.containsKey(child) 
                        || costMap.get(child) > 
                           costMap.get(node) + graph.getEdgeWeight(node, child)) {
                    costMap.put(child, 
                                costMap.get(node) + 
                                        graph.getEdgeWeight(node, child));

                    parentMap.put(child, node);
                }
            }
        }

        throw new PathDoesNotExistException(sourceNode, targetNode);
    }

    @Override
    public long getPreprocessingDuration() {
        return graphPreprocessor.getPreprocessingDuration();
    }

    private void checkGraphDirtyStatus() {
        if (expectedGraphModCount != graph.getModificationCount()) {
            expectedGraphModCount = graph.getModificationCount();
            graphPreprocessor.preprocessGraph();
            topologicallySortedNodes.clear();
            topologicallySortedNodes.addAll(
                    graphPreprocessor.getTopologicallySortedNodes());

            indexMap.clear();
            indexMap.putAll(graphPreprocessor.getIndexMap());
        }
    }
}

com.github.coderodde.graph.sp.impl.NaivePreprocessingDagShortestPathQueryRunner.java:

package com.github.coderodde.graph.sp.impl;

import com.github.coderodde.graph.PathDoesNotExistException;
import com.github.coderodde.graph.impl.DirectedGraph;
import com.github.coderodde.graph.sp.AbstractDagShortestPathQueryRunner;
import com.github.coderodde.graph.sp.AbstractGraphPreprocessor;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * This class implements a method for running shortest path queries.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 19, 2022)
 * @since 1.6 (Jul 19, 2022)
 */
public class NaivePreprocessingDagShortestPathQueryRunner 
        extends AbstractDagShortestPathQueryRunner {

    private final List<Integer> topologicallySortedNodes = new ArrayList<>();

    /**
     * Constructs the preprocessing shortest path query provider.
     * 
     * @param graph             the graph in which to run the shortest path 
     *                          search.
     * @param graphPreprocessor the graph preprocessor.
     */
    public NaivePreprocessingDagShortestPathQueryRunner(
            DirectedGraph graph,
            AbstractGraphPreprocessor graphPreprocessor) {
        super(graph, graphPreprocessor);
    }

    @Override
    public DirectedGraph.Path queryShortestPath(Integer sourceNode, 
                                                Integer targetNode) {
        // If this runner's expected mod count does not match the mod count of
        // the graph, graph is changed and so we need to re-preprocess the 
        // graph.
        checkGraphDirtyStatus();

        checkSourceNode(sourceNode);
        checkTargetNode(targetNode);

        Map<Integer, Double> costMap = new HashMap<>();
        Map<Integer, Integer> parentMap = new HashMap<>();

        costMap.put(sourceNode, 0.0);
        parentMap.put(sourceNode, null);

        for (Integer node : topologicallySortedNodes) {
            if (!costMap.containsKey(node)) {
                continue;
            }

            if (node.equals(targetNode)) {
                return tracebackPath(node, parentMap);
            }

            for (Integer child : graph.getChildrenOf(node)) {
                if (!costMap.containsKey(child) 
                        || costMap.get(child) > 
                           costMap.get(node) + 
                            graph.getEdgeWeight(node, child)) {

                    costMap.put(child, 
                                costMap.get(node) + 
                                        graph.getEdgeWeight(node, child));

                    parentMap.put(child, node);
                }
            }
        }

        throw new PathDoesNotExistException(sourceNode, targetNode);
    }

    @Override
    public long getPreprocessingDuration() {
        return graphPreprocessor.getPreprocessingDuration();
    }

    private void checkGraphDirtyStatus() {
        if (expectedGraphModCount != graph.getModificationCount()) {
            expectedGraphModCount = graph.getModificationCount();
            graphPreprocessor.preprocessGraph();
            topologicallySortedNodes.clear();
            topologicallySortedNodes.addAll(
                    graphPreprocessor.getTopologicallySortedNodes());
        }
    }
}

com.github.coderodde.graph.impl.DFSTopologicalSorter.java:

package com.github.coderodde.graph.impl;

import com.github.coderodde.graph.GraphContainsCyclesException;
import com.github.coderodde.graph.TopologicalSorter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * This class implements a method for topologically sorting graph nodes via 
 * DFS-like algorithm.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 19, 2022)
 * @since 1.6 (Jul 19, 2022)
 */
public class DFSTopologicalSorter implements TopologicalSorter {

    @Override
    public List<Integer> sort(DirectedGraph graph) 
            throws GraphContainsCyclesException {

        List<Integer> sortedNodes = new ArrayList<>(graph.size());
        Set<Integer> unmarkedNodes = new HashSet<>(graph.getAllNodes());
        Set<Integer> temporarilyMarkedNodes = new HashSet<>();
        Set<Integer> permanentlyMarkedNodes = new HashSet<>();
        Deque<Integer> nodeStack = new ArrayDeque<>();
        Deque<Iterator<Integer>> iteratorStack = new ArrayDeque<>();

        while (!unmarkedNodes.isEmpty()) {
            Integer root = removeNodeFromSet(unmarkedNodes);
            nodeStack.add(root);
            iteratorStack.add(graph.getChildrenOf(root).iterator());
            visit(graph,
                  nodeStack,
                  iteratorStack, 
                  unmarkedNodes,
                  temporarilyMarkedNodes,
                  permanentlyMarkedNodes,
                  sortedNodes);
        }

        Collections.reverse(sortedNodes);
        return sortedNodes;
    }

    private static void visit(DirectedGraph graph,
                              Deque<Integer> nodeStack,
                              Deque<Iterator<Integer>> iteratorStack,
                              Set<Integer> unmarkedNodes,
                              Set<Integer> temporarilyMarkedNodes,
                              Set<Integer> permanentlyMarkedNodes,
                              List<Integer> sortedNodes) {
        mainLoop:
        while (!nodeStack.isEmpty()) {
            Integer node = nodeStack.peek();
            Iterator<Integer> iterator = iteratorStack.peek();

            unmarkedNodes.remove(node);
            temporarilyMarkedNodes.add(node);

            while (iterator.hasNext()) {
                Integer child = iterator.next();

                if (unmarkedNodes.contains(child)) {
                    nodeStack.push(child);
                    iteratorStack.push(graph.getChildrenOf(child).iterator());
                    continue mainLoop;
                } else if (temporarilyMarkedNodes.contains(child)) {
                    throw new GraphContainsCyclesException();
                }
            }

            while (!iteratorStack.isEmpty() 
                    && !iteratorStack.peek().hasNext()) {
                iteratorStack.pop();
                node = nodeStack.pop();
                temporarilyMarkedNodes.remove(node);
                permanentlyMarkedNodes.add(node);
                sortedNodes.add(node);
            }
        }
    }
}

com.github.coderodde.graph.impl.KahnsTopologicalSorter.java:

package com.github.coderodde.graph.impl;

import com.github.coderodde.graph.GraphContainsCyclesException;
import com.github.coderodde.graph.TopologicalSorter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm">Kahn's algorithm</a> for topologically sorting 
 * graph nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Jul 19, 2022)
 * @since 1.6 (Jul 19, 2022)
 */
public class KahnsTopologicalSorter implements TopologicalSorter {

    @Override
    public List<Integer> sort(DirectedGraph graph)
            throws GraphContainsCyclesException {

        List<Integer> children = new ArrayList<>(graph.size());
        // First, get a copy of the input graph, since the algorithm  removes
        // the arcs from the graph it works on:
        graph = new DirectedGraph(graph);
        List<Integer> sortedNodeList = new ArrayList<>(graph.size());
        Set<Integer> nodesToProcess = getStartNodes(graph);

        while (!nodesToProcess.isEmpty()) {
            Integer node = removeFromSet(nodesToProcess);
            sortedNodeList.add(node);

            children.clear();
            children.addAll(graph.getChildrenOf(node));

            for (Integer child : children) {
                graph.removeEdge(node, child);

                if (graph.getParentsOf(child).size() == 0) {
                    nodesToProcess.add(child);
                }
            }
        }

        if (graph.getNumberOfEdges() > 0) {
            throw new GraphContainsCyclesException();
        }

        return sortedNodeList;
    }

    private Set<Integer> getStartNodes(DirectedGraph graph) {
        Set<Integer> set = new HashSet<>();

        for (Integer node : graph.getAllNodes()) {
            if (graph.getParentsOf(node).isEmpty()) {
                set.add(node);
            }
        }

        return set;
    }

    private Integer removeFromSet(Set<Integer> set) {
        Iterator<Integer> iterator = set.iterator();
        Integer node = iterator.next();
        iterator.remove();
        return node;
    }
}

Critique request

As always, tell me anything that comes to mind.

\$\endgroup\$
1
  • \$\begingroup\$ very nice written code \$\endgroup\$ Aug 9, 2022 at 6:05

1 Answer 1

2
\$\begingroup\$

duplicated code

com.github.coderodde.graph.sp.impl.AbstractDagShortestPathQueryRunner implementations have much code in common, provide a proper method to reduce duplications (DRY)

for (Integer node : topologicallySortedNodes) {
    if (!costMap.containsKey(node)) {
        continue;
    }

    if (node.equals(targetNode)) {
         return tracebackPath(node, parentMap);
    }

    for (Integer child : graph.getChildrenOf(node)) {
        if (!costMap.containsKey(child) ... ) { //shortened see next issue
            costMap.put(child, 
                costMap.get(node) + 
                graph.getEdgeWeight(node, child));

            parentMap.put(child, node);
        }
    }
}

should be

for (Integer node : topologicallySortedNodes) {
    if (!costMap.containsKey(node)) {
        continue;
    }

    if (node.equals(targetNode)) {
         return tracebackPath(node, parentMap);
    }

    for (Integer child : graph.getChildrenOf(node)) {
        expandIfRequired(node, child);
    }
}

first class collections

instead of using Maps and Listss directly wrap your Collections in a class. This Clean Code Principle helps you to write more readable code

let's assume you have a first class collection for costMap and see how this lightens your code:

for (Integer node : topologicallySortedNodes) {
    if (costMap.isNotInMap(node)) { //far more readable
        continue;
    }
}

and as mentioned before, you can now put your conditions on the proper place:

if (!costMap.containsKey(child) 
    || costMap.get(child) > costMap.get(node) + graph.getEdgeWeight(node, child)) 
    ...
}

would have a proper place:

if (costMap.requiresExpansion(node, child)){ //anyone can now read this code
    ...
}
\$\endgroup\$
1
  • \$\begingroup\$ whenever i say "anyone can read it" it is also an indicator for "anyone can TEST it now" \$\endgroup\$ Aug 9, 2022 at 6:44

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.