AStar may return invalid paths on directed graphs.

Description

AStar may return invalid paths on directed graphs. The problem seems to occur when there are no directed paths between an origin and a destination node, but there is an undirected path between the two nodes. In this case, the AStar will return the 'undirected' path, ignoring that fact that consecutive edges have different directions and therefore the resulting path should be invalid.

I have attached an example code to illustrate the problem. In a simple directed graph, there exists only one directed path from node 1 to node 4 and both Dijkstra and Astar are able to find this path. Then, one of the edges is removed from the graph so that there are no possible directed paths from node 1 to node 4. However, AStar is still returning a path such that one of the edges (between nodes 2 and 4) has a wrong direction.

I have tried patching the problem by modifying the step function (cont) of the AStarIterator so that it iterates only over outRelated nodes as opposed to all related nodes, but the AStarShorestPathFinder is now throwing the WrongPathException. Ideally, it should return a null object when the path does not exist.

Another possibly related issue is that the result of both Dijkstra and AStar is a Path object, which is a sequence of nodes. The list of edges is then constructed on the fly by invoking the getEdges method on the path object. The potential issue is that getEdges uses any edge between two nodes irrespective of the direction, which is fine for undirected graphs, but not for directed graphs. So, perhaps there should also be a direction version of the Path class which uses outEdges between two nodes to make sure the directions of all edges in the path are the same?

P.S. Another interesting finding is that AStar seems to work even with edges that have Double.POSITIVE_INFINITY set as their weight. So, the only way to 'block' and edge in the graph is to remove it from the graph. It would be nice to have a feature to blacklist edges (or nodes) without removing them from the network.

Environment

Windows 10 Enterprise
Eclipse Java Neon
java version "1.8.0_144"

Assignee

Unassigned

Reporter

Milan

Triage

None

Components

Fix versions

Affects versions

Priority

Medium
Configure