Tree matching

[hamsterman]

So I have a problem. Basically it's just pathfinding, only with trees..

I have a set of conversions from one tree to another. Using this set I want to find a path from tree A to tree B. The difference from usual pathfinding is that A is convertible to C not only when there is a defined A->C conversion in the set, but also if every child of A is convertible to the corresponding child of C.
Thus the problem is recursive.

Example: if the set = A->B, conversion [A, A] -> [B, B] is possible.

The problem is that there is a danger of infinite recursion here.

Example: if the only path from A to B is A -> [A, A] -> C -> [B, B] -> B, while searching for this path, the algorithm will check if it is possible to convert [A, A] to [B, B]. To know this, it will try to find a path from A to B again.

Is it clear what I'm trying to do? I'd appreciate some suggestions..

[ne555]

¿What does A -> [A,A] meant?

The problem is that there is a danger of infinite recursion here.

¿Isn't there a reduction of the problem when you considerer the children?

[hamsterman]

A is a tree, [A, A] is another tree which has two children, which are both copies of the tree A.
x -> y means that there is a path from x to y. In a normal pathfinding problem, you could consider x and y to be two connected vertexes of a graph. However, in this case that wouldn't work, as the number of such vertices isn't really finite.

¿Isn't there a reduction of the problem when you considerer the children?

I don't understand. What do you mean?

[hamsterman]

shameful bump

Here's a piece of code which exhibits the problem.
http://pastebin.com/X5k83qEP

[ne555]

gcc is complaining about this

std::vector<T> & operator << ( std::vector<T> & v, const U & t );
#define B std::vector< Tree * >()

B << new Leaf( "A" ); 
//error no match for 'operator<<' in 'std::vector<Tree*, std::allocator<Tree*> >()
//candidates are: std::vector<T, std::allocator<_Tp1> >& operator<< 

So you only care about the structure of the tree, and the leafs.
I remember a problem when you needed to say if a code was ambiguous, and the length of the shortest ambiguous sentence. Maybe you can use a similar approach.

edit: http://www.spoj.pl/problems/AMCODES/ now that I re-read it, dunno that that could help, sorry.

[hamsterman]

I don't understand the error. Is it because a temporary B should be only passed as cont reference?

Now that I think about it, I guess I could solve the problem simply by keeping a stack of pairs of arguments passed to path() and checking it before calling path() from short_path(). Not really elegant or efficient, but could work..

[ne555]

Is it because a temporary B should be only passed as cont reference?

... or value.

Not sure if I follow, ¿but wouldn't fail in this case?
defined A -> [A,A]
testing A -> [A,A; A,A; A,A; A,A] (all in the same level)

[hamsterman]

You're right. I didn't think about that..