This assignment is the first of a two-part solution and will count for Lab #11, with the second part counting as Lab #12.
Graph and Input File
The data file posted in this module, contains a data set with information on a social media network (Facebook). This is a real data set with anonymized names from the data competition site Kaggle_(links to an external_site.) lots more to explore there, by the way!
The format of the file is CSV (which you used in previous labs) but this time there are more fields in each row. The file forms an adjacency matrix for 200 people. Each row contains the name in the first field, then a series of 0 or 1 indicating whether that person is a friend of the person in that column. If there is a 1 in that column, the two people are friends (they are connected to each other in the graph), otherwise they are not. The graph is not connected there are some disconnected islands of people in the file.
The supplied file starter.cpp builds a graph using a std::map structure from the data, where the key is the persons name (a string) and the value is a Person structure holding the adjacencies:
struct Person {
vector
};
The friends field is a list of neighbors, identified by their integer index into an array of names, which is also that persons key in the map. For example, if friends[1] is 1, that person is adjacent to the person with column index 1. There are no weights in this graph; two people are either connected or not.
Assignment
Write a program that prompts the user for the names of two people, and output whether or not there is a path between them in the graph. You can output only a yes/no answer (no printing of the path is required). Continue looping for more input until the user enters X for a name.
Hints
Use depth-first search (DFS) or breadth-first search (BFS), either recursive or interative, and stop the search when you reach the target node.
You will need to keep track of which nodes have been visited somewhere in your code.
Note that the first column (names) can be either a first name, or a first and last name. Like most data sets, this one could use some cleaning.
What to submit
Submit only your .cpp file for the solution.
Example Input/Output
Here are a few examples to try to make sure your code is working:
Enter the starting name (X to quit): Mirza Khan
Enter the ending name (X to quit): Amir
There IS a path between these two people.
Enter the starting name (X to quit): Tu Viloria
Enter the ending name (X to quit): Isabelle
There IS a path between these two people.
Enter the starting name (X to quit): Ali Ghufron
Enter the ending name (X to quit): Michael Felix
There is NOT a path between these two people.
Enter the starting name (X to quit): Hanno Plitz
Enter the ending name (X to quit): Denno
There is NOT a path between these two people.
Enter the starting name (X to quit): X
Exiting…
starter.cpp:
#include
#include
#include
#include
#include