Package org.openstreetmap.josm.data.osm
Class NodeGraph
java.lang.Object
org.openstreetmap.josm.data.osm.NodeGraph
A directed or undirected graph of nodes. Nodes are connected via edges represented by NodePair instances.
- Since:
- 12463 (extracted from CombineWayAction)
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate intThe number of edges that were added.private int -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoidAdd a list of node pairs.voidAdd a node pair.buildNodePairs(List<Way> ways, boolean directed) Builds a list of pair of nodes from the given ways.buildNodePairs(Way way, boolean directed) Builds a list of pair of nodes from the given way.buildPathFromNodePairs(Deque<NodePair> path) Tries to find a path through the graph which visits each edge (i.e.buildSpanningPath(Node startNode) Tries to find a spanning path starting from nodestartNode.Tries to find a path through the graph which visits each edge (i.e.static NodeGraphCreate a directed graph from the given node pairs.static NodeGraphCreate a directed graph from the given ways.Constructs a lookup table from the existing edges in the graph to enable efficient querying.static NodeGraphCreate a nearly undirected graph from the given ways, but prevent reversing of all non-new ways by fixing one direction.static NodeGraphCreate an undirected graph from the given node pairs.static NodeGraphCreate an undirected graph from the given ways, but prevent reversing of all non-new ways by fixing one direction.eliminateDuplicateNodePairs(List<NodePair> pairs) Builds a new list of pair nodes without the duplicated pairs (including inverse copies).getConnectedPairs(Node node) getEdges()Return the edges containing the node pairs of the graph.Sort the nodes by number of appearances in the edges.getNodes()Return the graph's nodes.getOutboundPairs(Node node) getOutboundPairs(NodePair pair) Return the terminal nodes of the graph.private booleanFind out if the graph is connected.protected booleanisSpanningWay(Collection<NodePair> way) protected booleanReplies true ifnis a terminal node of the graph.protected voidprepare()protected voidrememberPredecessors(NodePair pair) Seeprepare()protected voidrememberSuccessor(NodePair pair) Seeprepare()
-
Field Details
-
edges
-
numUndirectedEdges
-
addedEdges
The number of edges that were added. -
successors
-
predecessors
-
-
Constructor Details
-
NodeGraph
public NodeGraph()Constructs a newNodeGraph.
-
-
Method Details
-
buildNodePairs
Builds a list of pair of nodes from the given way.- Parameters:
way- waydirected- iftrueeach pair of nodes will occur once, in the way nodes order. iffalseeach pair of nodes will occur twice (the pair and its inverse copy)- Returns:
- a list of pair of nodes from the given way
-
buildNodePairs
Builds a list of pair of nodes from the given ways.- Parameters:
ways- waysdirected- iftrueeach pair of nodes will occur once, in the way nodes order.
iffalseeach 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
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
Seeprepare() -
rememberPredecessors
Seeprepare() -
isTerminalNode
Replies true ifnis a terminal node of the graph. Internal variables should be initialized first.- Parameters:
n- Node to check- Returns:
trueif it is a terminal node- See Also:
-
prepare
-
add
Add a node pair.- Parameters:
pair- node pair
-
add
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
Return the terminal nodes of the graph.- Returns:
- the terminal nodes of the graph
-
getConnectedPairs
-
getOutboundPairs
-
getOutboundPairs
-
getNodes
Return the graph's nodes.- Returns:
- the graph's nodes
-
isSpanningWay
-
buildPathFromNodePairs
-
buildSpanningPath
Tries to find a spanning path starting from nodestartNode.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
Find out if the graph is connected.- Returns:
trueif 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
-