Graph.cpp

#include "Graph.h"
#include <climits>

Graph ::Graph() : numEdges(0) {}

Graph :: ~Graph() {}

Pair Graph::getSize() {
    int vertexCount = 0;
    MapNode<int, List<Pair>>* node = adjList.head;

    // Iterate over the map to count the vertices
    while (node != nullptr) {
        vertexCount++;
        node = node->next;
    }

    // Return the vertex count and edge count as a Pair
    return Pair(vertexCount, numEdges);
}

// Insert an edge into the graph
bool Graph::insertEdge(int v1, int v2, int weight) {
    // Ensure both vertices exist in the adjacency list, or add them if they don't
    if (adjList[v1].head == nullptr) {
        adjList[v1] = List<Pair>();  // Create a new list of edges for vertex v1 if it doesn't exist
    }
    if (adjList[v2].head == nullptr) {
        adjList[v2] = List<Pair>();  // Create a new list of edges for vertex v2 if it doesn't exist
    }

    // Check if an edge already exists from v1 to v2
    ListNode<Pair>* current = adjList[v1].head;
    while (current != nullptr) {
        if (current->data.first == v2) {
            return false;  // Edge already exists, return false
        }
        current = current->next;
    }

    // If the edge does not exist, add it to both v1's and v2's lists
    adjList[v1].push_back(Pair(v2, weight));
    adjList[v2].push_back(Pair(v1, weight));  // Since the graph is undirected
    numEdges++;  // Increment the number of edges
    return true;  // Edge added successfully, return true
}

// Delete an edge from the graph
bool Graph::deleteEdge(int v1, int v2) {
    bool removedFromV1 = false, removedFromV2 = false;

    // Helper function to remove an edge from a list if it exists
    auto removeEdge = [](List<Pair>& list, int vertex, bool& removed) {
        ListNode<Pair>* current = list.head;
        ListNode<Pair>* prev = nullptr;
        while (current != nullptr) {
            if (current->data.first == vertex) {
                if (prev == nullptr) { // Edge is at the head of the list
                    list.head = current->next;
                } else {
                    prev->next = current->next;
                }
                delete current;
                removed = true;  // Mark as removed
                return;
            }
            prev = current;
            current = current->next;
        }
    };

    // Remove edge from v1's list pointing to v2
    if (adjList[v1].head != nullptr) {
        removeEdge(adjList[v1], v2, removedFromV1);
    }

    // Remove edge from v2's list pointing to v1
    if (adjList[v2].head != nullptr) {
        removeEdge(adjList[v2], v1, removedFromV2);
    }

    // If an edge was successfully removed, decrement the number of edges
    if (removedFromV1 || removedFromV2) {
        numEdges--;
        return true;  // Edge removed successfully
    }

    return false;  // No edge was removed
}

// Helper function to perform DFS
void Graph::DFS(int v, Map<int, bool>& visited) {
    visited[v] = true;  // Mark the current node as visited

    // Get the adjacency list of the current vertex
    List<Pair>& edges = adjList[v];
    ListNode<Pair>* current = edges.head;
    while (current != nullptr) {
        int neighbor = current->data.first;
        if (!visited[neighbor]) {  // If not visited, recurse on the neighbor
            DFS(neighbor, visited);
        }
        current = current->next;
    }
}

// Function to find the number of connected components in the graph
int Graph::findConnectedComponents() {
    int count = 0;
    Map<int, bool> visited;  // Custom map to track visited vertices

    // Initialize visited map for all vertices
    MapNode<int, List<Pair>>* node = adjList.head;
    while (node != nullptr) {
        visited[node->key] = false;
        node = node->next;
    }

    // Iterate through all vertices and perform DFS if not visited
    node = adjList.head;
    while (node != nullptr) {
        if (!visited[node->key]) {  // If a vertex is not visited, it's a new component
            DFS(node->key, visited);
            count++;  // Increase the count of connected components
        }
        node = node->next;
    }

    return count;
}

int Graph::minDistance(const Map<int, int>& dist, const Map<int, bool>& sptSet) {
    int min = INT_MAX, min_index = -1;

    MapNode<int, int>* node = dist.head;
    while (node != nullptr) {
        if (!sptSet.at(node->key) && node->value < min) {
            min = node->value;
            min_index = node->key;
        }
        node = node->next;
    }
    return min_index;
}


// Function to compute the shortest path using Dijkstra's algorithm
List<int> Graph::computeShortestPath(int v1, int v2) {
    Map<int, int> dist;     // Distance values used to pick the minimum weight edge in cut
    Map<int, int> pred;     // Predecessors
    Map<int, bool> sptSet;  // sptSet[v] will be true if vertex v is included in shortest path tree

    // Initialize all distances as INFINITE and stpSet[] as false
    MapNode<int, List<Pair>>* node = adjList.head;
    while (node != nullptr) {
        dist[node->key] = INT_MAX;
        pred[node->key] = -1;
        sptSet[node->key] = false;
        node = node->next;
    }

    // Distance of source vertex from itself is always 0
    dist[v1] = 0;

    // Find shortest path for all vertices
    for (int count = 0; count < adjList.size() - 1; count++) {
        // Pick the minimum distance vertex from the set of vertices not yet processed
        int u = minDistance(dist, sptSet);

        // Mark the picked vertex as processed
        sptSet[u] = true;

        // Update dist value of the adjacent vertices of the picked vertex.
        ListNode<Pair>* edgeNode = adjList[u].head;
        while (edgeNode != nullptr) {
            int v = edgeNode->data.first;
            int weight = edgeNode->data.second;

            if (!sptSet[v] && dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pred[v] = u;
            }
            edgeNode = edgeNode->next;
        }
    }

    // Store the path from v1 to v2
    List<int> path;
    if (dist[v2] == INT_MAX) {
        return path; // return empty path if no path exists
    }

    for (int at = v2; at != 0 && at!=-1; at = pred[at]) {
        path.push_front(at);
    }

    return path;
}

int Graph ::computeSpanningTree() {
    if (adjList.head == nullptr) return 0; // Empty graph

    Map<int, bool> inMST; // Tracks whether a vertex is in the MST
    Map<int, int> key;   // Key values used to pick minimum weight edge in cut
    Map<int, int> parent; // To store the resulting MST, if needed

    // Initialize keys as infinite and inMST as false for all vertices
    MapNode<int, List<Pair>>* node = adjList.head;
    while (node) {
        key[node->key] = INT_MAX;
        inMST[node->key] = false;
        parent[node->key] = -1;
        node = node->next;
    }

    // Start from the first vertex (arbitrary choice)
    key[adjList.head->key] = 0;
    parent[adjList.head->key] = -1; // First node is root of MST

    // The MST will have V vertices
    int totalWeight = 0;
    for (int count = 0; count < adjList.size(); count++) {
        // Pick the minimum key vertex from the set of vertices not yet included in MST
        int u = -1;
        int min = INT_MAX;
        MapNode<int, bool>* tempNode = inMST.head;
        while (tempNode) {
            if (!tempNode->value && key[tempNode->key] < min) {
                min = key[tempNode->key];
                u = tempNode->key;
            }
            tempNode = tempNode->next;
        }

        // Add the picked vertex to the MST Set
        inMST[u] = true;
        totalWeight += key[u];

        // Update key value and parent index of the adjacent vertices of the picked vertex.
        // Consider only those vertices which are not yet included in MST
        ListNode<Pair>* edgeNode = adjList[u].head;
        while (edgeNode != nullptr) {
            int v = edgeNode->data.first;
            int weight = edgeNode->data.second;
            if (!inMST[v] && weight < key[v]) {
                parent[v] = u;
                key[v] = weight;
            }
            edgeNode = edgeNode->next;
        }
    }

    return totalWeight; // Return the weight of the MST
}