(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<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,
weightFunction);
}
if (closed.contains(currentNode)) {
continue;
}
closed.add(currentNode);
for (UndirectedGraphNode childNode :
currentNode.getNeighborNodes()) {
if (closed.contains(childNode)) {
continue;
}
Double tentativeCost = distance.get(currentNode) +
weightFunction.get(currentNode, childNode);
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 Path tracebackPath(
UndirectedGraphNode target,
Map<UndirectedGraphNode, UndirectedGraphNode> parents,
UndirectedGraphProbabilisticWeightFunction weightFunction) {
List<UndirectedGraphNode> nodeList = new ArrayList<>();
UndirectedGraphNode currentNode = target;
while (currentNode != null) {
nodeList.add(currentNode);
currentNode = parents.get(currentNode);
}
Collections.<UndirectedGraphNode>reverse(nodeList);
double pathCost = 0.0;
for (int i = 0; i < nodeList.size() - 1; ++i) {
pathCost += weightFunction.get(nodeList.get(i),
nodeList.get(i + 1));
}
double base =
UndirectedGraphProbabilisticWeightFunction.NORMALIZATION_BASE;
return new Path(nodeList, Math.pow(base, pathCost));
}
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.HashSet;
import java.util.Set;
public final class UndirectedGraphNode {
private final int id;
private final Set<UndirectedGraphNode> neighbors = new HashSet<>();
public UndirectedGraphNode(int id) {
this.id = id;
}
public void addNeighbor(UndirectedGraphNode neighbor) {
if (equals(neighbor)) {
return;
}
neighbors.add(neighbor);
neighbor.neighbors.add(this);
}
public Set<UndirectedGraphNode> getNeighborNodes() {
return Collections.unmodifiableSet(neighbors);
}
public int getId() {
return id;
}
@Override
public String toString() {
return "[" + id + "]";
}
@Override
public boolean equals(Object o) {
if (o == null || !o.getClass().equals(getClass())) {
return false;
}
if (o == this) {
return true;
}
return id == ((UndirectedGraphNode) o).id;
}
@Override
public int hashCode() {
return id;
}
}
UndirectedGraphProbabilisticWeightFunction.java
package net.coderodde;
import java.util.HashMap;
import java.util.Map;
public final class UndirectedGraphProbabilisticWeightFunction {
static final double NORMALIZATION_BASE = 0.5;
private static final double NORMALIZATION_DIVISOR =
Math.log(NORMALIZATION_BASE);
private final Map<UndirectedGraphNode,
Map<UndirectedGraphNode, Double>> map = new HashMap<>();
public void put(UndirectedGraphNode node1,
UndirectedGraphNode node2,
Double probability) {
checkIsValidProbability(probability);
if (node1.equals(node2)) {
return;
}
if (node1.getId() > node2.getId()) {
UndirectedGraphNode tmp = node1;
node1 = node2;
node2 = tmp;
}
if (!map.containsKey(node1)) {
map.put(node1, new HashMap<>());
}
map.get(node1).put(node2, probability);
}
public Double get(UndirectedGraphNode node1, UndirectedGraphNode node2) {
if (node1.getId() > node2.getId()) {
UndirectedGraphNode tmp = node1;
node1 = node2;
node2 = tmp;
}
return map.get(node1).get(node2);
}
UndirectedGraphProbabilisticWeightFunction normalize() {
UndirectedGraphProbabilisticWeightFunction normalized =
new UndirectedGraphProbabilisticWeightFunction();
for (Map.Entry<UndirectedGraphNode,
Map<UndirectedGraphNode, Double>> entry :
map.entrySet()) {
UndirectedGraphNode node = entry.getKey();
Map<UndirectedGraphNode, Double> newMap = new HashMap<>();
normalized.map.put(node, newMap);
for (Map.Entry<UndirectedGraphNode, Double> neighbor :
entry.getValue().entrySet()) {
newMap.put(neighbor.getKey(),
Math.log(neighbor.getValue()) /
NORMALIZATION_DIVISOR);
}
}
return normalized;
}
private void checkIsValidProbability(Double probability) {
if (probability.isInfinite()) {
throw new IllegalArgumentException("infinite probability");
}
if (probability.isNaN()) {
throw new IllegalArgumentException("NaN");
}
if (probability <= 0.0) {
// Edge reliability of zero (0.0) should be represented by the
// absence of the edge.
throw new IllegalArgumentException("Too small probability: " +
probability);
}
if (probability > 1.0) {
throw new IllegalArgumentException("Too large probability: " +
probability);
}
}
}
Path.java
package net.coderodde;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public final class Path {
private final List<UndirectedGraphNode> nodeList = new ArrayList<>();
private final double probability;
public Path(List<UndirectedGraphNode> nodeList, double probability) {
this.nodeList.addAll(nodeList);
this.probability = probability;
}
public List<UndirectedGraphNode> getNodes() {
return Collections.<UndirectedGraphNode>unmodifiableList(nodeList);
}
public double getProbability() {
return probability;
}
public String toString() {
StringBuilder sb = new StringBuilder();
String separator = "";
for (UndirectedGraphNode node : nodeList) {
sb.append(separator);
sb.append(node);
separator = " -> ";
}
sb.append(" ").append(probability);
return sb.toString();
}
}
Demo.java
package net.coderodde;
public class Demo {
public static void main(String[] args) {
UndirectedGraphNode node1 = new UndirectedGraphNode(1);
UndirectedGraphNode node2 = new UndirectedGraphNode(2);
UndirectedGraphNode node3 = new UndirectedGraphNode(3);
UndirectedGraphNode node4 = new UndirectedGraphNode(4);
UndirectedGraphNode node5 = new UndirectedGraphNode(5);
UndirectedGraphNode node6 = new UndirectedGraphNode(6);
UndirectedGraphProbabilisticWeightFunction wf =
new UndirectedGraphProbabilisticWeightFunction();
node1.addNeighbor(node2);
node1.addNeighbor(node3);
node1.addNeighbor(node4);
node2.addNeighbor(node3);
node2.addNeighbor(node4);
node3.addNeighbor(node4);
node5.addNeighbor(node2);
node5.addNeighbor(node6);
node6.addNeighbor(node2);
wf.put(node1, node2, 0.1);
wf.put(node1, node3, 0.9);
wf.put(node1, node4, 0.9);
wf.put(node2, node3, 0.9);
wf.put(node2, node4, 0.2);
wf.put(node3, node4, 0.1);
wf.put(node2, node5, 0.2);
wf.put(node5, node6, 0.8);
wf.put(node6, node2, 0.99);
System.out.println(new MostReliablePathFinder()
.findLeastReliablePath(node4, node5, wf));
}
}
The demo graph
The demo output is
[4] -> [1] -> [3] -> [2] -> [6] -> [5] 0.577368
Critique request
Please tell me anything that comes to mind.
node5.addNeighbor(node2)
which handles the connection between nodes 5 and 2. Same goes for 2 and 6. \$\endgroup\$neighbor.neighbors.add(this);
Gotcha. \$\endgroup\$