CSCI2275 Assignment 8 Solved

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 if people know each other 

3.      Print groups 

4.      Find the least number of introductions required  

5.      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 if people know each other. This option takes two vertices as user inputs and displays True is the vertices are adjacent, and False if they are not adjacent.

 

If this is a part of the file:  

Akhil-Paramvir,Aurangzeb 

Aurangzeb-Akhil,Kieran 

Earl-Paramvir,Kieran,Zack 

 

Then Earl and Zack know each other Kieran and Aurangzeb know each other and so on. 

 

3.      Print groups. If the user selects this option, you need to do a depth-first search (DFS) of the graph to determine the connected people in the graph, and assign those cities the same group ID. The connected people are the vertices that are connected, either directly by an edge, or indirectly through another vertex. For example, in the above example, Akhil is connected to Kieran via Aurangzeb. When assigning group Ids, start at the first vertex and find all vertices connected to that vertex. This is group 1. Next, find the first vertex that is not assigned to group 1. This vertex is the first member of group 2, and you can repeat the depth-first search to find all vertices connected to this vertex. Repeat this process until all vertices have been assigned to a group.

 

4.      Find the least number of introductions required- If the user selects this option, they should be prompted for the names of two names. Your code should first determine if they are in the same group. If the people are in different groups, print “No way to introduce them”. If the people are in the same group, run a breadth-first search (BFS) that returns the number of vertices to traverse along the shortest path,

and the names of the vertices along the path. For example,  

For Akhil and Paramvir no one else is required as they are directly connected. But Kieran and Akhil can be introduced via Aurangzeb. 

So your output should be something like : 

1, Aurangzeb 

 

If there were N people in between then output: 

N, Name1-Name2-.....-NameN