Binary Tree Tour

[qube99]

I am trying to write a script that will tour a binary tree.

 

Each node in the tree has 2 children, Left and Right, a classic binary tree.

 

I wish to visit every node in the tree. I wish to tour the tree in a breadth first manner. I'd like to tour all level 2 nodes, then all level 3 nodes, etc.

 

I'm having a hard time getting my head around how to approach this script. It looks to me like it will involve recursion. Can anyone share their ideas on binary tree scripting?

[comment]

In Filemaker terms, this is a non-question. There are no "nodes", "trees" or "visits" in Filemaker (or, I think, in a relational database in general).

 

The closest thing I can think of is a recursive self-join relationship. In such arrangement you can use GTRR from the root record to its children in order to establish a found set of the two first-generation children. Then use GTRR (match found set) to get to the four grandchildren, and so on. However, GTRR (match found set) gets slower as the found set grows, so I am not sure how practical such a procedure might be.

[qube99]

Nice idea.

 

I'm working on something that will visit each node once. I went ahead and started coding a brute force method and discovered why this one is so hard. The root has 4 children, and they each have 4 children, but at the next level they have either 3 or 4 children depending on a conditional. To make it even worse the 3 children nodes come in 3 varieties.

 

I have a feeling it's going to end up a candidate for Guiness as Most Incomprehensible Script. I'm already spending a lot of time renaming variables and subscripts, and writing lots of comments, even writing an outline document, and I'm only at 3 levels deep. I'm hoping to eventually derive an algorithm for this type of data tree that will go to any depth with a subroutine that will tell it when to stop.

 

What I'm actually doing is creating tables of all the unique states for intersecting ring puzzles. I want to chart n rings of n size of n colors. With a 2 ring design one can move ring A or B, left or right, for 4 children. A move is a commutator that changes all the values in 1 ring. When a ring is rotated to half of it's size, any additional rotation would better be done by a smaller anti-rotation and this is where the 3 children nodes come into play.

 

As each node is visited I write the state into a field as a string of letters. This allows for detection of duplicate states. I also record the move sequence that generated each state so that I know how far away from root each state is. The end product is a list with 1 record for each unique state.

 

[comment]

Well, I can't pretend I understand what this is about. Let me suggest, however, that a child can use the value of its parent directly through the relationship - so an actual "visit" (whatever that means in Filemaker terms) should not be necessary. OTOH, you need to be careful of cascading chains of unstored calculations - that's where controlled relookups might come in handy.

[qube99]

I'm don't think we're talking about the same thing. Here's a link to an unlocked FMPA12 file so you can see what's up.

 

https://dl.dropboxusercontent.com/u/16660951/Enumerator%200.02.fmp12

 

What I'm doing is trying to use a binary tree tour to create the data. I've gotten the first 3 levels done by brute force but now I need to start looping. I think I will need a function that calls itself recursively, and I think that means a custom function. I have no idea how many levels the trees will have, some could have hundreds of levels, so nested loops are out. The scripting challenge is the fact that the tree must be traveled horizontally in order to generate the loop termination test.

 

I'll see if I have any unstored calculations. I'm trying to use variables in subscripts, plus some global variables that get rewritten within each loop.

 

I've never done a recursive function in FileMaker Pro before. I've also never done a binary tree tour and am finding some of the variables and loop conditionals quite daunting.

[qube99]

I have some thoughts on this script.

 

I need to know when to increment the level value in a recursive script. I believe I can use a node count. When the node count reaches (R^3 * 3^(L-2))+5 that's the end of a level. R = number of rings and L = level.

 

Next I need to know when to create a new record. I can test the node count to see if I'm at the next node and call the subscript and then check to see if the state value is a duplicate or not. Even if the state is a duplicate and no record is created, node count will be incremented.

 

When generating children I need to know who the parent is in order to eliminate making a move followed by an anti-move. I'm not sure how this can be implemented in a recursive script. For now I may allow this and have the duplicate function eliminate them from the data. But I need to figure it out. When I leave them in the 3's in above changes to 4's.

 

Then I need to know when I'm done. At the start of each level I will set a flag to 0. If any new states are found the flag is changed to 1. At the end of a level I exit script if this flag is at 0 (no new states found).

 

At some point I may need to address efficiency. Some of the problems I'll run will generate millions of records and may require hundreds of millions of script steps. Jobs like this can show up any memory leaks. The maximum size of a given problem here is P! where P is the number of pieces and all are unique.  I have a problem with 36! nodes I want to run. What will FMP do when confronted with such a job?

 

For now I'll code what I can and deal with the parent identity problem later.

[bruceR]

As I'm sure Lee will remind you, you need to post your file as an attachment here, not as a link to some unknown external source.

[Lee Smith]

 

Besides the unknown site, we want to ensure that it will be available for future reference, and if for some reason you removed it, then future readers will not have access to it.

 

TIA for you cooperation. 

 

Lee

 

p.s.

 

If you need assistance in how to attach a file, just follow the steps here.

Edited December 2, 2013 by Lee Smith
add the p.s.

[qube99]

Thanks for the tips. That file was in Dropbox website. It's just a temp file.

 

I started off looking at my data structure as a binary tree with no knowledge how to code one. After seeing this illustration at Wolfram the solution came to me. First I realized that my data structure was actually a ternary tree, exactly like this:

 

 

Looking at this I realized that I could construct one with FMP without using recursion. Here's how.

 

The nodes are numbered sequentially. So all I had to do was use a node counter. Go to node 1 (which is record 1 in FMP speak) and spawn 3 children with a script. Increment the node counter by 1 and go to node 2 and run the 3 child spawn script again. Each child becomes a node for more 3 child spawns, and this could go on forever. So I used a loop to keep going until the termination conditions are met.

 

In my case most nodes are duplicates and these were not written to the data (using a conditional) and therefore did not become parents for spawning vast numbers of triplicate children. If I were to graph my ternary tree it would be pretty ragged looking with lots of terminal nodes called "leaves". Every record is connected back to the root through its parents, grandparents, etc and this graph shows exactly those relationships.

 

My next challenge is efficiency and speed. My first full calculation with this will have a bit ovber 40,000 nodes and that's the smakllest problem. Some larger problems I want to run will have many millions of nodes. I think I have a handle on memory bt I'll look for ways to cache the data to reduce disk I/O. I also have a scripted search in each loop that coulkd be a real time killer. Might be a few places where I can reduce redundant script calls.

 

Now for some practice attaching a file.

Enumerator 0.03.zip