min_heap.h

#ifndef MIN_HEAP_H #define MIN_HEAP_H #include  #include  // Heap implementation derived from: // https://www.geeksforgeeks.org/binary-heap/ class MinHeap { private: // Creating internal "nested" classes is an alternative // to friending entire classes. This way, only MinHeap has access // to the a HeapNode object and its contents. class HeapNode { public: int priority; int value; HeapNode() { value = priority = 0; } HeapNode(int v, int p) { value = v; priority = p; } ~HeapNode() { value = priority = 0; } }; std::vector* heap; void swap_heap_node(int, int); void min_heapify(int); public: MinHeap() { heap = new std::vector(); heap->push_back(new HeapNode(0,0)); } ~MinHeap(); bool is_empty() { return size() int parent(int index) { return index / 2; } int left(int index) { return 2 * index; } int right(int index) { return 2 * index + 1; } int min() { return (*heap)[0]->value; } int extract_min(); int size() { return heap->size() - 1; } void insert(int, int); bool decrease_priority(int, int); void print(); }; MinHeap::~MinHeap() { while (heap->size()) { delete (*heap)[size()]; heap->pop_back(); } delete heap; } void MinHeap::swap_heap_node(int x, int y) { int p = (*heap)[x]->priority; int v = (*heap)[x]->value; (*heap)[x]->priority = (*heap)[y]->priority; (*heap)[x]->value = (*heap)[y]->value; (*heap)[y]->priority = p; (*heap)[y]->value = v; } void MinHeap::min_heapify(int index) { int lc = left(index); int rc = right(index); int smallest = index; // do comparisons with child nodes to determine small value // if l or r is > size, then there is no node at that index if (lc priority priority) smallest = lc; if (rc priority priority) smallest = rc; if (smallest != index) // if the node at index is not the smallest, perculate down the heap { swap_heap_node(index, smallest); min_heapify(smallest); // check again if we need to perculate down another level } } int MinHeap::extract_min() { int min_value; if (is_empty()) exit(1); if (size() == 1) { min_value = (*heap)[size()]->value; delete (*heap)[size()]; heap->pop_back(); return min_value; } min_value = (*heap)[1]->value; // copy min value before delete the top node swap_heap_node(1, size()); // swap min node with last node delete (*heap)[size()]; // delete last node (prev min node) heap->pop_back(); min_heapify(1); // reheapify starting at root node (index 1) return min_value; } void MinHeap::insert(int value, int priority) { heap->push_back(new HeapNode(value, priority)); int index = size(); // position new node correctly in min heap while ( index != 1 && (*heap)[parent(index)]->priority > (*heap)[index]->priority) { // since the new node is smaller than its parent, // we the nodes to swap places. swap_heap_node(index, parent(index)); index = parent(index); // update the index to reflect our new position in the heap } } bool MinHeap::decrease_priority(int value, int priority) { for (int i = 1; i if ((*heap)[i]->value == value) { (*heap)[i]->priority = priority; while (i != 1 && (*heap)[parent(i)]->priority > (*heap)[i]->priority) { swap_heap_node(i, parent(i)); i = parent(i); } return true; } } return false; } void MinHeap::print() { for (int i = 1; i priority  
 
 
 
 
 -------------------------------------------------------------------------------------------------------------------------------------------
 
 
 
graph.h
 
#ifndef GRAPH_H #define GRAPH_H #include  #include  #include  #include  class Graph { private: int adj_matrix_size; int* adj_matrix; bool filled; public: Graph() { adj_matrix_size = 0; adj_matrix = 0; filled = false; }; ~Graph(); bool create_graph(std::string); int get_weight(int, int); void print_adj_matrix(); int dimension() { return adj_matrix_size; } }; Graph::~Graph() { filled = false; for (int r = 0; r for (int c = 0; c if (adj_matrix) delete adj_matrix; } bool Graph::create_graph(std::string path) { // open file with input file stream on given path std::ifstream fs(path); std::string line; // check for errors openign file if (!fs.is_open()) return false; // clear any existing graph data adj_matrix_size = 0; filled = false; if (adj_matrix) { delete adj_matrix; adj_matrix = 0; } // get matrix size from first line std::getline(fs, line); std::istringstream ss(line); ss >> adj_matrix_size; // create square matrix to store graph information adj_matrix = new int[adj_matrix_size * adj_matrix_size]; for (int r = 0; r if (!std::getline(fs, line)) return false; // clear previous flag, set iss to read over new string ss.clear(); ss.str(line); for (int c = 0; c if (!(ss >> adj_matrix[r * adj_matrix_size + c])) return false; // exit if reading token failed } } if (fs.bad()) return false; fs.close(); filled = true; return true; } int Graph::get_weight(int row, int column) { if (row return adj_matrix[row * adj_matrix_size + column]; } void Graph::print_adj_matrix() { for (int r = 0; r for (int c = 0; c  
 
 
 
 
 ------------------------------------------------------------------------------------------------------------------------------------------
 
 
 
set.h
 
#ifndef SET_H #define SET_H #include "list.h" class Set { private: List* list; int set_size; public: Set() { list = new List(); set_size = 0; } ~Set() { delete list; } bool contains(int value) { return list->contains(value); } bool add(int); bool remove(int); void clear(); void print(); int size() { return set_size; } }; bool Set::add(int value) { if (list->contains(value)) return false; list->addToTail(value); ++set_size; return true; } bool Set::remove(int value) { if (list->contains(value)) return list->remove(value); return false; } void Set::print() { const ListNode* temp = list->getHead(); while (temp != 0) { std::cout valueOf(temp) getNext(temp); } std::cout  
 
 
 
 
 ----------------------------------------------------------------------------------------------------------------------
 
 
 
stack.h
 
#ifndef STACK_H #define STACK_H #include "list.h" class Stack { private: List* list; public: Stack() { list = new List(); } ~Stack() { delete list; } bool isEmpty() { return list->isEmpty(); } void clear() { list->clear(); } void push(int data) { list->addToHead(data); } int pop() { return list->removeHead(); } int top() { return list->valueOf(list->getHead()); } }; #endif 
 
 
 
 
 
 ----------------------------------------------------------------------------------------------------------
 
 
 
list.h
 
#ifndef LIST_H #define LIST_H class ListNode { private: int data; ListNode* prev; ListNode* next; public: ListNode() { data = 0; prev = next = 0; } ListNode(int d, ListNode* p, ListNode* n) { data = d; prev = p; next = n; } ~ListNode() { data = 0; prev = next = 0; } friend class List; }; class List { private: ListNode* head; ListNode* tail; int removeNode(ListNode*); public: List() { head = tail = 0; } ~List(); void clear(); bool isEmpty() { return head == 0; } bool contains(int value); void addToHead(int value); void addToTail(int value); int removeHead(); int removeTail(); int removeAt(int index); bool remove(int value); int at(int index); int valueOf(const ListNode* elem); const ListNode* getNext(const ListNode* node); const ListNode* getPrevious(const ListNode* node); const ListNode* getHead() { return head; } const ListNode* getTail() { return tail; } }; List::~List() { clear(); } void List::clear() { while (!isEmpty()) removeTail(); } int List::removeNode(ListNode* node) { if (node == head) return removeHead(); if (node == tail) return removeTail(); int value = node->data; node->prev->next = node->next; node->next->prev = node->prev; delete node; return value; } bool List::contains(int value) { ListNode *temp = head; while (temp != 0 && temp->data != value) temp = temp->next; return temp != 0; } void List::addToHead(int value) { if (isEmpty()) { head = tail = new ListNode(value, 0, 0); } else  { head = new ListNode(value, 0, head); head->next->prev = head; } } void List::addToTail(int value) { if (isEmpty()) { head = tail = new ListNode(value, 0, 0); } else  { tail = new ListNode(value, tail, 0); tail->prev->next = tail; } } int List::removeHead() { int value = head->data; if (head == tail) { delete tail; head = tail = 0; } else  { head = head->next; delete head->prev; head->prev = 0; } return value; } int List::removeTail() { int value = head->data; if (head == tail) { delete tail; head = tail = 0; } else  { tail = tail->prev; delete tail->next; tail->next = 0; } return value; } int List::removeAt(int index) { int idx = 0; ListNode* temp = head; while (temp != 0 && idx next; ++idx; } if (temp == 0) exit(1); return removeNode(temp); } bool List::remove(int value) { ListNode* temp = head; while (temp != 0 && temp->data != value) temp = temp->next; if (temp == 0) return false; removeNode(temp); return true; } int List::at(int index) { int idx = 0; const ListNode* temp = head; while (temp != 0 && idx if (temp == 0) exit(1); return temp->data; } int List::valueOf(const ListNode* elem) { return elem->data; } const ListNode* List::getNext(const ListNode* node) { if (node == 0) return 0; return node->next; } const ListNode* List::getPrevious(const ListNode* node) { if (node == 0) return 0; return node->prev; } #endif
 
 -----------------------------------------------------------------------------------------------------------------------------
 
dij.cpp
 
#include  #include  #include "graph.h" #include "min_heap.h" #include "set.h" #include "stack.h" using namespace std; int main() { Graph g; string path; MinHeap h; cout > path; g.create_graph(path); cout return 0; }
 
 
 
 ----------------------------------------------------------------------------------------------------------------
 
graph_1_win.txt
 
 
 
8
 
0 8 2 5 0 0 0 0
 
8 0 0 2 0 13 0 0
 
2 0 0 2 5 0 0 0
 
5 2 2 0 1 6 3 0
 
0 0 5 1 0 0 1 0
 
0 13 0 6 0 0 2 3
 
0 0 0 3 1 2 0 6
 
0 0 0 0 0 3 6 0
 
 
  This assignment involves graphs, and using several different data structures together in order to implement a class graph search algorithm. Dijkastra's Shortest Path Algorithm Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later Thc algorithm cxists in many variants; Dijkstra's original variant found thc shortcst path bctwecn two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from thc sourcc to all othcr nodcs in the graph, producing a shortcst-path trcc For a given source nodc in the graph, thc algorithm finds thc shortcst path bctwcen that node and cvcry othcr. It can also bc used for finding thc shortest paths from a singlc node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if thc nodes of thc graph reprcsent citics and cdgc path costs rcprcscnt driving distanccs bctwccn pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all othcr citics Source: I https://en.wikipedia.org wiki/Dilkstra%27s algorithm l Heap A hcap is an ADT that is vcry similar to thc priority-qucuc from thc last assignment. A hcap is callcd a min-heap or a max-heap based on whether smaller or larger values determine the priority of a value. For this assignment, we will be using a min-hcap to determinc which vcrticcs wc want to visit ncxt. You will bc using the valucs in thc distancc array (scc pscudocodc) as the priority of a vertcx. The min-hcap will automatically keep its heap structure when new values are inserted or the min value is extracted from the to Resources A visual goes a long way in explaining complex algorithms. This video goes through the entire process of Dijkstra's algorithm on the graph that is provided to you in the graph text files Source. ? https://www.youtube.com/watch /-5 Take note of the process and how it related to the pseudocode below Pseudocode 0 Graph represents the adjacency matrix of a graph. You can determine all of the edges and vertex in the graph just with the adjacency matrix. Source and target are both vertices from the graph, and simply indices from the adjacency matrix.  This assignment involves graphs, and using several different data structures together in order to implement a class graph search algorithm. Dijkastra's Shortest Path Algorithm Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later Thc algorithm cxists in many variants; Dijkstra's original variant found thc shortcst path bctwecn two nodes, but a more common variant fixes a single node as the "source" node and finds shortest paths from thc sourcc to all othcr nodcs in the graph, producing a shortcst-path trcc For a given source nodc in the graph, thc algorithm finds thc shortcst path bctwcen that node and cvcry othcr. It can also bc used for finding thc shortest paths from a singlc node to a single destination node by stopping the algorithm once the shortest path to the destination node has been determined. For example, if thc nodes of thc graph reprcsent citics and cdgc path costs rcprcscnt driving distanccs bctwccn pairs of cities connected by a direct road, Dijkstra's algorithm can be used to find the shortest route between one city and all othcr citics Source: I https://en.wikipedia.org wiki/Dilkstra%27s algorithm l Heap A hcap is an ADT that is vcry similar to thc priority-qucuc from thc last assignment. A hcap is callcd a min-heap or a max-heap based on whether smaller or larger values determine the priority of a value. For this assignment, we will be using a min-hcap to determinc which vcrticcs wc want to visit ncxt. You will bc using the valucs in thc distancc array (scc pscudocodc) as the priority of a vertcx. The min-hcap will automatically keep its heap structure when new values are inserted or the min value is extracted from the to Resources A visual goes a long way in explaining complex algorithms. This video goes through the entire process of Dijkstra's algorithm on the graph that is provided to you in the graph text files Source. ? https://www.youtube.com/watch /-5 Take note of the process and how it related to the pseudocode below Pseudocode 0 Graph represents the adjacency matrix of a graph. You can determine all of the edges and vertex in the graph just with the adjacency matrix. Source and target are both vertices from the graph, and simply indices from the adjacency matrix