main.cpp

// CSCI 411 Project Implementation
// main.cpp
// Brennan Watts
// Fall 2025


// For running this program, input is as follows:
// First line: vertices and edges (i.e. "5 7") where 5 is number of vertices and 7 is number of edges - int
// Next v lines: x and y coordinates for each vertex (i.e. "5 10") where 5 ix first x coordinate and 10 is first y coordinate - float
// Next e lines: edge vertices (i.e. "1 3") where 1 is from vertex and 3 is to vertex - int
// Last line: starting and ending vertex (i.e. "1 5") where 1 is starting vertex and 5 is ending vertex - int
// negative numbers and decimals work for coordinates, referring to vertices starts at 1 and not 0 in inputs
// Test cases are included which were generated from the test_generation.cpp file.
// There are 3 test cases with 5 vertices, 3 with 50 vertices, and 3 with 500 vertices.
// More can be created from the test_generation.cpp file



#include <iostream>
#include <vector>
#include <memory>
#include <climits>
#include <cmath>
#include <chrono>
using namespace std;

struct Node{
    int id;
    float dist;
    float x;
    float y;
    int priority;
};

struct Edge{
    shared_ptr<Node> from;
    shared_ptr<Node> to;
    float weight;
};


// finds the mininimum dist node in Q and removes that node from Q.
shared_ptr<Node> findMin(vector<shared_ptr<Node>>& Q){
    float min = numeric_limits<float>::infinity();
    int min_index = -1;
    for (int i = 0; i < Q.size(); i ++){
        if (Q[i]->dist < min){
            min = Q[i]->dist;
            min_index = i;
        }
    }

    if (min_index == -1){
        return nullptr;
    }

    // remove min node from Q
    shared_ptr<Node> min_node = Q[min_index];
    for (int i = min_index; i < Q.size() - 1; i ++){
        Q[i] = Q[i + 1];
    }
    Q.pop_back();
    return min_node;
}

// version of findMin for A* using f(n) instead of dist
shared_ptr<Node> findMinA(vector<shared_ptr<Node>>& Q, vector<float> f_score){
    float min = numeric_limits<float>::infinity();
    int min_index = -1;
    for (int i = 0; i < Q.size(); i ++){
        int id = Q[i]->id;
        if (f_score[id - 1] < min){
            min = f_score[id - 1];
            min_index = i;
        }
    }
    if (min_index == -1){
        return nullptr;
    }

    shared_ptr<Node> min_node = Q[min_index];
    for (int i = min_index; i < Q.size() - 1; i ++){
        Q[i] = Q[i + 1];
    }
    Q.pop_back();
    return min_node;
}

// Implementation of Dijkstra's algorithm
vector<shared_ptr<Node>> Dijkstra(vector<vector<shared_ptr<Edge>>> G, shared_ptr<Node> start){
    vector<shared_ptr<Node>> prev;
    vector<shared_ptr<Node>> Q;
    shared_ptr<Node> v;
    // initializations
    for (int i = 1; i < G.size(); i ++){
        G[0][i]->from->dist = numeric_limits<float>::infinity();
        prev.push_back(NULL);
        Q.push_back(G[0][i]->from);
    }
    start->dist = 0;
    // continue looping until Q is empty
    while (Q.size() > 0){
        v = findMin(Q);
        if (!v || !isfinite(v->dist)){
            break;
        }

        // check neighbors of min dist in Q
        for (int i = 0; i < G[v->id].size(); i ++){
            shared_ptr<Edge> e = G[v->id][i];
            float alt = (e->from->dist) + (e->weight);
            if (alt < e->to->dist){
                e->to->dist = alt;
                prev[e->to->id - 1] = e->from;
            }
        }
    }
    return prev;
}

// straight-line distance heuristic function
float heuristic(shared_ptr<Node> start, shared_ptr<Node> goal){
    return pow(pow(goal->y - start->y, 2) + pow(goal->x - start->x, 2), 0.5);
}

vector<shared_ptr<Node>> reconstruct_path(vector<shared_ptr<Node>> cameFrom, shared_ptr<Node> current){
    vector<shared_ptr<Node>> total_path;
    total_path.push_back(current);
    while (current != NULL){
        current = cameFrom[current->id - 1];
        if (current != NULL){
            total_path.push_back(current);
        }
    }
    return total_path;
}

// Implementation of A* Algorithm
vector<shared_ptr<Node>> A_Star(vector<vector<shared_ptr<Edge>>> G, shared_ptr<Node> start, shared_ptr<Node> goal){
    vector<shared_ptr<Node>> open_list;
    vector<shared_ptr<Node>> cameFrom(G.size() - 1);
    vector<float> g_score, f_score;

    // Initializations
    for (int i = 1; i < G.size(); i ++){
        G[0][i]->from->dist = numeric_limits<float>::infinity();
        g_score.push_back(numeric_limits<float>::infinity());
        f_score.push_back(numeric_limits<float>::infinity());
    }
    start->dist = 0;
    g_score[start->id - 1] = 0;
    f_score[start->id - 1] = heuristic(start, goal);
    open_list.push_back(start);

    // continue looping unitl open_list is empty
    while (open_list.size() > 0){
        shared_ptr<Node> current = findMinA(open_list, f_score);
        if (!current){
            return {};
        }
        current->dist = g_score[current->id - 1];
        // case where we've reached the goal node
        if (current == goal){
            return reconstruct_path(cameFrom, current);
        }
        // when goal node is not reached, calculate f_score for neighbors
        for (int i = 0; i < G[current->id].size(); i ++){
            shared_ptr<Edge> e = G[current->id][i];
            float tentative_gScore = g_score[current->id - 1] + e->weight;
            shared_ptr<Node> neighbor = e->to;
            if (tentative_gScore < g_score[neighbor->id - 1]){
                cameFrom[neighbor->id - 1] = current;
                g_score[neighbor->id - 1] = tentative_gScore;
                f_score[neighbor->id - 1] = g_score[neighbor->id - 1] + heuristic(neighbor, goal);
            }
            bool in_open = false;
            // adding neighbors to open_list if not already there
            for (int j = 0; j < open_list.size(); j ++){
                if (open_list[j]->id == neighbor->id){
                    in_open = true;
                    break;
                }
            }
            if (!in_open){
                open_list.push_back(neighbor);
            }
        }
    }
    return {};
}

int main(){
    chrono::high_resolution_clock::time_point start_time;
    chrono::high_resolution_clock::time_point end_time;
    
    // Input number of vertices and edges to file
    int n = -1, m = -1;
    cout << "Number of Vertices and Edges:" << endl;
    cin >> n >> m;
    vector<vector<shared_ptr<Edge>>> A(n+1);
    A[0].push_back(shared_ptr<Edge>(new Edge()));

    // Input X Y coordinates for each vertex
    // Used to calculate weight between each edge and for A* heuristic function
    float x, y;
    cout << "x/y coordinates of each Vertex:" << endl;
    for (int i = 1; i < n + 1; i ++){
        cin >> x >> y;
        shared_ptr<Node> v = shared_ptr<Node>(new Node());
        shared_ptr<Edge> e = shared_ptr<Edge>(new Edge());
        v->id = i;
        v->dist = numeric_limits<float>::infinity();
        v->x = x;
        v->y = y;
        e->from = v;
        e->to = v;
        e->weight = 0;
        A[0].push_back(e);
    }

    // Input Vertices of Each Edge
    int u = -1, v = -1;
    cout << "Edge Vertices:" << endl;
    for (int i = 0; i < m; i ++){
        cin >> u >> v;
        shared_ptr<Edge> e = shared_ptr<Edge>(new Edge());
        e->from = A[0][u]->from;
        e->to = A[0][v]->to;
        e->weight = pow(pow(e->to->y - e->from->y, 2) + pow(e->to->x - e->from->x, 2), 0.5);
        A[u].push_back(e);
    }

    // Input Starting and Ending Vertex
    int start = -1, end = -1;
    cout << "Starting and Ending Vertex:" << endl;
    cin >> start >> end;

    // Call Dijkstra's algorithm with timing directly before and after
    start_time = chrono::high_resolution_clock::now();
    vector<shared_ptr<Node>> d = Dijkstra(A, A[0][start]->from);
    end_time = chrono::high_resolution_clock::now();

    cout << "Dijkstra's Shortest distance from node " << start << " to node " << end << ": " << A[0][end]->from->dist << endl;
    cout << "Runtime:" << chrono::duration_cast<chrono::duration<double>>(end_time - start_time).count() << " seconds" << endl;

    // Call A* algorithm with timing directly before and after
    start_time = chrono::high_resolution_clock::now();
    vector<shared_ptr<Node>> a = A_Star(A, A[0][start]->from, A[0][end]->from);
    end_time = chrono::high_resolution_clock::now();

    cout << "A* Shortest distance from node " << start << " to node " << end << ": " << A[0][end]->from->dist << endl;
    cout << "Runtime:" << chrono::duration_cast<chrono::duration<double>>(end_time - start_time).count() << " seconds" << endl;
    return 0;
}