pombreda / python-graph

Automatically exported from code.google.com/p/python-graph
Other
0 stars 0 forks source link

shortest_path should be faster #80

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago
pygraph.algorithms,minmax.shortest_path executes in n^2 time, as indicated by a 
comment in the function. A modified version using a priority queue with a 
binary insert is n*log(n). I've attached a diff against r708 as well as the 
complete function for easy inspection.

Thanks

Original issue reported on code.google.com by peter.sagerson@gmail.com on 24 Jul 2010 at 2:34

Attachments:

GoogleCodeExporter commented 9 years ago
Have you re-run this against the test-suite?

Original comment by salimfadhley@gmail.com on 24 Jul 2010 at 8:17

GoogleCodeExporter commented 9 years ago
Of course. The tests pass with the change. Outstanding test suite, by the way.

Original comment by peter.sagerson@gmail.com on 24 Jul 2010 at 3:49

GoogleCodeExporter commented 9 years ago
One other thing to note: if you call the current implementation with an invalid 
source (a node that is not in the graph), it will return ({source: None}, 
{source: 0}). This is probably a bad choice, as it is indistinguishable from 
the case where source is a valid node with no neighbors. It's also arguably 
inconsistent with the documentation: "Inaccessible target nodes do not appear 
in either dictionary." The proposed implementation will raise a KeyError in 
this case, which I think is a legitimate response. My second choice would be 
returning ({}, {}).

Since this edge case is neither documented nor tested, one could argue that 
it's undefined behavior and not necessarily subject to backwards compatibility. 
However, the old behavior could be emulated if this is a concern.

Original comment by peter.sagerson@gmail.com on 24 Jul 2010 at 5:08

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 3 Oct 2010 at 8:25

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 3 Oct 2010 at 8:46

GoogleCodeExporter commented 9 years ago
Merged in r720.

Original comment by pmatiello on 3 Oct 2010 at 9:14

GoogleCodeExporter commented 9 years ago

Original comment by pmatiello on 3 Oct 2010 at 9:14