Issue in finding the least-cost paths to create the MPG : Some LCP are actually not the LCP ?

[Klemet]

Hello there 😄 ! Sorry to come yet again with an issue.

To make it simple : I found a case where Grainscape seemed to have created a link between two patches via the MPG function that does not actually correspond to the least-cost path between the two.

See GrainscapeIssue.zip for sample files.

Here is the resistance map (yellow = cost of 1 for forests, green = cost of 1000 for lakes) + the patches (white) :

Here is the resulting MPG, and a highlight of the two patches with the problematic connection :

Zooming in in QGIS, we can see that the obvious least-cost path is a path with a final cost of 3 through three cells with a cost of 1 (displayed in purple on this screenshot, wtith the patches in green and the lakes with cost 1000 in yellow) :

However, the least-cost path indicated by the MPG object (see lcpPerimWeight raster) goes straight through the lake, giving a path of 1 cell, but with cost 1000 (in orange on this screenshot) :

I don't think this questions the structure of the MPG, but only the weight of some particular links. I noticed it while doing an analysis similar to what Linkage Mapper does with corridors, where the pixels of the corridor maps correspond to "the additional cost of going through this pixel compared to using the least-cost path between the two patches linked by the corridor". In that case, because some least-cost path were wrong (I had several cases in my landscape), this resulted in negative values for this corridors (which should not happen).

No idea as to why this happens, and I haven't identified a pattern in this errors that could give me a pointer where the LCP algorithm of Grainscape might have an issue. I can post other cases if needed.

[achubaty]

Thanks for reporting this. I will try to get to this as soon as possible, but unlikely before September. (I'm hoping to get updated version of this package to CRAN this fall.)

@ecologics do you have time to investigate before then?

[Klemet]

There's no rush on my side; thank you for taking a look at it !

[achubaty]

@Klemet I can reproduce this, even zoomed into (i.e., cropped to) the problem area highlighted. I'm taking a look at this now, and hope to have it fixed in a few days.

[Klemet]

Happy to see that it's reproducible ! Will be curious to see what was the issue.

[achubaty]

@Klemet @pgalpern I'm sorry I ran out of time to fully address this issue before needing to submit to CRAN. I've identified the problem(s) with the LCP MPG algorithm, but solutions are much more involved than I had hoped, and requires further debugging/reworking on the C++ side.

The general problem right now is that as the algorithm is building the voronoi polygons and adding ActiveCells to the spread_list, it's also finding paths/links between nodes, and is erroneously including ActiveCells that have been queued for later processing because of high resistance/cost values. We only triggered/noticed this because this example had two patch cells separated by a single non-patch cell with high resistance. During spreading, the patch on the right establishes a link to the middle cell, and queues it for later. Subsequently, when the patch on the left establishes a link to that middle cell, it immediately finds and establishes a path connecting the two patches. For computational reasons, once a link between patches is established, stop looking for other links because we had assumed the first link found would be the LCP. I need to find an efficient way to delay the establishment of these links, so that lower cost paths get processed first, and the link established between nodes actually is the least cost one.

I will come back to it in a few weeks.

[Klemet]

Thank you for the update, @achubaty !! It's very interesting to see how this came to be.

Also, just wanted to say thanks for your work on Grainscape, and for you to not feel in a rush. I'm already very grateful of everything I was able to do with the package, and for the attention you're giving to this fix 🙏

Good luck for finding a fix !