Instructions
Requirements and Specifications
Source Code and Solution
#include <fstream>
#include <sstream>
#include <limits>
#include "Graph.h"
/**
* Initialize a Graph object from a given edge list CSV, where each line `u,v,w` represents an edge between nodes `u` and `v` with weight `w`.
* @param edgelist_csv_fn The filename of an edge list from which to load the Graph.
*/
Graph::Graph(const char* const & edgelist_csv_fn) {
ifstream f(edgelist_csv_fn);
string line;
string token;
while (getline(f, line)) {
stringstream ss(line);
getline(ss, token, ',');
string node1 = token;
getline(ss, token, ',');
string node2 = token;
getline(ss, token, ',');
double w = stod(token);
int i1 = -1;
int i2 = -1;
if (_nameToIndex.find(node1) != _nameToIndex.end()) {
i1 = _nameToIndex[node1];
}
else {
i1 = _nodes.size();
_nameToIndex[node1] = i1;
_nodes.push_back(node1);
vector<tuple<int,double>> adjs;
_adjList.push_back(adjs);
}
if (_nameToIndex.find(node2) != _nameToIndex.end()) {
i2 = _nameToIndex[node2];
}
else {
i2 = _nodes.size();
_nameToIndex[node2] = i2;
_nodes.push_back(node2);
vector<tuple<int,double>> adjs;
_adjList.push_back(adjs);
}
tuple<int,double> edge1 = make_tuple(i2, w);
tuple<int,double> edge2 = make_tuple(i1, w);
_adjList[i1].push_back(edge1);
_adjList[i2].push_back(edge2);
}
}
/**
* Return the number of nodes in this graph.
* @return The number of nodes in this graph.
*/
unsigned int Graph::num_nodes() {
return _nodes.size();
}
/**
* Return a `vector` of node labels of all nodes in this graph, in any order.
* @return A `vector` containing the labels of all nodes in this graph, in any order.
*/
vector<string> Graph::nodes() {
return _nodes;
}
/**
* Return the number of (undirected) edges in this graph.
* Example: If our graph has edges "A"<-(0.1)->"B" and "A"<-(0.2)->"C", this function should return 2.
* @return The number of (undirected) edges in this graph.
*/
unsigned int Graph::num_edges() {
int count = 0;
for (int i = 0; i<_nodes.size(); i++) {
count += _adjList[i].size();
}
return count / 2;
}
/**
* Return the number of neighbors of a given node.
* @param node_label The label of the query node.
* @return The number of neighbors of the node labeled by `node_label`.
*/
unsigned int Graph::num_neighbors(string const & node_label) {
int index = _nameToIndex[node_label];
return _adjList[index].size();
}
/**
* Return the weight of the edge between a given pair of nodes, or -1 if there does not exist an edge between the pair of nodes.
* @param u_label The label of the first node.
* @param v_label The label of the second node.
* @return The weight of the edge between the nodes labeled by `u_label` and `v_label`, or -1 if there does not exist an edge between the pair of nodes.
*/
double Graph::edge_weight(string const & u_label, string const & v_label) {
int i1 = _nameToIndex[u_label];
int i2 = _nameToIndex[v_label];
for(int i = 0; i<_adjList[i1].size(); i++) {
if (get<0>(_adjList[i1][i]) == i2) {
return get<1>(_adjList[i1][i]);
}
}
return -1;
}
/**
* Return a `vector` containing the labels of the neighbors of a given node.
* The neighbors can be in any order within the `vector`.
* Example: If our graph has edges "A"<-(0.1)->"B" and "A"<-(0.2)->"C", if we call this function on "A", we would return the following `vector`: {"B", "C"}
* @param node_label The label of the query node.
* @return A `vector` containing the labels of the neighbors of the node labeled by `node_label`.
*/
vector<string> Graph::neighbors(string const & node_label) {
vector<string> result;
int i1 = _nameToIndex[node_label];
for(int i = 0; i<_adjList[i1].size(); i++) {
int i2 = get<0>(_adjList[i1][i]);
result.push_back(_nodes[i2]);
}
return result;
}
int minDist(int n, double distance[], bool visited[])
{
double min = numeric_limits<double>::max();
int index = -1;
for(int k=0; k<n; k++) {
if(visited[k]==false && distance[k] < min){
min = distance[k];
index = k;
}
}
return index;
}
/**
* Return the shortest unweighted path from a given start node to a given end node as a `vector` of `node_label` strings, including the start node.
* If there does not exist a path from the start node to the end node, return an empty `vector`.
* If there are multiple equally short unweighted paths from the start node to the end node, you can return any of them.
* If the start and end are the same, the vector should just contain a single element: that node's label.
* Example: If our graph has edges "A"<-(0.1)->"B", "A"<-(0.5)->"C", "B"<-(0.1)->"C", and "C"<-(0.1)->"D", if we start at "A" and end at "D", we would return the following `vector`: {"A", "C", "D"}
* Example: If we start and end at "A", we would return the following `vector`: {"A"}
* @param start_label The label of the start node.
* @param end_label The label of the end node.
* @return The shortest unweighted path from the node labeled by `start_label` to the node labeled by `end_label`, or an empty `vector` if no such path exists.
*/
vector<string> Graph::shortest_path_unweighted(string const & start_label, string const & end_label) {
int n = _nodes.size();
double distance[n];
int parent[n];
bool visited[n];
for(int k = 0; k<n; k++)
{
distance[k] = numeric_limits<double>::max();
parent[k] = -1;
visited[k] = false;
}
int i1 = _nameToIndex[start_label];
distance[i1] = 0;
for(int i = 0; i<n; i++)
{
int m = minDist(n, distance, visited);
visited[m] = true;
for(int k = 0; k<n; k++)
{
if (visited[k]) {
continue;
}
double w = edge_weight(_nodes[m], _nodes[k]);
if (w < 0) {
continue;
}
if (distance[k] == numeric_limits<double>::max() || distance[k] > distance[m] + 1) {
parent[k] = m;
distance[k] = distance[m] + 1;
}
}
}
int curr = _nameToIndex[end_label];
vector<string> result;
while(curr != -1) {
result.insert(result.begin(), _nodes[curr]);
curr = parent[curr];
}
return result;
}
/**
* Return the shortest weighted path from a given start node to a given end node as a `vector` of (`from_label`, `to_label`, `edge_weight`) tuples.
* If there does not exist a path from the start node to the end node, return an empty `vector`.
* If there are multiple equally short weighted paths from the start node to the end node, you can return any of them.
* If the start and end are the same, the vector should just contain a single element: (`node_label`, `node_label`, -1)
* Example: If our graph has edges "A"<-(0.1)->"B", "A"<-(0.5)->"C", "B"<-(0.1)->"C", and "C"<-(0.1)->"D", if we start at "A" and end at "D", we would return the following `vector`: {("A","B",0.1), ("B","C",0.1), ("C","D",0.1)}
* Example: If we start and end at "A", we would return the following `vector`: {("A","A",-1)}
* @param start_label The label of the start node.
* @param end_label The label of the end node.
* @return The shortest weighted path from the node labeled by `start_label` to the node labeled by `end_label`, or an empty `vector` if no such path exists.
*/
vector<tuple<string,string,double>> Graph::shortest_path_weighted(string const & start_label, string const & end_label) {
int n = _nodes.size();
double distance[n];
int parent[n];
bool visited[n];
for(int k = 0; k<n; k++)
{
distance[k] = numeric_limits<double>::max();
parent[k] = -1;
visited[k] = false;
}
int i1 = _nameToIndex[start_label];
distance[i1] = 0;
for(int i = 0; i<n; i++)
{
int m = minDist(n, distance, visited);
visited[m] = true;
for(int k = 0; k<n; k++)
{
if (visited[k]) {
continue;
}
double w = edge_weight(_nodes[m], _nodes[k]);
if (w < 0) {
continue;
}
if (distance[k] == numeric_limits<double>::max() || distance[k] > distance[m] + w) {
parent[k] = m;
distance[k] = distance[m] + w;
}
}
}
int curr = _nameToIndex[end_label];
vector<tuple<string, string, double>> result;
while(curr != -1) {
int from = parent[curr];
if (from == -1) {
break;
}
string fromS = _nodes[from];
string currS = _nodes[curr];
double w = edge_weight(fromS, currS);
tuple<string, string, double> edge = make_tuple(fromS, currS, w);
result.insert(result.begin(), edge);
curr = from;
}
return result;
}
/**
* Given a threshold, ignoring all edges with a weight greater than the threshold, return the connected components of the resulting graph as a `vector` of `vector` of `string` (i.e., each connected component is a `vector` of `string`, and you return a `vector` containing all of the connected components).
* The components can be in any order, and the node labels within a component can be in any order.
* Example: If our graph has edges "A"<-(0.1)->"B", "B"<-(0.2)->"C", "D"<-(0.3)->"E", and "E"<-(0.4)->"F", if our threshold is 0.3, we would output the following connected components: {{"A","B","C"}, {"D","E"}, {"F"}}
* @param threshold The maximum edge weight to consider
* @return The connected components of this graph, if we ignore edges with weight greater than `threshold`, as a `vector<vector<string>>`.
*/
vector<vector<string>> Graph::connected_components(double const & threshold) {
vector<vector<string>> result;
return result;
}
/**
* Return the smallest `threshold` such that, given a start node and an end node, if we only considered all edges with weights <= `threshold`, there would exist a path from the start node to the end node.
* If there does not exist such a threshold (i.e., it's impossible to go from the start node to the end node even if we consider all edges), return -1.
* Example: If our graph has edges "A"<-(0.2)->"B", "B"<-(0.4)->"C", and "A"<-(0.5)->"C", if we start at "A" and end at "C", we would return 0.4.
* Example: If we start and end at "A", we would return 0
* Note: The smallest connecting threshold isn't necessarily part of the shortest weighted path (such as in the first example above)
* @param start_label The label of the start node.
* @param end_label The label of the end node.
* @return The smallest `threshold` such that, if we only considered all edges with weights <= `threshold, there would exist a path connecting the nodes labeled by `start_label` and `end_label`, or -1 if no such threshold exists.
*/
double Graph::smallest_connecting_threshold(string const & start_label, string const & end_label) {
return 0.0;
}