FastIsochroneAlgorithm.java

/*  This file is part of Openrouteservice.
 *
 *  Openrouteservice is free software; you can redistribute it and/or modify it under the terms of the
 *  GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1
 *  of the License, or (at your option) any later version.

 *  This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
 *  without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *  See the GNU Lesser General Public License for more details.

 *  You should have received a copy of the GNU Lesser General Public License along with this library;
 *  if not, see <https://www.gnu.org/licenses/>.
 */
package org.heigit.ors.fastisochrones;

import com.carrotsearch.hppc.IntObjectMap;
import com.carrotsearch.hppc.cursors.IntObjectCursor;
import com.graphhopper.coll.GHIntObjectHashMap;
import com.graphhopper.routing.SPTEntry;
import com.graphhopper.routing.util.EdgeFilter;
import com.graphhopper.routing.util.TraversalMode;
import com.graphhopper.routing.weighting.Weighting;
import com.graphhopper.storage.Graph;
import org.heigit.ors.fastisochrones.partitioning.storage.CellStorage;
import org.heigit.ors.fastisochrones.partitioning.storage.IsochroneNodeStorage;
import org.heigit.ors.fastisochrones.storage.BorderNodeDistanceStorage;
import org.heigit.ors.fastisochrones.storage.EccentricityStorage;
import org.heigit.ors.routing.graphhopper.extensions.edgefilters.EdgeFilterSequence;

import java.util.*;

/**
 * Implementation of Fast Isochrones
 * <p>
 *
 * @author Hendrik Leuschner
 */
public class FastIsochroneAlgorithm extends AbstractIsochroneAlgorithm {
    private static final String NAME = "FastIsochrone";
    protected IntObjectMap<SPTEntry> startCellMap;
    protected Set<Integer> activeBorderNodes;
    protected Set<Integer> inactiveBorderNodes;
    protected Set<Integer> fullyReachableCells;
    protected Map<Integer, Map<Integer, Double>> upAndCoreGraphDistMap;
    protected Map<Integer, IntObjectMap<SPTEntry>> activeCellMaps;
    int from;
    int fromNonVirtual;

    public FastIsochroneAlgorithm(Graph graph,
                                  Weighting weighting,
                                  TraversalMode tMode,
                                  CellStorage cellStorage,
                                  IsochroneNodeStorage isochroneNodeStorage,
                                  EccentricityStorage eccentricityStorage,
                                  BorderNodeDistanceStorage borderNodeDistanceStorage,
                                  EdgeFilter additionalEdgeFilter) {
        super(graph, weighting, tMode, cellStorage, isochroneNodeStorage, eccentricityStorage, borderNodeDistanceStorage, additionalEdgeFilter);
    }

    @Override
    protected void initCollections(int size) {
        startCellMap = new GHIntObjectHashMap<>(size);
    }

    @Override
    public void init(int from, int fromNonVirtual, double isochroneLimit) {
        this.from = from;
        this.fromNonVirtual = fromNonVirtual;
        this.isochroneLimit = isochroneLimit;
        activeBorderNodes = new HashSet<>();
        inactiveBorderNodes = new HashSet<>();
        fullyReachableCells = new HashSet<>();
        upAndCoreGraphDistMap = new HashMap<>();
    }

    @Override
    void runStartCellPhase() {
        int startCell = isochroneNodeStorage.getCellId(fromNonVirtual);
        CoreRangeDijkstra coreRangeDijkstra = new CoreRangeDijkstra(graph, weighting, isochroneNodeStorage, borderNodeDistanceStorage);
        EdgeFilterSequence edgeFilterSequence = new EdgeFilterSequence();
        if (additionalEdgeFilter != null)
            edgeFilterSequence.add(additionalEdgeFilter);
        edgeFilterSequence.add(
                new CellAndBorderNodeFilter(isochroneNodeStorage,
                        startCell,
                        graph.getNodes())
        );
        coreRangeDijkstra.setEdgeFilter(edgeFilterSequence);
        coreRangeDijkstra.setIsochroneLimit(isochroneLimit);
        coreRangeDijkstra.initFrom(from);
        coreRangeDijkstra.runAlgo();
        startCellMap = coreRangeDijkstra.getFromMap();
        findFullyReachableCells(startCellMap);

        for (int inactiveBorderNode : inactiveBorderNodes) {
            startCellMap.remove(inactiveBorderNode);
            activeBorderNodes.remove(inactiveBorderNode);
        }

        for (int sweepEndNode : activeBorderNodes) {
            double dist = coreRangeDijkstra.fromMap.get(sweepEndNode).getWeightOfVisitedPath();
            int cell = isochroneNodeStorage.getCellId(sweepEndNode);
            if (cell == startCell)
                continue;
            if (!upAndCoreGraphDistMap.containsKey(cell))
                upAndCoreGraphDistMap.put(cell, new HashMap<>());
            upAndCoreGraphDistMap.get(cell).put(sweepEndNode, dist);
            startCellMap.remove(sweepEndNode);
        }
    }

    @Override
    public boolean finishedStartCellPhase() {
        return true;
    }

    /**
     * Run the ALT algo in the core
     */
    @Override
    void runBorderNodePhase() {
        //This implementation combines running in the start cell and running on the border nodes in one phase
    }

    @Override
    public boolean finishedBorderNodePhase() {
        //This implementation combines running in the start cell and running on the border nodes in one phase
        return true;
    }

    @Override
    void runActiveCellPhase() {
        activeCellMaps = new HashMap<>(upAndCoreGraphDistMap.entrySet().size());
        activeCellMaps.put(isochroneNodeStorage.getCellId(fromNonVirtual), startCellMap);
        for (Map.Entry<Integer, Map<Integer, Double>> entry : upAndCoreGraphDistMap.entrySet()) {
            ActiveCellDijkstra activeCellDijkstra = new ActiveCellDijkstra(graph, weighting, isochroneNodeStorage, entry.getKey());
            activeCellDijkstra.setIsochroneLimit(isochroneLimit);
            //Add all the start points with their respective already visited weight
            for (int nodeId : entry.getValue().keySet()) {
                activeCellDijkstra.addInitialBordernode(nodeId, entry.getValue().get(nodeId));
            }
            activeCellDijkstra.init();
            activeCellDijkstra.runAlgo();
            activeCellMaps.put(entry.getKey(), activeCellDijkstra.getFromMap());
        }
    }

    @Override
    public boolean finishedActiveCellPhase() {
        return false;
    }

    private void findFullyReachableCells(IntObjectMap<SPTEntry> entryMap) {
        for (IntObjectCursor<SPTEntry> entry : entryMap) {
            int baseNode = entry.key;
            if (!isochroneNodeStorage.getBorderness(baseNode))
                continue;
            SPTEntry sptEntry = entry.value;
            int baseCell = isochroneNodeStorage.getCellId(baseNode);
            int eccentricity = eccentricityStorage.getEccentricity(baseNode);
            if (isWithinLimit(sptEntry, eccentricity)
                    && eccentricityStorage.getFullyReachable(baseNode)) {
                addFullyReachableCell(baseCell);
                addInactiveBorderNode(baseNode);
            } else {
                if (!getFullyReachableCells().contains(baseCell)) {
                    addActiveBorderNode(baseNode);
                }
            }
        }
    }

    /**
     * Consider all active cells that have a percentage of *approximation* of their nodes visited to be fully reachable.
     *
     * @param approximation factor of approximation. 1 means all nodes must be found, 0 means no nodes have to be found.
     */
    public void approximateActiveCells(double approximation) {
        Iterator<Map.Entry<Integer, IntObjectMap<SPTEntry>>> activeCellIterator = getActiveCellMaps().entrySet().iterator();
        while (activeCellIterator.hasNext()) {
            Map.Entry<Integer, IntObjectMap<SPTEntry>> activeCell = activeCellIterator.next();
            if (activeCell.getValue().size() / (double) cellStorage.getNodesOfCell(activeCell.getKey()).size() > approximation) {
                activeCellIterator.remove();
                getFullyReachableCells().add(activeCell.getKey());
            }
        }
    }

    private boolean isWithinLimit(SPTEntry sptEntry, int eccentricity) {
        return sptEntry.getWeightOfVisitedPath() + eccentricity <= isochroneLimit;
    }

    private void addFullyReachableCell(int cellId) {
        fullyReachableCells.add(cellId);
    }

    protected void addActiveBorderNode(int nodeId) {
        activeBorderNodes.add(nodeId);
    }

    protected void addInactiveBorderNode(int nodeId) {
        inactiveBorderNodes.add(nodeId);
    }

    public Set<Integer> getFullyReachableCells() {
        return fullyReachableCells;
    }

    public IntObjectMap<SPTEntry> getStartCellMap() {
        return startCellMap;
    }

    public String getName() {
        return NAME;
    }

    public Map<Integer, IntObjectMap<SPTEntry>> getActiveCellMaps() {
        return activeCellMaps;
    }
}