Help with an algorithm wanted

[Bjorn Pettersen]

> 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')