public class NodeGraph extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
private int |
addedEdges
counts the number of edges that were added
|
private java.util.Set<NodePair> |
edges |
private int |
numUndirectedEges |
private java.util.Map<Node,java.util.List<NodePair>> |
predecessors |
private java.util.Map<Node,java.util.List<NodePair>> |
successors |
Constructor and Description |
---|
NodeGraph()
Constructs a new
NodeGraph . |
Modifier and Type | Method and Description |
---|---|
void |
add(java.util.Collection<NodePair> pairs)
Add a list of node pairs.
|
void |
add(NodePair pair)
Add a node pair.
|
static java.util.List<NodePair> |
buildNodePairs(java.util.List<Way> ways,
boolean directed)
Builds a list of pair of nodes from the given ways.
|
static java.util.List<NodePair> |
buildNodePairs(Way way,
boolean directed)
Builds a list of pair of nodes from the given way.
|
protected java.util.List<Node> |
buildPathFromNodePairs(java.util.Deque<NodePair> path) |
java.util.List<Node> |
buildSpanningPath()
Tries to find a path through the graph which visits each edge (i.e.
|
protected java.util.List<Node> |
buildSpanningPath(Node startNode)
Tries to find a spanning path starting from node
startNode . |
java.util.List<Node> |
buildSpanningPathNoRemove()
Tries to find a path through the graph which visits each edge (i.e.
|
static NodeGraph |
createDirectedGraphFromNodePairs(java.util.List<NodePair> pairs) |
static NodeGraph |
createDirectedGraphFromWays(java.util.Collection<Way> ways) |
static NodeGraph |
createNearlyUndirectedGraphFromNodeWays(java.util.Collection<Way> ways) |
static NodeGraph |
createUndirectedGraphFromNodeList(java.util.List<NodePair> pairs)
Create an undirected graph from the given node pairs.
|
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 fix one direction.
|
static java.util.List<NodePair> |
eliminateDuplicateNodePairs(java.util.List<NodePair> pairs)
Builds a new list of pair nodes without the duplicated pairs (including inversed copies).
|
private java.util.List<NodePair> |
getConnectedPairs(Node node) |
private java.util.Set<Node> |
getMostFrequentVisitedNodesFirst()
Sort the nodes by number of appearances in the edges.
|
protected java.util.Set<Node> |
getNodes() |
protected java.util.List<NodePair> |
getOutboundPairs(Node node) |
protected java.util.List<NodePair> |
getOutboundPairs(NodePair pair) |
protected java.util.Set<Node> |
getTerminalNodes() |
private boolean |
isConnected()
Find out if the graph is connected.
|
protected boolean |
isSpanningWay(java.util.Collection<NodePair> way) |
protected boolean |
isTerminalNode(Node n) |
protected void |
prepare() |
protected void |
rememberPredecessors(NodePair pair) |
protected void |
rememberSuccessor(NodePair pair) |
private int numUndirectedEges
private int addedEdges
private final java.util.Map<Node,java.util.List<NodePair>> successors
private final java.util.Map<Node,java.util.List<NodePair>> predecessors
public NodeGraph()
NodeGraph
.public static java.util.List<NodePair> buildNodePairs(Way way, boolean directed)
way
- waydirected
- 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 inversed copy)public static java.util.List<NodePair> buildNodePairs(java.util.List<Way> ways, boolean directed)
ways
- waysdirected
- 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 inversed copy)public static java.util.List<NodePair> eliminateDuplicateNodePairs(java.util.List<NodePair> pairs)
pairs
- existing list of pairspublic static NodeGraph createDirectedGraphFromNodePairs(java.util.List<NodePair> pairs)
public static NodeGraph createDirectedGraphFromWays(java.util.Collection<Way> ways)
public static NodeGraph createUndirectedGraphFromNodeList(java.util.List<NodePair> pairs)
pairs
- Node pairs to build the graph frompublic static NodeGraph createUndirectedGraphFromNodeWays(java.util.Collection<Way> ways)
ways
- Ways to build the graph frompublic static NodeGraph createNearlyUndirectedGraphFromNodeWays(java.util.Collection<Way> ways)
protected void rememberSuccessor(NodePair pair)
protected void rememberPredecessors(NodePair pair)
protected boolean isTerminalNode(Node n)
protected void prepare()
public void add(java.util.Collection<NodePair> pairs)
pairs
- list of node pairsprotected java.util.Set<Node> getTerminalNodes()
private java.util.List<NodePair> getConnectedPairs(Node node)
protected java.util.List<NodePair> getOutboundPairs(NodePair pair)
protected java.util.List<NodePair> getOutboundPairs(Node node)
protected boolean isSpanningWay(java.util.Collection<NodePair> way)
protected java.util.List<Node> buildPathFromNodePairs(java.util.Deque<NodePair> path)
protected java.util.List<Node> buildSpanningPath(Node startNode)
startNode
.
Traverses the path in depth-first order.startNode
- the start nodepublic java.util.List<Node> buildSpanningPath()
Note that duplicated edges are removed first!
public java.util.List<Node> buildSpanningPathNoRemove()
private boolean isConnected()
private java.util.Set<Node> getMostFrequentVisitedNodesFirst()