Facebook Graph #2 (C++ Program) PLEASE USE C++ The new data file is in the module here: fb_weighted.csv (USE YOUR OWN D

[answerhappygod]

Facebook Graph #2 (C++
Program) PLEASE USE C++
The new data file is in the module
here: fb_weighted.csv (USE YOUR OWN DATA TO MAKE
SURE CODE IS FUNCTIONING)
Assignment:
Write a program that prompts the user for two people as
before, but outputs the lowest cost path between them.
The program should consider the friend edge weights
between the 'from' person and the 'to' person and compute the cost
of the path as well as be able to output the list of nodes and
friend edges used:
This assignment builds on the friend relationships (edges) have
weights, forming a directed, weighted graph.
The 'best_parent' field contains the string ID of the previous
node used along the cheapest path to reach it (in other words, the
"parent" node in the best path).
The 'best_weight' field contains the cheapest cost (the sum of all
the weights along this path).
The algorithm should stop when it locates the lowest path to the
destination node.
After calculating the best path, to complete the assignment add
the remaining code in main() which should output the edges used in
order -- starting from the 'from' person and ending with the 'to'
person.
Hint:
If you start with the end node, you can rebuild the path
backwards following each 'best_parent', then use a stack to reverse
the output.
Example Input/Output:
Enter the starting name (X to quit): Umar
Enter the ending name (X to quit): Lema
The best path between these two people is:
Umar
Saim Shah Hamdani
Arwen
Sara
Lema
The cost of this path is: 4
Enter the starting name (X to quit): Tommy
Enter the ending name (X to quit): Amir
The best path between these two people is:
Tommy
Mohsin Khan
Dennis
Umar Patek
Amir
The cost of this path is: 5
Enter the starting name (X to quit):
Gabriel
Enter the ending name (X to quit): Varga Melinda
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>
#include <queue>
#include <stack>
using namespace std;
#define IS_QUIT(s) (s == "X" || s == "x")
#define FILENAME "fb_weighted.csv"
using namespace std;
// A node in the Facebook graph
struct Person
{
int best_weight; // The sum of the weights along the best
path
string best_parent; // The parent node for the best path
vector friends; // String names of the friend edges
vector weights; // Weights for each friend edge
};
// A candidate entry for the priority queue
struct PersonCandidate
{
string name; // The name of the node we found
string parent; // The node before this one in the path
int weight; // The best known weight on the best path
bool operator< (const PersonCandidate &rhs) const
{
return weight > rhs.weight;
}
};
void parse_line(const string &str, vector &line)
{
istringstream istr(str);
string tmp;
while (getline(istr, tmp, ','))
{
line.push_back(tmp);
}
}
// Output the shortest path
// - everyone: reference variable to the graph
// - starting: string name of the starting person
// - ending: string name of the ending person
bool dijkstra(map &everyone, string starting, string
ending)
{
priority_queue pq;
// Add all of the source's edges into the
// priority queue
Person &source = everyone[starting];
for (size_t i = 0; i < source.friends.size(); i++)
{
PersonCandidate c;
c.name = source.friends;
c.weight = source.weights;
c.parent = starting;
pq.push(c);
}
source.best_parent = "";
source.best_weight = 0;
while (!pq.empty())
{
// Get the next best candidate from TENT
PersonCandidate nextBest = pq.top();
pq.pop();
// Add this node to PATHS. PATHS is stored
// in each Person in the graph
Person &p = everyone[nextBest.name];
// If this node is already in PATHS, ignore
// this candidate. If the node is in PATHS
// here it means we found a better path prior
// to this.
if (p.best_weight != -1)
continue;
// Now that this node is in PATHS, we can
// record the best weight and parent.
p.best_weight = nextBest.weight;
p.best_parent = nextBest.parent;
// This means we found the node
if (nextBest.name == ending)
return (true);
for (unsigned int i = 0; i < p.friends.size(); i++)
{
PersonCandidate newCandidate;
newCandidate.name = p.friends;
// Total weight of the path
newCandidate.weight = p.best_weight + p.weights;
newCandidate.parent = nextBest.name;
pq.push(newCandidate);
}
}
return (false);
}
int main()
{
ifstream inFile(FILENAME);
vector row;
vector names;
map 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
when
// needed.
getline(inFile, inputLine);
parse_line(inputLine, names);
// Reach each subsequent entry
while (getline(inFile, inputLine))
{
if (inFile.eof())
break;
vector 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.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 > 0)
{
p.friends.push_back(names);
p.weights.push_back(adj_status);
}
// Initialize the other fields
p.best_weight = -1;
p.best_parent = "";
}
// 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));
}
// The main loop of the program
for (;;)
{
string to, from;
cout << endl << "Enter the starting name (X to
quit): ";
getline(cin, from);
if (IS_QUIT(from))
break;
cout << endl << "Enter the ending name (X to quit):
";
getline(cin, to);
if (IS_QUIT(to))
break;
if (everyone.count(from) == 0 || everyone.count(to) == 0)
{
cout << "One or more people is not in the map." <<
endl;
continue;
}
// Run the calculation
if (dijkstra(everyone, from, to))
{
cout << "The best path between these two people is: "
<< endl;
// Construct the path from the parents stored
// Output the path in reverse
}
else
{
cout << "There is NOT a path between these two people."
<< endl;
}
// Print the path
// Clean up all the state
for (auto i = everyone.begin(); i != everyone.end(); i++)
{
Person &p = i->second;
p.best_weight = -1;
p.best_parent = "";
}
}
cout << "Exiting..." << endl;
}