NetworkSimplifier.java

Go to the documentation of this file.

/* *********************************************************************** *
 * project: org.matsim.*
 * NetworkCleaner.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.network.algorithms;

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.Scenario;
import org.matsim.api.core.v01.network.Link;
import org.matsim.api.core.v01.network.Network;
import org.matsim.api.core.v01.network.Node;
import org.matsim.core.config.ConfigUtils;
import org.matsim.core.network.NetworkUtils;
import org.matsim.core.network.io.MatsimNetworkReader;
import org.matsim.core.network.io.NetworkWriter;
import org.matsim.core.scenario.ScenarioUtils;
import org.matsim.core.utils.collections.Tuple;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import java.util.function.BiConsumer;
import java.util.function.BiPredicate;

public final class NetworkSimplifier {

    private static final Logger log = LogManager.getLogger(NetworkSimplifier.class);
    private boolean mergeLinksWithDifferentAttributes = false;
    private Collection<Integer> nodeTopoToMerge = Arrays.asList( NetworkCalcTopoType.PASS1WAY , NetworkCalcTopoType.PASS2WAY );

    private Set<Id<Node>> nodesNotToMerge = new HashSet<>();

    private final Map<Id<Link>,List<Node>> mergedLinksToIntermediateNodes = new HashMap<>();

    public static final BiPredicate<Link, Link> DEFAULT_IS_MERGEABLE_PREDICATE = (inLink, outLink) -> true;
    public static final BiConsumer<Tuple<Link, Link>, Link> DEFAULT_TRANSFER_ATTRIBUTES_CONSUMER = (inOutLinks,
            newLink) -> {
        // do nothing
    };

    public void run(final Network network){
        run(network, Double.POSITIVE_INFINITY, ThresholdExceeded.EITHER);
    }

    public void run(final Network network, final BiPredicate<Link, Link> isMergeable,
            final BiConsumer<Tuple<Link, Link>, Link> transferAttributes) {
        run(network, Double.POSITIVE_INFINITY, ThresholdExceeded.EITHER, isMergeable, transferAttributes);
    }

    @Deprecated
    public void run(final Network network, double thresholdLength){
        run(network, thresholdLength, ThresholdExceeded.BOTH);
        run(network, thresholdLength, ThresholdExceeded.EITHER);
    }

    public void setNodesNotToMerge(Set<Long> nodeIDs){
        for(Long l : nodeIDs){
            this.nodesNotToMerge.add(Id.createNodeId(l));
        }
    }
    
    private void run(final Network network, double thresholdLength, ThresholdExceeded type) {
        run(network, thresholdLength, type, DEFAULT_IS_MERGEABLE_PREDICATE, DEFAULT_TRANSFER_ATTRIBUTES_CONSUMER);
    }

    private void run(final Network network, double thresholdLength, ThresholdExceeded type,
            final BiPredicate<Link, Link> isMergeable, final BiConsumer<Tuple<Link, Link>, Link> transferAttributes) {

        if(this.nodeTopoToMerge.size() == 0){
            throw new RuntimeException("No types of node specified. Please use setNodesToMerge to specify which nodes should be merged");
        }

        log.info("running " + this.getClass().getName() + " algorithm...");

        NetworkCalcTopoType nodeTopo = new NetworkCalcTopoType();
        nodeTopo.run(network);

        for (Node node : network.getNodes().values()) {
            
            if(this.nodeTopoToMerge.contains(nodeTopo.getTopoType(node)) && (!this.nodesNotToMerge.contains(node.getId())) ){

                List<Link> removedLinks = new ArrayList<>();

                List<Link> iLinks = new ArrayList<>(node.getInLinks().values());
                List<Link> oLinks = new ArrayList<>(node.getOutLinks().values());

                for (Link inLink : iLinks) {
                    for (Link outLink : oLinks) {

                        if(areLinksMergeable(inLink, outLink) && isMergeable.test(inLink, outLink)) {
                            if(this.mergeLinksWithDifferentAttributes){

                                // Only merge if threshold criteria is met.
                                boolean criteria = false;
                                switch (type) {
                                case BOTH:
                                    criteria = bothLinksAreShorterThanThreshold(inLink, outLink, thresholdLength);
                                    break;
                                case EITHER:
                                    criteria = eitherLinkIsShorterThanThreshold(inLink, outLink, thresholdLength);
                                    break;
                                default:
                                    break;
                                }

                                // yyyy The approach here depends on the sequence in which this goes through the nodes:
                                // * in the "EITHER" situation, a long link may gobble up short neighboring links
                                // until it hits another long link doing the same.
                                // * In the "BOTH" situation, something like going through nodes randomly will often merge
                                // the neighboring links, while going through the nodes along some path will mean that it will
                                // gobble up until the threshold is met.
                                // I would strongly advise against setting thresholdLength to anything other than POSITIVE_INFINITY.
                                // kai, feb'18

                                if(criteria){
                                    // Try to merge both links by guessing the resulting links attributes
                                    Link link = network.getFactory().createLink(
                                            Id.create(inLink.getId() + "-" + outLink.getId(), Link.class),
                                            inLink.getFromNode(),
                                            outLink.getToNode());

                                    // length can be summed up
                                    link.setLength(inLink.getLength() + outLink.getLength());

                                    // freespeed depends on total length and time needed for inLink and outLink
                                    link.setFreespeed(
                                            (inLink.getLength() + outLink.getLength()) /
                                            (NetworkUtils.getFreespeedTravelTime(inLink) + NetworkUtils.getFreespeedTravelTime(outLink))
                                            );

                                    // the capacity and the new links end is important, thus it will be set to the minimum
                                    link.setCapacity(Math.min(inLink.getCapacity(), outLink.getCapacity()));

                                    // number of lanes can be derived from the storage capacity of both links
                                    link.setNumberOfLanes((inLink.getLength() * inLink.getNumberOfLanes()
                                            + outLink.getLength() * outLink.getNumberOfLanes())
                                            / (inLink.getLength() + outLink.getLength())
                                            );
                                    if (NetworkUtils.getOrigId(inLink) != null || NetworkUtils.getOrigId(outLink) != null) {
                                        NetworkUtils.setOrigId(link, NetworkUtils.getOrigId(inLink) + "-" + NetworkUtils.getOrigId(outLink));
                                    }
                                    network.addLink(link);
                                    transferAttributes.accept(Tuple.of(inLink, outLink), link);
                                    network.removeLink(inLink.getId());
                                    network.removeLink(outLink.getId());
                                    removedLinks.add(inLink);
                                    removedLinks.add(outLink);
                                    collectMergedLinkNodeInfo(inLink, outLink, link.getId());
                                }
                            } else {

                                // Only merge links with same attributes
                                if(bothLinksHaveSameLinkStats(inLink, outLink)){

                                    // Only merge if threshold criteria is met.
                                    boolean isHavingShortLinks = false;
                                    switch (type) {
                                    case BOTH:
                                        isHavingShortLinks = bothLinksAreShorterThanThreshold(inLink, outLink, thresholdLength);
                                        break;
                                    case EITHER:
                                        isHavingShortLinks = eitherLinkIsShorterThanThreshold(inLink, outLink, thresholdLength);
                                        break;
                                    default:
                                        break;
                                    }

                                    if(isHavingShortLinks){
                                        Link newLink = NetworkUtils.createAndAddLink(network,Id.create(inLink.getId() + "-" + outLink.getId(), Link.class), inLink.getFromNode(), outLink.getToNode(), inLink.getLength() + outLink.getLength(), inLink.getFreespeed(), inLink.getCapacity(), inLink.getNumberOfLanes());
                                        if (NetworkUtils.getOrigId(inLink) != null || NetworkUtils.getOrigId(outLink) != null) {
                                            NetworkUtils.setOrigId(newLink, NetworkUtils.getOrigId(inLink) + "-" + NetworkUtils.getOrigId(outLink));
                                        }

                                        newLink.setAllowedModes(inLink.getAllowedModes());

                                        transferAttributes.accept(Tuple.of(inLink, outLink), newLink);
                                        network.removeLink(inLink.getId());
                                        network.removeLink(outLink.getId());
                                        removedLinks.add(inLink);
                                        removedLinks.add(outLink);
                                        collectMergedLinkNodeInfo(inLink, outLink, newLink.getId());
                                    }
                                }
                            }
                        }
                    }
                }
                for (Link removedLink : removedLinks) {
                    this.mergedLinksToIntermediateNodes.remove(removedLink.getId());
                }
            }
        }

        log.info("  resulting network contains " + network.getNodes().size() + " nodes and " +
                network.getLinks().size() + " links.");
        log.info("done.");

        // writes stats as a side effect
        nodeTopo = new NetworkCalcTopoType();
        nodeTopo.run(network);
    }

    private boolean areLinksMergeable(Link inLink, Link outLink) {
        Set<Node> fromNodes = new HashSet<>();
        List<Node> tmp = this.mergedLinksToIntermediateNodes.get(inLink.getId());
        if (tmp != null) fromNodes.addAll(tmp);
        fromNodes.add(inLink.getFromNode());

        Set<Node> toNodes = new HashSet<>();
        tmp = this.mergedLinksToIntermediateNodes.get(outLink.getId());
        if (tmp != null) toNodes.addAll(tmp);
        toNodes.add(outLink.getToNode());

        // build intersection of from-nodes and to-nodes
        fromNodes.retainAll(toNodes);
        // there should be no intersection in order to merge the links
        return fromNodes.isEmpty();
    }

    private void collectMergedLinkNodeInfo(Link inLink, Link outLink, Id<Link> mergedLinkId) {
        List<Node> nodes = new ArrayList<>();
        List<Node> tmp = this.mergedLinksToIntermediateNodes.get(inLink.getId());
        if (tmp != null) {
            nodes.addAll(tmp);
        }
        tmp = this.mergedLinksToIntermediateNodes.get(outLink.getId());
        if (tmp != null) {
            nodes.addAll(tmp);
        }
        nodes.add(inLink.getToNode());

        this.mergedLinksToIntermediateNodes.put(mergedLinkId, nodes);
    }
    

    public void setNodesToMerge(Set<Integer> nodeTypesToMerge){
        this.nodeTopoToMerge.addAll(nodeTypesToMerge);
    }

    public void setMergeLinkStats(boolean mergeLinksWithDifferentAttributes){
        this.mergeLinksWithDifferentAttributes = mergeLinksWithDifferentAttributes;
    }

    // helper

    private boolean bothLinksAreShorterThanThreshold(Link linkA, Link linkB, double thresholdLength){
        boolean hasTwoShortLinks = false;
        if(linkA.getLength() < thresholdLength && linkB.getLength() < thresholdLength){
            hasTwoShortLinks = true;
        }
        return hasTwoShortLinks;
    }
    
    private boolean eitherLinkIsShorterThanThreshold(Link linkA, Link linkB, double thresholdLength){
        boolean hasShortLink = false;
        if(linkA.getLength() < thresholdLength || linkB.getLength() < thresholdLength){
            hasShortLink = true;
        }
        return hasShortLink;
    }
    
    private boolean bothLinksHaveSameLinkStats(Link linkA, Link linkB){

        boolean bothLinksHaveSameLinkStats = true;

        if(!linkA.getAllowedModes().equals(linkB.getAllowedModes())){ bothLinksHaveSameLinkStats = false; }

        if(linkA.getFreespeed() != linkB.getFreespeed()){ bothLinksHaveSameLinkStats = false; }

        if(linkA.getCapacity() != linkB.getCapacity()){ bothLinksHaveSameLinkStats = false; }

        if(linkA.getNumberOfLanes() != linkB.getNumberOfLanes()){ bothLinksHaveSameLinkStats = false; }

        return bothLinksHaveSameLinkStats;
    }

    public static void main(String[] args) {
        final String inNetworkFile = args[ 0 ];
        final String outNetworkFile = args[ 1 ];

        Set<Integer> nodeTypesToMerge = new TreeSet<>();
        nodeTypesToMerge.add(4);
        nodeTypesToMerge.add(5);

        Scenario scenario = ScenarioUtils.createScenario(ConfigUtils.createConfig());
        final Network network = scenario.getNetwork();
        new MatsimNetworkReader(scenario.getNetwork()).readFile( inNetworkFile );

        NetworkSimplifier nsimply = new NetworkSimplifier();
        nsimply.setNodesToMerge(nodeTypesToMerge);
//      nsimply.setMergeLinkStats(true);
        nsimply.run(network, Double.NEGATIVE_INFINITY);

        new NetworkWriter(network).write( outNetworkFile );

    }
    
    private enum ThresholdExceeded {
        EITHER, BOTH
    }
}