gama.old icon indicating copy to clipboard operation
gama.old copied to clipboard

Published 20 hours ago • verified publisher icon gama-platform

k multiple paths bug

Open sriramab opened this issue 7 years ago • 7 comments

Hi

The current k shortest path algorithm works for very simple graphs. But it fails for more realistic road networks as downloaded from open street map. These more real world maps with cycling paths and roads are not handled correctly (gama hangs, gives no output, does not even initialize if you ask output within initialization) with the current implementation.

I would like to request to check this more popular java library for k shortest paths https://github.com/yan-qi/k-shortest-paths-java-version

Thank you

sriramab avatar Nov 17 '17 08:11 sriramab

I tried to integrate this library into GAMA, but the java version of the library seems to bug.

ptaillandier avatar Dec 06 '17 10:12 ptaillandier

Thank you Patrick, I will look if there are other libraries. Or may be you can look again later at your convenience.

sriramab avatar Dec 06 '17 15:12 sriramab

@sriramab, @ptaillandier , something new on this issue ? Can we close it of keep it opened as an Enhancement ?

benoitgaudou avatar Mar 11 '18 15:03 benoitgaudou

I do not think any improvements have been made on this. So it still remains.

sriramab avatar Mar 11 '18 16:03 sriramab

Hi, before integrating a new library (with all the constraints implied, like another interface for Graphs, etc.), maybe it would be interesting to check if the newest version of JGraphT (https://github.com/jgrapht/jgrapht) is not up to the task. They have been working on performance improvements, etc. (and a slew of new algorithms, generators, imports and exports -- potentially reducing the interest of carrying other libraries like Prefuse and GraphStreams).

I've made a first attempt when moving to 1.8 (there : https://github.com/gama-platform/gama/commit/25bc6b12dca069c5d424d5bf9ea31af450401d6a) but we had to remove it because it has been insufficiently tested. I can try another one !

AlexisDrogoul avatar Jun 13 '18 03:06 AlexisDrogoul

@ptaillandier do the new additions in 1.8.2 solve this issue ?

AlexisDrogoul avatar Aug 17 '21 02:08 AlexisDrogoul

I don't know. Thanks to the new version of Jgrapht, we have now 2 K-shortest path algorithms:

  • Yen algorithm (Q. V. Martins, Ernesto and M. B. Pascoal, Marta. (2003). A new implementation of Yen’s ranking loopless paths algorithm. Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 1. 121-133. 10.1007/s10288-002-0010-2)
  • Bhandari algorithm - not usable for directed graph (Bhandari, Ramesh 1999. Survivable networks: algorithms for diverse routing. 477. Springer. p. 46. ISBN 0-7923-8381-8.)

I don't know if it is enough or not.

ptaillandier avatar Aug 17 '21 03:08 ptaillandier