**Assignment 03: Graphs and Friend Circles** *Due Thu Mar 4 11:00 PM Pacific Time* [Back to Algorithms](http://cs.pomona.edu/classes/cs140/) # Learning Goals - Analyze new graph problems and propose solutions. - Implement a graph search algorithm. - Compare graph representations. - Trace through graph algorithms. # Overview This assignment includes two parts: 1. Answer the [question in this PDF](resources/graphs.pdf). 2. Write a program for the problem described in section Friend Circles Problem (must be compatible with Python 3.8). You may work on this assignment alone or with a partner. Please send me a message on Slack if you want me to assign you to work with a random partner. Whether you work alone or with a partner, only one partner will submit a both parts to [gradescope](https://www.gradescope.com/). Three key points: 1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with Edge (Windows) or Preview (OSX) (using the correct format and spacing will help us grade), 2. ensure that the uploading partner adds the other partners after submission, and 3. **if you have any questions please ask them on [Slack](https://divisionii.slack.com/archives/G019H3HEXBK)**. # Example Execution I always like to start by showing you the end result. If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/361812 **You can copy and past from the above animation!** # Friend Circles Problem There are $n$ students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature, i.e., if `A` is a friend of `B` and `B` is a friend of `C`, then `A` is also a friend of `C`. A friend circle is a group of students who are directly or indirectly friends. Indirect friendships can result from multiple levels of indirection. Your program will take a filename as a program argument, and it will print the number of friend circles found in the class data found in the file. The input file contains an $n$ by $n$ adjacency matrix containing the characters `Y` and `N`. A `Y` found in the $i^{th}$ row and $j^{th}$ column indicates that $student_i$ and $student_j$ are friends; an `N` indicates they are not friends. You can assume the following: - Each element of input file will be `Y` or `N` - The number of rows and columns in the input file will be equal - All students are friends with themselves (the diagonal of the matrix is filled with `Y`s) - If $student_i$ is friends with $student_j$, then $student_j$ is friends with $student_i$ # Generating Test Cases If you are interested in testing your code on more inputs, here is the script that I use to generate test input files (you can [download the script here](resources/generate_friend_matrix.py)): ~~~python linenumbers #!/usr/bin/env python3 """ Generating a new test file: ./generate_friend_matrix.py 8 0.32 > test_file.txt """ from argparse import ArgumentParser from random import random arg_parser = ArgumentParser("Generate an adjacency matrix.") arg_parser.add_argument("-n", help="Number of students.", default=10, type=int) arg_parser.add_argument( "-p", help="Probability of two students being friends", default=0.2, type=float ) args = arg_parser.parse_args() friends = [["N" for _ in range(args.n)] for _ in range(args.n)] for i in range(args.n): for j in range(i, args.n): if i == j or random() < args.p: friends[i][j] = "Y" friends[j][i] = "Y" print("\n".join(["".join(f) for f in friends])) ~~~ # Reading the input file Here is my Python3 code for reading the input file: ~~~python linenumbers if __name__ == "__main__": arg_parser = ArgumentParser("Count the number of friend circles.") arg_parser.add_argument("file", help="Path to an adjacency matrix file.") args = arg_parser.parse_args() with open(args.file, "r") as matrix_file: friends_matrix = [line.strip() for line in matrix_file.readlines()] num_circles = count_friend_circles(friends_matrix) print(f"Number of friend circles: {num_circles}") ~~~ # Submitting Your Assignment You will submit your PDF assignment on [gradescope](https://gradescope.com/). **Only one partner should submit your PDF.** The submitter will add the other partner through the gradescope interface. You will also submit your code to gradescope. You will submit Python file on gradescope, and it must be named `friend_circles.py`. **Only one partner should submit your code.** The submitter will add the other partner through the gradescope interface. Please add your names in comments at the top of the file. To pass the autograder, your output must exactly match the expected output. You can use [text-compare](https://text-compare.com/) to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do). I've enabled a leaderboard for the assignment. You do not need to worry about it affecting your grade. I just thought it looked like a cute feature. Feel free to give yourself (your group) any name you'd like for the leaderboard. Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Scanning Work on a Mobile Device](https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)