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 person’s name (a string) and the “value” is a Person structure holding the adjacencies:

struct Person {
    vector<string> friends;
};

The ‘friends’ field is a list of neighbors, identified by their integer index into an array of names, which is also that person’s 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 <fstream>

#include <iostream>

#include <sstream>

#include <vector>

#include <map>

#include <iomanip>

#include <cstdlib>

using namespace std;

//

// This file provides a starting point for Lab #11. It reads the

// input file (.csv), builds a graph from the adjacencies in the file,

// and will print the friends list for any node requested.

//

// The graph is a simple adjacency list format — each node (struct Person)

// contains a string vector of all of its friend nodes.

//

#define IS_QUIT(s) (s == “X” || s == “x”)

#define FILENAME “facebook.csv”

using namespace std;

struct Person {

vector<string> friends;

};

void parse_line(const string &str,

vector<string> &line) {

istringstream istr(str);

string tmp;

while (getline(istr, tmp, ‘,’)) {

line.push_back(tmp);

}

}

int main() {

ifstream inFile(FILENAME);

vector<string> row;

vector<string> names;

map<string, Person> everyone;

string inputLine;

// Verify that the file open was OK

if (!inFile.good()) {

cerr << “Invalid file.” << endl;

return (-1);

}

// Read the header line of the file (first line, contains column labels).

// We save this line (names) so we can lookup the string names in the

// below loop.

getline(inFile, inputLine);

parse_line(inputLine, names);

// Reach each subsequent entry

while (getline(inFile, inputLine)) {

if (inFile.eof())

break;

vector<string> row;

Person p;

parse_line(inputLine, row);

// Start at 1 (0th field is the string name)

for (size_t i = 1; i < row.size(); i++) {

int adj_status = atoi(row[i].c_str());

// A ‘1’ indicates an adjacency, so skip if we get a ‘0’

// If there is an adjacency to this person, push the string name

// of that person on the adjacency list.

if (adj_status == 1)

p.friends.push_back(names[i]);

}

// Add this (new) person to the map.

// In this map, the key is the string name of the person, and

// the value is their Person structure (adjacency list).

everyone.insert(make_pair(row[0], p));

}

for (;;) {

cout << endl << “Enter the name “

<< “and I’ll tell you their friends (X to quit): “;

getline(cin, inputLine);

if (IS_QUIT(inputLine))

break;

// Look up the adjacency list of this person in the map

if (everyone.count(inputLine) == 0) {

cout << “That person is not in the map.” << endl;

continue;

}

Person this_person = everyone[inputLine];

// Output all their friends

cout << inputLine << ” is friends with: ” << endl;

for (size_t i = 0; i < this_person.friends.size(); i++) {

cout << “t” << this_person.friends[i] << endl;

}

}

cout << “Exiting…” << endl;

return (0);

}