We are using Oracle's Load-on-Demand java library to find shortest path on a network. The network has turn restrictions, each of which may have more than 2 links. So we are calling NetworkAnalyst's nearestPoints() and shortestPathDijkstra() methods, passing in a LODNetworkConstraint.
When I use the MultiLinkPTurnConstraint (attached as "RecommendVehicles10.java.txt") from the NDM tutorial's SpWithProhibitedTurn.java (also attached), on a simple network, I get some simple errors.
Its a case where a turn restriction prevents you from turning into the target node, so you have to revisit the current node to make a turn. Like if you cannot right-turn into your office, so you go to the next junction and do a u-turn first.
The isCurrentNodePartiallyExpanded() and isSatisfied() methods were filled in as suggested.
The test case graph network is attached (graph network diagram.jpg), we are going from Node 5 to Node 3. A turn restriction from link 8 to 17 means the shortest path should be 17,23,24,8.
When running, it gave me path with links [15, 4] as the fastest route.
Debugging (see output.txt) showed that Node 6 was added to openNode (ie: partially expanded), but then later on removed from the openNode list by this code in isSatisfied():
if (!isNextLinkInMap) //no pturn involved
{
boolean[] ret = openNodes.remove(currNode.getId());
if (ret != null)
System.out.println("Removing Node " + currNode.getId() + " because nextLinkId " + nextLinkId + " is not in pTurns");
}
After this it not did not bother to test the other links from Node 6 (link 17)
Commenting out this 'remove()' made it work.
My questions are:
-
Is my understanding correct?
a) We should add a node as 'partially expanded' when there is a turn restriction that stopped us leaving this node.
b) We should remove that node from the 'partially expanded' list only if we manage to later (re-enter and) exit the node via ALL its outgoing links. This guarantees that we (ie: Dijkstra's algorithm) will not visit it again.
-
What was this remove() trying to do?
I cannot see why we would remove a node from the 'partially expanded' list when the next link has no turn restriction.
We may still want to revisit it later.
-
If I fail to remove a node from the partially expanded list, will it cause problems (eg: search looping forever)?
a) Like how I delete the first remove() above.
b) Or, if a node has its one (only) outgoing link blocked by turn restrictions for all incoming links.
Then it will always be in the partially expanded list. (It should never be revisited, but the criteria in 1b will not test for that).
Thanks
Roger
SpWithProhibitedTurn.java.txt (23.75 KB)output.txt (1.24 KB)RecommendVehicles10.java.txt (6.02 KB)