KSP bugfix - performance

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

KSP bugfix - performance

Hoeltzcke, Claus-Dieter (EXTERN: Ethon)
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: KSP bugfix - performance

gu boulmi
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 :
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,
Very sorry again about my bug.

It appears that I strongly focused my JUnit test cases on the complete graphs (complete graphs being my real use cases at that time) and I do not pay enough attention to sparse graphs.

After further analysis, I think that the bug was not only for not-biconnected graphs but could emerge in non-complete graphs and I will try to explain below why it could.

When storing an intermediary path in the paths list of a vertex, I omitted to check that the path can be extended to the end-vertex (the one in argument of the KSP algorithm). Indeed, a path that could not be extended to the end-vertex would be of no interest because infeasible at the end.

Because I omitted to do this check, "infeasible" paths could be stored during the process in the paths list of a vertex.
"Feasible" paths explored afterwards by the search would not be necessarily inserted in the list in priority to the "infeasible" ones since the insertion relies only on the weight criteria.
Thus, a "feasible" path with a heavy weight could be rejected/discarded by the insertion process when the list is full (max size set to the number k of expected paths by the KSP algorithm) even though other "infeasible" paths are in the list.

Hereafter my analysis of the possible cases when the algorithm could produce inaccurate results :
  • not-complete graphs n-connected and k<n |--> k paths will be returned but possibily not the shortest (1st shortest path always in the returned paths however)
  • not-complete graphs n-connected and k>=n |--> the number of paths returned by the algorithm could be lower than the number of paths possible (because of the "feasible" path discarded effect)
  • complete graphs: no problem, it works fine.

Please find attached the files I modified to correct the bug. It mainly consists in checking that an intermediary path can be extended to the end-vertex before storing it in the paths list. Before that I only checked that a resulting path explored during the search
was a simple path before storing it in the list.

This modification increases the complexity of the algorithm to O(n*k*m²)
By the way I noticed that the mentioned complexity in the javadoc was not right: it was written O(n*k*m) whereas it should have been O(n*k*m*n).
I think that the complexity O(n) to check that a resulting path is a simple path was forgotten in the algorithm complexity calculation.

Last year Olivier mentioned the Jimenez and Marzal algorithm 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 think that their REA algorithm would be worthy to be added to the JGraphT library.
Olivier, would you be ready to have a try ?

Kinds regards,

Guillaume Boulmier


------------------------------------------------------------------------------
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
Loading...