C++

Forum

 
word adjacency list

clarkkent (57)
Given two words of the same length I want to create a table that displays a word's neighbors that are have a one letter difference with it. For example...

kind - mind, king...
mind - mine, mend...
...
for each word that is found to be adjacent to another word then the words adjacent to it should be displayed as well

The problem I am having is that I am able to get the adjacent words of the first word and those of the words adjacent to it but that is as far I am able to go

Hope I was able to express what my problem is

here is the code I have
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 

#include <iostream>
#include <fstream>
#include <cassert>
#include <string> 
#include <cstdlib>
#include <ctime>
#include <vector>
#include<map>
#include "hash.h"
#include "queueType.h"
#include "arrayBasedListType.h"

using namespace std;



struct node
{
	string word;
	int distance;
	string predecesor;

	node(string word1, string pre)
	{
		word = word1;
		distance = 1; 
		predecesor = pre;
	}

	string getWord()
	{
		return word; 
	}
	string getPredecesor()
	{
		return predecesor;
	}
};

vector<string> exchange(string&, hashTableType<string, strHashFunctor>&ht, vector<node*>&, vector<vector<node*>>&);

int main()
{
	int S = 100000;
	hashTableType<string, strHashFunctor> ht(S);
	vector<node*> wordlist; 
	vector<vector<node*>> vectorOfVectors;
	ifstream infile;
	infile.open("dictionary.txt");
	string temp;

	//scan the file and add contents to the hash table 
	while (!infile.eof())
	{
		infile >> temp;
		ht.insert(temp);

	}
	//print the dictionary
	//for (int i = 0; i<S; i++)//print the dictioanry
	//{
	//	cout << " i = " << i << endl;
	//	ht.print(i);
	//	cout << endl; 
	//}

	ifstream inFile;
	string first, second;
	char choice = 'y';
	vector<string> listOfWords;
	while (choice != 'n'&&choice != 'N')
	{
		cout << "Enter first word " << endl;
		cin >> first;
		cout << "Enter second word " << endl;
		cin >> second;

		listOfWords = exchange(first, ht,wordlist, vectorOfVectors);
		for (int i = 0; i < listOfWords.size(); i++)
		{
			exchange(listOfWords[i], ht, wordlist,vectorOfVectors);
		}

	
		for (int i = 0; i < vectorOfVectors.size(); i++)
		{
			for (int j = 0; j < vectorOfVectors[i].size(); j++)
			{
				cout << vectorOfVectors[i][j]->word << "  ";
			}
			cout << endl<<".................."<<endl;
		}
	
		cout << "Do you want to try again? (y/n): ";
		cin >> choice;

	}


	return 0;
}

vector<string> exchange(string & word, hashTableType<string, strHashFunctor>&ht, vector<node*>&wordlist, vector<vector<node*>>& vectorOfVectors)
{
	wordlist.clear();

	string word1;
	vector<string> words;
	node *root = new node(word, word);
	wordlist.push_back(root);
	for (int i = 0; i < word.size(); i++)//loop for every letter of the word
	{
		word1 = word;
		for (char letter = 'a'; letter <= 'z'; ++letter)//loop for every letter of the alphabet
		{
			word1[i] = letter;

			if (ht.search(word1) && word1 != word)
			{
				//cout << word1 << endl;
				node *root = new node(word1, word);
				wordlist.push_back(root);
				words.push_back(word1);
			}

		}

	}

	vectorOfVectors.push_back(wordlist);
	return words; 

}
Last edited on
clarkkent (57)
Actually, its an adjacency list but I could not update the tile

updated
Last edited on
clarkkent (57)
Does anybody have any idea what I'm doing wrong?
dhayden (5798)
If I'm reading your code right, line 79 creates a list of everything adjacent to word. Then lines 80-83 adds to it a list of everything adjacent to those words . That's fine, but what about the words adjacent to those words?

Here's a function that should print what you want. Note that this is off the top of my head so it might not even compile, but it should show you how to do it. The idea is to keep a collection of words printed/to print. Each time you find a word that isn't in the collection, add it to the end.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
void printAdjacency(const string &word)
{
    vector<string> wordsToPrint;
    wordsToPrint.push_back(word);  // start with this one word to print

    for (size_t i = 0; i < wordsToPrint.size(); ++i) {
        string &cur(wordsToPrint[i]);

        // get the adjacency list for current word.  I'm passing wordList and v because your
        // function requires them, but notice that this print algo doesn't need them at all,
        // so you should consider getting rid of them in exchange().
        vector<node*> wordList;
        vector<vector<node*> > v;
        vector<string> adjacent = exchange(cur, ht, wordList, v);

        // now do the print adjacent words. If you find one that isn't in your list of words
        // to print then add it.
        if (adjacent.size()) {
            cout << cur << " :";
            for (int j=0; j<adjacent.size(); ++j) {
                cout << ' ' << adjacent[j];

                // If the adjacent word isn't in our list or words to print,
                // then add it to the end.
                if (wordsToPrint.find(adjacent[j]) != wordsToPrint.end()) {
                    wordsToPrint.push_back(adjacent[j]);
                }
            }
             cout << '\n';
        }
    }
}


clarkkent (57)
Thanks so much for your help.

This part I dont get, there seems to be a problem with find
1
2
3
 
if (wordsToPrint.find(adjacent[j]) != wordsToPrint.end()) {
	wordsToPrint.push_back(adjacent[j]);
}

wordsToPrint is a vector and it says that it does not have a member called find
dhayden (5798)
clarkkent (57)
thanks, that fixed it

however I'm back where I started, I am able to print one adjacency line but can't make it keep on working, should I have a loop or some kind of recursion?

here is the code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
#include <iostream>
#include <fstream>
#include <cassert>
#include <string> 
#include <cstdlib>
#include <ctime>
#include <vector>
#include<map>
#include "hash.h"
#include "queueType.h"
#include "arrayBasedListType.h"

using namespace std;



struct node
{
	string word;
	int distance;
	string predecesor;

	node(string word1, string pre)
	{
		word = word1;
		distance = 1; 
		predecesor = pre;
	}

	string getWord()
	{
		return word; 
	}
	string getPredecesor()
	{
		return predecesor;
	}
};

vector<string> exchange(string&, hashTableType<string, strHashFunctor>&ht, vector<node*>&, vector<vector<node*>>&);
void printAdjacency(const string &word, hashTableType<string, strHashFunctor>&ht);

int main()
{
	int S = 100000;
	hashTableType<string, strHashFunctor> ht(S);
	vector<node*> wordlist; 
	vector<vector<node*>> vectorOfVectors;
	ifstream infile;
	infile.open("dictionary.txt");
	string temp;

	//scan the file and add contents to the hash table 
	while (!infile.eof())
	{
		infile >> temp;
		ht.insert(temp);

	}


	ifstream inFile;
	string first, second;
	char choice = 'y';
	vector<string> listOfWords;
	arrayQueueType<string> queueofWords;
	while (choice != 'n'&&choice != 'N')
	{
		cout << "Enter first word " << endl;
		cin >> first;
		cout << "Enter second word " << endl;
		cin >> second;

		printAdjacency(first, ht);//shoud I put this inside a loop?
	
		/*listOfWords = exchange(first, ht,wordlist, vectorOfVectors);
		for (int i = 0; i < listOfWords.size(); i++)
		{
			exchange(listOfWords[i], ht, wordlist,vectorOfVectors);
		}

	
		for (int i = 0; i < vectorOfVectors.size(); i++)
		{
			for (int j = 0; j < vectorOfVectors[i].size(); j++)
			{
				cout << vectorOfVectors[i][j]->word << "  ";
			}
			cout << endl<<".................."<<endl;
		}*/
	
		cout << "Do you want to try again? (y/n): ";
		cin >> choice;

	}


	return 0;
}

vector<string> exchange(string & word, hashTableType<string, strHashFunctor>&ht, vector<node*>&wordlist, vector<vector<node*>>& vectorOfVectors)
{
	wordlist.clear();

	string word1;
	vector<string> words;
	node *root = new node(word, word);
	wordlist.push_back(root);
	for (int i = 0; i < word.size(); i++)//loop for every letter of the word
	{
		word1 = word;
		for (char letter = 'a'; letter <= 'z'; ++letter)//loop for every letter of the alphabet
		{
			word1[i] = letter;

			if (ht.search(word1) && word1 != word)
			{
				//cout << word1 << endl;
				node *root = new node(word1, word);
				wordlist.push_back(root);
				words.push_back(word1);
			}

		}

	}

	vectorOfVectors.push_back(wordlist);
	return words; 

}

void printAdjacency(const string &word, hashTableType<string, strHashFunctor>&ht)
{
	vector<string> wordsToPrint;
	wordsToPrint.push_back(word);  // start with this one word to print

	for (size_t i = 0; i < wordsToPrint.size(); ++i) {
		string &cur(wordsToPrint[i]);

		// get the adjacency list for current word.  I'm passing wordList and v because your
		// function requires them, but notice that this print algo doesn't need them at all,
		// so you should consider getting rid of them in exchange().
		vector<node*> wordList;
		vector<vector<node*> > v;
		vector<string> adjacent = exchange(cur, ht, wordList, v);

		// now do the print adjacent words. If you find one that isn't in your list of words
		// to print then add it.
		if (adjacent.size()) {
			cout << cur << " :";
			for (int j = 0; j<adjacent.size(); ++j) {
				cout << ' ' << adjacent[j];

				// If the adjacent word isn't in our list or words to print,
				// then add it to the end.
				vector<string>::iterator it;
				it = find(wordsToPrint.begin(), wordsToPrint.end(), adjacent[j]);
				if (it != wordsToPrint.end()) {
					wordsToPrint.push_back(adjacent[j]);
				}
			}
			cout << '\n';

		}
	}
}


dhayden (5798)
Hmm. That should work. Look at how printAdjacency() works. wordsToPrint is the list of words whose adjacency list it should print. The list starts with one item at line 136. Then as it finds adjacent words, it adds them to the list at line 160, so it should keep printing until it has the whole adjacency graph.
clarkkent (57)
I see what I did wrong.
Changed this
1
2
3
4
 
if (it != wordsToPrint.end()) 
{
     wordsToPrint.push_back(adjacent[j]);
}

into this
1
2
3
4
5
6
7
8
 
if (it != wordsToPrint.end()) 
{
	//this is if it found the word	
}
else
{
wordsToPrint.push_back(adjacent[j]);
}


the problem is now I get an endless loop
Topic archived. No new replies allowed.