> 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
