Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include <stdexcept>
#include <iostream>

using namespace std;

struct Pair {
    int first;
    int second;

    Pair(int f, int s) : first(f), second(s) {}
};

template<typename T>
struct ListNode {
    T data;
    ListNode* next;

    ListNode(T d) : data(d), next(nullptr) {}
};

template<typename T>
class List {
public:
    ListNode<T>* head;

    List() : head(nullptr) {}
    ~List() {
        clear();
    }

    void push_back(const T& value) {
        if (!head) {
            head = new ListNode<T>(value);
        } else {
            ListNode<T>* node = head;
            while (node->next) {
                node = node->next;
            }
            node->next = new ListNode<T>(value);
        }
    }

    void push_front(const T& value) {
        ListNode<T>* new_node = new ListNode<T>(value);
        new_node->next = head;
        head = new_node;
    }

    void erase(ListNode<T>* node) {
        if (!node) return;
        if (node == head) {
            head = head->next;
            delete node;
        } else {
            ListNode<T>* prev = head;
            while (prev && prev->next != node) {
                prev = prev->next;
            }
            if (prev) {
                prev->next = node->next;
                delete node;
            }
        }
    }

    void clear() {
        ListNode<T>* node = head;
        while (node) {
            ListNode<T>* temp = node;
            node = node->next;
            delete temp;
        }
        head = nullptr;
    }
    void print() const {
        ListNode<T>* node = head;
        while (node) {
            std::cout << node->data << " ";
            node = node->next;
        }
        std::cout << std::endl;
    }
    T get(int index) const {
        ListNode<T>* current = head;
        int count = 0;
        while (current != nullptr) {
            if (count == index) {
                return current->data;
            }
            current = current->next;
            count++;
        }
        throw std::out_of_range("Index out of bounds"); // Index out of valid range
    }
    int size() const {
        int count = 0;
        ListNode<T>* current = head;
        while (current != nullptr) {
            count++;
            current = current->next;
        }
        return count;
    }
};

template<typename K, typename V>
struct MapNode {
    K key;
    V value;
    MapNode* next;

    MapNode(K k, V v) : key(k), value(v), next(nullptr) {}
};

template<typename K, typename V>
class Map {
public:
    MapNode<K, V>* head;
    int count;

    Map() : head(nullptr) {}
    ~Map() {
        clear();
    }

    V& operator[](const K& key) {
        MapNode<K, V>* node = head;
        while (node) {
            if (node->key == key) {
                return node->value;
            }
            node = node->next;
        }
        // If not found, add new node
        V v{};
        MapNode<K, V>* newNode = new MapNode<K, V>(key, v);
        newNode->next = head;
        head = newNode;
        count++;
        return head->value;
    }

    const V& at(const K& key) const {
        const MapNode<K, V>* node = head;
        while (node) {
            if (node->key == key) {
                return node->value;
            }
            node = node->next;
        }
        throw out_of_range("Key not found");
    }

    void clear() {
        MapNode<K, V>* node = head;
        while (node) {
            MapNode<K, V>* temp = node;
            node = node->next;
            delete temp;
        }
        head = nullptr;
        count = 0;
    }
    int size() const {
        int size = 0;
        MapNode<K, V>* current = head;
        while (current) {
            size++;
            current = current->next;
        }
        return size;
    }

};

class Graph {
private:
    Map<int, List<Pair> > adjList;
    int numEdges;

    void DFS(int v, Map<int,bool>& visited);
    int minDistance(const Map<int, int>& dist, const Map<int, bool>& sptSet);
public:
    Graph();
    ~Graph();
    Pair getSize();
    bool insertEdge(int v1, int v2, int weight);
    bool deleteEdge(int v1, int v2);
    int findConnectedComponents();
    List<int> computeShortestPath(int v1, int v2);
    int computeSpanningTree();
};


#endif //UNTITLED4_GRAPH_H