[TRNSPRTPCE-147] k shortest paths with include constraint Created: 10/Sep/19 Updated: 13/Mar/20 Resolved: 06/Feb/20 |
|
| Status: | Verified |
| Project: | transportpce |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | None |
| Type: | Improvement | Priority: | Low |
| Reporter: | Jonas MÃ¥rtensson | Assignee: | Ahmed Triki |
| Resolution: | Done | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | 0 minutes | ||
| Time Spent: | 4 days | ||
| Original Estimate: | Not Specified | ||
| 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? |