Help with an algorithm wanted
Bjorn Pettersen
BPettersen at NAREX.com
Wed Jun 26 17:13:32 EDT 2002
> From: Russell E. Owen [mailto:rowen at cesmail.net]
>
> 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.
>
> I am pretty sure recursion is the heart of the solution. An
> object with
> A as the given could have a method getD that returned D<-C
> and a method
> getC that returned C<-A.
>
> The real issue is creating such objects without hand coding each one
> (since in the real world I have more representations and the
> number of
> casese proliferates badly).
>
> I suspect I should use recursion to create the object, too, but it
> sounds like it'll need a lot of introspection. For instance
> to create an
> object with A as the given, one might:
> - start by defining method getA to return A
> - look through the set of conversion functions that output A;
> the only
> one is A<-C, so method getC returns C<-A.
> - repeat with all methods that return C and don't have
> methods already
> defined; this gives method getB returns B<-C and method getD returns
> D<-C.
>
> Alternatively, I can imagine making each object basically identical
> except for some kind of meta-data that tells each method
> which data item
> to query; the appropriate function can then be looked up as
> needed (e.g.
> via a dictionary that takes as a key the output and input
> representation). This would slow down the methods but avoid the
> introspection.
>
> Any suggestions?
Here's some lightly tested code to get you started. It does a depth
first search of the graph. Detecting cycles in the graph, and populating
the mapping is left as an exercise to the reader <wink>
-- bjorn
def fromAtoB(): pass
def fromAtoC(): pass
def fromCtoD(): pass
mapping = {
'A' : [('B', fromAtoB), ('C', fromAtoC)],
'C' : [('D', fromCtoD)]
}
def findShortestPath(mapping, source, dest):
bestPath = [[]] # ref list
def _findSP(source, dest, res):
try:
next = mapping[source]
except KeyError:
return # dead end
for item in next:
if item[0] == dest:
res += [item[1]]
if bestPath[0] == [] or len(res) <
len(bestPath[0]):
bestPath[0] = res
else:
_findSP(item[0], dest, res + [item[1]])
_findSP(source, dest, [])
return bestPath[0]
print findShortestPath(mapping, 'A', 'D')
More information about the Python-list
mailing list