Details
-
Improvement
-
Status: Verified
-
Low
-
Resolution: Done
-
None
-
None
-
None
-
None
Description
In the runKgraphs() method in PceGraph.java there is the following code:
// local optimization. if 'include' constraint exists then increase amount of paths to return. // it's because this constraint is checked at the last step when part of good paths // are dropped by other constraints if (!pceHardConstraints.getListToInclude().isEmpty()) { kpathsToBring = kpathsToBring * 10; LOG.info("k = {}",kpathsToBring); }
So the number of paths to be returned by the k shortest paths algorithm is increased by a factor 10 when there are include constraints. It is not clear to me why this is needed. From the jgrapht documentation it seems to me that the KShortestSimplePaths.getPaths method returns k paths fulfilling the constraints if such paths exist (i.e. it's not that it first calculates k paths and then removes some of them that doesn't fulfill the constraints) so why increase k in this case? Have I misunderstood the implementation?