+1 (315) 557-6473 

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


Instructions

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

Requirements and Specifications

Program to use graphs ADT and dictionaries in C++

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;

}