add tsp codeL3

8 files changed, 450 insertions, 0 deletions

diff --git a/labb3/tsp/TSP.pro b/labb3/tsp/TSP.pro
new file mode 100644
index 0000000..a63cef6
--- /dev/null
+++ b/labb3/tsp/TSP.pro
@@ -0,0 +1,40 @@
+QT += widgets
+SOURCES = $$PWD/src/*.cpp
+#SOURCES += $$PWD/lib/*.cpp
+HEADERS = $$PWD/src/*.h
+#HEADERS += $$PWD/lib/*.h
+
+QMAKE_CXXFLAGS += -std=c++11
+
+INCLUDEPATH += $$PWD/lib/
+
+# Copies the given files to the destination directory
+defineTest(copyToDestdir) {
+    files = $$1
+
+    for(FILE, files) {
+        DDIR = $$OUT_PWD
+
+        # Replace slashes in paths with backslashes for Windows
+        win32:FILE ~= s,/,\\,g
+        win32:DDIR ~= s,/,\\,g
+
+        !win32 {
+            QMAKE_POST_LINK += cp -r '"'$$FILE'"' '"'$$DDIR'"' $$escape_expand(\\n\\t)
+        }
+        win32 {
+            QMAKE_POST_LINK += xcopy '"'$$FILE'"' '"'$$DDIR'"' /e /y $$escape_expand(\\n\\t)
+        }
+    }
+
+    export(QMAKE_POST_LINK)
+}
+!win32 {
+    copyToDestdir($$files($$PWD/res/*))
+}
+win32 {
+    copyToDestdir($$PWD/res)
+}
+macx {
+    cache()
+}
diff --git a/labb3/tsp/src/Node.cpp b/labb3/tsp/src/Node.cpp
new file mode 100644
index 0000000..3b7697b
--- /dev/null
+++ b/labb3/tsp/src/Node.cpp
@@ -0,0 +1,32 @@
+/*
+ * TDDD86 TSP
+ * This file contains the implementation of the Node structure.
+ * See Node.h for comments about each member.
+ * Your code should work properly with an unmodified version of this file.
+ */
+
+#include <iomanip>
+#include <iostream>
+#include <sstream>
+#include "Node.h"
+
+Node::Node(Point p, Node* _next)
+    : point(p.x, p.y), next(_next) {}
+
+string Node::toString() const {
+    stringstream out;
+    out << "Node{addr=" << ((void*) this);
+    out << ", point=" << point;
+    if (next != nullptr) {
+        out << ", next=" << ((void*) next);
+    } else {
+        out << ", next=nullptr";
+    }
+    out << "}";
+    return out.str();
+}
+
+ostream& operator <<(ostream& out, const Node& node) {
+    out << node.toString();
+    return out;
+}
diff --git a/labb3/tsp/src/Node.h b/labb3/tsp/src/Node.h
new file mode 100644
index 0000000..f9908e4
--- /dev/null
+++ b/labb3/tsp/src/Node.h
@@ -0,0 +1,47 @@
+/*
+ * TDDD86 TSP
+ * This file contains the declaration of the Node structure.
+ * See Node.cpp for implementation of each member.
+ * Your code should work properly with an unmodified version of this file.
+ */
+
+#ifndef NODE_H
+#define NODE_H
+
+#include <iostream>
+#include "Point.h"
+using namespace std;
+
+/*
+ * Each Node structure represents a single node in a circular linked list
+ * used in a TSP tour.
+ */
+struct Node {
+    Point point;     // this nodes point
+    Node* next;      // pointer to next node in the list  (nullptr if none)
+
+    /*
+     * Constructs a new node storing the given point and next pointer.
+     */
+    Node(Point p, Node* _next = nullptr);
+
+    /*
+     * Returns a string representation of the Node for debugging, such as
+     * "Node{addr=0x7e83f4, point=(2.5, 3.5), next=0x43b2a0}".
+     *
+     * Note that the toString output includes the node's memory address, as well
+     * as the memory address where its next pointer points.
+     *
+     * Keep in mind that toString won't be called if you try to print a Node*.
+     * You must print the node itself.
+     */
+    string toString() const;
+};
+
+/*
+ * Outputs the given node to the given output stream (e.g. cout) in the same
+ * format as returned by its toString member function.
+ */
+ostream& operator <<(ostream& out, const Node& node);
+
+#endif // END NODE_H
diff --git a/labb3/tsp/src/Point.cpp b/labb3/tsp/src/Point.cpp
new file mode 100644
index 0000000..bb3a87d
--- /dev/null
+++ b/labb3/tsp/src/Point.cpp
@@ -0,0 +1,50 @@
+/*
+ * TDDD86 TSP
+ * This file contains the implementation of the Point structure.
+ * See Point.h for comments about each member.
+ * Your code should work properly with an unmodified version of this file.
+ */
+
+#include <iomanip>
+#include <iostream>
+#include <sstream>
+#include <cmath>
+#include <QGraphicsEllipseItem>
+#include <QGraphicsLineItem>
+#include "Point.h"
+
+Point::Point(double _x, double _y)
+    : x(_x), y(_y) {}
+
+double Point::distanceTo(Point that) const
+{
+    double dx = x - that.x;
+    double dy = y - that.y;
+    return std::sqrt(dx*dx + dy*dy);
+}
+
+void Point::draw(QGraphicsScene *scene) const
+{
+    QGraphicsEllipseItem *item = new QGraphicsEllipseItem(x, y, 1, 1);
+    item->setBrush(QBrush(QColor(255, 0, 0)));
+    scene->addItem(item);
+}
+
+void Point::drawTo(Point that, QGraphicsScene *scene) const
+{
+    QGraphicsLineItem *item = new QGraphicsLineItem(x, y, that.x, that.y);
+    scene->addItem(item);
+}
+
+string Point::toString() const
+{
+    stringstream string;
+    string << "(" << std::fixed << std::setprecision(1) << std::showpoint
+        << x << ", " << y << ")";
+    return string.str();
+}
+
+ostream& operator <<(ostream& out, const Point& p) {
+    out << p.toString();
+    return out;
+}
diff --git a/labb3/tsp/src/Point.h b/labb3/tsp/src/Point.h
new file mode 100644
index 0000000..e0d0f31
--- /dev/null
+++ b/labb3/tsp/src/Point.h
@@ -0,0 +1,53 @@
+/*
+ * TDDD86 TSP
+ * This file contains the declaration of the Point structure.
+ * See Point.cpp for implementation of each member.
+ * Your code should work properly with an unmodified version of this file.
+ */
+
+#ifndef POINT_H
+#define POINT_H
+
+#include <iostream>
+#include <string>
+#include <QGraphicsScene>
+using namespace std;
+
+/*
+ * Each Point structure represents a single point in the Euclidean plane.
+ */
+struct Point {
+    const double x; // x position of point
+    const double y; // y position of point
+
+    Point(double _x, double _y);
+
+    /*
+     * Returns Euclidean distance between this point and that.
+     */
+    double distanceTo(Point that) const;
+
+    /*
+     * Draws the point onto the given QGraphicsScene.
+     */
+    void draw(QGraphicsScene* scene) const;
+
+    /*
+     * Draws the line from this point to that onto the given QGraphicsScene.
+     */
+    void drawTo(Point that, QGraphicsScene* scene) const;
+
+    /*
+     * Returns a string representation of the point, such as
+     * (2.5, 3.5).
+     */
+    string toString() const;
+};
+
+/*
+ * Outputs the given point to the given output stream (e.g. cout) in the same
+ * format as returned by its toString member function.
+ */
+ostream& operator<<(ostream& out, const Point& p);
+
+#endif // POINT_H
diff --git a/labb3/tsp/src/Tour.cpp b/labb3/tsp/src/Tour.cpp
new file mode 100644
index 0000000..8f5dd99
--- /dev/null
+++ b/labb3/tsp/src/Tour.cpp
@@ -0,0 +1,143 @@
+#include <iostream>
+#include "Tour.h"
+#include "Node.h"
+#include "Point.h"
+
+Tour::Tour() : first(nullptr)
+{ }
+
+Tour::~Tour()
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return;
+    }
+    Node *node = first;
+    Node *next = first->next;
+    do {
+        delete node;
+        node = next;
+        next = node->next;
+    }
+    while (node != first);
+    first = nullptr;
+}
+
+void Tour::show() const
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return;
+    }
+    Node *node = first;
+    do {
+        cout << node << " " << node->next << endl;
+        node = node->next;
+    }
+    while (node != first);
+}
+
+void Tour::draw(QGraphicsScene *scene) const
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return;
+    }
+    Node *node = first;
+    do {
+        node->point.drawTo(node->next->point, scene);
+        node = node->next;
+    }
+    while (node != first);
+}
+
+int Tour::size() const
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return 0;
+    }
+    Node *node = first;
+    int amount = 0;
+    do {
+        amount++;
+        node = node->next;
+    }
+    while (node != first);
+    return amount;
+}
+
+double Tour::distance() const
+{
+    if (!first) {
+        cout << "Empty tour" << endl;
+        return 0;
+    }
+    Node *node = first;
+    double sum = 0;
+    do {
+        sum += node->point.distanceTo(node->next->point);
+        node = node->next;
+    }
+    while (node != first);
+    return sum;
+}
+
+void Tour::insertNearest(Point p)
+{
+    if (!first) {
+        Node *node = new Node(p);
+        first = node;
+        node->next = node;
+        return;
+    }
+    if (first == first->next) {
+        Node *node = new Node(p, first);
+        first->next = node;
+        return;
+    }
+    double smallestDistance = first->point.distanceTo(p);
+    Node *smallestDistanceNode = first;
+    Node *node = first->next;
+    do {
+        double distance = node->point.distanceTo(p);
+        if (distance < smallestDistance) {
+            smallestDistance = distance;
+            smallestDistanceNode = node;
+        }
+        node = node->next;
+    }
+    while (node != first);
+    Node *newNode = new Node(p, smallestDistanceNode->next);
+    smallestDistanceNode->next = newNode;
+}
+
+void Tour::insertSmallest(Point p)
+{
+    if (!first) {
+        Node *node = new Node(p);
+        first = node;
+        node->next = node;
+        return;
+    }
+    if (first == first->next) {
+        Node *node = new Node(p, first);
+        first->next = node;
+        return;
+    }
+    
+    double smallestDiff = first->point.distanceTo(p) + p.distanceTo(first->next->point) - first->point.distanceTo(first->next->point);
+    Node *smallestDiffNode = first;
+    Node *node = first->next;
+    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);
+    Node *newNode = new Node(p, smallestDiffNode->next);
+    smallestDiffNode->next = newNode;
+}
diff --git a/labb3/tsp/src/Tour.h b/labb3/tsp/src/Tour.h
new file mode 100644
index 0000000..6e4622f
--- /dev/null
+++ b/labb3/tsp/src/Tour.h
@@ -0,0 +1,22 @@
+#ifndef TOUR_H
+#define TOUR_H
+
+#include "Node.h"
+#include "Point.h"
+
+class Tour {
+public:
+    Tour();
+    ~Tour();
+    void show() const;
+    void draw(QGraphicsScene* scene) const;
+    int size() const;
+    double distance() const;
+    void insertNearest(Point p);
+    void insertSmallest(Point p);
+
+private:
+    Node *first;
+};
+
+#endif // TOUR_H
diff --git a/labb3/tsp/src/tsp.cpp b/labb3/tsp/src/tsp.cpp
new file mode 100644
index 0000000..297cc26
--- /dev/null
+++ b/labb3/tsp/src/tsp.cpp
@@ -0,0 +1,63 @@
+/*
+ * TDDD86 TSP
+ * This client program uses your Tour class and contains the 'main'
+ * function to open the input file and set up the program's primitive GUI.
+ */
+
+#include <QApplication>
+#include <QGraphicsView>
+#include <QGraphicsScene>
+#include <chrono>
+#include <thread>
+#include <fstream>
+#include <iostream>
+#include <iomanip>
+#include "Point.h"
+#include "Tour.h"
+
+int main(int argc, char *argv[]) {
+    QApplication a(argc, argv);
+
+    string filename = "tsp100.txt";
+    ifstream input;
+    input.open(filename);
+
+    // get dimensions
+    int width;
+    int height;
+    input >> width;
+    input >> height;
+
+    // setup graphical window
+    QGraphicsView *view = new QGraphicsView();
+    QGraphicsScene *scene = new QGraphicsScene();
+    view->setScene(scene);
+    view->scale(1, -1); //screen y-axis is inverted
+    view->setSceneRect(0, 0, width, height);
+    view->show();
+
+    // run insertion heuristic
+    Tour tour;
+    double x;
+    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();
+    }
+    input.close();
+
+    // print tour to standard output
+    cout << "Tour distance: " << std::fixed << std::setprecision(4)
+         << std::showpoint << tour.distance() << endl;
+    cout << "Number of points: " << tour.size() << endl;
+    tour.show();
+
+    // draw tour
+    tour.draw(scene);
+    return a.exec(); // start Qt event loop
+}