MultimodalNetworkCleaner.java

Go to the documentation of this file.

/* *********************************************************************** *
 * project: org.matsim.*
 *                                                                         *
 * *********************************************************************** *
 *                                                                         *
 * copyright       : (C) 2010 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.network.algorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

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 final class MultimodalNetworkCleaner {

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

    private final Network network;
    
    private final Set<Id<Link>> removedLinks = new HashSet<>();
    private final Set<Id<Link>> modifiedLinks = new HashSet<>();

    public MultimodalNetworkCleaner(final Network network) {
        this.network = network;
    }

    public void removeNodesWithoutLinks() {
        List<Node> toBeRemoved = new ArrayList<>();
        for (Node node : this.network.getNodes().values()) {
            if ((node.getInLinks().size() == 0) && (node.getOutLinks().size() == 0)) {
                toBeRemoved.add(node);
            }
        }
        for (Node node : toBeRemoved) {
            this.network.removeNode(node.getId());
        }
    }

    public void run(final Set<String> modes) {
        run(modes, new HashSet<String>());
    }

    public void run(final Set<String> cleaningModes, final Set<String> connectivityModes) {
        final Set<String> combinedModes = new HashSet<>(cleaningModes);
        combinedModes.addAll(connectivityModes);
        final Map<Id<Link>, Link> visitedLinks = new TreeMap<>();
        Map<Id<Link>, Link> biggestCluster = new TreeMap<>();

        log.info("running " + this.getClass().getName() + " algorithm for modes " + Arrays.toString(cleaningModes.toArray())
                + " with connectivity modes " + Arrays.toString(connectivityModes.toArray()) + "...");

        // search the biggest cluster of nodes in the network
        log.info("  checking " + this.network.getNodes().size() + " nodes and " +
                this.network.getLinks().size() + " links for dead-ends...");
        boolean stillSearching = true;
        Iterator<? extends Link> iter = this.network.getLinks().values().iterator();
        while (iter.hasNext() && stillSearching) {
            Link startLink = iter.next();
            if ((!visitedLinks.containsKey(startLink.getId())) && (intersectingSets(combinedModes, startLink.getAllowedModes()))) {
                Map<Id<Link>, Link> cluster = this.findCluster(startLink, combinedModes);
                visitedLinks.putAll(cluster);
                if (cluster.size() > biggestCluster.size()) {
                    biggestCluster = cluster;
                    if (biggestCluster.size() >= (this.network.getLinks().size() - visitedLinks.size())) {
                        // stop searching here, because we cannot find a bigger cluster in the lasting nodes
                        stillSearching = false;
                    }
                }
            }
        }
        log.info("    The biggest cluster consists of " + biggestCluster.size() + " links.");
        log.info("  done.");

        /* Remove the modes from all links not being part of the cluster. If a link has no allowed mode
         * anymore after this, remove the link from the network.
         */
        List<Link> allLinks = new ArrayList<>(this.network.getLinks().values());
        for (Link link : allLinks) {
            if (!biggestCluster.containsKey(link.getId())) {
                Set<String> reducedModes = new HashSet<>(link.getAllowedModes());
                reducedModes.removeAll(cleaningModes);
                link.setAllowedModes(reducedModes);
                if (reducedModes.isEmpty()) {
                    this.network.removeLink(link.getId());
                    if ((link.getFromNode().getInLinks().size() + link.getFromNode().getOutLinks().size()) == 0) {
                        this.network.removeNode(link.getFromNode().getId());
                    }
                    if ((link.getToNode().getInLinks().size() + link.getToNode().getOutLinks().size()) == 0) {
                        this.network.removeNode(link.getToNode().getId());
                    }
                    this.removedLinks.add(link.getId());
                }
                if(!removedLinks.contains(link.getId())) modifiedLinks.add(link.getId());
            }
        }
        log.info("  resulting network contains " + this.network.getNodes().size() + " nodes and " +
                this.network.getLinks().size() + " links.");
        log.info("done.");
    }

    private Map<Id<Link>, Link> findCluster(final Link startLink, final Set<String> modes) {

        final Map<Id<Link>, DoubleFlagRole> linkRoles = new HashMap<>(this.network.getLinks().size());

        ArrayList<Node> pendingForward = new ArrayList<>();
        ArrayList<Node> pendingBackward = new ArrayList<>();

        TreeMap<Id<Link>, Link> clusterLinks = new TreeMap<>();

        pendingForward.add(startLink.getToNode());
        pendingBackward.add(startLink.getFromNode());

        // step through the network in forward mode
        while (pendingForward.size() > 0) {
            int idx = pendingForward.size() - 1;
            Node currNode = pendingForward.remove(idx); // get the last element to prevent object shifting in the array
            for (Link link : currNode.getOutLinks().values()) {
                if (intersectingSets(modes, link.getAllowedModes())) {
                    DoubleFlagRole r = getDoubleFlag(link, linkRoles);
                    if (!r.forwardFlag) {
                        r.forwardFlag = true;
                        pendingForward.add(link.getToNode());
                    }
                }
            }
        }

        // now step through the network in backward mode
        while (pendingBackward.size() > 0) {
            int idx = pendingBackward.size()-1;
            Node currNode = pendingBackward.remove(idx); // get the last element to prevent object shifting in the array
            for (Link link : currNode.getInLinks().values()) {
                if (intersectingSets(modes, link.getAllowedModes())) {
                    DoubleFlagRole r = getDoubleFlag(link, linkRoles);
                    if (!r.backwardFlag) {
                        r.backwardFlag = true;
                        pendingBackward.add(link.getFromNode());
                        if (r.forwardFlag) {
                            // the node can be reached forward and backward, add it to the cluster
                            clusterLinks.put(link.getId(), link);
                        }
                    }
                }
            }
        }

        return clusterLinks;
    }

    public final Set<Id<Link>> getRemovedLinkIds() {
        return removedLinks;
    }

    public final Set<Id<Link>> getModifiedLinkIds() {
        return modifiedLinks;
    }

    private <T> boolean intersectingSets(final Set<T> setA, final Set<T> setB) {
        for (T t : setA) {
            if (setB.contains(t)) {
                return true;
            }
        }
        return false;
    }

    private static DoubleFlagRole getDoubleFlag(final Link l, final Map<Id<Link>, DoubleFlagRole> linkRoles) {
        DoubleFlagRole r = linkRoles.get(l.getId());
        if (null == r) {
            r = new DoubleFlagRole();
            linkRoles.put(l.getId(), r);
        }
        return r;
    }

    static class DoubleFlagRole {
        boolean forwardFlag = false;
        boolean backwardFlag = false;
    }

}