Hello everyone,
I was hoping to get some advice on dealing with the MCP_flexible class. Sorry if the email is too big, I tried to be as clear as possible.
I will use an example that I think will help me explaining the problem. I have a road network and a subway network in a raster format and I want to calculate least cost paths on them. To simplify it, consider this small example:
 # Piece of code (1)
# (1) Roads network:
roads = np.array([[2,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],
[10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],
[10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],[10,5,5,5,2]])
#The idea here is that 5 denotes a road, 10 denotes a place where you can walk and 2 denotes #a subway station.
# (2) Subway network:
subway = np.array([[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],
[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],
[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]])
# here the value 1 denotes a piece of the subway and the value 1 denotes a cell you cannot reach.
# So, my whole network is given by:
network = np.array([roads,subway])
# End of piece of code (1)

This I my input, and what I want to do is to calculate least cost path between the point (0,0,1) and (0,11,4).
Why can't I use MCP or MCP_Geometric? Because I want to allow my agent to enter the subway only by going through a subway station.
My solution so far is to use MCP_flexible and overload the 'travel_cost' method.
 # Piece of code (2)
# First, I write a offset that constraints moves in the third dimension (I want diagonal moves if #the agent is walking on the roads network or on the subway network, but not when he is #moving across those networks)
offsets = [np.array([1, 0, 0]), np.array([ 0, 1, 1]), np.array([ 0, 1, 0]), np.array([ 0, 1, 1]), np.array([ 0, 0, 1]), np.array([0, 0, 1]), np.array([ 0, 1, 1]), np.array([0, 1, 0]), np.array([0, 1, 1]), np.array([1, 0, 0])]
# Second, I create my own class, overloading the 'travel_cost' method:
@cython.boundscheck(True) @cython.wraparound(True) class MCP_subway(skimg.MCP_Flexible):
def travel_cost(self, old_cost, new_cost, offset_length):
""" travel_cost(old_cost, new_cost, offset_length) This method calculates the travel cost for going from the current node to the next.
In this method, if an agent tries to go from road to subway or from subway to road without going through a subway station he gets a infinity cost.
""" if (new_cost == 1 and old_cost not in [1,2]) or (old_cost == 1 and new_cost not in [1,2]): return np.inf else: return new_cost
# End of piece of code (2)

So far it gave me the correct answer, but I want to use it with bigger problems. So my questions are:
(1) Am I doing it right? I do not know Cython very well, so I overloaded the 'travel_cost' method with a method in pure python.
(2) Does anyone have a better idea to solve this problem? Reading suggestions?
Thank you very much,
Best regards,
Rafael
Hi Rafael,
Using inf costs to constrain the path makes sense to me, and it looks like you're using MCP_flexible in the intended way. I think that you can make the whole subclass pure Python (though my knowledge of Cython is rusty, so I might miss something), and only actually use Cython when performance demands it.
 Almar
On Thu, Feb 28, 2019, at 19:37, Rafael Carlquist Rabelo de Araujo wrote:
Hello everyone,
I was hoping to get some advice on dealing with the MCP_flexible class. Sorry if the email is too big, I tried to be as clear as possible.
I will use an example that I think will help me explaining the problem. I have a road network and a subway network in a raster format and I want to calculate least cost paths on them. To simplify it, consider this small example:
# Piece of code (1)
# (1) Roads network:
roads = np.array([[2,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10], [10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10], [10,5,10,10,10],[10,5,10,10,10],[10,5,10,10,10],[10,5,5,5,2]])
#The idea here is that 5 denotes a road, 10 denotes a place where you can walk and 2 denotes #a subway station.
# (2) Subway network:
subway = np.array([[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1], [1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1], [1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]])
# here the value 1 denotes a piece of the subway and the value 1 denotes a cell you cannot reach.
# So, my whole network is given by:
network = np.array([roads,subway])
# End of piece of code (1)
This I my input, and what I want to do is to calculate least cost path between the point (0,0,1) and (0,11,4).
Why can't I use MCP or MCP_Geometric? Because I want to allow my agent to enter the subway only by going through a subway station.
My solution so far is to use MCP_flexible and overload the 'travel_cost' method.
# Piece of code (2)
# First, I write a offset that constraints moves in the third dimension (I want diagonal moves if #the agent is walking on the roads network or on the subway network, but not when he is #moving across those networks)
offsets = [np.array([1, 0, 0]), np.array([ 0, 1, 1]), np.array([ 0, 1, 0]), np.array([ 0, 1, 1]), np.array([ 0, 0, 1]), np.array([0, 0, 1]), np.array([ 0, 1, 1]), np.array([0, 1, 0]), np.array([0, 1, 1]), np.array([1, 0, 0])]
# Second, I create my own class, overloading the 'travel_cost' method:
@cython.boundscheck(True) @cython.wraparound(True) class MCP_subway(skimg.MCP_Flexible):
def travel_cost(self, old_cost, new_cost, offset_length):
""" travel_cost(old_cost, new_cost, offset_length) This method calculates the travel cost for going from the current node to the next.
In this method, if an agent tries to go from road to subway or from subway to road without going through a subway station he gets a infinity cost.
""" if (new_cost == 1 and old_cost not in [1,2]) or (old_cost == 1 and new_cost not in [1,2]): return np.inf else: return new_cost
# End of piece of code (2)
So far it gave me the correct answer, but I want to use it with bigger problems. So my questions are:
(1) Am I doing it right? I do not know Cython very well, so I overloaded the 'travel_cost' method with a method in pure python.
(2) Does anyone have a better idea to solve this problem? Reading suggestions?
Thank you very much,
Best regards,
Rafael _______________________________________________ scikitimage mailing list  scikitimage@python.org To unsubscribe send an email to scikitimageleave@python.org
Hello Almar,
Thank you for taking the time to see my question. I tried it in a raster with 4+ millions cells and it worked fast enough for my purposes.
Best regards,
Rafael
participants (2)

Almar Klein

Rafael Carlquist Rabelo de Araujo