Graph.cpp

// Graph.cpp

#include "Graph.hpp"
#include <iostream>
#include <limits>
#include <algorithm>

void Graph::addVertex(std::string label) {
    if (getVertexIndex(label) != -1) {
        std::cout << "Vertex \"" << label << "\" already exists.\n";
        return;
    }
    Vertex v;
    v.label = label;
    vertices.push_back(v);
    std::cout << "Added vertex \"" << label << "\".\n";
}

void Graph::removeVertex(std::string label) {
    int idx = getVertexIndex(label);
    if (idx == -1) {
        std::cout << "Vertex \"" << label << "\" does not exist.\n";
        return;
    }
    // Remove all edges pointing to this vertex
    for (auto &v : vertices) {
        if (v.label != label) {
            removeEdgeFromList(v.edges, label);
        }
    }
    // Erase the vertex
    vertices.erase(vertices.begin() + idx);
    std::cout << "Removed vertex \"" << label << "\" and its incident edges.\n";
}

void Graph::addEdge(std::string label1, std::string label2, unsigned long weight) {
    if (label1 == label2) {
        std::cout << "Cannot add a self‑loop on \"" << label1 << "\".\n";
        return;
    }
    int i1 = getVertexIndex(label1);
    int i2 = getVertexIndex(label2);
    if (i1 < 0 || i2 < 0) {
        std::cout << "One or both vertices do not exist.\n";
        return;
    }
    if (edgeExists(vertices[i1].edges, label2)) {
        std::cout << "Edge between \"" << label1 << "\" and \"" << label2 << "\" already exists.\n";
        return;
    }
    // Add undirected edge
    vertices[i1].edges.push_back(Edge{label2, weight});
    vertices[i2].edges.push_back(Edge{label1, weight});
    std::cout << "Added edge (" << label1 << "–" << label2 << ", weight=" << weight << ").\n";
}

void Graph::removeEdge(std::string label1, std::string label2) {
    int i1 = getVertexIndex(label1);
    int i2 = getVertexIndex(label2);
    if (i1 < 0 || i2 < 0) {
        std::cout << "One or both vertices do not exist.\n";
        return;
    }
    if (!edgeExists(vertices[i1].edges, label2)) {
        std::cout << "No edge exists between \"" << label1 << "\" and \"" << label2 << "\".\n";
        return;
    }
    removeEdgeFromList(vertices[i1].edges, label2);
    removeEdgeFromList(vertices[i2].edges, label1);
    std::cout << "Removed edge between \"" << label1 << "\" and \"" << label2 << "\".\n";
}

unsigned long Graph::shortestPath(std::string startLabel,
                                  std::string endLabel,
                                  std::vector<std::string> &path) {
    const unsigned long INF = std::numeric_limits<unsigned long>::max();
    int start = getVertexIndex(startLabel);
    int end   = getVertexIndex(endLabel);
    if (start < 0 || end < 0) {
        std::cout << "Start or end vertex does not exist.\n";
        return INF;
    }

    size_t n = vertices.size();
    std::vector<unsigned long> dist(n, INF);
    std::vector<int> prev(n, -1);
    std::vector<bool> used(n, false);

    dist[start] = 0;
    for (size_t iter = 0; iter < n; ++iter) {
        int u = -1;
        unsigned long best = INF;
        for (size_t i = 0; i < n; ++i) {
            if (!used[i] && dist[i] < best) {
                best = dist[i];
                u = int(i);
            }
        }
        if (u < 0) break;
        used[u] = true;
        if (u == end) break;

        for (auto &e : vertices[u].edges) {
            int v = getVertexIndex(e.dest);
            if (v >= 0 && !used[v] && dist[u] + e.weight < dist[v]) {
                dist[v] = dist[u] + e.weight;
                prev[v] = u;
            }
        }
    }

    if (dist[end] == INF) {
        std::cout << "No path exists from \"" << startLabel << "\" to \"" << endLabel << "\".\n";
        return INF;
    }

    // Reconstruct path
    path.clear();
    for (int at = end; at != -1; at = prev[at]) {
        path.push_back(vertices[at].label);
    }
    std::reverse(path.begin(), path.end());
    return dist[end];
}

void Graph::printGraph() const {
    std::cout << "Current Graph:\n";
    for (auto &v : vertices) {
        std::cout << v.label << ": ";
        for (auto &e : v.edges) {
            std::cout << "(" << e.dest << ", " << e.weight << ") ";
        }
        std::cout << "\n";
    }
}

int Graph::getVertexIndex(const std::string &label) const {
    for (size_t i = 0; i < vertices.size(); ++i) {
        if (vertices[i].label == label) return int(i);
    }
    return -1;
}

bool Graph::edgeExists(const std::vector<Edge> &edges,
                       const std::string &destLabel) const {
    for (auto &e : edges) {
        if (e.dest == destLabel) return true;
    }
    return false;
}

void Graph::removeEdgeFromList(std::vector<Edge> &edges,
                               const std::string &destLabel) {
    edges.erase(
      std::remove_if(edges.begin(), edges.end(),
                     [&](const Edge &e){ return e.dest == destLabel; }),
      edges.end());
}