Adding pointers to a tree

[DemonGal711]

Alright, I had to design an N-ary tree so later I could use it to produce a word ladder. I got the tree to insert and print perfectly. Now what I need to do is add pointers so that everything points to the correct item.

Here's the example: Connect cat to dog
This is my test dictionary:
cat hat bat bag bog bot eat fat fan mad mat cot dog cog

So, I sorted it in respect to cat to avoid any issues, and then got everything inserted into the tree. So, at the moment, this is what I have. Image Here

What I need is every word to point to other words that are one letter off, like this (I apologize for how cramped it is). Second Image

So, I figure I need a new function that connects them all in such a way, which basically means I just need to pick a node, and compare it to all the other nodes in the tree.

Is there any short cut I could take? Like, if the difference hits a large number that it's unlikely that they will get close after that.

And, how do I avoid making sure that I don't add a pointer that already points to something. Like, bog points to dog already. How do I avoid bog adding another point to dog already?

[VernonDozier]

I did this project once, but I used a 2 x 2 grid rather than a tree.

0 cat
1 bat
2 cot
3 cog
4 dog

etc.

I'm not sure how you would do it with a tree, but I assigned each word an index. For each pair, I kept track of the number of hops and the "first hop" using a struct. -1 means that the two words can't be bridged. You start by going through and initializing everything to -1, -1. (First number is the number of hops, next number is the "first hop" index.

0        1         2         3         4
0 (-1,-1)  (-1,-1),  (-1, -1), (-1, -1), (-1, -1)
1 (-1,-1)  (-1, -1),  (-1, -1), (-1, -1), (-1, -1)
2 (-1,-1)  (-1, -1),  (-1, -1), (-1, -1), (-1, -1)
3 (-1,-1)  (-1, -1),  (-1, -1), (-1, -1), (-1, -1)
4 (-1,-1)  (-1, -1),  (-1, -1), (-1, -1), (-1, -1)

Trivial words are the ones on the diagonal (they're already there).

0        1         2         3         4
0 ( 0, 0)  (-1,-1),  (-1,-1), (-1,-1), (-1,-1)
1 (-1,-1)  ( 0, 0),  (-1,-1), (-1,-1), (-1,-1)
2 (-1,-1)  (-1,-1),  ( 0, 0), (-1,-1), (-1,-1)
3 (-1,-1)  (-1,-1),  (-1,-1), ( 0, 0), (-1,-1)
4 (-1,-1)  (-1,-1),  (-1,-1), (-1,-1), ( 0, 0)

Next do the ones that are one hop apart (like "cot" and "cog" - indexes 2 and 3) and ("cog" and "dog" - indexes 3 and 4).

0        1         2         3         4
0 ( 0, 0)  (-1,-1),  (-1,-1), (-1,-1), (-1,-1)
1 (-1,-1)  ( 0, 0),  (-1,-1), (-1,-1), (-1,-1)
2 (-1,-1)  (-1,-1),  ( 0, 0), ( 1, 3), (-1,-1)
3 (-1,-1)  (-1,-1),  ( 1, 2), ( 0, 0), ( 1, 4)
4 (-1,-1)  (-1,-1),  (-1,-1), ( 1, 3), ( 0, 0)

Do it for the rest of the single hops too. First number is the number of hops, second number is the "first hop". Once you have those single hops all filled in (they aren't all filled in above), you can connect 2 to 4 in the next iteration by looking down row 2 to find the single hops and seeing (1,3). Now look down row 3 and you see (1,4). That means that 2 can connect to 4 through 3. the number of hops from 2 to 4 is at most the number of hops from 2 to 3 (1) plus the number of hops from 3 to 4 (1). 1 + 1 = 2, so you can fill in that cell with (2,3). Two hops, first hop is 3.

0        1         2         3         4
0 ( 0, 0)  (-1,-1),  (-1,-1), (-1,-1), (-1,-1)
1 (-1,-1)  ( 0, 0),  (-1,-1), (-1,-1), (-1,-1)
2 (-1,-1)  (-1,-1),  ( 0, 0), ( 1, 3), ( 2, 3)
3 (-1,-1)  (-1,-1),  ( 1, 2), ( 0, 0), ( 1, 4)
4 (-1,-1)  (-1,-1),  (-1,-1), ( 1, 3), ( 0, 0)

Red cell is derived from the two green cells.

Anyway that's how I did it. I don't know how you'd do it with a tree.

[DemonGal711]

Yeah, I figured something like that would be easier, but my teacher is making us use an N-ary tree, so that's what I'm trying to work with.

I did get the tree set up, now I'm just trying to make sure I add the pointers correctly. Do you think I should make two functions? Like have one find the words that are one letter away from the original, and then another that checks to make sure a word isn't already pointed to?

[VernonDozier]

Yeah, I figured something like that would be easier, but my teacher is making us use an N-ary tree, so that's what I'm trying to work with.

I did get the tree set up, now I'm just trying to make sure I add the pointers correctly. Do you think I should make two functions? Like have one find the words that are one letter away from the original, and then another that checks to make sure a word isn't already pointed to?

Well, if you don't care about efficiency and all you have to do is get from a word to another word and it doesn't have to be a direct route, have "cat" (or any other word) be the root node. Children of "cat" are any words where you only swap one letter to get the word. That would include "fat" and "hat". They would be connected to "cat", but not each other. Connecting "hat" to fat" takes two hops instead of one since you now go through "cat" instead of going directly. If that's acceptable, it simplifies your tree considerably. Children of "fat" are words like "far", but not words like "hat". Your tree is considerably simpler and now has no cycles. Insert a node as a word's child if and only if:

1) It's not in the tree already.
2) You can swap a letter and make a word.

In other words, each child has one and only one parent, like a normal tree. It will make the tree much more manageable.

All this hinges on the assumption that you just need to be able to get from one word to another and it's OK if it takes more than the minimum number of hops.

[DemonGal711]

I'm not sure if I can do that. It's an algorithm class and I think he would frown on that since the dictionary he's going to give is some 58,000 words long and if I need to jump a lot it would take a lot of time.

What I'm hoping to do is save some time by putting two pointers in at a time. Like when hat finds that fat is one letter apart, they both get a pointer that points to the other. But, yeah, I'm still hoping it doesn't cause issues.

One thing that does help eliminate the cycles is that we needed the shortest lexicographical chain. So for my dictionary, it would be cat, cot, cog, dog, where as now it goes through bat. Regardless though, keeping it the shortest should help avoid it from looping too many times.