From 0c39051ba80f04b1177833a006f2d442a7170b56 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Thu, 3 Dec 2020 17:11:43 +0100 Subject: add initial files l8 --- labb8/src/BasicGraph.cpp | 264 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 264 insertions(+) create mode 100755 labb8/src/BasicGraph.cpp (limited to 'labb8/src/BasicGraph.cpp') diff --git a/labb8/src/BasicGraph.cpp b/labb8/src/BasicGraph.cpp new file mode 100755 index 0000000..2c4e239 --- /dev/null +++ b/labb8/src/BasicGraph.cpp @@ -0,0 +1,264 @@ +/* + * TDDD86 Trailblazer + * This file contains the implementation of some useful graph types, + * specifically the Node and Arc structures used in the typical graph. + * We also implement BasicGraph, an instantiation of + * Stanford's Graph class using Node and Arc as its type parameters. + * + * See BasicGraph.h for documentation of each member. + * + * Please do not modify this provided file. Your turned-in files should work + * with an unmodified version of all provided code files. + * + * Author: Marty Stepp + * Slight modifications by Tommy Farnqvist + */ + +#include +#include "BasicGraph.h" + +/* + * Node member implementations + */ + +Grid* Node::s_world = nullptr; +double (* Node::s_heuristicFunction)(Node* const from, Node* const to, const Grid& world) = nullptr; + +Node::Node(string name, int row, int col, double gridValue) { + this->name = name; + this->m_row = row; + this->m_col = col; + this->m_gridValue = gridValue; + this->resetData(); +} + +Color Node::getColor() const { + return this->m_color; +} + +double Node::heuristic(Node* const other) const { + if (s_world == nullptr || s_heuristicFunction == nullptr) { + return 0.0; + } else { + return s_heuristicFunction(const_cast(this), const_cast(other), *s_world); + } +} + +void Node::resetData() { + this->cost = 0.0; + this->previous = nullptr; + this->visited = false; + this->m_color = WHITE; +} + +void Node::setColor(Color c) { + this->m_color = c; + if (s_world != nullptr) { + colorCell(*s_world, makeLoc(this->m_row, this->m_col), c); + } +} + +void Node::setHeuristicFunction(double (* func)(Node* const from, Node* const to, const Grid& world)) { + s_heuristicFunction = func; +} + +void Node::setWorld(const Grid& world) { + s_world = const_cast*>(&world); +} + +string Node::toString() const { + ostringstream out; + out << *this; + return out.str(); +} + +ostream& operator<<(ostream& out, const Node& node) { + out << "Node{name=" << node.name; + if (node.cost != 0.0) { + out << ", cost=" << node.cost; + } + out << ", cost=" << node.cost; + out << ", visited=" << (node.visited ? "true" : "false"); + out << ", previous=" << (node.previous == nullptr ? string("nullptr") : node.previous->name); + + out << ", neighbors={" << node.arcs; + int i = 0; + foreach (Arc* arc in node.arcs) { + if (i > 0) { + out << ", "; + } + if (arc->finish) { + out << arc->finish->name; + } else { + out << "nullptr"; + } + } + out << "}"; + out << "}"; + return out; +} + + +/* + * Arc member implementations + */ + +Arc::Arc(Node* start, Node* finish, double cost) { + this->start = start; + this->finish = finish; + this->cost = cost; + this->resetData(); +} + +void Arc::resetData() { + this->visited = false; +} + +string Arc::toString() const { + ostringstream out; + out << *this; + return out.str(); +} + +ostream& operator<<(ostream& out, const Arc& arc) { + out << "Arc{start=" << arc.start->name << ", finish=" << arc.finish->name; + if (arc.cost != 0.0) { + out << ", cost=" << arc.cost; + } + if (arc.visited) { + out << ", visited=" << (arc.visited ? "true" : "false"); + } + out << "}"; + return out; +} + + +/* + * BasicGraph member implementations + */ + +Arc* BasicGraph::getArc(Node* v1, Node* v2) const { + foreach (Arc* arc in this->getArcSet(v1)) { + if (arc->finish == v2) { + return arc; + } + } + return nullptr; +} + +Arc* BasicGraph::getArc(string v1, string v2) const { + return this->getArc(this->getVertex(v1), this->getVertex(v2)); +} + +Arc* BasicGraph::getEdge(Node* v1, Node* v2) const { + return this->getArc(v1, v2); +} + +Arc* BasicGraph::getEdge(string v1, string v2) const { + return this->getArc(v1, v2); +} + +Arc* BasicGraph::getInverseArc(Arc* arc) const { + return this->getArc(arc->finish, arc->start); +} + +Arc* BasicGraph::getInverseEdge(Arc* arc) const { + return this->getInverseArc(arc); +} + +bool BasicGraph::isNeighbor(string v1, string v2) const { + return this->isNeighbor(this->getVertex(v1), this->getVertex(v2)); +} + +bool BasicGraph::isNeighbor(Node* v1, Node* v2) const { + foreach (Arc* edge in this->getEdgeSet(v1)) { + if (edge->finish == v2) { + return true; + } + } + return false; +} + +void BasicGraph::resetData() { + foreach (Node* node in getNodeSet()) { + node->resetData(); + } + foreach (Arc* arc in getArcSet()) { + arc->resetData(); + } +} + + +// members below are just mirrors of ones from Graph + +Arc* BasicGraph::addEdge(string v1, string v2, double cost, bool directed) { + return this->addEdge(getVertex(v1), getVertex(v2), cost, directed); +} + +Arc* BasicGraph::addEdge(Node* v1, Node* v2, double cost, bool directed) { + Arc* e = new Arc(v1, v2, cost); + return addEdge(e, directed); +} + +Arc* BasicGraph::addEdge(Arc* e, bool directed) { + Arc* result = this->addArc(e); + if (!directed) { + Arc* result2 = this->addArc(e->finish, e->start); + result2->cost = e->cost; + } + return result; +} + +Node* BasicGraph::addVertex(string name) { + return this->addNode(name); +} + +Node* BasicGraph::addVertex(Node* v) { + return this->addNode(v); +} + +const Set& BasicGraph::getEdgeSet() const { + return this->getArcSet(); +} + +const Set& BasicGraph::getEdgeSet(Node* v) const { + return this->getArcSet(v); +} + +const Set& BasicGraph::getEdgeSet(string v) const { + return this->getArcSet(v); +} + +Node* BasicGraph::getVertex(string name) const { + return this->getNode(name); +} + +const Set& BasicGraph::getVertexSet() const { + return this->getNodeSet(); +} + +void BasicGraph::removeEdge(string v1, string v2, bool directed) { + this->removeEdge(this->getVertex(v1), this->getVertex(v2), directed); +} + +void BasicGraph::removeEdge(Node* v1, Node* v2, bool directed) { + this->removeArc(v1, v2); + if (!directed) { + this->removeArc(v2, v1); + } +} + +void BasicGraph::removeEdge(Arc* e, bool directed) { + this->removeArc(e); + if (!directed) { + this->removeArc(e->finish, e->start); + } +} + +void BasicGraph::removeVertex(string name) { + this->removeNode(name); +} + +void BasicGraph::removeVertex(Node* v) { + this->removeNode(v); +} -- cgit v1.2.1