environment.cpp

#include "environment.h"

/**
 * @brief computes a driving-walking route
 *
 * @param graph data structure representing the city
 * @param drivingGraph similar to graph but with no walk-only edges
 * @param source id of source node
 * @param destination id of destination node
 * @param parkingNode id of parking node
 *
 * @return vector<vector<int>> containing all information about the route inside vectors (in order: drivingRoute, walkingRoute, drivingTime, walkingTime, parkingNode)
 * @complexity O((V + E) logV), dominated by dijkstra
 */
std::vector<std::vector<int>> findEnvironmentRoute(Graph<int> &graph, Graph<int> &drivingGraph, int source, int destination, int parkingNode) {
    std::vector<std::vector<int>> totalRoute;
    dijkstra(&drivingGraph, source);
    std::vector<int> drivingRoute=getPath(&drivingGraph, source, parkingNode);
    int drivingTime=drivingGraph.findVertex(parkingNode)->getDrivingDist();
    dijkstra(&graph,parkingNode);
    std::vector<int> walkingRoute=getPath(&graph,parkingNode,destination);
    int walkingTime=graph.findVertex(destination)->getWalkingDist();
    totalRoute.push_back(drivingRoute);
    totalRoute.push_back(walkingRoute);
    totalRoute.push_back(std::vector<int>{drivingTime});
    totalRoute.push_back(std::vector<int>{walkingTime});
    totalRoute.push_back(std::vector<int>{parkingNode});
    return totalRoute;
}

/**
 * @brief writes environmental route information in output.txt
 *
 * @param info tuple containing all route data
 * @complexity O(N), N being the length of driving + walking paths
 */
void outputEnvironmentRoute(std::tuple<int, int, int, std::vector<int>, std::vector<int>, int, int> info) {
    std::ofstream outputFile("output.txt");
    outputFile << "Source:" << std::get<0>(info) << std::endl;
    outputFile << "Destination:" << std::get<1>(info) << std::endl;
    outputFile << "DrivingRoute:";
    for (int i=0; i<std::get<3>(info).size(); i++) {
        outputFile << std::get<3>(info)[i];
        if (i<std::get<3>(info).size()-1) {
            outputFile << ",";
        }
    }
    outputFile << "(" << std::get<5>(info) << ")" << std::endl;
    outputFile << "ParkingNode:" << std::get<2>(info) << std::endl;
    outputFile << "WalkingRoute:";
    for (int i=0; i<std::get<4>(info).size(); i++) {
        outputFile << std::get<4>(info)[i];
        if (i<std::get<4>(info).size()-1) {
            outputFile << ",";
        }
    }
    outputFile << "(" << std::get<6>(info) << ")" << std::endl;
    outputFile << "TotalTime:" << std::get<5>(info)+std::get<6>(info) <<std::endl;
}

/**
 * @brief outputs the data of the two approximate solutions in output.txt
 *
 * @param first Path of first route
 * @param second Path of second route
 * @param source id of source node
 * @param destination id of destination node
 * @param firstParkingNode id of the parking node of the first route
 * @param secondParkingNode id of the parking node of the second route
 * @param firstTotalTime time to traverse the first route
 * @param secondTotalTime time to traverse the second route
 * @complexity O(N), N being the total length of both routes
 */
void outputApproximateRoutes(std::vector<std::vector<int>> first, std::vector<std::vector<int>> second, int source, int destination, int firstParkingNode, int secondParkingNode, int firstTotalTime, int secondTotalTime) {
    std::ofstream outputFile("output.txt");
    outputFile << "Source:" << source << std::endl;
    outputFile << "Destination:" << destination << std::endl;
    outputFile << "DrivingRoute:" << std::endl;
    outputFile << "ParkingNode:" << std::endl;
    outputFile << "WalkingRoute:" << std::endl;
    outputFile << "Total Time:" << std::endl;
    outputFile << "Message:No possible route with max. walking time of 5 minutes." << std::endl;
    outputFile << std::endl;
    outputFile << "DrivingRoute1:";
        for (int i=0; i<first[0].size(); i++) {
            outputFile << first[0][i];
            if (i<first[0].size()-1) {
                outputFile << ",";
            }
        }
        outputFile << "(" << first[2][0] << ")" << std::endl;
        outputFile << "ParkingNode1:" << firstParkingNode << std::endl;
        outputFile << "WalkingRoute1:";
        for (int i=0; i<first[1].size(); i++) {
            outputFile << first[1][i];
            if (i<first[1].size()-1) {
                outputFile << ",";
            }
        }
        outputFile << "(" << first[3][0] << ")" << std::endl;
        outputFile << "TotalTime1:" << firstTotalTime <<std::endl;
        outputFile << "DrivingRoute2:";
        for (int i=0; i<second[0].size(); i++) {
            outputFile << second[0][i];
            if (i<second[0].size()-1) {
                outputFile << ",";
            }
        }
        outputFile << "(" << second[2][0] << ")" << std::endl;
        outputFile << "ParkingNode2:" << secondParkingNode << std::endl;
        outputFile << "WalkingRoute2:";
        for (int i=0; i<second[1].size(); i++) {
            outputFile << second[1][i];
            if (i<second[1].size()-1) {
                outputFile << ",";
            }
        }
        outputFile << "(" << second[3][0] << ")" << std::endl;
        outputFile << "TotalTime2:" << secondTotalTime <<std::endl;
}

/**
 * @brief creates city graph without walk-only edges
 *
 * @return graph representing the city but with no walking-only edges
 * @complexity O(V + E), time for copying the graph with V vertices and E edges
 */
Graph<int> drivingGraphGenerator(Graph<int> &graph) {
    Graph<int> drivingGraph=graph;
    for (auto v : drivingGraph.getVertexSet()) {
        for (auto e : v->getAdj()) {
            if (e->getDrivingWeight()==0.0) {
                drivingGraph.removeEdge(e->getOrig()->getInfo(),e->getDest()->getInfo());
            }
        }
    }
    return drivingGraph;
}

/**
 * @brief removes user specified nodes from the graph
 *
 * @param graph data structure representing the city
 * @param nodesToRemove string enunciating the nodes to remove
 * @complexity O(N + VlogV), N time for parsing the input string and VlogV for removing the nodes
 */
void removeNodesEnvironment(Graph<int> &graph, const std::string& nodesToRemove) {
    std::vector<int> avoidNodes;
    std::stringstream ss(nodesToRemove);
    std::string token;
    while (std::getline(ss, token, ',')) {
        avoidNodes.push_back(std::stoi(token));
    }
    for (auto id : avoidNodes) {
        graph.removeVertex(id);
    }
}

/**
 * @brief removes user specified edges from the graph
 *
 * @param graph data structure representing the city
 * @param edgesToRemove string enunciating the edges to remove
 * @commpplexity O(N + ElogV), same as removeNodesEnvironment but for edges
 */
void removeEdgesEnvironment(Graph<int> &graph, const std::string& edgesToRemove) {
    std::vector<std::string> avoidEdges;
    std::vector<std::vector<int>> edgesToAvoid;
    std::stringstream ass(edgesToRemove);
    std::string atoken;
    while (std::getline(ass,atoken,')')) {
        size_t start=atoken.find('(');
        if (start!=std::string::npos) {
            avoidEdges.push_back(atoken.substr(start)+")");
        }
    }
    for (int i=0; i<avoidEdges.size(); i++) {
        std::vector<int> idEdge;
        size_t start = avoidEdges[i].find('(');
        size_t end = avoidEdges[i].find(')');
        std::string ids=avoidEdges[i].substr(start+1,end-start-1);
        std::stringstream bss(ids);
        std::string value;
        while (std::getline(bss, value, ',')) {
            idEdge.push_back(std::stoi(value));  // Convert each value to an integer
        }
        edgesToAvoid.push_back(idEdge);
    }
    for (auto elem : edgesToAvoid) {
        graph.removeEdge(elem[0],elem[1]);
        graph.removeEdge(elem[1],elem[0]);
    }
}

/**
 * @brief gets values from data, calls function to modify the graph accordingly, dijkstra and output function
 *
 * @param graph data structure representing the city
 * @param data stores the input values and their meaning, in a value - key relation
 * @complexity O(N + VlogV + E logV), as it depends on the two functions it calls
 */
void modifyGraphEnvironment(Graph<int> &graph, std::map<std::string, std::string> data) {
    if (data["AvoidNodes"]!="") {
        removeNodesEnvironment(graph, data["AvoidNodes"]);
    }
    if (data["AvoidSegments"]!="") {
        removeEdgesEnvironment(graph,data["AvoidSegments"]);
    }
}

/**
 * @brief gets values from data, calls function to modify the graph accordingly, dijkstra, checks if path exists and calls functions to compute the path or the approximate paths and ouput them
 *
 * @param data stores the input values and their meaning, in a value - key relation
 * @param data structure representing the city
 * @complexity O((V + E) logV), in case it finds the best route in the first time, O((V + E) logV + N + VlogV + ElogV) otherwise because it has to go through all the function calls
 */
void mainEnvironment(std::map<std::string, std::string> data, Graph<int> &graph) {
    ///Separate graph with no walking-only edges in order to compute drivingPath
    Graph<int> drivingGraph=drivingGraphGenerator(graph);
    int source=std::stoi(data["Source"]);
    int destination=std::stoi(data["Destination"]);
    int maxWalkTime=std::stoi(data["MaxWalkTime"]);
    modifyGraphEnvironment(graph, data);
    dijkstra(&graph, destination);
    std::vector<int> candidateNodes;
    for (auto v : graph.getVertexSet()) {
        ///Get possible parking nodes ("candidates").
        if (v->hasParking() && v->getInfo()!=destination && v->getInfo()!=source) {
            candidateNodes.push_back(v->getInfo());
        }
    }
    ///Sort parking nodes by ascending order of the difference between the walking time from them to the destination and the max walk time defined by the user
    sort(candidateNodes.begin(), candidateNodes.end(),
        [&graph, maxWalkTime](int v1, int v2) {
            return abs(graph.findVertex(v1)->getWalkingDist() - maxWalkTime) < abs(graph.findVertex(v2)->getWalkingDist() - maxWalkTime);
        });
    ///If that difference for the first "candidate" parking node is positive then the walking time from all "candidates" to the destination is bigger than the max walk time and there´s no solution.
    if (graph.findVertex(candidateNodes[0])->getWalkingDist()-maxWalkTime>0) {
        ///Get the two most approximate solutions.
        std::vector<std::vector<int>> approximatePath1=findEnvironmentRoute(graph, drivingGraph,source,destination,candidateNodes[0]);
        std::vector<std::vector<int>> approximatePath2=findEnvironmentRoute(graph,drivingGraph,source,destination,candidateNodes[1]);
        std::vector<std::vector<std::vector<int>>> twoRoutes;
        twoRoutes.push_back(approximatePath1);
        twoRoutes.push_back(approximatePath2);
        //Sort the routes by ascending order of their total traversal times in order to find the order for them to be printed in the output
        sort(twoRoutes.begin(), twoRoutes.end(),[](std::vector<std::vector<int>> p1, std::vector<std::vector<int>> p2){
            int sump1=p1[2][0]+p1[3][0];
            int sump2=p2[2][0]+p2[3][0];
            if (sump1==sump2) {
                return p1[3][0]>p2[3][0];
            }
            return sump1<sump2;
        });
        outputApproximateRoutes(twoRoutes[0], twoRoutes[1], source, destination, twoRoutes[0][4][0], twoRoutes[1][4][0], twoRoutes[0][2][0]+twoRoutes[0][3][0], twoRoutes[1][2][0]+twoRoutes[1][3][0]);
    }
    else{
        dijkstra(&drivingGraph, source);
        ///Tuple containing source, destination, drivingRoute, walkingRoute, drivingTime and walkingTime (in order).
        std::vector<std::tuple<int, int, int, std::vector<int>, std::vector<int>, int, int>> routeInfo;
        for (auto v : candidateNodes) {
            dijkstra(&graph, v);
            if (graph.findVertex(destination)->getWalkingDist()) {
                routeInfo.push_back(std::make_tuple(source,destination,v,getPath(&drivingGraph, source, v),getPath(&graph, v, destination),drivingGraph.findVertex(v)->getDrivingDist(),graph.findVertex(destination)->getWalkingDist()));
            }
        }
        ///Sort the routes by ascending order of their total traversal times
        std::sort(routeInfo.begin(), routeInfo.end(),
                [](const auto &a, const auto &b) {
                    int sumA = std::get<5>(a) + std::get<6>(a);
                    int sumB = std::get<5>(b) + std::get<6>(b);
                    ///If two routes have the same total traversal time, sort them by descending order of their walking time.
                    if (sumA == sumB) {
                        return std::get<5>(a) > std::get<5>(b);
                    }
                    return sumA<sumB;
                });
        ///Output the one with the best time.
        outputEnvironmentRoute(routeInfo[0]);
        }
    }