Computing most reliable path in undirected probabilistic graphs using Java

(See the next iteration.)

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:
Prior to computing the path, set for each edge \$e\$ \$w(e) \leftarrow \log_d w(e)\$, where \$d \in (0, 1)\$. Then, compute the ordinary shortest path in the same graph using the modified weight function. Next, suppose \$P = (v_1, \dots, v_k)\$ is a shortest path in the graph. You return \$P\$ as is, and you return as its cost \$d^{c(P)}\$, where
$$
c(P) = \sum_{i = 1}^{k - 1} w(v_i, v_{i + 1})
$$
is the cost of \$P\$ in the modified 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 {

Path
findLeastReliablePath(
UndirectedGraphNode source,
UndirectedGraphNode target,
UndirectedGraphProbabilisticWeightFunction weightFunction) {
weightFunction = weightFunction.normalize();

Queue open = new PriorityQueue<>();
Set closed = new HashSet<>();
Map parents = new HashMap<>();
Map distance = new HashMap<>();

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

while (!open.isEmpty()) {
UndirectedGraphNode currentNode = ope

Just a few things. Nothing to do with the algorithm.

UndirectedGraphProbabilisticWeightFunction

The fact that this is a class ending with the word Function is a sign this isn't a true class. The state that this encapsulates is the minimum probability and a list of connections between nodes. We already have that list of connections in the form of the node's neighbours.

I would change the sets of neighbours contained by the nodes to contain Edges. An Edge would simply consist of a Node and a probability.

class Edge
{
   final double              probability;
   final UndirectedGraphNode neighbor;
}

class UndirectedGraphNode 
{
    private final Set neighbors = new HashSet<>(); //maybe rename this

    public void addNeighbor(Edge edge) { //maybe rename this
        if (this.equals(edge.neighbor)) return;

        neighbors.add(edge);
        neighbor.neighbors.add(new Edge(edge.probability, this));
    }
}

This gets rid of the entire WeightFunction class. It also (I think) allows you to get rid of the ID concept in the Node.

Speaking of which, if you cannot get rid of the ID counter, consider generating the ID of the Node from a private static counter rather than forcing the user of the class to add one.

(what happens if they add multiple Nodes with the same ID?)

On a related note, I question whether your equals function in a Node is good enough. I would say a Node is equal to another Node if their set of Edges is equal.

checkIsValidProbability is a funny function. I would change it to

private boolean isValidProbability(Double probability) {
    return !probability.isInfinite() && !probability.isNaN() //...
}

If the user violates this, simply throw an exception saying "probability must be between zero (exclusive) and one (inclusive)". This covers all bases without being ambiguous.

Path should not be told what it's probability is. It should calculate it for itself. What if a user of the class wanted to create a Path where they didn't know the probability beforehand? What if a path is created and one of the Nodes within it subsequently gains or loses a neighbour? The probability of the path is then not reliable.

Sorry if that was a bit unstructured but hopefully there's something useful in there. I may add more thoughts as I think of them.

StackExchange Code Review Q#161118, answer score: 2