Lab Four TA

LabFour_.idea_.name

untitled

LabFour_.idea_misc.xml

<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="CMakeWorkspace" PROJECT_DIR="$PROJECT_DIR$" />
  <component name="JavaScriptSettings">
    <option name="languageLevel" value="ES6" />
  </component>
</project>

LabFour_.idea_modules.xml

<?xml version="1.0" encoding="UTF-8"?>
<project version="4">
  <component name="ProjectModuleManager">
    <modules>
      <module fileurl="file://$PROJECT_DIR$/.idea/untitled.iml" filepath="$PROJECT_DIR$/.idea/untitled.iml" />
    </modules>
  </component>
</project>

LabFour_.idea_untitled.iml

<?xml version="1.0" encoding="UTF-8"?>
<module classpath="CMake" type="CPP_MODULE" version="4" />

LabFour_CMakeLists.txt

cmake_minimum_required(VERSION 3.14)
project(untitled)

set(CMAKE_CXX_STANDARD 14)

add_executable(untitled main.cpp Graph.h)

LabFour_main.cpp

#include <clocale>
#include<memory>
#include <map>
#include <memory>
#include <cmath>
#include <string>
#include <iostream>
#include<vector>
#include <climits>

template<typename T>
class MinPriorQueue
{
private:
    struct QElem {
        int id;
        T data;
        QElem(float id, T data) {
            this->id = id;
            this->data = data;
        };
    };
    std::vector<QElem*> queue;
    void siftDown(int ind) {
        int left = 2 * ind + 1,
                right = 2 * ind + 2,
                smallest = ind;
        if (left < this->queue.size() &&
            this->queue.at(left)->id < this->queue.at(ind)->id) {
            smallest = left;
        }
        if (right < this->queue.size() &&
            this->queue.at(right)->id < this->queue.at(smallest)->id) {
            smallest = right;
        }
        if (smallest != ind) {
            std::swap(this->queue.at(ind), this->queue.at(smallest));
            this->siftDown(smallest);
        }
    };
    void siftUp(int ind) {
        int parent;
        while (ind > 0) {
            parent = (ind - 1) / 2;
            if (this->queue.at(ind)->id >= this->queue.at(parent)->id)
                return;
            std::swap(this->queue.at(ind), this->queue.at(parent));
            ind = parent;
        }
    };
public:
    MinPriorQueue() {};
    MinPriorQueue(float prior, T data) {
        this->queue.push_back(new QElem(prior, data));
    };
    void push_back(float prior, T data) {
        this->queue.push_back(new QElem(prior, data));
        this->siftUp(this->queue.size() - 1);
    };
    T pop_front() {
        QElem *res = this->queue.at(0);
        this->queue.at(0) = this->queue.at(this->queue.size() - 1);
        this->queue.pop_back();
        if (!this->queue.empty()) {
            this->siftDown(0);
        }
        return res->data;
    };
    bool isEmpty() {
        return this->queue.empty();
    };
    void clear() {
        for (int i = 0; i < this->queue.size(); i++) {
            delete this->queue.at(i);
        }
        this->queue.clear();
    };
    int indexOf(T data) {
        for (int i = 0; i < this->queue.size(); i++) {
            if (this->queue.at(i)->data == data) return i;
        }
        return -1;
    };
    void print() {
        for (auto QElem : this->queue) {
            std::cout << QElem->data->name << "(" << QElem->id << ") ";
        }
    };
    ~MinPriorQueue() {
        this->clear();
    };
};


namespace Graph {
    struct Way {
        std::string begin;
        std::string end;
        std::vector<std::string> *road;
        int length;
        Way() {
            this->begin = "";
            this->end = "";
            this->road = new std::vector<std::string>();
            this->length = -1;
        }
        Way(std::string begin, std::string end, int length) {
            this->begin = begin;
            this->end = end;
            this->road = new std::vector<std::string>;
            this->length = length;
        }
        ~Way() {
            delete this->road;
        }
    };
    template<typename T>
    class Graph
    {
    protected:
        struct Vertex {
            std::string name;
            std::map<Vertex*, int> connections;
            bool checked;
            Vertex * fromWhere;
            int minWayLength;
            float latitude;
            float longtitude;
            Vertex() {
                this->name = "";
                this->checked = false;
                this->fromWhere = nullptr;
                this->minWayLength = INT_MAX;
                this->latitude = 0;
                this->longtitude = 0;
            }
            Vertex(std::string name, float latitude, float londtitude) {
                this->name = name;
                this->checked = false;
                this->fromWhere = nullptr;
                this->minWayLength = INT_MAX;
                this->latitude = latitude;
                this->longtitude = londtitude;
            }
        };

        std::map<std::string, Vertex*> vertices;

        std::shared_ptr<Way> formWay(std::string begin, std::string end, int length) {
            Vertex *finish = this->vertices.find(end)->second;
            std::shared_ptr<Way> way(new Way(begin, end, length));
            Vertex *prevOnWay = finish->fromWhere;
            while (prevOnWay != nullptr && prevOnWay->name != begin) {
                way->road->push_back(prevOnWay->name);
                prevOnWay = prevOnWay->fromWhere;
            }
            return way;
        };
        float toRad(float deg) {
            double PI = 3.14159265358979323846;
            return (deg * PI) / 180;
        };
    public:
        Graph() {};
        ~Graph() {
            this->clear();
        };
        void addVertex(std::string name, float latitude, float londtitude) {
            this->vertices.emplace(name, new Vertex(name, latitude, londtitude));
        };
        void removeVertex(std::string name) {
            auto vertexIter = this->vertices.find(name);
            if (vertexIter != this->vertices.end()) {
                for (auto vertex : this->vertices) {
                    vertex.second->connections.erase(vertexIter->second);
                }
                this->vertices.erase(vertexIter);
            }
        };
        void connect(std::string from, std::string to, int length) {
            auto iterFrom = this->vertices.find(from);
            auto iterTo = this->vertices.find(to);
            if (iterFrom != this->vertices.end() && iterTo != this->vertices.end()) {
                iterFrom->second->connections[iterTo->second] = length;
                iterTo->second->connections[iterFrom->second] = length;
            }
        };
        void disconnect(std::string from, std::string to) {
            auto iterFrom = this->vertices.find(from);
            auto iterTo = this->vertices.find(to);
            if (iterFrom != this->vertices.end()) {
                iterFrom->second->connections.erase(to);
                iterTo->second->connections.erase(from);
            }
        };
        void clear() {
            for (auto vertex : this->vertices) {
                delete vertex.second;
            }
        };
        std::shared_ptr<Way> findMinWayGreed(std::string from, std::string to) {
            auto start = this->vertices.find(from);
            auto finish = this->vertices.find(to);

            this->clearFields();
            Vertex *location = start->second,
                    *next;
            location->minWayLength = 0;
            MinPriorQueue<Vertex*> open;
            float HLength;
            while (location->name != to) {
                location->checked = true;
                for (auto link : location->connections) {
                    HLength = this->HFunc(link.first, finish->second);
                    if (!link.first->checked)
                        open.push_back(HLength, link.first);
                }
                if (open.isEmpty()) break;
                next = open.pop_front();
                next->fromWhere = location;
                next->minWayLength = location->minWayLength + location->connections.find(next)->second;
                location = next;
                open.clear();
            }
            if (location->name == to)
                return this->formWay(from, to, location->minWayLength);
            return this->findMinWayGreed(location->fromWhere->name, to);
        };
        std::shared_ptr<Way> findMinWayA(std::string from, std::string to) {
            auto start = this->vertices.find(from);
            auto finish = this->vertices.find(to);
            this->clearFields();
            Vertex *location = start->second;
            location->minWayLength = 0;
            float HLength = HFunc(start->second, finish->second);
            int length = 0;
            MinPriorQueue<Vertex*> open(HLength, location);
            while (!open.isEmpty()) {
                location = open.pop_front();
                if (location->name == to) {
                    return this->formWay(from, to, location->minWayLength);
                }
                location->checked = true;
                auto link = location->connections.begin();
                while (link != location->connections.end()) {
                    length = location->minWayLength + link->second;
                    if (link->first->minWayLength > length) {
                        link->first->fromWhere = location;
                        link->first->minWayLength = length;
                    }
                    if (!link->first->checked) {
                        HLength = HFunc(link->first, finish->second);
                        open.push_back(length + HLength, link->first);
                    }
                    ++link;
                }
            }
            return this->formWay(from, to, INT_MAX);
        };
        void clearFields() {
            for (auto vertex : this->vertices) {
                vertex.second->checked = false;
                vertex.second->fromWhere = nullptr;
                vertex.second->minWayLength = INT_MAX;
            }
        };
        float HFunc(Vertex* from, Vertex *to) {
            int R = 6371;
            float dLat = this->toRad(to->latitude - from->latitude);
            float dLon = this->toRad(to->longtitude - from->longtitude);
            float x = pow(sin(dLat / 2), 2) + cos(this->toRad(from->latitude))
                                              * cos(this->toRad(to->latitude)) * pow(sin(dLon / 2), 2);
            float y = 2 * atan2(sqrt(x), sqrt(1 - x));
            return R * y;
        };

        void print() {
            for (auto vertex : this->vertices) {
                std::cout << vertex.first << ":  ";
                for (auto link : vertex.second->connections) {
                    std::cout << link.first->name << "(" << link.second << ") ";
                }
                std::cout << std::endl;
            }
        };
        void printWay(std::shared_ptr<Way> way) {
            std::cout << way->begin << " -> ";
            for (int i = way->road->size() - 1; i >= 0; i--) {
                std::cout << way->road->at(i) << " -> ";
            }
            std::cout << way->end;
            if (way->length != INT_MAX)
                std::cout << " (Расстояние: " << way->length << " км)\n";
            else std::cout << " (Расстояние: UNKNOWN)\n";
        };

    };
}

int main()
{
    setlocale(LC_ALL, "ru");
    //SetConsoleCP(1251);
    //SetConsoleOutputCP(1251);
    Graph::Graph<std::string> g;
    g.addVertex("Porters", 13.20, 59.63);//
    g.addVertex("Bridgetown", 13.05, 59.37);//
    g.addVertex("Hoytes", 13.23, 59.58);//
    g.addVertex("Coach Hill", 13.17, 59.48);//
    g.addVertex("Long Bay", 13.12, 59.43);//
    g.addVertex("Hopefield", 13.09, 59.47);//
    g.addVertex("Carrington", 13.19, 59.56);//
    g.addVertex("Fustic", 13.28, 59.64);//
    g.addVertex("Speightstown", 13.25, 59.64);//
    g.addVertex("Greenland", 13.26, 59.57);//
    g.addVertex("Locust Hall", 13.14, 59.58);
    g.addVertex("Retreat", 13.32, 59.62);//
    g.addVertex("Haggat Hall", 13.11, 59.60);
    g.addVertex("Oistins", 13.04, 59.31);//
    g.addVertex("Swanns", 13.22, 59.59);


    g.connect("Porters", "Bridgetown", 14);
    g.connect("Porters", "Carrington", 10);
    g.connect("Porters", "Locust Hall", 17);
    g.connect("Porters", "Swanns", 11);
    g.connect("Porters", "Speightstown", 7);

    g.connect("Bridgetown", "Coach Hill", 20);
    g.connect("Bridgetown", "Fustic", 28);
    g.connect("Bridgetown", "Greenland", 24);
    g.connect("Bridgetown", "Oistins", 10);
    g.connect("Bridgetown", "Swanns", 20);

    g.connect("Hoytes", "Porters", 7);
    g.connect("Hoytes", "Carrington", 9);
    g.connect("Hoytes", "Retreat", 15);
    g.connect("Hoytes", "Haggat Hall", 13);
    g.connect("Hoytes", "Bridgetown", 10);

    g.connect("Coach Hill", "Swanns", 20);
    g.connect("Coach Hill", "Oistins", 18);
    g.connect("Coach Hill", "Greenland", 17);
    g.connect("Coach Hill", "Hopefield", 15);
    g.connect("Coach Hill", "Long Bay", 10);

    g.connect("Long Bay", "Carrington", 24);
    g.connect("Long Bay", "Fustic", 40);
    g.connect("Long Bay", "Haggat Hall", 17);
    g.connect("Long Bay", "Porters", 33);
    g.connect("Long Bay", "Bridgetown", 22);

    g.connect("Hopefield", "Porters", 28);
    g.connect("Hopefield", "Speightstown", 33);
    g.connect("Hopefield", "Retreat", 34);
    g.connect("Hopefield", "Oistins", 8);
    g.connect("Hopefield", "Greenland", 33);


    bool close = false;
    int oper;
    std::string start, end, st, ed;
    std::shared_ptr<Graph::Way> way;
    while (!close) {
        std::cout << "Выберите операцию:\n"
                  << "1. Поиск минимального пути с помощью алгоритма жадного алгоритма\n"
                  << "2. Поиск минимального пути с помощью алгоритма А*\n"
                  << "0. Закрыть\n";
        std::cout << "Операция: ";
        std::cin >> oper;
        switch (oper)
        {
            case 1:
                std::cout << "Введите город начала движения: ";
                std::cin >> start;
                std::cout << "Введите конечный город: ";
                std::cin >> end;
                try {
                    way = g.findMinWayGreed(start, end);
                }
                catch (std::exception &err) {
                    std::cout << err.what() << "\n\n";
                    break;
                }
                std::cout << "Путь, найденый жадным алгоритмом:\n";
                g.printWay(way);
                std::cout << std::endl;
                break;
            case 2:
                std::cout << "Введите город начала движения: ";
                std::cin >> start;
                std::cout << "Введите конечный город: ";
                std::cin >> end;
                try {
                    way = g.findMinWayA(start, end);
                }
                catch (std::exception &err) {
                    std::cout << err.what() << "\n\n";
                    break;
                }
                std::cout << "Путь, найденый алгоритмом А*:\n";
                g.printWay(way);
                g.print();
                std::cout << std::endl;
                break;
            case 0:
                close = true;
                break;
            default:
                std::cout << "Ошибка ввода!\n";
                break;
        }
    }
    return 0;
}