Graph.cpp

// Graph.cpp
#include "Graph.h"
#include <iomanip>      // For std::setw
#include <queue>        // For std::priority_queue
#include <limits>       // For std::numeric_limits
#include <algorithm>    // For std::reverse, std::next_permutation
#include <map>          // Can be used if needed
#include <iostream>     // For std::cout, std::cerr
#include <set>          // For returning sets from helper functions
#include <sstream>      // For parsing node names in helper functions
#include <vector>       // For path vectors and priority queue underlying container

// Note: Removed 'using namespace std;'

Graph::Graph() : nextNodeId(0) {}

// --- Core Graph Functions ---

int Graph::getNodeId(const std::string& locationName) {
    if (locationToId.find(locationName) == locationToId.end()) {
        locationToId[locationName] = nextNodeId;
        idToLocation[nextNodeId] = locationName;
        nextNodeId++;
    }
    return locationToId[locationName];
}

void Graph::addEdge(const std::string& locationA, const std::string& locationB, double distance) {
    int idA = getNodeId(locationA);
    int idB = getNodeId(locationB);
    adjList[idA].push_back({idB, distance});
    adjList[idB].push_back({idA, distance});
}

int Graph::getNodeCount() {
    return nextNodeId;
}

void Graph::printGraph() {
    std::cout << "--- Ride-Sharing Map Graph ---" << std::endl;
    std::cout << "Total unique locations: " << getNodeCount() << std::endl << std::endl;

    for (const auto& mapPair : adjList) {
        int nodeId = mapPair.first;
        const std::list<Edge>& neighbors = mapPair.second;
        std::string locationName = idToLocation.at(nodeId);
        std::cout << "NODE: " << locationName << std::endl;

        for (const auto& edge : neighbors) {
            int neighborId = edge.first;
            double distance = edge.second;
            std::string neighborName = idToLocation.at(neighborId);
            std::cout << "  -> connects to " << std::setw(45) << std::left
                      << neighborName << " (" << distance << " km)" << std::endl;
        }
        std::cout << "---------------------------------" << std::endl;
    }
}

// --- Single Segment Dijkstra ---

// Pair for priority queue: <distance, nodeId>
using PqPair = std::pair<double, int>;

Graph::PathResult Graph::findShortestPath(const std::string& startLoc, const std::string& endLoc) {
    PathResult result;

    if (locationToId.find(startLoc) == locationToId.end()) {
        std::cerr << "Internal Error: Start location '" << startLoc << "' not found in graph!" << std::endl;
        return result;
    }
    if (locationToId.find(endLoc) == locationToId.end()) {
        std::cerr << "Internal Error: End location '" << endLoc << "' not found in graph!" << std::endl;
        return result;
    }

    int startId = locationToId.at(startLoc);
    int endId = locationToId.at(endLoc);

    std::priority_queue<PqPair, std::vector<PqPair>, std::greater<PqPair>> pq;
    std::unordered_map<int, double> dist;
    std::unordered_map<int, int> prev;

    for (const auto& mapPair : idToLocation) {
        int id = mapPair.first;
        dist[id] = std::numeric_limits<double>::infinity();
    }

    dist[startId] = 0;
    pq.push({0.0, startId});

    while (!pq.empty()) {
        double currentDist = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (currentDist > dist[u]) {
            continue;
        }
        if (u == endId) {
            break;
        }

        if (adjList.count(u)) {
            for (const auto& edge : adjList.at(u)) {
                int v = edge.first;
                double weight = edge.second;
                double newDist = dist[u] + weight;

                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.push({newDist, v});
                }
            }
        }
    }

    if (dist.at(endId) == std::numeric_limits<double>::infinity()) {
        return result; // Path not found
    }

    result.distance = dist.at(endId);
    int curr = endId;
    std::vector<std::string> reversed_path; // Build path reversed first

    while (prev.count(curr)) { // Check predecessor exists
         reversed_path.push_back(idToLocation.at(curr));
         curr = prev.at(curr);
         if (curr == startId) break; // Stop once we backtrack to start
    }
    reversed_path.push_back(startLoc); // Add start node

    // Use std::vector constructor for efficient reversal
    result.path = std::vector<std::string>(reversed_path.rbegin(), reversed_path.rend());

    return result;
}

// --- Multi-Point Dijkstra (Ride Sharing Route) ---

Graph::PathResult Graph::findShortestMultiPointPath(const std::string& startLoc,
                                                  const std::vector<std::string>& pickupLocs,
                                                  const std::string& endLoc) {
    PathResult finalResult; // Initialized to infinity distance, empty path

    // Handle the simple case directly
    if (pickupLocs.empty()) {
        return findShortestPath(startLoc, endLoc);
    }

    // 1. Create a list of all critical waypoints in order: Start, Pickups..., End
    std::vector<std::string> waypoints;
    waypoints.push_back(startLoc);
    waypoints.insert(waypoints.end(), pickupLocs.begin(), pickupLocs.end());
    waypoints.push_back(endLoc);

    // 2. Create indices representing the pickup points (1 to N)
    std::vector<int> p_indices(pickupLocs.size());
    for(size_t i = 0; i < pickupLocs.size(); ++i) {
        p_indices[i] = i + 1; // Index in 'waypoints' vector (0 is start, N+1 is end)
    }

    double minTotalDistance = std::numeric_limits<double>::infinity();
    std::vector<int> best_p_order = p_indices; // Store the best permutation order

    // 3. Iterate through all permutations of pickup point indices
    do {
        double currentPermutationDistance = 0.0;
        bool possiblePermutation = true;

        // --- Calculate distance for this specific order ---

        // a) Start to first pickup in current order
        PathResult segmentResult = findShortestPath(startLoc, waypoints[p_indices[0]]);
        if (segmentResult.distance == std::numeric_limits<double>::infinity()) {
            possiblePermutation = false;
        } else {
            currentPermutationDistance += segmentResult.distance;
        }

        // b) Between consecutive pickups in current order
        for (size_t i = 0; possiblePermutation && i < p_indices.size() - 1; ++i) {
            segmentResult = findShortestPath(waypoints[p_indices[i]], waypoints[p_indices[i+1]]);
            if (segmentResult.distance == std::numeric_limits<double>::infinity()) {
                possiblePermutation = false;
            } else {
                currentPermutationDistance += segmentResult.distance;
            }
        }

        // c) Last pickup to End destination
        if (possiblePermutation) {
            // Index of last pickup in 'waypoints' is p_indices.back()
            segmentResult = findShortestPath(waypoints[p_indices.back()], endLoc);
             if (segmentResult.distance == std::numeric_limits<double>::infinity()) {
                possiblePermutation = false;
            } else {
                currentPermutationDistance += segmentResult.distance;
            }
        }

        // --- Update best result if this permutation is shorter ---
        if (possiblePermutation && currentPermutationDistance < minTotalDistance) {
            minTotalDistance = currentPermutationDistance;
            best_p_order = p_indices; // Save this order
        }

    } while (std::next_permutation(p_indices.begin(), p_indices.end()));


    // 4. Reconstruct the final path using the best order found
    if (minTotalDistance != std::numeric_limits<double>::infinity()) {
        finalResult.distance = minTotalDistance;
        finalResult.path.clear(); // Ensure path is empty before building

        // a) Add path from Start to the first best pickup
        PathResult segment = findShortestPath(startLoc, waypoints[best_p_order[0]]);
        finalResult.path.insert(finalResult.path.end(), segment.path.begin(), segment.path.end());

        // b) Add paths between consecutive best pickups
        for (size_t i = 0; i < best_p_order.size() - 1; ++i) {
             // Find path from current pickup to next pickup in best order
             segment = findShortestPath(waypoints[best_p_order[i]], waypoints[best_p_order[i+1]]);
             // Append path, skipping the first element (which duplicates the previous end point)
             finalResult.path.insert(finalResult.path.end(), std::next(segment.path.begin()), segment.path.end());
        }

        // c) Add path from the last best pickup to the End
        // Index of last pickup in 'waypoints' is best_p_order.back()
        segment = findShortestPath(waypoints[best_p_order.back()], endLoc);
        // Append path, skipping the first element
        finalResult.path.insert(finalResult.path.end(), std::next(segment.path.begin()), segment.path.end());
    }
    // else: finalResult remains initialized to infinity/empty path, indicating no complete route found

    return finalResult;
}


// --- IMPLEMENTATIONS FOR HELPER FUNCTIONS (User Interaction) ---

std::set<std::string> Graph::getAllStates() const {
    std::set<std::string> states;
    for (const auto& pair : idToLocation) {
        const std::string& fullNodeName = pair.second;
        size_t firstComma = fullNodeName.find(',');
        if (firstComma != std::string::npos) {
            states.insert(fullNodeName.substr(0, firstComma));
        }
    }
    return states;
}

std::set<std::string> Graph::getCitiesInState(const std::string& state) const {
    std::set<std::string> cities;
    std::string statePrefix = state + ",";
    for (const auto& pair : idToLocation) {
        const std::string& fullNodeName = pair.second;
        if (fullNodeName.rfind(statePrefix, 0) == 0) { // Check if it starts with "State,"
            size_t firstComma = statePrefix.length();
            size_t secondComma = fullNodeName.find(',', firstComma);
            if (secondComma != std::string::npos) {
                cities.insert(fullNodeName.substr(firstComma, secondComma - firstComma));
            }
        }
    }
    return cities;
}

std::set<std::string> Graph::getLocationsInCity(const std::string& state, const std::string& city) const {
    std::set<std::string> locations;
    std::string cityPrefix = state + "," + city + ",";
    for (const auto& pair : idToLocation) {
        const std::string& fullNodeName = pair.second;
        if (fullNodeName.rfind(cityPrefix, 0) == 0) { // Check if it starts with "State,City,"
            locations.insert(fullNodeName.substr(cityPrefix.length()));
        }
    }
    return locations;
}

std::string Graph::formatLocationName(const std::string& fullNodeName) const {
     size_t lastComma = fullNodeName.find_last_of(',');
     if (lastComma != std::string::npos) {
         return fullNodeName.substr(lastComma + 1);
     }
     return fullNodeName; // Fallback
}