Graph.hpp

#pragma once

#include <vector>
#include <set>   // To store neighbors, allows easy alphabetical sorting later
#include <queue> // For BFS
#include <map>   // For BFS visited/distance tracking
#include <limits> // For std::numeric_limits

//Vertices represent users, edges represent friendships.

class Graph {
private:
    // Adjacency list: user_id -> set_of_friend_ids
    std::vector<std::set<int>> adjList;
    int numVertices;

public:
    Graph() : numVertices(0) {}

    int addVertex() {
        adjList.push_back(std::set<int>());
        return numVertices++; //return userID
    }

    void addEdge(int u, int v) {
        if (u < numVertices && v < numVertices) {
            adjList[u].insert(v);
            adjList[v].insert(u);
        }
    }

    const std::set<int>& getNeighbors(int u) const { //Friends of a user
        if (u < numVertices) {
            return adjList[u];
        }

        static const std::set<int> emptySet;
        return emptySet; //For Invalid USER ID
    }

    int getNumVertices() const {
        return numVertices;
    }

    int getDegreesOfSeparation(int startNode, int endNode) { //uses BFS
        if (startNode == endNode) return 0;

        std::queue<std::pair<int, int>> q; //{node, distance}
        std::map<int, int> distance; //For tracking visited nodes and distance

        q.push({startNode, 0});
        distance[startNode] = 0;

        while (!q.empty()) {
            std::pair<int, int> current = q.front();
            q.pop();
            int u = current.first;
            int dist = current.second;

            for (int v : adjList[u]) {
                if (distance.find(v) == distance.end()) {
                    if (v == endNode) {
                        return dist + 1;
                    }
                    distance[v] = dist + 1;
                    q.push({v, dist + 1});
                }
            }
        }
        return -1;
    }
};