Help with an algorithm wanted
Russell E. Owen
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?
-- Russell
Bjorn Pettersen
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')
William Park
> For instance, an object with A as the given would return D by solving
> A->C->D.
> 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).
If pairing (ie. mapping between 2 objects) occurs randomly, then it's
virtually impossible, because you don't know which direction to go from any
one object. It would be travelling from city to city, without knowing
which state or county.
--
William Park, Open Geometry Consulting, <openge...@yahoo.ca>
8-CPU Cluster, Hosting, NAS, Linux, LaTeX, python, vim, mutt, tin
Russell E. Owen
William Park <openge...@yahoo.ca> wrote:
>On Wed, Jun 26, 2002 at 01:02:02PM -0700, Russell E. Owen wrote:
>> For instance, an object with A as the given would return D by solving
>> A->C->D.
>
>> 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).
>
>If pairing (ie. mapping between 2 objects) occurs randomly, then it's
>virtually impossible, because you don't know which direction to go from any
>one object. It would be travelling from city to city, without knowing
>which state or county.
Fortunately the pairings (conversion functions) are completely fixed. So
the graph never varies, and it even has a fairly simple shape (basically
a fork with 3 tines and a long handle, if that makes any sense).
The problem is that the graph has 10 nodes. Rather than hand code 10
different objects, I'm trying to create a factory that will generate the
required object based on which node (data representation) is a given
from which the others are derived.
For example, given conversion functions CtoA(C), AtoC(A), CtoB(C),
BtoC(B), CtoD(C), DtoC(D), then I'll want to be able to create four
objects, one with A as a given, one with B, etc. The object for A as a
given should act like:
class Agiven:
def getA(self):
return self.A
def getB(self):
return CtoB(self.getC)
def getC(self):
return AtoC(self.getA)
def getD(self):
return CtoD(self.getC)
I'm not too worried about figuring out what methods to run depending on
which representation is a given. My main worry is how to generate the
desired objects programmatically in a way that is fairly understandable.
The obvious thing is probably to create a new object and
programmatically add methods to it. But I'm not sure how to do it. If
that's messy, I may have to have generate the created object by passing
it a set of functions in the init method. Bjorn Pettersen just sent me
some code that may do the trick. i have to study it. I'm not yet sure if
it creates objects or pseudo-objects.
Of course I could create a text representation of the object and eval
it, but that really sounds ugly!
-- Russell
Niklas Frykholm
> 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.
Here is one possible solution. Given a set of classes A, B, C... and
known conversion functions A.to_B, B.to_C, etc this code creates all
derived conversion functions (such as A.to_C). It thus solves the problem
statically. (In some cases a dynamic solution is preferrable.)
def add_conversion(fromm, via, to):
"Add conversion from class fromm to class to, via class via."
def convert(self):
via_object = getattr(self, "to_" + via)()
return getattr(via_object, "to_" + to)()
setattr(globals()[fromm], "to_" + to, convert)
def has_conversion(fromm, to):
"Is there a conversion function from class fromm to class to?"
return hasattr(globals()[fromm], "to_" + to)
def conversions(klass):
"Returns all the conversion functions of klass."
l = filter(lambda s: s.startswith('to_'), dir(globals()[klass]))
return map(lambda s: s[3:len(s)], l)
def create_quick_conversions(classes):
"Create all possible derived conversions for the set of classes."
for via in classes:
tos = conversions(via)
for fromm in classes:
if fromm != via and has_conversion(fromm, via):
for to in tos:
if not has_conversion(fromm, to):
add_conversion(fromm, via, to)
# end of for
create_quick_conversions(["A", "B", "C", "D"])
// Niklas
William Park
> In article <mailman.102512565...@python.org>, William Park
> <openge...@yahoo.ca> wrote:
>>If pairing (ie. mapping between 2 objects) occurs randomly, then it's
>>virtually impossible, because you don't know which direction to go from any
>>one object. It would be travelling from city to city, without knowing
>>which state or county.
>
> Fortunately the pairings (conversion functions) are completely fixed. So
> the graph never varies, and it even has a fairly simple shape (basically
> a fork with 3 tines and a long handle, if that makes any sense).
>
> The problem is that the graph has 10 nodes. Rather than hand code 10
> different objects, I'm trying to create a factory that will generate the
> required object based on which node (data representation) is a given
> from which the others are derived.
In your previous example, C is the central "hub" for A, B, and D. If you
have
hub = {'A': 'C', 'B': 'C', 'D': 'C'}
then, you can find the node to which A, B, and D are attached, ie.
>>> hub['D']
'C'
Can you organize other objects around hubs? After that, organize the hubs
into central hub of their own? If so, then the traversal will be much
easier.
It's difficult to get our teeth into without knowing what the big picture
looks like... :-)
Russell E. Owen
"Russell E. Owen" <ro...@cesmail.net> wrote a long complicated message
about a generating what is basically a data converter object.
I really appreciate everybody's help on this. I apologize for not making
the problem clearer in the first place.
I offer my solution below with enough comments to, I hope, make the
problem clearar. Any critique would be appreciated.
"""Sample object that converts between different data
representations A-D, starting from a given value in one representation.
In reality there will be more representations and the conversion code
will be complicated (though much of it may reside in an external
library of subroutines). But the graph of data representations
connected by conversion functions will always be a constant
and will always be very simple (one hub with lines of varying
numbers of nodes radiating from it).
Figuring out which order to do the conversions (as a function of
what is a given) is solved with a rather simplistic algorithm
that tests too many cases but is short and easy to read.
Thanks to Bjorn Pettersen for his help (but the crudeness is mine).
The main thing I am worried about is: given the order in which to do
the conversions, how best to create an object that implements it.
The solution shown here works, but I suspect there's a better way.
It feels as if I'm creating some sort of meta-object
(by using a function dictionary) instead of making best use
of the existing optimized object mechanism.
"""
class CnvObj (object):
def __init__(self, givenValue, whatGiven):
assert whatGiven in ("A", "B", "C", "D")
self.givenValue = givenValue
self.funcDict = {whatGiven: self.getGiven}
self.addFunctions(whatGiven)
def addFunctions(self, fromWhat):
for toWhat in ("A", "B", "C", "D"):
if not self.funcDict.has_key(toWhat):
funcName = "%sfrom%s" % (toWhat, fromWhat)
if hasattr(self, funcName):
self.funcDict[toWhat] = getattr(self, funcName)
self.addFunctions(toWhat)
def getItem(self, item):
return self.funcDict[item]()
def BfromC(self):
return "BfromC(%s)" % self.getItem("C")
def CfromA(self):
return "CfromA(%s)" % self.getItem("A")
def DfromC(self):
return "DfromC(%s)" % self.getItem("C")
def getGiven(self):
return self.givenValue
#...etc. only the functions needed for "A given" are shown
co = CnvObj("value for A", "A")
for rep in ("A", "B", "C", "D"):
print co.getItem(rep)
"""this prints out:
value for A
BfromC(CfromA(value for A))
CfromA(value for A)
DfromC(CfromA(value for A))
"""
Andrae Muys
> 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
Andrae Muys
>
> 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
Andrae Muys
>
> 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
Russell E. Owen
>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
Andrae Muys
> The problem is that the graph has 10 nodes. Rather than hand code 10
> different objects, I'm trying to create a factory that will generate the
> required object based on which node (data representation) is a given
> from which the others are derived.
>
Indeed a factory sounds like the way to go. Personally I would stick
with the adjacency graph, and generate the the required compound
functions at runtime per-request. Python's good at that sort of
thing, in fact here's one I prepared earlier.... (uses shortest path
impl from recipies I posted before).
#!/usr/bin/python
import shortest_path as spath
# Shortest path requires addition, and I require annotating with a
callable.
# Obvious solution, create an addable callable ;)
class Edge(object):
def __init__(self, func):
self._func = func
def __add__(self, other):
return 1 + other
def __radd__(self, other):
return 1 + other
def __call__(self, *args):
return self._func(*args)
class ConverterFactory(object):
def __init__(self, graph):
self._graph = graph
def getConverter(self, fromNode, toNode=None):
def closure(value, toNode=toNode):
def convert(value, func):
return func(value)
return reduce(convert, self.shortestPath(fromNode,
toNode), value)
return closure
def shortestPath(self, fromNode, toNode):
if (toNode == None):
raise RuntimeException, "Final Representation required"
vpath = spath.shortestPath(self._graph, fromNode, toNode)
epath = []
for i in range(len(vpath) - 1):
epath.append(G[vpath[i]][vpath[i+1]])
return epath
if (__name__=='__main__'):
AB = Edge(lambda x: x + ' AB')
AE = Edge(lambda x: x + ' AE')
BA = Edge(lambda x: x + ' BA')
CB = Edge(lambda x: x + ' CB')
CD = Edge(lambda x: x + ' CD')
CE = Edge(lambda x: x + ' CE')
DE = Edge(lambda x: x + ' DE')
EA = Edge(lambda x: x + ' EA')
EC = Edge(lambda x: x + ' EC')
ED = Edge(lambda x: x + ' ED')
G = { 'A' : { 'B' : AB, 'E' : AE },
'B' : { 'A' : BA },
'C' : { 'B' : CB, 'D' : CD, 'E' : CE },
'D' : { 'E' : DE },
'E' : { 'A' : EA, 'C' : EC, 'D' : ED },
}
factory = ConverterFactory(G)
BDconverter = factory.getConverter('B', 'D')
Bconverter = factory.getConverter('B')
print BDconverter("BString to Dform:")
print BDconverter("Another BString to Dform:")
print Bconverter("B->D:", 'D')
print Bconverter("B->C:", 'C')
print Bconverter("B->B:", 'B')
print factory.getConverter('D', 'C')("D->C:")
print factory.getConverter('C', 'D')("C->D:")
And of course when run generates:
$ ./converter.py
BString to Dform: BA AE ED
Another BString to Dform: BA AE ED
B->D: BA AE ED
B->C: BA AE EC
B->B:
D->C: DE EC
C->D: CD
Now the key to understanding the above code is getConverter, so here
it is again.
def getConverter(self, fromNode, toNode=None):
def closure(value, toNode=toNode):
def convert(value, func):
return func(value)
return reduce(convert, self.shortestPath(fromNode,
toNode), value)
return closure
This method creates/returns a closure that will perform the requested
conversion. A closure is a function that remembers what variables it
was able to see when it was created, so can use them when it gets
executed.
In this case the converter-closure remembers which object created it
(via self), where it's coming from (via fromNode), and where it's
going to (via toNode). This means that when you call it, to perform a
conversion, it knows which object can calculate the required path for
it, and which path it's looking for.
Now as the path is a list of function-like objects that represent
conversions; and reduce is a function that runs through a list
accumulating it's contents (according to a provided 'accumulation
function'); And ultimately what we would really like to accumulate
the conversions; The converted value we're looking for is really just
the accumulated conversions on an initial value....
...how convenient :).
reduce(convert, self.shortestPath(fromNode, toNode), value)
'convert' is just a helper function that knows how to apply a
conversion to a value and returns the result.
I recommend if you plan to use this that you add some convenience
methods to ConverterFactory to allow you to manipulate the graph.
For flexibility's sake the code currently recalculates the
shortest-path each time you do a conversion, so if you are doing alot
of conversions you may find profiling identifies this as a problem
(remember... it isn't a problem until profiling says it is!). In this
case you may want to move the path calculation outside the closure so
you only do it once per getConverter() call.
Andrae Muys
P.S. I think this might demonstrate one occasion where lambda is
superior to the equivelent nested-function. The test-code would have
been far less readable if each of the ten 'conversion functions' had
been defined independently prior to use. I will note however that
while 'convert' could have been defined lambda v,f:f(v); I personally
find the nested-function much easier to read.