3
\$\begingroup\$

I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem.

Below is my version. It's super slow, but I find it funny.

BruteForceShortestPath.java:

package net.coderodde.graph.experimental;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements a brute force shortest path algorithm for directed,
 * weighted graphs.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 25, 2015)
 */
public class BruteForceShortestPath {

    private final DirectedGraphNode source;
    private final DirectedGraphNode target;
    private final DirectedGraphWeightFunction weightFunction;
    private final Set<DirectedGraphNode> visitedSet = new HashSet<>();
    private final Map<DirectedGraphNode, DirectedGraphNode> parentMap = 
            new HashMap<>();

    public static List<DirectedGraphNode> 
        search(DirectedGraphNode source,
               DirectedGraphNode target,
               DirectedGraphWeightFunction weightFunction) {
        Objects.requireNonNull(source, "The source node is null.");
        Objects.requireNonNull(target, "The target node is null.");
        Objects.requireNonNull(weightFunction, "The weight function is null.");

        return new BruteForceShortestPath(source, 
                                          target, 
                                          weightFunction).search();
    }

    private BruteForceShortestPath(DirectedGraphNode source,
                                   DirectedGraphNode target,
                                   DirectedGraphWeightFunction weightFunction) {
        this.source = source;
        this.target = target;
        this.weightFunction = weightFunction;
        this.parentMap.put(source, null);
    }

    private double w(DirectedGraphNode tail, DirectedGraphNode head) {
        return weightFunction.get(tail, head);
    }

    private double search(DirectedGraphNode current,
                          double costFromSource,
                          double bestKnownCost) {
        if (current.equals(target)) {
            return costFromSource;
        }

        if (costFromSource >= bestKnownCost) {
            return bestKnownCost;
        }

        visitedSet.add(current);
        double currentCost;

        for (DirectedGraphNode child : current.children()) {
            if (!visitedSet.contains(child)) {
                currentCost = search(child,
                                     costFromSource + w(current, child),
                                     bestKnownCost);

                if (bestKnownCost > currentCost) {
                    bestKnownCost = currentCost;
                    parentMap.put(child, current);
                }
            }
        }

        visitedSet.remove(current);
        return bestKnownCost;
    }

    private List<DirectedGraphNode> search() {
        search(source, 0.0, Double.POSITIVE_INFINITY);

        if (!parentMap.containsKey(target)) {
            return Collections.<DirectedGraphNode>emptyList();
        }

        return tracebackPath();
    }

    private List<DirectedGraphNode> tracebackPath() {
        DirectedGraphNode current = target;
        List<DirectedGraphNode> path = new ArrayList<>();

        while (current != null) {
            path.add(current);
            current = parentMap.get(current);
        }

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

DirectedGraphNode.java (ignore):

package net.coderodde.graph.experimental;

import java.util.Collections;
import java.util.LinkedHashSet;
import java.util.Objects;
import java.util.Set;

/**
 * This class implements directed graph nodes.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Sep 25, 2015)
 */
public class DirectedGraphNode {

    private final String name;
    private final Set<DirectedGraphNode> children = new LinkedHashSet<>();

    public DirectedGraphNode(String name) {
        Objects.requireNonNull(name, "The name of a new node is null.");
        this.name = name;
    }

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

    public Set<DirectedGraphNode> children() {
        return Collections.<DirectedGraphNode>unmodifiableSet(children);
    }

    @Override
    public String toString() {
        return "[DirectedGraphNode \"" + name + "\"]";
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof DirectedGraphNode)) {
            return false;
        }

        return name.equals(((DirectedGraphNode) o).name);
    }

    // Generated by NetBeans.
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 17 * hash + Objects.hashCode(this.name);
        return hash;
    }
}

DirectedGraphWeightFunction.java (ignore):

package net.coderodde.graph.experimental;

import java.util.HashMap;
import java.util.Map;

/**
 * This class implements directed graph weight functions.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class DirectedGraphWeightFunction {

    private final Map<DirectedGraphNode, Map<DirectedGraphNode, Double>> map = 
            new HashMap<>();

    public void put(DirectedGraphNode tail,
                    DirectedGraphNode head, 
                    double weight) {
        if (!map.containsKey(tail)) {
            map.put(tail, new HashMap<>());
        }

        map.get(tail).put(head, weight);
    }

    public double get(DirectedGraphNode tail, DirectedGraphNode head) {
        return map.get(tail).get(head);
    }
}

Demo.java (ignore):

import java.util.List;
import net.coderodde.graph.experimental.BruteForceShortestPath;
import net.coderodde.graph.experimental.DirectedGraphNode;
import net.coderodde.graph.experimental.DirectedGraphWeightFunction;

public class Demo {

    public static void main(final String... args) {
        DirectedGraphNode a = new DirectedGraphNode("A");
        DirectedGraphNode b = new DirectedGraphNode("B");
        DirectedGraphNode c = new DirectedGraphNode("C");
        DirectedGraphNode d = new DirectedGraphNode("D");
        DirectedGraphNode e = new DirectedGraphNode("E");
        DirectedGraphNode f = new DirectedGraphNode("F");

        DirectedGraphWeightFunction wf = new DirectedGraphWeightFunction();

        /* The first graph:
         *
         * +--2.0--B--1.0--D--4.0--E
         * |               |\
         * A--3.5--C--3.0--+ +--1.6--F
         */

        a.addChild(b); wf.put(a, b, 2.0);
        a.addChild(c); wf.put(a, c, 3.5);
        b.addChild(a); wf.put(b, a, 2.0);
        b.addChild(d); wf.put(b, d, 1.0);
        c.addChild(a); wf.put(c, a, 3.5);
        c.addChild(d); wf.put(c, d, 3.0);
        d.addChild(b); wf.put(d, b, 1.0);
        d.addChild(c); wf.put(d, c, 3.0);
        d.addChild(e); wf.put(d, e, 4.0);
        d.addChild(f); wf.put(d, f, 1.6);
        e.addChild(d); wf.put(e, d, 4.0);
        f.addChild(d); wf.put(f, d, 1.6);

        long ta = System.currentTimeMillis();
        List<DirectedGraphNode> path = BruteForceShortestPath.search(a, f, wf);
        long tb = System.currentTimeMillis();

        System.out.println("Time: " + (tb - ta) + " ms.");
        printPath(path);

        System.out.println("\nLarger demo:");

        // (1) Change 4 to 5, and "brute-forceness" will become obvious. :)
        // (2) Change the cost arguments to their respective inverses
        // (i.e., -1.0 & -1.414), and see what happens.
        Data data = getLargerGraph(8, 1.0, 1.414);
        DirectedGraphNode[][] G = data.gridGraph;
        DirectedGraphWeightFunction wf2 = data.weightFunction;

        // Top-left corner node [0, 0].
        DirectedGraphNode source = G[0][0];

        // [x = 3, y = 2].
        DirectedGraphNode target = G[6][7];

        System.out.println("Source: " + source);
        System.out.println("Target: " + target);

        ta = System.currentTimeMillis();
        path = BruteForceShortestPath.search(source, target, wf2);
        tb = System.currentTimeMillis();

        System.out.println("Time: " + (tb - ta) + " ms.");
        printPath(path);
    }

    private static final class Data {
        DirectedGraphNode[][] gridGraph;
        DirectedGraphWeightFunction weightFunction;
    }

    /**
     * Generates a grid graph with width and height of {@code N} nodes.
     */
    private static Data getLargerGraph(int N,
                                       double horzVertCost,
                                       double diagonalCost) {
        DirectedGraphNode[][] graph = new DirectedGraphNode[N][N];
        DirectedGraphWeightFunction f = new DirectedGraphWeightFunction();

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                graph[y][x] = new DirectedGraphNode("[" + x + ", " + y + "]");
            }
        }

        // Horizontal edges.
        for (int x = 0; x < N - 1; x++) {
            for (int y = 0; y < N; y++) {
                graph[y][x].addChild(graph[y][x + 1]);
                graph[y][x + 1].addChild(graph[y][x]);
                f.put(graph[y][x], graph[y][x  + 1], horzVertCost);
                f.put(graph[y][x + 1], graph[y][x], horzVertCost);
            }
        }

        // Vertical edges.
        for (int y = 0; y < N - 1; y++) {
            for (int x = 0; x < N; x++) {
                graph[y][x].addChild(graph[y + 1][x]);
                graph[y + 1][x].addChild(graph[y][x]);
                f.put(graph[y][x], graph[y + 1][x], horzVertCost);
                f.put(graph[y + 1][x], graph[y][x], horzVertCost);
            }
        }

        // Diagonal "\"-edges.
        for (int x = 0; x < N - 1; x++) {
            for (int y = 0; y < N - 1; y++) {
                graph[y][x].addChild(graph[y + 1][x + 1]);
                graph[y + 1][x + 1].addChild(graph[y][x]);
                f.put(graph[y][x], graph[y + 1][x + 1], diagonalCost);
                f.put(graph[y + 1][x + 1], graph[y][x], diagonalCost);
            }
        }

        // Diagonal "/"-edges.
        for (int x = 0; x < N - 1; x++) {
            for (int y = 1; y < N; y++) {
                graph[y][x].addChild(graph[y - 1][x + 1]);
                graph[y - 1][x + 1].addChild(graph[y][x]);
                f.put(graph[y][x], graph[y - 1][x + 1], diagonalCost);
                f.put(graph[y - 1][x + 1], graph[y][x], diagonalCost);
            }
        }

        Data ret = new Data();
        ret.gridGraph = graph;
        ret.weightFunction = f;
        return ret;
    }

    private static void printPath(List<DirectedGraphNode> path) {
        for (DirectedGraphNode node : path) {
            System.out.println(node);       
        }
    }  
}

I posted all other classes required for running the demonstration, yet they are not of my top concern. So, anything I could do to improve the program text?

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