From 8b6a241faee1e0d9aac9281be7be883ba0332ac1 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Mon, 21 Sep 2020 15:44:37 +0200 Subject: Initial solution L3 --- labb3/tsp/src/Tour.cpp | 170 +++++++++++++++++++++++++++++++++++++++++++------ labb3/tsp/src/Tour.h | 31 +++++---- labb3/tsp/src/tsp.cpp | 23 +++++-- 3 files changed, 181 insertions(+), 43 deletions(-) (limited to 'labb3/tsp/src') diff --git a/labb3/tsp/src/Tour.cpp b/labb3/tsp/src/Tour.cpp index 2dc3fcc..135e10e 100644 --- a/labb3/tsp/src/Tour.cpp +++ b/labb3/tsp/src/Tour.cpp @@ -1,50 +1,180 @@ -// This is the .cpp file you will edit and turn in. -// We have provided a skeleton for you, -// but you must finish it as described in the spec. -// Also remove these comments here and add your own. -// TODO: remove this comment header +#include "Tour.h" #include -#include "Tour.h" #include "Node.h" #include "Point.h" Tour::Tour() -{ - // TODO: write this member -} + : first(nullptr) +{} Tour::~Tour() { - // TODO: write this member + if (!first) { + cout << "Empty tour" << endl; + return; + } + + // since node is freed, we need to keep track of next as well + Node *node = first; + Node *next = first->next; + do { + delete node; + node = next; + next = node->next; + } while (node != first); // do-while since `node == first` for the first node + + first = nullptr; } -void Tour::show() +void Tour::show() const { - // TODO: write this member + if (!first) { + cout << "Empty tour" << endl; + return; + } + + Node *node = first; + do { + cout << node << " " << node->next << endl; + node = node->next; + } while (node != first); // do-while since `node == first` for the first node } -void Tour::draw(QGraphicsScene *scene) +void Tour::draw(QGraphicsScene *scene) const { - // TODO: write this member + if (!first) { + cout << "Empty tour" << endl; + return; + } + + Node *node = first; + do { + node->point.drawTo(node->next->point, scene); + node = node->next; + } while (node != first); // do-while since `node == first` for the first node } -int Tour::size() +int Tour::size() const { - // TODO: write this member + if (!first) { + cout << "Empty tour" << endl; + return 0; + } + + int amount = 0; + Node *node = first; + do { + amount++; + node = node->next; + } while (node != first); // do-while since `node == first` for the first node + return amount; } -double Tour::distance() +double Tour::distance() const { - // TODO: write this member + if (!first) { + cout << "Empty tour" << endl; + return 0.0; + } + + double sum = 0.0; + Node *node = first; + do { + sum += node->point.distanceTo(node->next->point); + node = node->next; + } while (node != first); // do-while since `node == first` for the first node + return sum; } void Tour::insertNearest(Point p) { - // TODO: write this member + if (!first) { + // no current nodes + Node *node = new Node(p); + first = node; + node->next = node; + return; + } + if (first == first->next) { + // only one current node + Node *node = new Node(p, first); + first->next = node; + return; + } + + /* + * For each node, inserting a new node at p makes a triangle like below. + * We insert p in order to minimize d1. + * + * p ----* + * / \----* + * d1 / \----* d2 + * / \----* + * / \----* + * / \----* + * node ------------------------------------ next + * d0 + */ + double smallestDistance = first->point.distanceTo(p); // d1 + Node *node = first->next; + Node *smallestDistanceNode = first; // the node to insert this node after + while (node != first) { + double distance = node->point.distanceTo(p); + if (distance < smallestDistance) { + smallestDistance = distance; + smallestDistanceNode = node; + } + node = node->next; + } + Node *newNode = new Node(p, smallestDistanceNode->next); + smallestDistanceNode->next = newNode; } void Tour::insertSmallest(Point p) { - // TODO: write this member + if (!first) { + // no current nodes + Node *node = new Node(p); + first = node; + node->next = node; + return; + } + if (first == first->next) { + // only one current node + Node *node = new Node(p, first); + first->next = node; + return; + } + + /* + * For each node, inserting a new node at p makes a triangle like below. + * We insert p in order to minimize d1 + d2 - d0. + * + * p ----* + * / \----* + * d1 / \----* d2 + * / \----* + * / \----* + * / \----* + * node ------------------------------------ next + * d0 + */ + double smallestDiff = first->point.distanceTo(p) // d1 + + p.distanceTo(first->next->point) // d2 + - first->point.distanceTo(first->next->point); // d0 + Node *node = first->next; + Node *smallestDiffNode = first; // the node to insert this node after + do { + double diff = node->point.distanceTo(p) + + p.distanceTo(node->next->point) + - node->point.distanceTo(node->next->point); + if (diff < smallestDiff) { + smallestDiff = diff; + smallestDiffNode = node; + } + node = node->next; + } while (node != first); // do-while since `node == first` for the first node + Node *newNode = new Node(p, smallestDiffNode->next); + smallestDiffNode->next = newNode; } diff --git a/labb3/tsp/src/Tour.h b/labb3/tsp/src/Tour.h index 5262792..bb5166b 100644 --- a/labb3/tsp/src/Tour.h +++ b/labb3/tsp/src/Tour.h @@ -1,9 +1,9 @@ -// This is the .h file you will edit and turn in. -// We have provided a skeleton for you, -// but you must finish it as described in the spec. -// Also remove these comments here and add your own, as well as on the members. -// TODO: remove this comment header - +/* + * TDDD86 Lab 3b - gusso230 (group 11) + * This file contains the tour structure. + * You can insert points using two algorithms (nearest neighbour and smallest + * increase), get the total length of the tour and draw the tour. + */ #ifndef TOUR_H #define TOUR_H @@ -12,18 +12,17 @@ class Tour { public: - - Tour(); - ~Tour(); - void show(); - void draw(QGraphicsScene* scene); - int size(); - double distance(); - void insertNearest(Point p); - void insertSmallest(Point p); + Tour(); // create an empty tour + ~Tour(); // free all nodes + void show() const; // print the tour to stdout + void draw(QGraphicsScene *scene) const; // draw the tour on `scene` + int size() const; // return number of points on tour + double distance() const; // return total distance of tour + void insertNearest(Point p); // insert `p` using nearestNeighbour + void insertSmallest(Point p); // insert `p` using insertSmallest private: - + Node *first; // first node }; #endif // TOUR_H diff --git a/labb3/tsp/src/tsp.cpp b/labb3/tsp/src/tsp.cpp index 566bf7c..57de067 100644 --- a/labb3/tsp/src/tsp.cpp +++ b/labb3/tsp/src/tsp.cpp @@ -18,7 +18,16 @@ int main(int argc, char *argv[]) { QApplication a(argc, argv); - string filename = "tsp10.txt"; + // MY ADDITION + cout << "file: "; + string filename; + getline(cin, filename); + if (filename == "") { + filename = "tsp10.txt"; + } + // END OF ADDITION + + //string filename = "tsp100.txt"; ifstream input; input.open(filename); @@ -42,12 +51,12 @@ int main(int argc, char *argv[]) { double y; while (input >> x >> y) { Point p(x, y); - tour.insertNearest(p); - //uncomment the 4 lines below to animate - //tour.draw(scene); - //std::chrono::milliseconds dura(50); - //std::this_thread::sleep_for(dura); - //a.processEvents(); + tour.insertSmallest(p); + // uncomment the 4 lines below to animate + // tour.draw(scene); + // std::chrono::milliseconds dura(50); + // std::this_thread::sleep_for(dura); + // a.processEvents(); } input.close(); -- cgit v1.2.1