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.h | 230 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 230 insertions(+) create mode 100755 labb8/src/BasicGraph.h (limited to 'labb8/src/BasicGraph.h') diff --git a/labb8/src/BasicGraph.h b/labb8/src/BasicGraph.h new file mode 100755 index 0000000..e0bdeee --- /dev/null +++ b/labb8/src/BasicGraph.h @@ -0,0 +1,230 @@ +/* + * TDDD86 Trailblazer + * This file contains the declaration of some useful graph types, + * specifically the Node and Arc structures used in the typical graph. + * We also declare BasicGraph, an instantiation of + * Stanford's Graph class using Node and Arc as its type parameters. + * + * See BasicGraph.cpp for implementation 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 + */ + +#ifndef _basicgraph_h +#define _basicgraph_h + +#include +#include "graph.h" +#include "grid.h" +#include "set.h" +#include "trailblazergui.h" +using namespace std; + +/* + * Forward declarations of Node/Arc structures so that they can refer + * to each other mutually. + */ +struct Node; +struct Arc; + +/* + * Canonical Node structure implementation needed by Graph class template. + * A Node structure represents a vertex in the graph. + */ +struct Node { +public: + string name; // required by Stanford Graph; vertex's name + Set arcs; // edges outbound from this vertex; to neighbors + + /* + * The following three fields are 'supplementary data' inside each vertex. + * You can use them in your path-searching algorithms to store various + * information related to the vertex + */ + double cost; // cost to reach this vertex (initially 0; you can set this) + bool visited; // whether this vertex has been visited before (initally false; you can set this) + Node* previous; // vertex that comes before this one (initially nullptr; you can set this) + + /* + * The following three fields are used internally and not by your code. You + * must not use their values nor rely on them in any way in your algorithms. + */ + int m_row; + int m_col; + double m_gridValue; + + /* + * Constructs a vertex with the given name and optional extra information. + * The extra information is used internally to convert it back to a Grid + * entry for legacy support if needed. + */ + Node(string name = "", int row = 0, int col = 0, double gridValue = 0.0); + + /* + * Returns the color of this node, if any. Initially WHITE. + */ + Color getColor() const; + + /* + * Returns a 'heuristic' value, or rough estimation, of the distance between + * this vertex and the given other vertex. + * The heuristic function is guaranteed to be an 'admissible heuristic', + * meaning that it is never an overestimation of the distance. + * That property is important for the heuristic function to work properly + * when used with the A* search algorithm. + */ + double heuristic(Node* const other) const; + + /* + * Wipes the supplementary data of this vertex back to its initial state. + * Specifically, sets cost to 0, visited to false, and previous to nullptr. + */ + void resetData(); + + /* + * Sets the color of this vertex to be the given color. + * The color must be one of WHITE, GRAY, YELLOW, or GREEN. + * Future calls to getColor will return the color you pass here. + */ + void setColor(Color c); + + /* + * Returns a string representation of this vertex for debugging, such as + * "Node{name=r13c42, cost=11, visited=true, previous=r12c41, neighbors={r12c41, r12c43}}". + */ + string toString() const; + + /* + * These static functions are used by the provided client code to set up + * information about the world and heuristic functions used by nodes. + * You should not call these functions directly in your path algorithms. + */ + static void setHeuristicFunction(double (* func)(Node* const from, Node* const to, const Grid& world)); + static void setWorld(const Grid& world); + +private: + Color m_color; // node's color as passed to setColor + static double (* s_heuristicFunction)(Node* const from, Node* const to, + const Grid& world); + static Grid* s_world; +}; + +/* + * Makes a node printable to an output stream. + * See toString for an example of the output format. + * Note that printing a node is not the same as printing a node pointer. + * If you try to print a pointer, you will just see its address in hex. + */ +ostream& operator<<(ostream& out, const Node& node); + +/* + * You can refer to a Node as a Vertex if you prefer. + */ +#define Vertex Node + +/* + * Canonical Arc structure implementation needed by Graph class template. + * An Arc structure represents an edge in the graph. + */ +struct Arc { +public: + Node* start; // edge's starting vertex (required by Graph) + Node* finish; // edge's ending vertex (required by Graph) + double cost; // edge weight (required by Graph) + bool visited; // whether this edge has been visited before (initally false; you can set this) + + /* + * Constructs a new edge between the given start/end vertices with + * the given cost. + */ + Arc(Node* start = nullptr, Node* finish = nullptr, double cost = 0.0); + + /* + * Wipes the supplementary data of this vertex back to its initial state. + * Specifically, sets visited to false. + */ + void resetData(); + + /* + * Returns a string representation of this edge for debugging, such as + * "Arc{start=r12c42, finish=r12c41, cost=0.75}". + */ + string toString() const; + + /* + * The following fields are used internally and not by your code. You + * must not use their values nor rely on them in any way in your algorithms. + */ + int m_startRow; + int m_startCol; + int m_finishRow; + int m_finishCol; +}; + +/* + * Makes an arc printable to an output stream. + * See toString for an example of the output format. + * Note that printing an arc is not the same as printing an arc pointer. + * If you try to print a pointer, you will just see its address in hex. + */ +ostream& operator<<(ostream& out, const Arc& arc); + +/* + * You can refer to an Arc as an Edge if you prefer. + */ +#define Edge Arc + + +/* + * BasicGraph is just basically an instantiation of Graph using Node and Arc + * as its template parameters. It also adds a few convenience functions such + * as mirroring members like "addArc" with an equivalent more familiar name + * like "addEdge". + * + * There are a few convenience functions related to neighbors, like isNeighbor. + * BasicGraph contains a DFS implementation called isReachable, not found + * in the normal Stanford Graph class. + * + * There are also a few functions added to make edges more convenient to work with: + * getEdge(v1, v2) to get the edge between a given pair of vertices, + * and getInverseArc(arc) to get the edge v2 -> v1 for a given edge v1 -> v2. + */ +class BasicGraph : public Graph { +public: + Arc* getArc(Node* v1, Node* v2) const; + Arc* getArc(string v1, string v2) const; + Arc* getEdge(Node* v1, Node* v2) const; + Arc* getEdge(string v1, string v2) const; + Arc* getInverseArc(Arc* arc) const; + Arc* getInverseEdge(Arc* arc) const; + bool isNeighbor(string v1, string v2) const; + bool isNeighbor(Node* v1, Node* v2) const; + void resetData(); + + /* + * The members below are mirrors of ones from Graph but with 'Node' changed + * to 'Vertex' and/or 'Arc' changed to 'Edge', with identical behavior, + * and so they are not documented in detail. See Graph documentation. + */ + Arc* addEdge(string v1, string v2, double cost = 0.0, bool directed = true); + Arc* addEdge(Node* v1, Node* v2, double cost = 0.0, bool directed = true); + Arc* addEdge(Arc* e, bool directed = true); + Node* addVertex(string name); + Node* addVertex(Node* v); + const Set& getEdgeSet() const; + const Set& getEdgeSet(Node* v) const; + const Set& getEdgeSet(string v) const; + Node* getVertex(string name) const; + const Set& getVertexSet() const; + void removeEdge(string v1, string v2, bool directed = true); + void removeEdge(Node* v1, Node* v2, bool directed = true); + void removeEdge(Arc* e, bool directed = true); + void removeVertex(string name); + void removeVertex(Node* v); +}; + +#endif -- cgit v1.2.1