CISC220 F2023 Lab9

Lab #9

1. Word graphs

Starter code for a WordGraph class is provided which reads in words (all the same length) from a dictionary. Five key data structures are declared 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

here: Maze and UnionFind. UnionFind is an implementation of the union/find data structure which uses an array to represent the equivalence class "uptrees", and Maze is a data structure to represent and draw N x M grids with walls (see the comments in maze.hh for details).

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 functions that are required but not directly tested. Every print function should either call one of these or use data structures it has modified.

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

These functions will be directly tested:

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

You may work with a (human) partner on this lab

3. Submission

Submit 2 files to Gradescope: (1) your README and (2) your modified main.cpp. The README should contain your name and your partner's name, notes on any limitations or issues with your code, and your interpretation of any ambiguities in the assignment instructions. Both code files should also contain your name(s)