Difference between revisions of "CISC220 F2023 Lab9"

Latest revision as of 15:45, 10 November 2023

Lab #9

1. Word graphs

Starter code for a WordGraph class is provided here which reads in words (all the same length) from a dictionary. As detailed in class on Nov. 9, the vertices in this graph are words (strings) that are all the same length, and an edge exists between two words w1 and w2 if and only if they differ by exactly one character. For example, there is an edge between the strings dog and fog because the characters at index 0, d and f, are different while the rest of the strings are the same. Conversely, there is NOT an edge between dog and cot because they differ at two character indices, 0 and 2.

The following dictionaries are supplied in the link above:

• twos.txt 107 2-letter English words
• threes.txt 1005 3-letter English words
• fours.txt 3130 4-letter English words
• fives.txt 5757 5-letter English words
• toy.txt 10 5-letter English words

Five key data structures are declared in WordGraph and should be used by the functions below:

• set<string> word_set: Stores all words read from the dictionary (which should be the same length). This is initialized for you in the constructor
• map<string, set<string>> word_neighbors_map: Keys are words, values are sets of neighbor words. This is initialized by repeated calls to calculate_neighbor_words()
• map<string, bool> word_visited_map: Scratch data structure for DFS
• map<string, int> word_distance_map: Scratch data structure for BFS
• map<string, string> word_path_map: Scratch data structure for DFS/BFS. Keys are words, values are words visited JUST BEFORE key during DFS/BFS

The executable is called as follows: wordgraph <dictionary> <command> <0, 1, or 2 parameters>. Commands and their parameters are explained below:

• NUM_NEIGHBORS w: Print number of neighbors of word w
• NEIGHBORS w: Print all neighbors of word w, one per line
• CONNECTED w1 w2: Using DFS, print "CONNECTED" if w1 and w2 are connected, "NOT CONNECTED" otherwise
• NUM_CONNECTED w: Using DFS, print number of words that are connected to w. w itself counts as 1
• PATH_LENGTH w1 w2: Using BFS, print length of shortest path connecting w1 and w2. If they are not connected, print "NOT CONNECTED"
• PATH w1 w2: Using BFS, print sequence of words on that path (one per line starting with w1 and ending with w2). If they are not connected, print "NOT CONNECTED"
• LONGEST_PATH: Using BFS, test all possible pairs of words and print length of longest shortest path, then the pair of words on their own lines. This can take seconds to minutes depending on the size of the dictionary, so for grading only small dictionaries will be used.

If any word is not in the dictionary selected, print "ERROR" and nothing else.

2. Programming tasks

These are core WordGraph functions that are required but not directly tested. Since they don't generate output but have side effects on the data structures above, every print function should either call one of these or use the modified data structure(s).

• calculate_neighbor_words(string &)
• DFS_traversal(string &)
• BFS_traversal(string &)

These WordGraph functions will be directly tested and correspond one-to-one with the commands listed above:

• [0.5 points] print_num_neighbors(string &)
• [0.5 points] print_neighbors(string &)
• [1 point] DFS_print_connected(string &, string &)
• [1 point] DFS_print_num_connected(string &)
• [0.5 points] BFS_print_path_length(string &, string &)
• [1 point] BFS_print_path(string &, string &)
• [0.5 points] BFS_print_longest_path()

You may use AI on any part of this lab, but no human partner.

3. Submission

Submit 2 files to Gradescope: (1) your README and (2) your modified main.cpp. The README should contain your name, complete declarations of AI use, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. main.cpp should also contain your name and per-function comments on AI usage.