Shortest Path algorithm
Hi all, Please review the Shortest Path functionality implemented in branch 'spath' of http://github.com/stefanv/scikits.image Thanks Stéfan
Hi Stefan, 2009/11/2 Stéfan van der Walt <stefan@sun.ac.za>
Hi all,
Please review the Shortest Path functionality implemented in branch 'spath' of
Looks good, both the shortest path algorithm and the Cython build improvements. About the build first, I had to run the setup.py in analysis separately, it wasn't picked up by the main setup.py. I do not have Cython installed. Some questions / points to think about for shortest path: - why only left-to-right through the image? it would be easy to have an axis keyword and then transpose the image if necessary. - module name. "analysis" is quite generic, if that is where most algorithms end up it will be a very large module after a while. maybe that is okay, i'm not sure. - docstring is rather incomplete: needs Returns, References, Examples, Notes: synonym=Dijkstra's algorithm - for the test, why is path [0, 0, 1] instead of either [1, 0 ,1] or [0, 1, 0]? I would expect path to contain either indices or values of the followed path. - and some questions motivated by my lack of knowledge of Cython: * can you write r_bracket_min = max(r - 1, 0) and leave out the if < 0 check afterward? * what is the overhead (if any) of a triple for loop in Cython? I don't see an obvious way to vectorize things, but if it's possible (even partially), would that help? Cheers, Ralf
Hi Ralf 2009/11/3 Ralf Gommers <ralf.gommers@googlemail.com>:
About the build first, I had to run the setup.py in analysis separately, it wasn't picked up by the main setup.py. I do not have Cython installed.
I think I fixed that this morning, please confirm.
- why only left-to-right through the image? it would be easy to have an axis keyword and then transpose the image if necessary.
I guess you can manipulate the data any way you like before sending it in. This is just the way most algorithms, such as Viterbi, are defined.
- module name. "analysis" is quite generic, if that is where most algorithms end up it will be a very large module after a while. maybe that is okay, i'm not sure.
I'd be glad for some suggestions on a different name -- I wasn't quite sure myself.
- docstring is rather incomplete: needs Returns, References, Examples, Notes: synonym=Dijkstra's algorithm
I added some of that last night, but it could do with a lot more, you're right!
- for the test, why is path [0, 0, 1] instead of either [1, 0 ,1] or [0, 1, 0]? I would expect path to contain either indices or values of the followed path.
It contains the row coordinate for each column. Using that information, constructing the values along that path would be easy: x[path, :] -> values If there are many equivalent paths, the first is picked.
* can you write r_bracket_min = max(r - 1, 0) and leave out the if < 0 check afterward?
You could, but then you'd need to define max, otherwise a Python call is made.
* what is the overhead (if any) of a triple for loop in Cython? I don't see an obvious way to vectorize things, but if it's possible (even partially), would that help?
I don't think there's any advantage in this case -- we're working at the C level, so vectorising has very little chance on making things faster (unless you somehow manage to get better cache locality). When you vectorise, you just pass the buck to a library lower down the food chain. Regards Stéfan
2009/11/3 Stéfan van der Walt <stefan@sun.ac.za>
Hi Ralf
2009/11/3 Ralf Gommers <ralf.gommers@googlemail.com>:
About the build first, I had to run the setup.py in analysis separately, it wasn't picked up by the main setup.py. I do not have Cython installed.
I think I fixed that this morning, please confirm.
Ah yes, works now. I tested your spath branch and now see you made more improvements in master. Merging before review eh:)
- why only left-to-right through the image? it would be easy to have an axis keyword and then transpose the image if necessary.
I guess you can manipulate the data any way you like before sending it in. This is just the way most algorithms, such as Viterbi, are defined.
Sure.
- module name. "analysis" is quite generic, if that is where most algorithms end up it will be a very large module after a while. maybe that is okay, i'm not sure.
I'd be glad for some suggestions on a different name -- I wasn't quite sure myself.
"graph" maybe? or "tree"?
- for the test, why is path [0, 0, 1] instead of either [1, 0 ,1] or [0, 1, 0]? I would expect path to contain either indices or values of the followed path.
It contains the row coordinate for each column. Using that information, constructing the values along that path would be easy:
x[path, :] -> values
If there are many equivalent paths, the first is picked.
Ah yes, the docstring I looked at was incomplete so I was confused about the definition of cost. Makes perfect sense now. Cheers, Ralf
participants (2)
-
Ralf Gommers -
Stéfan van der Walt