Help with an algorithm wanted

[Andrae Muys]

"Russell E. Owen" <rowen at cesmail.net> wrote in message news:<rowen-3B9D8A.16590026062002 at nntp3.u.washington.edu>...
> 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.