1
\$\begingroup\$

This program is not that much about graph search as it is about a design pattern that allows us to decide how much time we may invest in searching for a path. Here's the code:

BreadthFirstSearch.java

package net.coderodde.graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * This class implements the breadth-first search.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 18, 2017)
 * @param <N> the graph node type.
 */
public final class BreadthFirstSearch<N extends ChildNodeExpander<N>> {

    /**
     * This interface implements the node listener.
     * 
     * @param <N> the graph node type.
     */
    public interface NodeListener<N> {

        /**
         * Called right before starting to expand the nodes.
         * 
         * @param sourceNode the source node.
         */
        public void onBeginSearch(N sourceNode);

        /**
         * Called when {@code node} is reached by the search for the first time.
         * 
         * @param node the reached node.
         */
        public void onReach(N node);

        /**
         * Called when {@code node} is removed from the search frontier and is
         * expanded.
         * 
         * @param node the expanded node.
         */
        public void onExpand(N node);

        /**
         * Called right after the graph search reaches the target node.
         * 
         * @param targetNode the target node.
         */
        public void onEndSearchSuccess(N targetNode);

        /**
         * Called right after the graph search decides that the target node is
         * not reachable.
         * 
         * @param targetNode the target node.
         */
        public void onEndSearchFailure(N targetNode);
    }

    /**
     * Initiates the path search.
     * 
     * @param <N> the graph node type.
     * @return the source node selector.
     */
    public static <N extends ChildNodeExpander<N>> 
            SourceNodeSelector<N> findShortestPath() {
        return new SourceNodeSelector<>();
    }

    /**
     * Implements the source node selector.
     * 
     * @param <N> the graph node type.
     */
    public static final class 
            SourceNodeSelector<N extends ChildNodeExpander<N>> {

        /**
         * Selects the source node.
         * 
         * @param sourceNode the source node.
         * @return the target node selector.
         */
        TargetNodeSelector<N> from(N sourceNode) {
            return new TargetNodeSelector<>(
                Objects.requireNonNull(sourceNode, "The sourceNode is null."));
        }
    }

    /**
     * Implements the target node selector.
     * 
     * @param <N> the graph node type.
     */
    public static final class 
            TargetNodeSelector<N extends ChildNodeExpander<N>> {

        private final N sourceNode;

        TargetNodeSelector(N sourceNode) {
            this.sourceNode = sourceNode;
        }

        /**
         * Selects the target node.
         * 
         * @param targetNode the target node.
         * @return the search state.
         */
        public SearchState<N> to(N targetNode) {
            return new SearchState<>(
                sourceNode,
                Objects.requireNonNull(targetNode, "The targetNode is null."));
        }
    }

    /**
     * Implements the actual path search state.
     * 
     * @param <N> the graph node.
     */
    public static final class SearchState<N extends ChildNodeExpander<N>> {

        /**
         * The state of search.
         */
        public static enum State {
            RUNNING,    // Still running.
            FOUND_PATH, // Target node reached.
            NO_PATH     // Target node not reachable.
        }

        private static final int DEFAULT_NUMBER_OF_EXPANSIONS_PER_ITERATION = 1;

        private final N sourceNode;
        private final N targetNode;
        private int expansionsPerIteration = 
                DEFAULT_NUMBER_OF_EXPANSIONS_PER_ITERATION;

        private State state = null;
        private final Deque<N> queue = new ArrayDeque<>();
        private final Map<N, N> parents = new HashMap<>();
        private final List<NodeListener<N>> nodeListeners = new ArrayList<>();

        SearchState(N sourceNode, N targetNode) {
            this.sourceNode = sourceNode;
            this.targetNode = targetNode;
            this.queue.addLast(sourceNode);
            this.parents.put(sourceNode, null);
        }

        /**
         * Sets the number of node expansion per single iteration, i.e., per 
         * single call to {@link iterate}.
         * 
         * @param expansions the number of expansions per iteration.
         * @return this state object.
         */
        public SearchState<N> setExpansionsPerIteration(int expansions) {
            this.expansionsPerIteration = Math.max(1, expansions);
            return this;
        }

        public SearchState<N> addNodeListener(NodeListener<N> listener) {
            nodeListeners.add(
                    Objects.requireNonNull(
                            listener, 
                            "The input listener is null."));
            return this;
        }

        /**
         * Performs a single iteration.
         */
        public void iterate() {
            if (state == null) {
                onBeginSearch(sourceNode);
                state = State.RUNNING;
            }

            if (isSearchComplete()) {
                return;
            }

            for (int i = 0; i < expansionsPerIteration; ++i) {
                if (queue.isEmpty()) {
                    state = State.NO_PATH;
                    onEndSearchFailure(targetNode);
                    return;
                }

                N currentNode = queue.removeFirst();
                onExpand(currentNode);

                if (currentNode.equals(targetNode)) {
                    state = State.FOUND_PATH;
                    onEndSearchSuccess(targetNode);
                    return;
                }

                for (N childNode : currentNode.getChildren()) {
                    if (!parents.containsKey(childNode)) {
                        // We came to childNode from currentNode:
                        onReach(childNode);
                        parents.put(childNode, currentNode); 
                        queue.addLast(childNode);
                    }
                }
            }
        }

        /**
         * Searches for the 
         */
        public void search() {
            while (!isSearchComplete()) {
                iterate();
            }
        }

        /**
         * Searches until {@code milliseconds} milliseconds are elapsed, or
         * until the search is complete, whichever happens first.
         * 
         * @param milliseconds the maximum allowed duration of the search.
         */
        public void searchFor(long milliseconds) {
            long startTime = System.currentTimeMillis();

            while (!isSearchComplete()) {
                iterate();
                long endTime = System.currentTimeMillis();
                long elapsedTime = endTime - startTime;

                if (elapsedTime >= milliseconds) {
                    break;
                }
            }
        }

        public State getState() {
            return state;
        }

        public boolean isSearchComplete() {
            return state != null && state != State.RUNNING;
        }

        public List<N> getShortestPath() {
            switch (state) {
                case RUNNING:
                    throw new IllegalStateException(
                            "The path search is not yet complete.");

                case NO_PATH:
                    throw new IllegalStateException(
                            "The target node is not reachable from the source " +
                                    "node.");

                case FOUND_PATH:
                    return tracebackPath();

                default:
                    throw new IllegalStateException("This should not happen.");
            }
        }

        private List<N> tracebackPath() {
            List<N> path = new ArrayList<>();
            N currentNode = targetNode;

            while (currentNode != null) {
                path.add(currentNode);
                currentNode = parents.get(currentNode);
            }

            Collections.<N>reverse(path);
            return path;
        }

        private void onBeginSearch(N sourceNode) {
            for (NodeListener<N> nodeListener : nodeListeners) {
                nodeListener.onBeginSearch(sourceNode);
            }
        }

        private void onReach(N node) {
            for (NodeListener<N> nodeListener : nodeListeners) {
                nodeListener.onReach(node);
            }
        }

        private void onExpand(N node) {
            for (NodeListener<N> nodeListener : nodeListeners) {
                nodeListener.onExpand(node);
            }
        }

        private void onEndSearchSuccess(N targetNode) {
            for (NodeListener<N> nodeListener : nodeListeners) {
                nodeListener.onEndSearchSuccess(targetNode);
            }
        }

        private void onEndSearchFailure(N targetNode) {
            for (NodeListener<N> nodeListener : nodeListeners) {
                nodeListener.onEndSearchFailure(targetNode);
            }
        }
    }
}

ChildNodeExpander.java

package net.coderodde.graph;

import java.util.Collection;

/**
 * This interface defines the API for graph node types providing a view over its
 * child nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @param <N> the graph node type.
 */
public interface ChildNodeExpander<N> {

    /**
     * Returns a view over the child nodes.
     * 
     * @return a collection of child nodes.
     */
    public Collection<N> getChildren();
}

DirectedGraphNode.java

package net.coderodde.graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

/**
 * This class implements a directed graph node type using the adjacency lists.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 18, 2017)
 */
public final class DirectedGraphNode 
        implements ChildNodeExpander<DirectedGraphNode> {

    private final int id;

    public DirectedGraphNode(int id) {
        this.id = id;
    }

    private final List<DirectedGraphNode> children = new ArrayList<>();
    private final List<DirectedGraphNode> immutableChildrenView = 
            Collections.<DirectedGraphNode>unmodifiableList(children);

    public void addChild(DirectedGraphNode child) {
        children.add(Objects.requireNonNull(child));
    }

    @Override
    public List<DirectedGraphNode> getChildren() {
        return immutableChildrenView;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) {
            return true;
        } 

        if (o == null) {
            return false;
        } 

        if (!getClass().equals(o.getClass())) {
            return false;
        }

        DirectedGraphNode other = (DirectedGraphNode) o;
        return id == other.id;
    }

    @Override
    public int hashCode() {
        return id;
    }

    @Override
    public String toString() {
        return Integer.toString(id);
    }
}

Main.java

package net.coderodde.graph;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Runs a demonstration program.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 18, 2017)
 */
public final class Main {

    private static final int NODES = 1_000_000;
    private static final int ARCS = 6_000_000;

    public static void main(String[] args) {
        Random random = new Random();
        System.out.println("Building graph...");
        List<DirectedGraphNode> nodes = createRandomGraph(NODES,
                                                          ARCS,
                                                          random);

        System.out.println("Graph built!");
        DirectedGraphNode sourceNode = choose(nodes, random);
        DirectedGraphNode targetNode = choose(nodes, random);

        System.out.println();
        System.out.println("Source: " + sourceNode);
        System.out.println("Target: " + targetNode);
        System.out.println();

        long start = System.currentTimeMillis();

        BreadthFirstSearch.SearchState<DirectedGraphNode> bfs = 
                BreadthFirstSearch.<DirectedGraphNode>findShortestPath()
                                  .from(sourceNode)
                                  .to(targetNode)
                                  .setExpansionsPerIteration(10);

        while (!bfs.isSearchComplete()) {
            bfs.searchFor(250L);
            System.out.println("Time elapsed.");
        }

        long end = System.currentTimeMillis();

        if (bfs.getState()
                .equals(BreadthFirstSearch.SearchState.State.FOUND_PATH)) {
            System.out.println("Path: " + bfs.getShortestPath());
        } else {
            System.out.println("Target not reachable.");
        }

        System.out.println("Duration: " + (end - start) + " milliseconds.");
        System.out.println();

        start = System.currentTimeMillis();

        bfs = BreadthFirstSearch.<DirectedGraphNode>findShortestPath()
                                .from(sourceNode)
                                .to(targetNode)
                                .setExpansionsPerIteration(10);

        bfs.search();
        end = System.currentTimeMillis();

        if (bfs.getState()
                .equals(BreadthFirstSearch.SearchState.State.FOUND_PATH)) {
            System.out.println("Path: " + bfs.getShortestPath());
        } else {
            System.out.println("Target not reachable.");
        }

        System.out.println("Duration: " + (end - start) + " milliseconds.");
    }

    private static List<DirectedGraphNode> createRandomGraph(int nodes,
                                                             int arcs,
                                                             Random random) {
        List<DirectedGraphNode> nodeList = new ArrayList<>(nodes);

        for (int i = 0; i < nodes; ++i) {
            nodeList.add(new DirectedGraphNode(i));
        }

        for (int arc = 0; arc < arcs; ++arc) {
            DirectedGraphNode tail = choose(nodeList, random);
            DirectedGraphNode head = choose(nodeList, random);
            tail.addChild(head);
        }

        return nodeList;
    }

    private static <T> T choose(List<T> list, Random random) {
        return list.get(random.nextInt(list.size()));
    }
}

BreadthFirstSearchTest.java

package net.coderodde.graph;

import java.util.Arrays;
import java.util.List;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class BreadthFirstSearchTest {

    @Test
    public void test() {
        DirectedGraphNode a  = new DirectedGraphNode(0);
        DirectedGraphNode b  = new DirectedGraphNode(1);
        DirectedGraphNode c1 = new DirectedGraphNode(2);
        DirectedGraphNode c2 = new DirectedGraphNode(3);
        DirectedGraphNode d  = new DirectedGraphNode(4);
        DirectedGraphNode e  = new DirectedGraphNode(5);

        a.addChild(b);
        b.addChild(c1);
        b.addChild(c2);
        c1.addChild(d);
        d.addChild(e);
        c2.addChild(e);

        BreadthFirstSearch.NodeListener<DirectedGraphNode> listener1 =
        new BreadthFirstSearch.NodeListener<DirectedGraphNode>() {

            @Override
            public void onBeginSearch(DirectedGraphNode sourceNode) {

            }

            @Override
            public void onReach(DirectedGraphNode node) {
                System.out.println("1.onReach: " + node);
            }

            @Override
            public void onExpand(DirectedGraphNode node) {
                System.out.println("1.onExpand: " + node);
            }

            @Override
            public void onEndSearchSuccess(DirectedGraphNode targetNode) {
                System.out.println("1.onEndSearchSuccess: " + targetNode);
            }

            @Override
            public void onEndSearchFailure(DirectedGraphNode targetNode) {
                System.out.println("1.onEndSearchFailure: " + targetNode);
            }
        };

        BreadthFirstSearch.NodeListener<DirectedGraphNode> listener2 =
        new BreadthFirstSearch.NodeListener<DirectedGraphNode>() {

            @Override
            public void onBeginSearch(DirectedGraphNode sourceNode) {
                System.out.println("2.onBeginSearch: " + sourceNode);
            }

            @Override
            public void onReach(DirectedGraphNode node) {

            }

            @Override
            public void onExpand(DirectedGraphNode node) {

            }

            @Override
            public void onEndSearchSuccess(DirectedGraphNode targetNode) {
                System.out.println("2.onEndSearchSuccess: " + targetNode);
            }

            @Override
            public void onEndSearchFailure(DirectedGraphNode targetNode) {
                System.out.println("2.onEndSearchFailure: " + targetNode);
            }
        };

        BreadthFirstSearch.SearchState<DirectedGraphNode> bfs = 
                BreadthFirstSearch.<DirectedGraphNode>findShortestPath()
                                  .from(a)
                                  .to(e)
                                  .addNodeListener(listener1)
                                  .addNodeListener(listener2);

        bfs.search();

        assertTrue(bfs.isSearchComplete());
        assertEquals(BreadthFirstSearch.SearchState.State.FOUND_PATH,
                     bfs.getState());

        List<DirectedGraphNode> path = bfs.getShortestPath();
        assertEquals(4, path.size());
        assertEquals(Arrays.asList(a, b, c2, e), path);
    }
}

Critique request

Any comment how am I doing here?

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