Class NodeGraph

java.lang.Object
org.openstreetmap.josm.data.osm.NodeGraph

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

  • Constructor Details

    • NodeGraph

      public NodeGraph()
      Constructs a new NodeGraph.
  • Method Details

    • buildNodePairs

      public static 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 List<NodePair> buildNodePairs(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

      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

      Create a directed graph from the given node pairs.
      Parameters:
      pairs - Node pairs to build the graph from
      Returns:
      node graph structure
    • createDirectedGraphFromWays

      Create a directed graph from the given ways.
      Parameters:
      ways - ways to build the graph from
      Returns:
      node graph structure
    • createUndirectedGraphFromNodeList

      Create an undirected graph from the given node pairs.
      Parameters:
      pairs - Node pairs to build the graph from
      Returns:
      node graph structure
    • createUndirectedGraphFromNodeWays

      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

      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 Map<Node,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
    • rememberSuccessor

      protected void rememberSuccessor(NodePair pair)
    • rememberPredecessors

      protected void rememberPredecessors(NodePair pair)
    • 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

      protected void prepare()
    • add

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

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

      Return the edges containing the node pairs of the graph.
      Returns:
      the edges containing the node pairs of the graph
    • getTerminalNodes

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

    • getOutboundPairs

    • getOutboundPairs

      protected List<NodePair> getOutboundPairs(Node node)
    • getNodes

      Return the graph's nodes.
      Returns:
      the graph's nodes
    • isSpanningWay

      protected boolean isSpanningWay(Collection<NodePair> way)
    • buildPathFromNodePairs

    • buildSpanningPath

      protected 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

      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

      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

      Sort the nodes by number of appearances in the edges.
      Returns:
      set of nodes which can be start nodes in a spanning way