(See the previous iteration.)
What I did
Now I have took some (not all) good points from the previous iteration.
- Removed the entire weight function class,
- Got rid of node IDs,
- Improved the math a little bit,
- Removed the
hashCodeandequals, - 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
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.
