PreProcessDijkstra.java

Go to the documentation of this file.

/* *********************************************************************** *
 * project: org.matsim.*
 * PreProcessDijkstra.java
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 * copyright       : (C) 2007 by the members listed in the COPYING,        *
 *                   LICENSE and WARRANTY file.                            *
 * email           : info at matsim dot org                                *
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *   See also COPYING, LICENSE and WARRANTY file                           *
 *                                                                         *
 * *********************************************************************** */

package org.matsim.core.router.util;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
import java.util.concurrent.ConcurrentHashMap;

import org.apache.logging.log4j.LogManager;
import org.apache.logging.log4j.Logger;
import org.matsim.api.core.v01.Id;
import org.matsim.api.core.v01.network.Link;
import org.matsim.api.core.v01.network.Network;
import org.matsim.api.core.v01.network.Node;

public class PreProcessDijkstra {

    private static final Logger log = LogManager.getLogger(PreProcessDijkstra.class);

    private boolean containsData = false;

    protected Map<Node, DeadEndData> nodeData = null;

    public void run(final Network network) {
        markDeadEnds(network);
        this.containsData = true;
    }

    private void markDeadEnds(final Network network) {
        long now = System.currentTimeMillis();

        /*
         * We use a concurrentHashMap because if FastRouters are used for the re-routing,
         * their parallel initialization in multiple threads may result in concurrent
         * calls to getNodeData(...).
         */
        this.nodeData = new ConcurrentHashMap<Node, DeadEndData>(network.getNodes().size());

        DeadEndData deadEndData;
        for (Node node : network.getNodes().values()) {
            deadEndData = getNodeData(node);

            Map<Id<Node>, Node> incidentNodes = getIncidentNodes(node);
            if (incidentNodes.size() == 1) {
                ArrayList<Node> deadEndNodes = new ArrayList<Node>();

                while (deadEndData.getInDeadEndCount() == incidentNodes.size() - 1) {

                    deadEndNodes.add(node);
                    deadEndNodes.addAll(deadEndData.getDeadEndNodes());
                    deadEndData.getDeadEndNodes().clear();

                    // Just set a dummy DeadEndEntryNode, such that is
                    // isn't null. We use this as a flag to determine
                    // whether we already processed this node.
                    deadEndData.setDeadEndEntryNode(node);

                    Iterator<? extends Node> it = incidentNodes.values().iterator();
                    while (deadEndData.getDeadEndEntryNode() != null && it.hasNext()) {
                        node = it.next();
                        deadEndData = getNodeData(node);
                    }
                    if (deadEndData.getDeadEndEntryNode() == null) {
                        deadEndData.incrementInDeadEndCount();
                        incidentNodes = getIncidentNodes(node);
                    } else {
                        log.error("All " + incidentNodes.size() + " incident nodes of node " + node.getId() + " are dead ends!");
                        return;
                    }
                }
                deadEndData.getDeadEndNodes().addAll(deadEndNodes);
            }
        }

        // Now set the proper deadEndEntryNode for each node
        int deadEndNodeCount = 0;
        for (Node node : network.getNodes().values()) {
            deadEndData = getNodeData(node);
            for (Node n : deadEndData.getDeadEndNodes()) {
                DeadEndData r = getNodeData(n);
                r.setDeadEndEntryNode(node);
                deadEndNodeCount++;
            }
            deadEndData.getDeadEndNodes().clear();
        }
        log.info("nodes in dead ends: " + deadEndNodeCount
                + " (total nodes: " + network.getNodes().size() + "). Done in "
                + (System.currentTimeMillis() - now) + " ms");
    }

    private static Map<Id<Node>, Node> getIncidentNodes(Node node) {
        Map<Id<Node>, Node> nodes = new TreeMap<>();
        for (Link link : node.getInLinks().values()) {
            nodes.put(link.getFromNode().getId(), link.getFromNode());
        }
        for (Link link : node.getOutLinks().values()) {
            nodes.put(link.getToNode().getId(), link.getToNode());
        }
        return nodes;
    }

    public DeadEndData getNodeData(final Node n) {
        DeadEndData r = this.nodeData.get(n);
        if (null == r) {
            r = new DeadEndData();
            this.nodeData.put(n, r);
        }
        return r;
    }

    public static class DeadEndData {
        private Node deadEndEntryNode = null;

        private int inDeadEndCount = 0;

        private ArrayList<Node> deadEndNodes = new ArrayList<Node>(2);

        ArrayList<Node> getDeadEndNodes() {
            return this.deadEndNodes;
        }

        /*package*/ int getInDeadEndCount() {
            return this.inDeadEndCount;
        }

        /*package*/ void incrementInDeadEndCount() {
            this.inDeadEndCount++;
        }


        public Node getDeadEndEntryNode() {
            return this.deadEndEntryNode;
        }

        /*package*/ void setDeadEndEntryNode(final Node node) {
            this.deadEndEntryNode = node;
        }
    }

    public boolean containsData() {
        return this.containsData;
    }
}