Help with an algorithm wanted
Russell E. Owen
rowen at cesmail.net
Fri Jun 28 12:35:05 EDT 2002
>So effectively you have a conversion graph, where each vertex
>represents a known representation, and each edge represents a
>conversion (presumably with a conversion function as an annotation to
>the edge).
>
>What you are asking for appears to be an algorthm to find the shortest
>path between to representations in the graph. Fortunately for you,
>Dijkstra provided a solution to this problem a number of years ago,
>and implementing it is a standard algorthms assignment (I do hope
>you're not asking for help with a homework assignment?).
>
>You'll find an implementation in the Python Cookbook @
>http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466
>
>The recipie was submitted by David Eppstein. It dosn't look
>optimised, but that's ok because it is legible (much more important)
>and the algorithm is efficient.
Thank you very much for the pointer. My problem is exactly one of
converting data to different representations. In my case I am dealing
with targets for a telescope that may be in FK5, ICRS, Galactic,
Apparent Geocentric, Apparent Topocentric... coordinates. It's not a
homework assignment, but is for a telescope control GUI I'm working on.
The code will be available to others, probably being served at my web
site <http://www.astro.washington.edu/owen/>. (I serve all my utility
routines there, but the internals of the user interface I consider not
of general interest, so I only send that by request. I suspect this code
will end up in the former category, but I can't be sure until I finish
modularizing and writing it.)
Finding the shortest path isn't an issue, because the path between any
two representations will always be unique. Still, anything that can find
a shortest path can find a unique path. I'll definitely have a look at
the recipe.
The main thing I'm worried about is once I have a solution, how best to
implement on object that implements it. I'm afraid that might not make
much sense, but I hope it's clear from another posting I made with a
solution to the problem. That solution is definitely not optimised but I
hope it is legible.
Regards,
-- Russell
More information about the Python-list
mailing list