Program To Use Graphs ADT And Dictionaries in C++ Language Assignment Solution

Instructions

Objective

Write a program to use graphs ADT and dictionaries in C++ language.

Requirements and Specifications

Source Code and Solution

#include #include #include #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> 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> adjs; _adjList.push_back(adjs); } tuple edge1 = make_tuple(i2, w); tuple 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 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 Graph::neighbors(string const & node_label) { vector 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::max(); int index = -1; for(int k=0; 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 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 { distance[k] = numeric_limits::max(); parent[k] = -1; visited[k] = false; } int i1 = _nameToIndex[start_label]; distance[i1] = 0; for(int i = 0; i { int m = minDist(n, distance, visited); visited[m] = true; for(int k = 0; k { if (visited[k]) { continue; } double w = edge_weight(_nodes[m], _nodes[k]); if (w < 0) { continue; } if (distance[k] == numeric_limits::max() || distance[k] > distance[m] + 1) { parent[k] = m; distance[k] = distance[m] + 1; } } } int curr = _nameToIndex[end_label]; vector 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> 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 { distance[k] = numeric_limits::max(); parent[k] = -1; visited[k] = false; } int i1 = _nameToIndex[start_label]; distance[i1] = 0; for(int i = 0; i { int m = minDist(n, distance, visited); visited[m] = true; for(int k = 0; k { if (visited[k]) { continue; } double w = edge_weight(_nodes[m], _nodes[k]); if (w < 0) { continue; } if (distance[k] == numeric_limits::max() || distance[k] > distance[m] + w) { parent[k] = m; distance[k] = distance[m] + w; } } } int curr = _nameToIndex[end_label]; vector> 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 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> Graph::connected_components(double const & threshold) { vector> 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; }