Description
People in Graphville
You are the mayor of Graphville. You have a list of all the people in your town. You
also know the relation between them, basically if they know each other. You need to
increase the community interaction between your constituents. Now before you do
that you need to know a lot of other details like if two people know each other
directly or through a friend or in any other way, also how many groups are there in
your town.
What your program needs to do:
Build a graph. There is a file on canvas called people.txt that contains the names of
people and with them the names of people they know similar to an adjacency list.
When the user starts the program, read in the file and build a graph where every
person is a vertex, and there is an edge for every person they know.
For this assignment, you are building the graph and implementing functionalities
given in the menu.
Use a command-line argument to handle the filename.
Display a menu. Once the graph is built, your program should display a menu with
the following options:
1. Print list of people and their acquaintances
2. Print distance between 2 people
3. Print people who are ‘n’ hops away
4. Quit
Menu Items and their functionality:
1. Print list of people. If the user selects this option, the vertices and adjacent
vertices should be displayed.
2. Print distance between 2 people This option takes two vertices as user
inputs and prints the shortest distance between them. Use Dijkstra’s
algorithm.
3. Print people who are ‘n’ hops away: Print people who at ‘n’ hop from the
starting person which you will take as input. IGNORE THE WEIGHTS FOR
THIS ONE. If you draw out the graph you will observe That if the starting
person is Tang then Tessa, Simon and Simon will be at hops 2 and John and
Timothy are at hops 3. Please note that if a vertex is reachable in 2 hops and
3 hops then you only consider that vertex at 2 hops.
Project Proposal:
Write a 1-page proposal describing the project you would like to work on for the course.
You have the freedom to use any language (Preferably C++, C, Java, Python, JavaScript)
and could choose whatever topic you want.
Just some broad categories you can think about projects are:
1. Combining multiple data structure with a use case
2. Implementing a data structure not taught in class and is something difficult
3. Benchmarking performance of various data structures for various operations
4. Anything under the sun and the stars which can use data structures
This will be a rough proposal which we will then sit together and finalize. If you have
multiple ideas feel free to put them all in the proposal.
Submit it on Canvas – For any questions feel free to email the TA or Professor.
