Good point. Hadn't thought about the monotonic problem with Dijkstra. My problem is I need the costs to represent considerations other than pure distance but my ultimate outcome must be constrained by a total distance, so there's not really a good way that I can see to fold them together. One strategy I've been planning to investigate is developing an unconstrained cumulative cost matrix for each origin point and each destination point and then sum the O + D matrices to get the total route cost for the pair at every matrix coordinate. I'm not completely sure how I can use that to identify a route within my distance constraints but I think it might be a promising option. On Tue, May 2, 2017 at 3:01 PM, Zach Pincus <zpincus@gmail.com> wrote:

I can't think of any alternatives off the top of my head. The usual solution is to incorporate everything into your cost function, instead of having two separate stopping criteria -- most problems lend themselves to this pretty well.

And actually, now that I think of it: Dijkstra's algorithm (which is all this graph traversal is running) fails with non-monotonic cost functions. Since the algorithm only visits a given position one time (on the minimum cost path), a shorter but more expensive path to the same point will not be considered, even if that is part of the path that gives a global optimum on your "minimum cost path below a certain length" problem. It would be a good advanced algorithms problem set question to consider if optimal solutions to that problem will necessarily be exponential in complexity.

So that's why people usually try to blend their cost considerations into a single cost for traversing each node...

That said, you might get OK solutions from this modified algorithm, though there will be no guarantee of global optimality.

I can also think of one awful hack you could try to just see how well it works. You could "store" the number of steps in the cumulative cost by defining a custom travel_cost function. https://github.com/scikit-image/scikit-image/blob/ master/skimage/graph/_mcp.pyx#L885

Let's assume that your "actual" costs are all >> 1. Then, instead of returning new_cost, you return new_cost + 0.001. Then goal_reached could count the number of steps by just looking at the value of the cumulative cost after the decimal point.

Again, this is gross, and there are lots of cases where it won't work or will blow up badly. But for reasonably small maximum path lengths, it should be OK. Also, for speed you'll still need to implement this in a cython subclass. But you can use MCP_Flexible to proof out the implementation in slow pure python.

On Tue, May 2, 2017 at 2:43 PM, Spencer Gardner <spencergardner@gmail.com> wrote:

...

Thanks. That's extremely helpful. I think I'll be able to work out the subclassing. I've never worked in cython but there's a first time for everything.

Is there some alternative solution to my problem that I've missed? I've scoured the documentation from various software projects (GIS and non-GIS) to try to find something that implements an algorithm like this but I haven't come across anything. This seems odd to me, since it's a problem I assume others have had to solve before.

In any case, I'm sure I'll be back with more questions as I dive in.

Spencer

On Tue, May 2, 2017 at 2:11 PM, Zach Pincus <zpincus@gmail.com> wrote:

...

...

I need to implement a minimum cost path through an array of costs. The added twist is that I need to ensure the path does not exceed some maximum geometric distance (represented as a total number of traversed cells). So I need my goal_reached() method to check whether the current path has exceeded the maximum number of cells and return 1 if true (which tells MCP to stop checking neighbors).

Is there a good example implementation somewhere that I can refer to

for

...

...

some guidance? I've sketched out a rough outline but I'm not sure I'm on the right track:

graph = MCP(costSurfaceArray,fully_connected=False)

def goal_reached(index, cumcost): '''code to check total distance'''

graph.goal_reached = goal_reached

First, note that MCP is implemented in cython, so you can't monkeypatch goal-reached like you could with a pure-python class. Instead you have to subclass:

class MyMCP(MCP): def goal_reached(self, index, cumcost): print(index, cumcost) return 0

m = MyMCP(costSurfaceArray)

Second, let's figure out about casting your problem in a way that goal_reached can address. Here's the documentation for goal_reached:

""" int goal_reached(int index, float cumcost) This method is called each iteration after popping an index from the heap, before examining the neighbours. This method can be overloaded to modify the behavior of the MCP algorithm. An example might be to stop the algorithm when a certain cumulative cost is reached, or when the front is a certain distance away from the seed point. This method should return 1 if the algorithm should not check the current point's neighbours and 2 if the algorithm is now done. """

So basically, the function receives the "current" index (i.e. position in the array) under consideration, along with the minimum cost to get there. If the algorithm should not continue this portion of the search past that index, the function needs to return 1. If the algorithm should terminate wholesale, return 2.

If all you needed to do was stop searching after you'd gotten a certain euclidian distance from the starting point, you could calculate that with just the index and knowledge of the starting points. However, you want to find out the current path length terminating in the current index.

For this, you will need to deal with the MCP object's traceback_offsets attribute, which stores the paths to each point. For speed reasons, this is only available to subclasses written in cython, rather than pure-python. So you'll have to write it as a cpdef function in a cython subclass of MCP.

For the implementation, you'll need to consult how MCP.traceback(self, end) is implemented, and run the same procedure in goal_reached() to simply count the length of the path and return 1 if the path exceeds your acceptable length:

https://github.com/scikit-image/scikit-image/blob/ master/skimage/graph/_mcp.pyx#L648

This won't be totally trivial, however. You'll need to understand a bit of cython, and a bit about how MCP works under the hood: it doesn't store indices as n-dimensional tuples like (x,y,z) coordinates or whatever. Instead it stores them as 1-dimensional indices into the flattened cost array. So much of the logic in the traceback() function is converting those indices around. Basically you'll just need to copy-paste traceback() into goal_reached() but instead of un-flattening the indices to append them to a traceback list, just count the number of links required to get to a starting point.

Let me know if this helps.

Zach

On Tue, May 2, 2017 at 12:14 PM, Spencer Gardner <spencergardner@gmail.com> wrote:

...

The skimage.graph documentation states that the goal_reached method can be overloaded to introduce additional constraints on finding the minimum cost path. I'm having some trouble implementing this but I can't find any useful examples to follow online. I'm hoping someone can provide some guidance.

I need to implement a minimum cost path through an array of costs. The added twist is that I need to ensure the path does not exceed some maximum geometric distance (represented as a total number of traversed cells). So I need my goal_reached() method to check whether the current path has exceeded the maximum number of cells and return 1 if true (which tells MCP to stop checking neighbors).

Is there a good example implementation somewhere that I can refer to for some guidance? I've sketched out a rough outline but I'm not sure I'm on the right track:

graph = MCP(costSurfaceArray,fully_connected=False)

def goal_reached(index, cumcost): '''code to check total distance'''

graph.goal_reached = goal_reached

Thanks for any help!

PS I posted this also on a Google Group that appears to be defunct. Apologies if that list is actually active and you got a double post from me.

_______________________________________________ scikit-image mailing list scikit-image@python.org https://mail.python.org/mailman/listinfo/scikit-image

_______________________________________________ scikit-image mailing list scikit-image@python.org https://mail.python.org/mailman/listinfo/scikit-image

_______________________________________________ scikit-image mailing list scikit-image@python.org https://mail.python.org/mailman/listinfo/scikit-image

_______________________________________________ scikit-image mailing list scikit-image@python.org https://mail.python.org/mailman/listinfo/scikit-image