Hide edges with a weight of None in A*.#5945
Conversation
This matches the Dijkstra's weight interface.
rossbar
left a comment
There was a problem hiding this comment.
Aiming for consistency with the dijkstra method(s) makes sense to me. It seems that the current behavior would result in a TypeError when trying to add the heuristic to the weight, right? That means we don't need to worry about subtle behavior changes 👍 .
It'd be good to add tests for the new behavior as well.
|
Apologies for the delay. Invoking A* with a weight function wasn't previously tested, so I've added tests for basic usage with numerical weights and hidden edges with weights of None. |
dschult
left a comment
There was a problem hiding this comment.
I really like this improvement. It brings our useage of weight into better alignment and adds the feature of excluding edges (which will hopefully become more universal as we move to unifying the weight input parameters around the library.
I added a comment about wording for the docstring. But it is so minor, I'm going to approve this so we can get it merged soon.
Thanks @brianhou !
|
Thank you! I've updated the docstring wording as you suggested, so I think this might be ready to merge. |
rossbar
left a comment
There was a problem hiding this comment.
Generally LGTM, just one last question about the wording around how distances are calculated. I'm certainly no A* expert so it could just be that I'm misunderstanding things!
| Notes | ||
| ----- | ||
| Edge weight attributes must be numerical. | ||
| Distances are calculated as sums of weighted edges traversed. |
There was a problem hiding this comment.
The point I was getting at here with the original comment is that the "Distances are calculated as sums of weighted edges traversed" is not quite correct for the A* case, as the distance also takes into account the heuristic, right?
There was a problem hiding this comment.
If I understand correctly, the heuristic is an estimate of the distance. So the distance is still the sum of the weighted edges. But the estimate of the distance may include heuristic values. Perhaps we should add a sentence/phrase to make this clear?
Distances are calculated as sums of weighted edges traversed.
The algorithm uses heuristics to estimate these distances.
There was a problem hiding this comment.
If I understand correctly, the heuristic is an estimate of the distance. So the distance is still the sum of the weighted edges. But the estimate of the distance may include heuristic values.
That was my understanding as well. As a concrete example of where confusion may arise:
>>> G = nx.DiGraph()
>>> G.add_weighted_edges_from([(0, 1, 10), (1, 2, 10)])
>>> G.add_weighted_edges_from([(0, 2, 21)])
>>> nx.astar_path(G, 0, 2) # No heuristic, weights only
[0, 1, 2]
>>> heur = lambda u, v: 100 if (u, v) == (1, 2) else 0
>>> nx.astar_path(G, 0, 2, heuristic=heur) # "distance" between 1, 2 is now much larger because of heuristic - weights unchanged
[0, 2]Of course, there's nuance here. For example, A* is only guaranteed to work if the heuristic is "valid"; I doubt heur from the contrived example above counts.
Perhaps we should add a sentence/phrase to make this clear?
Agreed, I like your wording suggestion 👍 . There are some other finer points re: astar and weights vs. heuristics vs. distances that I think are worth investigating further, but those are broader topics to be discussed elsewhere so they don't block this PR!
* Hide edges with a weight of None in A*. This matches the Dijkstra's weight interface. * Update Dijkstra's and A* docs for weights of None. * Add tests for A* with weight of None. * Add another test for A* with a weight function. * Document that None indicates a hidden edge.
* Hide edges with a weight of None in A*. This matches the Dijkstra's weight interface. * Update Dijkstra's and A* docs for weights of None. * Add tests for A* with weight of None. * Add another test for A* with a weight function. * Document that None indicates a hidden edge.
Commit d82815d for issue networkx#5945 added the ability for A* weight functions to return None, in which case that edge is ignored. This was done for consistency with Dijkstra. The simple_paths() algorithms would benefit from the same ability. Signed-off-by: Jim Hull <jmhull@ieee.org>
* Hide edges with a weight of None in simple_paths Commit d82815d for issue #5945 added the ability for A* weight functions to return None, in which case that edge is ignored. This was done for consistency with Dijkstra. The simple_paths() algorithms would benefit from the same ability. --------- Signed-off-by: Jim Hull <jmhull@ieee.org> Co-authored-by: Dan Schult <dschult@colgate.edu>
* Hide edges with a weight of None in simple_paths Commit d82815d for issue networkx#5945 added the ability for A* weight functions to return None, in which case that edge is ignored. This was done for consistency with Dijkstra. The simple_paths() algorithms would benefit from the same ability. --------- Signed-off-by: Jim Hull <jmhull@ieee.org> Co-authored-by: Dan Schult <dschult@colgate.edu>
This matches the Dijkstra's weight interface, which ignores edges with a weight of
None.networkx/networkx/algorithms/shortest_paths/weighted.py
Line 838 in d2ceeb6
Documentation for this feature is copied from
dijkstra_path.networkx/networkx/algorithms/shortest_paths/weighted.py
Line 134 in d2ceeb6