## 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;
}
```

## Similar Samples

Explore our sample section to see the quality and range of programming assignments we offer. Each example showcases our expertise in various programming languages and concepts, ensuring you receive top-notch assistance tailored to your needs. Discover how we can help you excel in your studies.

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++

C++