Skip to content

Instantly share code, notes, and snippets.

@IvanLuchkin

IvanLuchkin/LabFour_.idea_.name

Created May 11, 2019 11:28
Show Gist options
  • Save IvanLuchkin/a4d4327247d8747bf3bd11a2a34d8e11 to your computer and use it in GitHub Desktop.
Save IvanLuchkin/a4d4327247d8747bf3bd11a2a34d8e11 to your computer and use it in GitHub Desktop.
Download ZIP
Lab Four TA
Raw
LabFour_.idea_.name
untitled
Raw
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>
Raw
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>
Raw
LabFour_.idea_untitled.iml
<?xml version="1.0" encoding="UTF-8"?>
<module classpath="CMake" type="CPP_MODULE" version="4" />
Raw
LabFour_CMakeLists.txt
cmake_minimum_required(VERSION 3.14)
project(untitled)
set(CMAKE_CXX_STANDARD 14)
add_executable(untitled main.cpp Graph.h)
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment