DSA-Assignments

Log | Files | Refs | README

Problem2.cpp (3665B)

      1 // Problem 2: Social Network
      2 // Description: 
      3 // Course: IT405G - Datastructures and Algorithms
      4 // Authors: William Lindholm, Lili Tran, Victor Adamson
      5 // Date: 29-11-2023
      6 //
      7 
      8 #include <iostream>
      9 #include <queue>
     10 #include <vector>
     11 #include <list>
     12 using namespace std;
     13 
     14 class Graph {
     15 private:
     16     int nodes; //Number of nodes
     17     vector<int>* adj;
     18 public:
     19     Graph(int nodes);
     20     void addEdge(int src, int dest); //src == Source node, dest == Destintaion node
     21     bool isEdge(int src, int dest);
     22     int getNumNodes();
     23     bool BFS(int src, int dest, int distance[], int predecessor[]);
     24     void printShortPath(int src, int dest);
     25     void printFriendsOf(int src);
     26 };
     27 
     28 Graph::Graph(int nodes) {
     29     this->nodes = nodes;
     30     adj = new vector <int>[nodes];
     31 }
     32 
     33 void Graph::addEdge(int src, int dest) {
     34     adj[src].push_back(dest);
     35     adj[dest].push_back(src);
     36 }
     37 
     38 bool Graph::isEdge(int src, int dest) {
     39     vector<int>::iterator i;
     40     for (i = adj[src].begin(); i != adj[src].end(); i++) {
     41         if (dest == *i) {
     42             return(true);
     43         }
     44         return(false);
     45     }
     46 }
     47 
     48 int Graph::getNumNodes() {
     49     return nodes;
     50 }
     51 
     52 bool Graph::BFS(int src, int dest, int distance[], int predecessor[]) {
     53     queue<int> queue;
     54     vector<bool> visited(nodes, false);
     55 
     56     for (int i = 0; i < nodes; i++) {
     57         visited[i] = false;
     58         distance[i] = INT_MAX;
     59         predecessor[i] = -1;
     60     }
     61 
     62     visited[src] = true;
     63     distance[src] = 0;
     64     queue.push(src); 
     65 
     66     while (!queue.empty()) {
     67         int current = queue.front();
     68         queue.pop();
     69         for (auto adjacent : adj[current]) {
     70             if (!visited[adjacent]) {
     71                 visited[adjacent] = true;
     72                 distance[adjacent] = distance[current] + 1;
     73                 predecessor[adjacent] = current;
     74                 queue.push(adjacent);
     75                 if (adjacent == dest) return true;
     76             }
     77         }
     78     }
     79     return false;
     80 }
     81 
     82 
     83 /*
     84 * Function: printFriendsOf
     85 * Print all friends of a node
     86 * @param src: the node to find friends 
     87 */
     88 void Graph::printFriendsOf(int src) {
     89 	cout << "Friends of " << src << ": ";
     90     for (int i = 0; i < nodes; i++) {
     91         int* distance = new int[nodes];
     92         int* predecessor = new int[nodes];
     93         if (BFS(src, i, distance, predecessor)) {
     94             if (distance[i] % 2 == 0) {
     95 				cout << i << " ";
     96             }
     97         }
     98 	}
     99 	cout << endl;
    100 }
    101 
    102 void Graph::printShortPath(int src, int dest) {
    103     int* distance = new int[nodes];
    104     int* predecessor = new int[nodes];
    105     if (BFS(src, dest, distance, predecessor)) {
    106         cout << "Path: ";
    107         int crawl = dest;
    108         while (crawl != -1) {
    109             cout << crawl << " ";
    110             crawl = predecessor[crawl];
    111         }
    112 
    113         // A node is a friend if the shortest path is even
    114         if (distance[dest] % 2 == 0) {
    115             cout << endl << "node: " << dest << " is a ";
    116             cout << "Friend\n";
    117         }
    118         else {
    119             cout << endl << "node: " << dest << " is an ";
    120             cout << "Adversary\n";
    121         }
    122     }
    123     else {
    124         cout << "No path found from " << src << " to " << dest << "\n";
    125     }
    126     delete[] distance;
    127     delete[] predecessor;
    128 }
    129 
    130 int main() {
    131     Graph network(4);
    132     int start = 0; // the head-node
    133     int end = 2; // the target-node
    134     network.addEdge(0, 1); //A dislikes B
    135     network.addEdge(1, 2); //B dislikes C
    136     network.addEdge(1, 3); //B dislikes D
    137     network.addEdge(2, 3); //C dislikes D
    138     network.addEdge(2, 1); //C dislikes B
    139     
    140     cout << endl << "Shortest Path from starting node to end node: \n";
    141 
    142     network.printFriendsOf(3);
    143 
    144     //network.printShortPath(start, end);
    145 }