Difference between revisions of "CISC220 F2023 Lab9"

Revision as of 17:11, 9 November 2023

Lab #9

1. Word graphs

Starter code for a WordGraph class is provided which reads in words (all the same length) from a dictionary and inserts each one into a set.

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 command parameters. Commands and their parameters are explained below:

• NUM_NEIGHBORS w: Print number of neighbors of word w
• NEIGHBORS w
• CONNECTED w1 w2
• NUM_CONNECTED w
• PATH_LENGTH w1 w2
• PATH w1 w2
• LONGEST_PATH

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)