Changeset 12463 in josm


Ignore:
Timestamp:
2017-07-10T02:01:00+02:00 (7 years ago)
Author:
Don-vip
Message:

extract NodeGraph and NodePair from CombineWayAction to data.osm package

Location:
trunk
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java

    r12356 r12463  
    1111import java.util.Collection;
    1212import java.util.Collections;
    13 import java.util.LinkedHashMap;
    1413import java.util.LinkedHashSet;
    1514import java.util.LinkedList;
    1615import java.util.List;
    17 import java.util.Map;
    18 import java.util.Objects;
    19 import java.util.Optional;
    20 import java.util.Set;
    21 import java.util.Stack;
    2216import java.util.stream.Collectors;
    2317
    … …  
    3226import org.openstreetmap.josm.data.osm.DataSet;
    3327import org.openstreetmap.josm.data.osm.Node;
     28import org.openstreetmap.josm.data.osm.NodeGraph;
    3429import org.openstreetmap.josm.data.osm.OsmPrimitive;
    3530import org.openstreetmap.josm.data.osm.TagCollection;
    … …  
    256251        setEnabled(numWays >= 2);
    257252    }
    258 
    259     /**
    260      * A pair of nodes.
    261      */
    262     public static class NodePair {
    263         private final Node a;
    264         private final Node b;
    265 
    266         /**
    267          * Constructs a new {@code NodePair}.
    268          * @param a The first node
    269          * @param b The second node
    270          */
    271         public NodePair(Node a, Node b) {
    272             this.a = a;
    273             this.b = b;
    274         }
    275 
    276         /**
    277          * Constructs a new {@code NodePair}.
    278          * @param pair An existing {@code Pair} of nodes
    279          */
    280         public NodePair(Pair<Node, Node> pair) {
    281             this(pair.a, pair.b);
    282         }
    283 
    284         /**
    285          * Replies the first node.
    286          * @return The first node
    287          */
    288         public Node getA() {
    289             return a;
    290         }
    291 
    292         /**
    293          * Replies the second node
    294          * @return The second node
    295          */
    296         public Node getB() {
    297             return b;
    298         }
    299 
    300         public boolean isSuccessorOf(NodePair other) {
    301             return other.getB() == a;
    302         }
    303 
    304         public boolean isPredecessorOf(NodePair other) {
    305             return b == other.getA();
    306         }
    307 
    308         public NodePair swap() {
    309             return new NodePair(b, a);
    310         }
    311 
    312         @Override
    313         public String toString() {
    314             return new StringBuilder()
    315             .append('[')
    316             .append(a.getId())
    317             .append(',')
    318             .append(b.getId())
    319             .append(']')
    320             .toString();
    321         }
    322 
    323         /**
    324          * Determines if this pair contains the given node.
    325          * @param n The node to look for
    326          * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
    327          */
    328         public boolean contains(Node n) {
    329             return a == n || b == n;
    330         }
    331 
    332         @Override
    333         public int hashCode() {
    334             return Objects.hash(a, b);
    335         }
    336 
    337         @Override
    338         public boolean equals(Object obj) {
    339             if (this == obj) return true;
    340             if (obj == null || getClass() != obj.getClass()) return false;
    341             NodePair nodePair = (NodePair) obj;
    342             return Objects.equals(a, nodePair.a) &&
    343                    Objects.equals(b, nodePair.b);
    344         }
    345     }
    346 
    347     public static class NodeGraph {
    348         public static List<NodePair> buildNodePairs(Way way, boolean directed) {
    349             List<NodePair> pairs = new ArrayList<>();
    350             for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
    351                 pairs.add(new NodePair(pair));
    352                 if (!directed) {
    353                     pairs.add(new NodePair(pair).swap());
    354                 }
    355             }
    356             return pairs;
    357         }
    358 
    359         public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
    360             List<NodePair> pairs = new ArrayList<>();
    361             for (Way w: ways) {
    362                 pairs.addAll(buildNodePairs(w, directed));
    363             }
    364             return pairs;
    365         }
    366 
    367         public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
    368             List<NodePair> cleaned = new ArrayList<>();
    369             for (NodePair p: pairs) {
    370                 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
    371                     cleaned.add(p);
    372                 }
    373             }
    374             return cleaned;
    375         }
    376 
    377         public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
    378             NodeGraph graph = new NodeGraph();
    379             for (NodePair pair: pairs) {
    380                 graph.add(pair);
    381             }
    382             return graph;
    383         }
    384 
    385         public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
    386             NodeGraph graph = new NodeGraph();
    387             for (Way w: ways) {
    388                 graph.add(buildNodePairs(w, true /* directed */));
    389             }
    390             return graph;
    391         }
    392 
    393         /**
    394          * Create an undirected graph from the given node pairs.
    395          * @param pairs Node pairs to build the graph from
    396          * @return node graph structure
    397          */
    398         public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
    399             NodeGraph graph = new NodeGraph();
    400             for (NodePair pair: pairs) {
    401                 graph.add(pair);
    402                 graph.add(pair.swap());
    403             }
    404             return graph;
    405         }
    406 
    407         /**
    408          * Create an undirected graph from the given ways, but prevent reversing of all
    409          * non-new ways by fix one direction.
    410          * @param ways Ways to build the graph from
    411          * @return node graph structure
    412          * @since 8181
    413          */
    414         public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
    415             NodeGraph graph = new NodeGraph();
    416             for (Way w: ways) {
    417                 graph.add(buildNodePairs(w, false /* undirected */));
    418             }
    419             return graph;
    420         }
    421 
    422         public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
    423             boolean dir = true;
    424             NodeGraph graph = new NodeGraph();
    425             for (Way w: ways) {
    426                 if (!w.isNew()) {
    427                     /* let the first non-new way give the direction (see #5880) */
    428                     graph.add(buildNodePairs(w, dir));
    429                     dir = false;
    430                 } else {
    431                     graph.add(buildNodePairs(w, false /* undirected */));
    432                 }
    433             }
    434             return graph;
    435         }
    436 
    437         private final Set<NodePair> edges;
    438         private int numUndirectedEges;
    439         private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
    440         private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
    441 
    442         protected void rememberSuccessor(NodePair pair) {
    443             if (successors.containsKey(pair.getA())) {
    444                 if (!successors.get(pair.getA()).contains(pair)) {
    445                     successors.get(pair.getA()).add(pair);
    446                 }
    447             } else {
    448                 List<NodePair> l = new ArrayList<>();
    449                 l.add(pair);
    450                 successors.put(pair.getA(), l);
    451             }
    452         }
    453 
    454         protected void rememberPredecessors(NodePair pair) {
    455             if (predecessors.containsKey(pair.getB())) {
    456                 if (!predecessors.get(pair.getB()).contains(pair)) {
    457                     predecessors.get(pair.getB()).add(pair);
    458                 }
    459             } else {
    460                 List<NodePair> l = new ArrayList<>();
    461                 l.add(pair);
    462                 predecessors.put(pair.getB(), l);
    463             }
    464         }
    465 
    466         protected boolean isTerminalNode(Node n) {
    467             if (successors.get(n) == null) return false;
    468             if (successors.get(n).size() != 1) return false;
    469             if (predecessors.get(n) == null) return true;
    470             if (predecessors.get(n).size() == 1) {
    471                 NodePair p1 = successors.get(n).get(0);
    472                 NodePair p2 = predecessors.get(n).get(0);
    473                 return p1.equals(p2.swap());
    474             }
    475             return false;
    476         }
    477 
    478         protected void prepare() {
    479             Set<NodePair> undirectedEdges = new LinkedHashSet<>();
    480             successors.clear();
    481             predecessors.clear();
    482 
    483             for (NodePair pair: edges) {
    484                 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
    485                     undirectedEdges.add(pair);
    486                 }
    487                 rememberSuccessor(pair);
    488                 rememberPredecessors(pair);
    489             }
    490             numUndirectedEges = undirectedEdges.size();
    491         }
    492 
    493         /**
    494          * Constructs a new {@code NodeGraph}.
    495          */
    496         public NodeGraph() {
    497             edges = new LinkedHashSet<>();
    498         }
    499 
    500         public void add(NodePair pair) {
    501             if (!edges.contains(pair)) {
    502                 edges.add(pair);
    503             }
    504         }
    505 
    506         public void add(List<NodePair> pairs) {
    507             for (NodePair pair: pairs) {
    508                 add(pair);
    509             }
    510         }
    511 
    512         protected Set<Node> getTerminalNodes() {
    513             Set<Node> ret = new LinkedHashSet<>();
    514             for (Node n: getNodes()) {
    515                 if (isTerminalNode(n)) {
    516                     ret.add(n);
    517                 }
    518             }
    519             return ret;
    520         }
    521 
    522         protected List<NodePair> getOutboundPairs(NodePair pair) {
    523             return getOutboundPairs(pair.getB());
    524         }
    525 
    526         protected List<NodePair> getOutboundPairs(Node node) {
    527             return Optional.ofNullable(successors.get(node)).orElseGet(Collections::emptyList);
    528         }
    529 
    530         protected Set<Node> getNodes() {
    531             Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
    532             for (NodePair pair: edges) {
    533                 nodes.add(pair.getA());
    534                 nodes.add(pair.getB());
    535             }
    536             return nodes;
    537         }
    538 
    539         protected boolean isSpanningWay(Stack<NodePair> way) {
    540             return numUndirectedEges == way.size();
    541         }
    542 
    543         protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
    544             List<Node> ret = new LinkedList<>();
    545             for (NodePair pair: path) {
    546                 ret.add(pair.getA());
    547             }
    548             ret.add(path.peek().getB());
    549             return ret;
    550         }
    551 
    552         /**
    553          * Tries to find a spanning path starting from node <code>startNode</code>.
    554          *
    555          * Traverses the path in depth-first order.
    556          *
    557          * @param startNode the start node
    558          * @return the spanning path; null, if no path is found
    559          */
    560         protected List<Node> buildSpanningPath(Node startNode) {
    561             if (startNode == null)
    562                 return null;
    563             Stack<NodePair> path = new Stack<>();
    564             Stack<NodePair> nextPairs = new Stack<>();
    565             nextPairs.addAll(getOutboundPairs(startNode));
    566             while (!nextPairs.isEmpty()) {
    567                 NodePair cur = nextPairs.pop();
    568                 if (!path.contains(cur) && !path.contains(cur.swap())) {
    569                     while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
    570                         path.pop();
    571                     }
    572                     path.push(cur);
    573                     if (isSpanningWay(path)) return buildPathFromNodePairs(path);
    574                     nextPairs.addAll(getOutboundPairs(path.peek()));
    575                 }
    576             }
    577             return null;
    578         }
    579 
    580         /**
    581          * Tries to find a path through the graph which visits each edge (i.e.
    582          * the segment of a way) exactly once.
    583          *
    584          * @return the path; null, if no path was found
    585          */
    586         public List<Node> buildSpanningPath() {
    587             prepare();
    588             // try to find a path from each "terminal node", i.e. from a
    589             // node which is connected by exactly one undirected edges (or
    590             // two directed edges in opposite direction) to the graph. A
    591             // graph built up from way segments is likely to include such
    592             // nodes, unless all ways are closed.
    593             // In the worst case this loops over all nodes which is very slow for large ways.
    594             //
    595             Set<Node> nodes = getTerminalNodes();
    596             nodes = nodes.isEmpty() ? getNodes() : nodes;
    597             for (Node n: nodes) {
    598                 List<Node> path = buildSpanningPath(n);
    599                 if (path != null)
    600                     return path;
    601             }
    602             return null;
    603         }
    604     }
    605253}

  • trunk/src/org/openstreetmap/josm/actions/mapmode/ParallelWays.java

    r12309 r12463  
    1212
    1313import org.openstreetmap.josm.Main;
    14 import org.openstreetmap.josm.actions.CombineWayAction;
    1514import org.openstreetmap.josm.command.AddCommand;
    1615import org.openstreetmap.josm.command.Command;
    … …  
    1817import org.openstreetmap.josm.data.coor.EastNorth;
    1918import org.openstreetmap.josm.data.osm.Node;
     19import org.openstreetmap.josm.data.osm.NodeGraph;
    2020import org.openstreetmap.josm.data.osm.Way;
    2121import org.openstreetmap.josm.tools.Geometry;
    … …  
    7070
    7171        // Find a linear ordering of the nodes. Fail if there isn't one.
    72         CombineWayAction.NodeGraph nodeGraph = CombineWayAction.NodeGraph.createUndirectedGraphFromNodeWays(ways);
     72        NodeGraph nodeGraph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
    7373        List<Node> sortedNodesPath = nodeGraph.buildSpanningPath();
    7474        if (sortedNodesPath == null)

  • trunk/test/unit/org/openstreetmap/josm/actions/CombineWayActionTest.java

    r10956 r12463  
    1313import org.junit.Test;
    1414import org.openstreetmap.josm.TestUtils;
    15 import org.openstreetmap.josm.actions.CombineWayAction.NodeGraph;
    16 import org.openstreetmap.josm.actions.CombineWayAction.NodePair;
    1715import org.openstreetmap.josm.data.osm.DataSet;
    1816import org.openstreetmap.josm.data.osm.Node;
     17import org.openstreetmap.josm.data.osm.NodeGraph;
     18import org.openstreetmap.josm.data.osm.NodePair;
    1919import org.openstreetmap.josm.io.IllegalDataException;
    2020import org.openstreetmap.josm.io.OsmReader;
Note: See TracChangeset for help on using the changeset viewer.