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 <zpin...@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 > <spencergard...@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
