Package org.openstreetmap.josm.data.osm

Class NodeGraph

  • public class NodeGraph
extends java.lang.Object
    A directed or undirected graph of nodes. Nodes are connected via edges represented by NodePair instances.
    Since:
    12463 (extracted from CombineWayAction)

    • Constructor Detail

      • NodeGraph

        public NodeGraph()
        Constructs a new NodeGraph.

    • Method Detail

      • buildNodePairs

        public static java.util.List<NodePair> buildNodePairs​(Way way,
                                                      boolean directed)
        Builds a list of pair of nodes from the given way.
        Parameters:
        way - way
        directed - if true each pair of nodes will occur once, in the way nodes order. if false each pair of nodes will occur twice (the pair and its inverse copy)
        Returns:
        a list of pair of nodes from the given way

      • buildNodePairs

        public static java.util.List<NodePair> buildNodePairs​(java.util.List<Way> ways,
                                                      boolean directed)
        Builds a list of pair of nodes from the given ways.
        Parameters:
        ways - ways
        directed - if true each pair of nodes will occur once, in the way nodes order.
        if false each pair of nodes will occur twice (the pair and its inverse copy)
        Returns:
        a list of pair of nodes from the given ways

      • eliminateDuplicateNodePairs

        public static java.util.List<NodePair> eliminateDuplicateNodePairs​(java.util.List<NodePair> pairs)
        Builds a new list of pair nodes without the duplicated pairs (including inverse copies).
        Parameters:
        pairs - existing list of pairs
        Returns:
        a new list of pair nodes without the duplicated pairs

      • createDirectedGraphFromNodePairs

        public static NodeGraph createDirectedGraphFromNodePairs​(java.util.List<NodePair> pairs)
        Create a directed graph from the given node pairs.
        Parameters:
        pairs - Node pairs to build the graph from
        Returns:
        node graph structure

      • createDirectedGraphFromWays

        public static NodeGraph createDirectedGraphFromWays​(java.util.Collection<Way> ways)
        Create a directed graph from the given ways.
        Parameters:
        ways - ways to build the graph from
        Returns:
        node graph structure

      • createUndirectedGraphFromNodeList

        public static NodeGraph createUndirectedGraphFromNodeList​(java.util.List<NodePair> pairs)
        Create an undirected graph from the given node pairs.
        Parameters:
        pairs - Node pairs to build the graph from
        Returns:
        node graph structure

      • createUndirectedGraphFromNodeWays

        public static NodeGraph createUndirectedGraphFromNodeWays​(java.util.Collection<Way> ways)
        Create an undirected graph from the given ways, but prevent reversing of all non-new ways by fixing one direction.
        Parameters:
        ways - Ways to build the graph from
        Returns:
        node graph structure
        Since:
        8181

      • createNearlyUndirectedGraphFromNodeWays

        public static NodeGraph createNearlyUndirectedGraphFromNodeWays​(java.util.Collection<Way> ways)
        Create a nearly undirected graph from the given ways, but prevent reversing of all non-new ways by fixing one direction. The first new way gives the direction of the graph.
        Parameters:
        ways - Ways to build the graph from
        Returns:
        node graph structure

      • createMap

        public java.util.Map<Node,​java.util.List<Node>> createMap()
        Constructs a lookup table from the existing edges in the graph to enable efficient querying. This method creates a map where each node is associated with a list of nodes that are directly connected to it.
        Returns:
        A map representing the graph structure, where nodes are keys, and values are their direct successors.
        Since:
        19062

      • isTerminalNode

        protected boolean isTerminalNode​(Node n)
        Replies true if n is a terminal node of the graph. Internal variables should be initialized first.
        Parameters:
        n - Node to check
        Returns:
        true if it is a terminal node
        See Also:
        prepare()

      • prepare

        protected void prepare()

      • add

        public void add​(NodePair pair)
        Add a node pair.
        Parameters:
        pair - node pair

      • add

        public void add​(java.lang.Iterable<NodePair> pairs)
        Add a list of node pairs.
        Parameters:
        pairs - collection of node pairs

      • getEdges

        public java.util.Collection<NodePair> getEdges()
        Return the edges containing the node pairs of the graph.
        Returns:
        the edges containing the node pairs of the graph

      • getTerminalNodes

        protected java.util.Set<Node> getTerminalNodes()
        Return the terminal nodes of the graph.
        Returns:
        the terminal nodes of the graph

      • getNodes

        public java.util.Collection<Node> getNodes()
        Return the graph's nodes.
        Returns:
        the graph's nodes

      • buildSpanningPath

        protected java.util.List<Node> buildSpanningPath​(Node startNode)
        Tries to find a spanning path starting from node startNode.

        Traverses the path in depth-first order.

        Parameters:
        startNode - the start node
        Returns:
        the spanning path; empty list if no path is found

      • buildSpanningPath

        public java.util.List<Node> buildSpanningPath()
        Tries to find a path through the graph which visits each edge (i.e. the segment of a way) exactly once.

        Note that duplicated edges are removed first!

        Returns:
        the path; null, if no path was found

      • buildSpanningPathNoRemove

        public java.util.List<Node> buildSpanningPathNoRemove()
        Tries to find a path through the graph which visits each edge (i.e. the segment of a way) exactly once. If the graph was build from overlapping ways duplicate edges were removed already. This method will return null if any duplicated edge was removed.
        Returns:
        List of nodes that build the path; an empty list if no path or duplicated edges were found
        Since:
        15573 (return value not null)

      • isConnected

        private boolean isConnected()
        Find out if the graph is connected.
        Returns:
        true if it is connected

      • getMostFrequentVisitedNodesFirst

        private java.util.Set<Node> getMostFrequentVisitedNodesFirst()
        Sort the nodes by number of appearances in the edges.
        Returns:
        set of nodes which can be start nodes in a spanning way