summaryrefslogtreecommitdiffstats
path: root/labb3/tsp/src
diff options
context:
space:
mode:
Diffstat (limited to 'labb3/tsp/src')
-rw-r--r--labb3/tsp/src/Node.cpp32
-rw-r--r--labb3/tsp/src/Node.h47
-rw-r--r--labb3/tsp/src/Point.cpp50
-rw-r--r--labb3/tsp/src/Point.h53
-rw-r--r--labb3/tsp/src/Tour.cpp143
-rw-r--r--labb3/tsp/src/Tour.h22
-rw-r--r--labb3/tsp/src/tsp.cpp63
7 files changed, 410 insertions, 0 deletions
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
+}
generated by cgit v1.2.1 (git 2.18.0) at 2025-12-11 21:10:17 +0100