From f41f0fdb066629597529ba12329d22040ce2878c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Gustav=20S=C3=B6rn=C3=A4s?= Date: Tue, 8 Dec 2020 15:01:32 +0100 Subject: l8 impl --- labb8/src/trailblazer.cpp | 192 ++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 160 insertions(+), 32 deletions(-) diff --git a/labb8/src/trailblazer.cpp b/labb8/src/trailblazer.cpp index 38e168b..6d10bd3 100755 --- a/labb8/src/trailblazer.cpp +++ b/labb8/src/trailblazer.cpp @@ -1,45 +1,173 @@ -// This is the CPP file you will edit and turn in. -// Also remove these comments here and add your own, along with -// comments on every function and on complex code sections. -// TODO: write comment header for this file; remove this comment - #include "costs.h" #include "trailblazer.h" -// TODO: include any other headers you need; remove this comment + +#include +#include +#include +#include +#include +#include "pqueue.h" + using namespace std; -vector depthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) { - // TODO: implement this function; remove these comments - // (The function body code provided below is just a stub that returns - // an empty vector so that the overall project will compile. - // You should remove that code and replace it with your implementation.) - vector path; +vector path_from_end(Node* end, bool color_green = false) { + if (!end->previous) { + return {}; + } + Node* cur = end; + vector path; + while (cur) { + if (color_green) { + cur->setColor(GREEN); + } + path.push_back(cur); + cur = cur->previous; + } + reverse(path.begin(), path.end()); + cout << "done" << endl; return path; } +template +void push_back_from(vector& to, const vector& from) { + for (const auto& el : from) { + to.push_back(el); + } +} + +vector dfs_helper(BasicGraph& graph, Vertex* start, Vertex* end) { + start->setColor(GREEN); + vector path = { start }; + if (start == end) { + return path; + } + start->visited = true; + for (const auto& arc : start->arcs) { + if (!arc->finish->visited) { + vector neighbour_path = dfs_helper(graph, arc->finish, end); + if (neighbour_path.size() == 0) { + continue; + } + vector new_path(path); + push_back_from(new_path, neighbour_path); + return new_path; + } + } + start->setColor(GRAY); + return {}; +} + +vector depthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) { + graph.resetData(); + return dfs_helper(graph, start, end); +} + vector breadthFirstSearch(BasicGraph& graph, Vertex* start, Vertex* end) { - // TODO: implement this function; remove these comments - // (The function body code provided below is just a stub that returns - // an empty vector so that the overall project will compile. - // You should remove that code and replace it with your implementation.) - vector path; - return path; + graph.resetData(); + + queue q; + q.push(start); + start->visited = true; + while (q.size() > 0) { + Node* cur = q.front(); + q.pop(); + cur->setColor(GREEN); + if (cur == end) { + break; + } + for (const auto& arc : cur->arcs) { + if (!arc->finish->visited) { + arc->finish->visited = true; + arc->finish->previous = cur; + arc->finish->setColor(YELLOW); + q.push(arc->finish); + } + } + } + return path_from_end(end); } -vector dijkstrasAlgorithm(BasicGraph& graph, Vertex* start, Vertex* end) { - // TODO: implement this function; remove these comments - // (The function body code provided below is just a stub that returns - // an empty vector so that the overall project will compile. - // You should remove that code and replace it with your implementation.) - vector path; - return path; +vector dijkstrasAlgorithm(BasicGraph& graph, Vertex* start, Vertex* end) { + graph.resetData(); + + PriorityQueue q; + q.enqueue(start, 0.0); + start->visited = true; + + while (q.size() > 0) { + Node* cur = q.dequeue(); + cur->visited = true; + cur->setColor(GREEN); + if (cur == end) { + break; + } + for (const auto& arc : cur->arcs) { + if (!arc->finish->visited) { + double new_dist = arc->start->cost + arc->cost; + if (arc->finish->cost == 0.0) { + arc->finish->previous = cur; + arc->finish->cost = new_dist; + arc->finish->setColor(YELLOW); + q.enqueue(arc->finish, new_dist); + } + else if (new_dist < arc->finish->cost) { + arc->finish->previous = cur; + arc->finish->cost = new_dist; + q.changePriority(arc->finish, new_dist); + } + } + } + } + return path_from_end(end); } -vector aStar(BasicGraph& graph, Vertex* start, Vertex* end) { - // TODO: implement this function; remove these comments - // (The function body code provided below is just a stub that returns - // an empty vector so that the overall project will compile. - // You should remove that code and replace it with your implementation.) - vector path; - return path; +vector aStar(BasicGraph& graph, Vertex* start, Vertex* end) { + ofstream log; + log.open("log"); + log << "reset" << endl; + graph.resetData(); + + PriorityQueue q; + q.enqueue(start, 0.0); + start->visited = true; + + while (q.size() > 0) { + log << q << endl; + Node* cur = q.dequeue(); + log << cur << endl; + cur->visited = true; + log << "green" << endl; + cur->setColor(GREEN); + log << "green done" << endl; + if (cur == end) { + log << "done" << endl; + break; + } + for (const auto& arc : cur->arcs) { + log << arc << " " << *arc << endl; + if (!arc->finish->visited) { + double new_dist = arc->start->cost + arc->cost; + if (arc->finish->cost == 0.0) { + log << "first" << endl; + arc->finish->previous = cur; + arc->finish->cost = new_dist; + log << "yellow" << endl; + arc->finish->setColor(YELLOW); + log << "yellow done" << endl; + log << "queing" << endl; + q.enqueue(arc->finish, new_dist + arc->finish->heuristic(end)); + } + else if (new_dist < arc->finish->cost) { + log << "new best" << endl; + arc->finish->previous = cur; + arc->finish->cost = new_dist; + log << "change prio" << endl; + q.changePriority(arc->finish, new_dist + arc->finish->heuristic(end)); + } + } + log << "done considering" << endl; + } + } + log.close(); + return path_from_end(end); } -- cgit v1.2.1