Changeset 19062 in josm


Ignore:
Timestamp:
2024-04-27T08:58:28+02:00 (13 days ago)
Author:
GerdP
Message:

fix #21881: Add a check for loops in directional waterways
Patch by gaben, slightly modified

  • implements Tarjan algorithm to find strongly connected components
  • new preference validator.CycleDetector.directionalWaterways contains the list of waterway values which should be checked
Location:
trunk
Files:
8 added
4 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java

    r17515 r19062  
    2222
    2323import org.openstreetmap.josm.tools.Pair;
     24import org.openstreetmap.josm.tools.Utils;
    2425
    2526/**
    26  * A directed or undirected graph of nodes.
     27 * A directed or undirected graph of nodes. Nodes are connected via edges represented by NodePair instances.
     28 *
    2729 * @since 12463 (extracted from CombineWayAction)
    2830 */
    … …  
    3335     * @param way way
    3436     * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.
    35      *                 if {@code false} each pair of nodes will occur twice (the pair and its inversed copy)
     37     *                 if {@code false} each pair of nodes will occur twice (the pair and its inverse copy)
    3638     * @return a list of pair of nodes from the given way
    3739     */
    3840    public static List<NodePair> buildNodePairs(Way way, boolean directed) {
    3941        List<NodePair> pairs = new ArrayList<>();
    40         for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
     42        for (Pair<Node, Node> pair : way.getNodePairs(false)) {
    4143            pairs.add(new NodePair(pair));
    4244            if (!directed) {
    … …  
    5052     * Builds a list of pair of nodes from the given ways.
    5153     * @param ways ways
    52      * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.
    53      *                 if {@code false} each pair of nodes will occur twice (the pair and its inversed copy)
     54     * @param directed if {@code true} each pair of nodes will occur once, in the way nodes order.<br>
     55     *                 if {@code false} each pair of nodes will occur twice (the pair and its inverse copy)
    5456     * @return a list of pair of nodes from the given ways
    5557     */
    5658    public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
    5759        List<NodePair> pairs = new ArrayList<>();
    58         for (Way w: ways) {
     60        for (Way w : ways) {
    5961            pairs.addAll(buildNodePairs(w, directed));
    6062        }
    … …  
    6365
    6466    /**
    65      * Builds a new list of pair nodes without the duplicated pairs (including inversed copies).
     67     * Builds a new list of pair nodes without the duplicated pairs (including inverse copies).
    6668     * @param pairs existing list of pairs
    6769     * @return a new list of pair nodes without the duplicated pairs
    … …  
    6971    public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
    7072        List<NodePair> cleaned = new ArrayList<>();
    71         for (NodePair p: pairs) {
     73        for (NodePair p : pairs) {
    7274            if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
    7375                cleaned.add(p);
    … …  
    7779    }
    7880
     81    /**
     82     * Create a directed graph from the given node pairs.
     83     * @param pairs Node pairs to build the graph from
     84     * @return node graph structure
     85     */
    7986    public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
    8087        NodeGraph graph = new NodeGraph();
    81         for (NodePair pair: pairs) {
     88        for (NodePair pair : pairs) {
    8289            graph.add(pair);
    8390        }
    … …  
    8592    }
    8693
     94    /**
     95     * Create a directed graph from the given ways.
     96     * @param ways ways to build the graph from
     97     * @return node graph structure
     98     */
    8799    public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
    88100        NodeGraph graph = new NodeGraph();
    89         for (Way w: ways) {
    90             graph.add(buildNodePairs(w, true /* directed */));
     101        for (Way w : ways) {
     102            graph.add(buildNodePairs(w, true));
    91103        }
    92104        return graph;
    … …  
    100112    public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
    101113        NodeGraph graph = new NodeGraph();
    102         for (NodePair pair: pairs) {
     114        for (NodePair pair : pairs) {
    103115            graph.add(pair);
    104116            graph.add(pair.swap());
    … …  
    109121    /**
    110122     * Create an undirected graph from the given ways, but prevent reversing of all
    111      * non-new ways by fix one direction.
     123     * non-new ways by fixing one direction.
    112124     * @param ways Ways to build the graph from
    113125     * @return node graph structure
    … …  
    116128    public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
    117129        NodeGraph graph = new NodeGraph();
    118         for (Way w: ways) {
    119             graph.add(buildNodePairs(w, false /* undirected */));
     130        for (Way w : ways) {
     131            graph.add(buildNodePairs(w, false));
    120132        }
    121133        return graph;
    122134    }
    123135
     136    /**
     137     * Create a nearly undirected graph from the given ways, but prevent reversing of all
     138     * non-new ways by fixing one direction.
     139     * The first new way gives the direction of the graph.
     140     * @param ways Ways to build the graph from
     141     * @return node graph structure
     142     */
    124143    public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
    125144        boolean dir = true;
    126145        NodeGraph graph = new NodeGraph();
    127         for (Way w: ways) {
     146        for (Way w : ways) {
    128147            if (!w.isNew()) {
    129148                /* let the first non-new way give the direction (see #5880) */
    … …  
    131150                dir = false;
    132151            } else {
    133                 graph.add(buildNodePairs(w, false /* undirected */));
     152                graph.add(buildNodePairs(w, false));
    134153            }
    135154        }
    … …  
    138157
    139158    private final Set<NodePair> edges;
    140     private int numUndirectedEges;
    141     /** counts the number of edges that were added */
     159    private int numUndirectedEdges;
     160    /** The number of edges that were added. */
    142161    private int addedEdges;
    143162    private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
    144163    private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
    145164
     165    /**
     166     * Constructs a lookup table from the existing edges in the graph to enable efficient querying.
     167     * This method creates a map where each node is associated with a list of nodes that are directly connected to it.
     168     *
     169     * @return A map representing the graph structure, where nodes are keys, and values are their direct successors.
     170     * @since xxx
     171     */
     172    public Map<Node, List<Node>> createMap() {
     173        final Map<Node, List<Node>> result = new HashMap<>(Utils.hashMapInitialCapacity(edges.size()));
     174
     175        for (NodePair edge : edges) {
     176            result.computeIfAbsent(edge.getA(), k -> new ArrayList<>()).add(edge.getB());
     177        }
     178
     179        return result;
     180    }
     181
     182    /**
     183     * See {@link #prepare()}
     184     */
    146185    protected void rememberSuccessor(NodePair pair) {
    147186        List<NodePair> l = successors.computeIfAbsent(pair.getA(), k -> new ArrayList<>());
    … …  
    151190    }
    152191
     192    /**
     193     * See {@link #prepare()}
     194     */
    153195    protected void rememberPredecessors(NodePair pair) {
    154196        List<NodePair> l = predecessors.computeIfAbsent(pair.getB(), k -> new ArrayList<>());
    … …  
    158200    }
    159201
     202    /**
     203     * Replies true if {@code n} is a terminal node of the graph. Internal variables should be initialized first.
     204     * @param n Node to check
     205     * @return {@code true} if it is a terminal node
     206     * @see #prepare()
     207     */
    160208    protected boolean isTerminalNode(Node n) {
    161209        if (successors.get(n) == null) return false;
    … …  
    175223        predecessors.clear();
    176224
    177         for (NodePair pair: edges) {
     225        for (NodePair pair : edges) {
    178226            if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
    179227                undirectedEdges.add(pair);
    … …  
    182230            rememberPredecessors(pair);
    183231        }
    184         numUndirectedEges = undirectedEdges.size();
     232        numUndirectedEdges = undirectedEdges.size();
    185233    }
    186234
    … …  
    203251    /**
    204252     * Add a list of node pairs.
    205      * @param pairs list of node pairs
    206      */
    207     public void add(Collection<NodePair> pairs) {
    208         for (NodePair pair: pairs) {
     253     * @param pairs collection of node pairs
     254     */
     255    public void add(Iterable<NodePair> pairs) {
     256        for (NodePair pair : pairs) {
    209257            add(pair);
    210258        }
    211259    }
    212260
     261    /**
     262     * Return the edges containing the node pairs of the graph.
     263     * @return the edges containing the node pairs of the graph
     264     */
     265    public Collection<NodePair> getEdges() {
     266        return Collections.unmodifiableSet(edges);
     267    }
     268
     269    /**
     270     * Return the terminal nodes of the graph.
     271     * @return the terminal nodes of the graph
     272     */
    213273    protected Set<Node> getTerminalNodes() {
    214274        return getNodes().stream().filter(this::isTerminalNode).collect(Collectors.toCollection(LinkedHashSet::new));
    … …  
    230290    }
    231291
    232     protected Set<Node> getNodes() {
     292    /**
     293     * Return the graph's nodes.
     294     * @return the graph's nodes
     295     */
     296    public Collection<Node> getNodes() {
    233297        Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
    234         for (NodePair pair: edges) {
     298        for (NodePair pair : edges) {
    235299            nodes.add(pair.getA());
    236300            nodes.add(pair.getB());
    … …  
    240304
    241305    protected boolean isSpanningWay(Collection<NodePair> way) {
    242         return numUndirectedEges == way.size();
     306        return numUndirectedEdges == way.size();
    243307    }
    244308
    … …  
    249313
    250314    /**
    251      * Tries to find a spanning path starting from node <code>startNode</code>.
    252      *
     315     * Tries to find a spanning path starting from node {@code startNode}.
     316     * <p>
    253317     * Traverses the path in depth-first order.
    254318     *
    … …  
    260324            Deque<NodePair> path = new ArrayDeque<>();
    261325            Set<NodePair> dupCheck = new HashSet<>();
    262             Deque<NodePair> nextPairs = new ArrayDeque<>();
    263             nextPairs.addAll(getOutboundPairs(startNode));
     326            Deque<NodePair> nextPairs = new ArrayDeque<>(getOutboundPairs(startNode));
    264327            while (!nextPairs.isEmpty()) {
    265328                NodePair cur = nextPairs.removeLast();
    … …  
    281344    /**
    282345     * Tries to find a path through the graph which visits each edge (i.e.
    283      * the segment of a way) exactly once.
    284      * <p><b>Note that duplicated edges are removed first!</b>
     346     * the segment of a way) exactly once.<p>
     347     * <b>Note that duplicated edges are removed first!</b>
    285348     *
    286      * @return the path; null, if no path was found
     349     * @return the path; {@code null}, if no path was found
    287350     */
    288351    public List<Node> buildSpanningPath() {
    289352        prepare();
    290         if (numUndirectedEges > 0 && isConnected()) {
    291             // try to find a path from each "terminal node", i.e. from a
    292             // node which is connected by exactly one undirected edges (or
    293             // two directed edges in opposite direction) to the graph. A
     353        if (numUndirectedEdges > 0 && isConnected()) {
     354            // Try to find a path from each "terminal node", i.e. from a
     355            // node which is connected by exactly one undirected edge (or
     356            // two directed edges in the opposite direction) to the graph. A
    294357            // graph built up from way segments is likely to include such
    295358            // nodes, unless the edges build one or more closed rings.
    … …  
    325388    /**
    326389     * Find out if the graph is connected.
    327      * @return true if it is connected.
     390     * @return {@code true} if it is connected
    328391     */
    329392    private boolean isConnected() {
    330         Set<Node> nodes = getNodes();
     393        Collection<Node> nodes = getNodes();
    331394        if (nodes.isEmpty())
    332395            return false;
    … …  
    351414    /**
    352415     * Sort the nodes by number of appearances in the edges.
    353      * @return set of nodes which can be start nodes in a spanning way.
     416     * @return set of nodes which can be start nodes in a spanning way
    354417     */
    355418    private Set<Node> getMostFrequentVisitedNodesFirst() {
    356419        if (edges.isEmpty())
    357420            return Collections.emptySet();
    358         // count appearance of nodes in edges
     421        // count the appearance of nodes in edges
    359422        Map<Node, Integer> counters = new HashMap<>();
    360423        for (NodePair pair : edges) {

  • trunk/src/org/openstreetmap/josm/data/osm/WaySegment.java

    r17897 r19062  
    33
    44/**
    5  * A segment consisting of 2 consecutive nodes out of a way.
     5 * A segment consisting of two consecutive nodes out of a way.
    66 */
    77public final class WaySegment extends IWaySegment<Node, Way> {
    … …  
    3737            endIndex--;
    3838        }
    39         throw new IllegalArgumentException("Node pair is not part of way!");
     39        throw new IllegalArgumentException("The node pair is not consecutive part of the way!");
    4040    }
    4141

  • trunk/src/org/openstreetmap/josm/data/validation/OsmValidator.java

    r18649 r19062  
    4545import org.openstreetmap.josm.data.validation.tests.ConnectivityRelations;
    4646import org.openstreetmap.josm.data.validation.tests.CrossingWays;
     47import org.openstreetmap.josm.data.validation.tests.CycleDetector;
    4748import org.openstreetmap.josm.data.validation.tests.DirectionNodes;
    4849import org.openstreetmap.josm.data.validation.tests.DuplicateNode;
    … …  
    155156        SharpAngles.class, // 3800 .. 3899
    156157        ConnectivityRelations.class, // 3900 .. 3999
    157         DirectionNodes.class, // 4000-4099
     158        DirectionNodes.class, // 4000 .. 4099
    158159        RightAngleBuildingTest.class, // 4100 .. 4199
     160        CycleDetector.class, // 4200 .. 4299
    159161    };
    160162

  • trunk/src/org/openstreetmap/josm/gui/history/HistoryLoadTask.java

    r16211 r19062  
    1010import java.util.ArrayList;
    1111import java.util.Collection;
     12import java.util.Iterator;
    1213import java.util.LinkedHashSet;
    1314import java.util.List;
    … …  
    1617
    1718import org.openstreetmap.josm.data.osm.Changeset;
     19import org.openstreetmap.josm.data.osm.ChangesetCache;
    1820import org.openstreetmap.josm.data.osm.OsmPrimitive;
    1921import org.openstreetmap.josm.data.osm.PrimitiveId;
    … …  
    230232            OsmServerChangesetReader changesetReader = new OsmServerChangesetReader();
    231233            List<Long> changesetIds = new ArrayList<>(ds.getChangesetIds());
     234            Iterator<Long> iter = changesetIds.iterator();
     235            while (iter.hasNext()) {
     236                long id = iter.next();
     237                Changeset cs = ChangesetCache.getInstance().get((int) id);
     238                if (cs != null && !cs.isOpen()) {
     239                    ds.putChangeset(cs);
     240                    iter.remove();
     241                }
     242            }
    232243
    233244            // query changesets 100 by 100 (OSM API limit)
    234245            int n = ChangesetQuery.MAX_CHANGESETS_NUMBER;
    235246            for (int i = 0; i < changesetIds.size(); i += n) {
     247                List<Changeset> downloadedCS = new ArrayList<>(changesetIds.size());
    236248                for (Changeset c : changesetReader.queryChangesets(
    237249                        new ChangesetQuery().forChangesetIds(changesetIds.subList(i, Math.min(i + n, changesetIds.size()))),
    238250                        progressMonitor.createSubTaskMonitor(1, false))) {
    239251                    ds.putChangeset(c);
     252                    downloadedCS.add(c);
    240253                }
     254                ChangesetCache.getInstance().update(downloadedCS);
    241255            }
    242256        }
Note: See TracChangeset for help on using the changeset viewer.