Computing most reliable path in undirected probabilistic graphs using Java

Question

(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.

Answer 1

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<Edge> 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.

Answer 2

Instead of NORMALIZATON_BASE = 0.5, I would choose either \$d=\frac{1}{10}\$ or \$d=\frac{1}{e}\$. That would effectively map each edge weight \$w\$ to \$-\log_{10}w\$ or \$-\ln w\$, respectively. (In other words, the instructions are slightly stupid, in my opinion.)