Hi,
the actual version history states: … - More KSP bugfixes
(spotted by Sebastian Mueller,
fixed by Guillaume Boulmier)
- The main reason for me to update, because 0.8.3 was worse on KSP than 0.8.1.
Since 0.9.0 (bugfix tested OK on my unit tests) the performance on KSP for multigraphs dramatically went down (feels like factor 50 slower!!!).
I did not change anything but the JGraphT version (0.8.1 -> 0.9.0)
Is there any chance to improve performance to what it was before, or is this the unchangeable side effect of the fix?
Thanks + Bye,
Claus
------------------------------------------------------------------------------ HPCC Systems Open Source Big Data Platform from LexisNexis Risk Solutions Find What Matters Most in Your Big Data with HPCC Systems Open Source. Fast. Scalable. Simple. Ideal for Dirty Data. Leverages Graph Analysis for Fast Processing & Easy Data Exploration http://p.sf.net/sfu/hpccsystems _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
Hi,
The worsening of the time complexity, from O(n*k*m*n) to O(n*k*m²), is indeed a side effect of the fix. :-( The fix corrected a bug for sparse graphs. See attached the summary that I wrote to explain the bug. Actually I initially designed the algorithm mainly for the purpose of complete graphs with possibly negative weight cycles and I did not pay enough attention to sparse graphs. However, if you graphs are always complete graphs you can live without the fix and rely on the 0.8.1 version of the algorithm (the bug spotted by Sebastien Muller and corrected in 0.9.0 is related to a "equals versus ==" issue for graphs constructed in a special way : see topic http://sourceforge.net/p/jgrapht/mailman/message/30787322/) Otherwise (if not complete) you would need the new version corrected for sparse graphs. Finally, if your graphs is without negative edge weights, mind thinking to the REA algorithm (Recursive Enumeration Algorithm) by Jimenez and Marzal that benefits from a far better complexity of O(m+Knlog(m/n)) and that remains relatively simple to implement (from what I read from the article http://www.springerlink.com/content/pl0054nt2d0d2u3t/ ). I could improve a lot the performance of your use case. Best regards, Guillaume Le 18/06/2014 07:59, Hoeltzcke, Claus-Dieter (EXTERN: Ethon) a écrit :
------------------------------------------------------------------------------ HPCC Systems Open Source Big Data Platform from LexisNexis Risk Solutions Find What Matters Most in Your Big Data with HPCC Systems Open Source. Fast. Scalable. Simple. Ideal for Dirty Data. Leverages Graph Analysis for Fast Processing & Easy Data Exploration http://p.sf.net/sfu/hpccsystems _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users JGraphT-0.8.2_KSP-connectivity-correction_20101206.zip (56K) Download Attachment |
Free forum by Nabble | Edit this page |