Package org.openstreetmap.josm.data.osm
Class NodeGraph
- java.lang.Object
-
- org.openstreetmap.josm.data.osm.NodeGraph
-
-
Field Summary
Fields Modifier and Type Field Description private int
addedEdges
counts the number of edges that were addedprivate Set<NodePair>
edges
private int
numUndirectedEges
private Map<Node,List<NodePair>>
predecessors
private Map<Node,List<NodePair>>
successors
-
Constructor Summary
Constructors Constructor Description NodeGraph()
Constructs a newNodeGraph
.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
add(Collection<NodePair> pairs)
Add a list of node pairs.void
add(NodePair pair)
Add a node pair.static List<NodePair>
buildNodePairs(List<Way> ways, boolean directed)
Builds a list of pair of nodes from the given ways.static List<NodePair>
buildNodePairs(Way way, boolean directed)
Builds a list of pair of nodes from the given way.protected List<Node>
buildPathFromNodePairs(Deque<NodePair> path)
List<Node>
buildSpanningPath()
Tries to find a path through the graph which visits each edge (i.e.protected List<Node>
buildSpanningPath(Node startNode)
Tries to find a spanning path starting from nodestartNode
.List<Node>
buildSpanningPathNoRemove()
Tries to find a path through the graph which visits each edge (i.e.static NodeGraph
createDirectedGraphFromNodePairs(List<NodePair> pairs)
static NodeGraph
createDirectedGraphFromWays(Collection<Way> ways)
static NodeGraph
createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways)
static NodeGraph
createUndirectedGraphFromNodeList(List<NodePair> pairs)
Create an undirected graph from the given node pairs.static NodeGraph
createUndirectedGraphFromNodeWays(Collection<Way> ways)
Create an undirected graph from the given ways, but prevent reversing of all non-new ways by fix one direction.static List<NodePair>
eliminateDuplicateNodePairs(List<NodePair> pairs)
Builds a new list of pair nodes without the duplicated pairs (including inversed copies).private List<NodePair>
getConnectedPairs(Node node)
private Set<Node>
getMostFrequentVisitedNodesFirst()
Sort the nodes by number of appearances in the edges.protected Set<Node>
getNodes()
protected List<NodePair>
getOutboundPairs(Node node)
protected List<NodePair>
getOutboundPairs(NodePair pair)
protected Set<Node>
getTerminalNodes()
private boolean
isConnected()
Find out if the graph is connected.protected boolean
isSpanningWay(Collection<NodePair> way)
protected boolean
isTerminalNode(Node n)
protected void
prepare()
protected void
rememberPredecessors(NodePair pair)
protected void
rememberSuccessor(NodePair pair)
-
-
-
Field Detail
-
numUndirectedEges
private int numUndirectedEges
-
addedEdges
private int addedEdges
counts the number of edges that were added
-
successors
private final Map<Node,List<NodePair>> successors
-
predecessors
private final Map<Node,List<NodePair>> predecessors
-
-
Constructor Detail
-
NodeGraph
public NodeGraph()
Constructs a newNodeGraph
.
-
-
Method Detail
-
buildNodePairs
public static List<NodePair> buildNodePairs(Way way, boolean directed)
Builds a list of pair of nodes from the given way.- Parameters:
way
- waydirected
- iftrue
each pair of nodes will occur once, in the way nodes order. iffalse
each pair of nodes will occur twice (the pair and its inversed 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
- waysdirected
- iftrue
each pair of nodes will occur once, in the way nodes order. iffalse
each pair of nodes will occur twice (the pair and its inversed copy)- Returns:
- a list of pair of nodes from the given ways
-
eliminateDuplicateNodePairs
public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs)
Builds a new list of pair nodes without the duplicated pairs (including inversed copies).- Parameters:
pairs
- existing list of pairs- Returns:
- a new list of pair nodes without the duplicated pairs
-
createDirectedGraphFromNodePairs
public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs)
-
createDirectedGraphFromWays
public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways)
-
createUndirectedGraphFromNodeList
public static NodeGraph createUndirectedGraphFromNodeList(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(Collection<Way> ways)
Create an undirected graph from the given ways, but prevent reversing of all non-new ways by fix one direction.- Parameters:
ways
- Ways to build the graph from- Returns:
- node graph structure
- Since:
- 8181
-
createNearlyUndirectedGraphFromNodeWays
public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways)
-
rememberSuccessor
protected void rememberSuccessor(NodePair pair)
-
rememberPredecessors
protected void rememberPredecessors(NodePair pair)
-
isTerminalNode
protected boolean isTerminalNode(Node n)
-
prepare
protected void prepare()
-
add
public void add(Collection<NodePair> pairs)
Add a list of node pairs.- Parameters:
pairs
- list of node pairs
-
getTerminalNodes
protected Set<Node> getTerminalNodes()
-
getConnectedPairs
private List<NodePair> getConnectedPairs(Node node)
-
getOutboundPairs
protected List<NodePair> getOutboundPairs(NodePair pair)
-
getOutboundPairs
protected List<NodePair> getOutboundPairs(Node node)
-
isSpanningWay
protected boolean isSpanningWay(Collection<NodePair> way)
-
buildPathFromNodePairs
protected List<Node> buildPathFromNodePairs(Deque<NodePair> path)
-
buildSpanningPath
protected List<Node> buildSpanningPath(Node startNode)
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
public 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 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 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.
-
-