CPHSolution.java

package cph.algorithm;
import cph.instance.CPHInstance;
import cph.instance.CPHNode;

import java.util.ArrayList;
import java.util.List;

import jmh.algorithm.SwapSolution;

/**
 * A CPH solution: the set of open hubs plus, for every client, the hub that
 * serves it ({@code spokes[i]} is the index of the hub serving node {@code i},
 * or {@code -1} if node {@code i} is itself a hub). The weight is the total
 * client-to-hub distance (to be minimized).
 *
 * <p>The neighbourhood exposed to the shared local searches is "replace an open
 * hub with a non-hub node": {@link #getSolutionElements()} are the hubs and a
 * swap is valid when the incoming node is not already a hub.
 */
public class CPHSolution extends SwapSolution<CPHNode> {

    private final List<CPHNode> hubs;

    // spokes[i] holds the index of the hub that serves node i, or -1 if node i is a hub
    private final int[] spokes;

    public CPHSolution(CPHInstance instance, List<CPHNode> hubs, int[] spokes) {
        super(instance);
        this.hubs = hubs;
        this.spokes = spokes;
        calculateWeight();
    }

    public void calculateWeight() {
        totalWeight = calculateWeight(hubs, spokes);
    }

    private int calculateWeight(List<CPHNode> solutionHubs, int[] solutionSpokes) {
        int weight = 0;

        // The solution weight is the sum of the distances from each
        // client to the hub that serves it
        for (CPHNode hub : solutionHubs) {
            for (int i = 0; i < solutionSpokes.length; i++) {
                if (solutionSpokes[i] == hub.getIndex()) {
                    weight += hub.getDistanceTo(instance.getNode(i));
                }
            }
        }

        return weight;
    }

    @Override
    public List<CPHNode> getSolutionElements() {
        return hubs;
    }

    @Override
    public boolean isValidSwap(CPHNode current, CPHNode candidate) {
        return !isHub(candidate);
    }

    @Override
    public double evaluateSwap(CPHNode oldHub, CPHNode newHub) {

        // Build new hub list and spokes with the old hub replaced
        // by the new one (the new hub takes over all its clients)
        List<CPHNode> newHubs = new ArrayList<>();
        for (CPHNode hub : hubs) {
            if (hub.equals(oldHub)) {
                newHubs.add(newHub);
            } else {
                newHubs.add(hub);
            }
        }

        int[] newSpokes = new int[spokes.length];
        for (int i = 0; i < spokes.length; i++) {
            if (spokes[i] == oldHub.getIndex()) {
                newSpokes[i] = newHub.getIndex();
            } else {
                newSpokes[i] = spokes[i];
            }
        }
        newSpokes[oldHub.getIndex()] = newHub.getIndex();
        newSpokes[newHub.getIndex()] = -1;

        return calculateWeight(newHubs, newSpokes);
    }

    @Override
    public void applySwap(CPHNode oldHub, CPHNode newHub) {
        for (int i = 0; i < hubs.size(); i++) {
            if (hubs.get(i).equals(oldHub)) {
                hubs.set(i, newHub);
                break;
            }
        }

        for (int i = 0; i < spokes.length; i++) {
            if (spokes[i] == oldHub.getIndex()) {
                spokes[i] = newHub.getIndex();
            }
        }
        spokes[oldHub.getIndex()] = newHub.getIndex();
        spokes[newHub.getIndex()] = -1;

        calculateWeight();
    }

    public boolean isHub(CPHNode node) {
        return hubs.contains(node);
    }

    @Override
    public String toString() {
        List<List<Integer>> hubsWithClients = new ArrayList<>();

        for (CPHNode hub : hubs) {
            List<Integer> elements = new ArrayList<>();
            elements.add(hub.getIndex());

            for (int i = 0; i < spokes.length; i++) {
                if (spokes[i] == hub.getIndex()) {
                    elements.add(i);
                }
            }

            hubsWithClients.add(elements);
        }

        return hubsWithClients.toString();
    }

}