Help with an algorithm wanted

[Andrae Muys]

"Russell E. Owen" <rowen at cesmail.net> wrote in message news:<rowen-CE3C0F.13020226062002 at nntp1.u.washington.edu>...
> I'd like some help solving a problem in Python.
> 
> The basic idea is I have an item of data that can be represented in any 
> of four ways: A,B,C and D. I also have conversion functions between 
> certain pairs of representations, such that there's always a path 
> between any two data representations. In this case suppose I know A<->C, 
> B<->C and C<->D, or graphically:
> 
> A <--+
>      +--> C <---> D
> B <--+
> 
> I'd like to create objects that have one of these items (A,B,C,D) as a 
> given, then be able to query any such object for any data representation.
> 
> For instance, an object with A as the given would return D by solving 
> A->C->D.
> 
> What I'm trying to figure out is a simple and reasonably elegant way to 
> code such objects.
> 

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.

Of signifigant interest to you is that it represents the graph as a
dictionary of edges, and as you will want to annotate the edges with
conversion functions, this is a good thing.

Also note that Dijkstra's algorthm uses weighted edges, so you get to
consider differing conversion costs for free.

Andrae Muys