2
\$\begingroup\$

(See the previous iteration.)

What I did

Now I have took some (not all) good points from the previous iteration.

  1. Removed the entire weight function class,
  2. Got rid of node IDs,
  3. Improved the math a little bit,
  4. Removed the hashCode and equals,
  5. Cosmetic improvements.

Problem definition

We are given an undirected graph \$G = (V, E)\$ and a weight function \$w \colon E \to (0, 1]\$. The weight of the edge \$e \in E\$, \$w(e)\$, describes its reliability, or, in other words, the probability that the edge is available. Given two distinguished nodes \$s, t \in V\$, we wish to compute a most reliable \$s,t\$ - path.

There is, however, a catch: the cost of a path \$(v_1, \dots, v_k)\$ is $$\prod_{i = 1}^{k-1} w(v_i, v_{i + 1})$$ and not $$\sum_{i = 1}^{k-1} w(v_i, v_{i + 1}).$$

There is however a trick to remember: Whenever we read the weight of an edge \$e\$, \$w(e)\$, we set instead \$w(e) \leftarrow -\ln w(e)\$. Then, compute the ordinary shortest path in the same graph using the modified weight function. Since the algorithm does not update the actual weights, one can recover the cost of the most reliable path from the original graph.

Solution

MostReliablePathFinder.java

package net.coderodde;

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.PriorityQueue;
import java.util.Queue;
import java.util.Set;

public final class MostReliablePathFinder {

    List<UndirectedGraphNode>
         findLeastReliablePath(UndirectedGraphNode source,
                               UndirectedGraphNode target) {
        Queue<NodeHolder> open = new PriorityQueue<>();
        Set<UndirectedGraphNode> closed = new HashSet<>();
        Map<UndirectedGraphNode, UndirectedGraphNode> parents = new HashMap<>();
        Map<UndirectedGraphNode, Double> distance = new HashMap<>();

        open.add(new NodeHolder(source, 0.0));
        parents.put(source, null);
        distance.put(source, 0.0);

        while (!open.isEmpty()) {
            UndirectedGraphNode currentNode = open.remove().getNode();

            if (currentNode.equals(target)) {
                return tracebackPath(target, 
                                     parents);
            }

            if (closed.contains(currentNode)) {
                continue;
            }

            closed.add(currentNode);

            for (UndirectedGraphNode childNode : currentNode.getNeighbors()) {
                if (closed.contains(childNode)) {
                    continue;
                }

                double originalWeight = currentNode.getWeight(childNode);
                double normalizedWeight = -Math.log(originalWeight);

                Double tentativeCost = distance.get(currentNode) + 
                        normalizedWeight;

                if (!distance.containsKey(childNode) 
                        || distance.get(childNode) > tentativeCost) {
                    open.add(new NodeHolder(childNode, tentativeCost));
                    parents.put(childNode, currentNode);
                    distance.put(childNode, tentativeCost);
                }
            }
        }

        throw new IllegalArgumentException("no path");
    }   

    private static List<UndirectedGraphNode> tracebackPath(
            UndirectedGraphNode target,
            Map<UndirectedGraphNode, UndirectedGraphNode> parents) {
        List<UndirectedGraphNode> nodeList = new ArrayList<>();
        UndirectedGraphNode currentNode = target;

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

        Collections.<UndirectedGraphNode>reverse(nodeList);
        return nodeList;
    }

    private static final class NodeHolder implements Comparable<NodeHolder> {

        private final UndirectedGraphNode node;
        private final double cost;

        NodeHolder(UndirectedGraphNode node, double cost) {
            this.node = node;
            this.cost = cost;
        }

        UndirectedGraphNode getNode() {
            return node;
        }

        @Override
        public int compareTo(NodeHolder o) {
            return Double.compare(cost, o.cost);
        }
    }
}

UndirectedGraphNode.java

package net.coderodde;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;
import java.util.Set;

public final class UndirectedGraphNode {

    private final String name;
    private final Map<UndirectedGraphNode, Double> neighbors = new HashMap<>();

    public UndirectedGraphNode(String name) {
        this.name = Objects.requireNonNull(name);
    }

    public UndirectedGraphNode() {
        this("unnamed node");
    }

    public void connectTo(UndirectedGraphNode node, double probability) {
        checkProbability(probability);
        neighbors.put(node, probability);
        node.neighbors.put(this, probability);
    }

    public Set<UndirectedGraphNode> getNeighbors() {
        return Collections.unmodifiableSet(neighbors.keySet());
    }

    public Double getWeight(UndirectedGraphNode node) {
        return neighbors.get(node);
    }

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

    private boolean isValidProbability(Double probability) {
        return !probability.isInfinite() 
                && !probability.isNaN()
                && probability > 0.0
                && probability <= 1.0;
    }

    private void checkProbability(Double probability) {
        if (!isValidProbability(probability)) {
            throw new IllegalArgumentException("Invalid probability: " +
                    probability);
        }
    }
}

Demo.java

package net.coderodde;

import java.util.List;

public class Demo {

    public static void main(String[] args) {
        UndirectedGraphNode nodeA = new UndirectedGraphNode("A");
        UndirectedGraphNode nodeB = new UndirectedGraphNode("B");
        UndirectedGraphNode nodeC = new UndirectedGraphNode("C");
        UndirectedGraphNode nodeD = new UndirectedGraphNode("D");
        UndirectedGraphNode nodeE = new UndirectedGraphNode("E");
        UndirectedGraphNode nodeF = new UndirectedGraphNode("F");

        nodeA.connectTo(nodeB, 0.1);
        nodeA.connectTo(nodeC, 0.9);
        nodeA.connectTo(nodeD, 0.9);
        nodeB.connectTo(nodeC, 0.9);
        nodeB.connectTo(nodeD, 0.2);
        nodeC.connectTo(nodeD, 0.1);
        nodeE.connectTo(nodeB, 0.2);
        nodeE.connectTo(nodeF, 0.8);
        nodeF.connectTo(nodeB, 0.99);

        List<UndirectedGraphNode> path = new 
            MostReliablePathFinder().findLeastReliablePath(nodeD, nodeE);

        System.out.println(path);
        System.out.println("Cost: " + getPathReliability(path));
    }

    private static double getPathReliability(List<UndirectedGraphNode> path) {
        double cost = 1.0;

        for (int i = 0; i < path.size() - 1; ++i) {
            cost *= path.get(i).getWeight(path.get(i + 1));
        }

        return cost;
    }
}

The demo graph

Demo graph

The demo output is

[[D], [A], [C], [B], [F], [E]]
Cost: 0.5773680000000001

Critique request

As always, please tell me anything that comes to mind.

\$\endgroup\$
  • 2
    \$\begingroup\$ Could you please re-iterate which good points you've ignored, and why? So that reviewers know about these points. \$\endgroup\$ – holroy Apr 19 '17 at 14:33
2
\$\begingroup\$

I'll start with what I consider the most important and move on to the less important:

The fact that MostReliablePathFinder contains no state (no fields whatsoever) is an indicator that it is not a proper class.

new MostReliablePathFinder().findLeastReliablePath(nodeD, nodeE);

Because of this, you create an instance which lives only briefly. You don't even store it (and indeed there is no point - every PathFinder is identical). You create it and destroy it immediately.

The first little refactor would be to make findLeastReliablePath a static method. Now we don't need to create a pointless new instance when we want to call this method.

MostReliablePathFinder.findLeastReliablePath(nodeD, nodeE);

But hey - now we have a "class" that only contains static methods! This is a bad thing if we can avoid it. It's a procedural way of thinking, not an object-oriented one.

When you think about it, findLeastReliablePath should really be a (non-static) method of a Node and it should only take one parameter. We should be able to say:

List<Node> path = nodeA.findLeastReliablePath(nodeB);

Doesn't that just feel more expressive?


private boolean isValidProbability(Double probability) {
    return !probability.isInfinite() 
            && !probability.isNaN()
            && probability > 0.0
            && probability <= 1.0;
}

Your probability comes in as a primitive double connectTo(... double probability), which then gets implicitly wrapped (meaning an object is created), simply for the purpose of checking whether .isInfinite().

In fact you don't need to check this. probability > 0.0 && probability <= 1.0 is sufficient. Now we can pass the function a regular double and don't need to worry about the extra object. That said, it's now so short I wouldn't even bother having this as a function.

Even though I am an advocate of small functions, I think I would move the contents of checkProbability in to connectTo. The fact its a void function which does nothing apart from maybe throw an exception doesn't sit well with me.


findLeastReliablePath is quite a long function. You've done a good job of keeping functions nice and short everywhere else in your code. I would try and split this up. 20 lines is my usual personal maximum.

I don't really understand what your for loop is doing but that seems like a good candidate to be moved to a separate function. It would make it more readable too because you would have fewer levels of indentation.


It's possible that the following function will return null.

public Double getWeight(UndirectedGraphNode node) {
    return neighbors.get(node);
}

Both of the callers currently don't check for this. Indeed, the manner in which they call this may mean they don't need actually need to.

Anyway, returning null as a sentinel is a bad thing, even if it's implicit as it is here. Perhaps return an Optional<Double> or throw an exception.


Use final more often, both in function prototypes and for local variables. It adds some semantic meaning for a reader of your code because it shows them what values you expect to change.

It can also prevent you from making silly mistakes because you will get a compilation error if you try to change a variable you didn't mean to change.

Unfortunately, final in Java is not the best. It leads to long lines. I very much like Project Lombok's val which you may be interested to read about.


NodeHolder is this really the best name for this class? Why not Edge or Connection?

As it's only an inner class, I wouldn't worry about providing a getter - it's just unnecessary fluff. Just make the fields public and final instead.


Overall, you've improved this a lot since the last iteration so well done.

\$\endgroup\$
  • \$\begingroup\$ NodeHolder is the only way I know how to make the actual Nodes be friends with PriorityQueue. Otherwise a nice review, keep them coming! \$\endgroup\$ – coderodde Apr 19 '17 at 17:04
  • \$\begingroup\$ I don't have a problem with NodeHolder as a class, I just think it could be named better. You're welcome. \$\endgroup\$ – Michael Apr 20 '17 at 8:34

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.