Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <limits>
- #include <vector>
- #include <stdio.h>
- using namespace std;
- class adjlist;
- class graph;
- struct node {
- string name;
- int num_children = 0;
- string colour = "white";
- adjlist* children = NULL;
- node* next = NULL;
- };
- struct child_node {
- node* point;
- child_node* next = NULL;
- double distance;
- node* parent;
- double shortest;
- child_node* path_parent = NULL;
- };
- class adjlist {
- private:
- public:
- child_node* head;
- int paths;
- adjlist() {
- head = NULL;
- paths = 0;
- }
- void insert(node* city2, double distance1, node* parent_path) {
- child_node* child = new child_node;
- child->point = city2;
- child->distance = distance1;
- child->shortest = distance1;
- child->parent = parent_path;
- if (head == NULL) {
- head = child;
- paths = paths + 1;
- return;
- }
- child_node* temp = head;
- if (temp->point == city2) {
- temp->distance = distance1;
- temp->shortest = distance1;
- return;
- }
- while (temp->next != NULL) {
- temp = temp->next;
- if (temp->point == city2) {
- temp->distance = distance1;
- temp->shortest = distance1;
- return;
- }
- }
- temp->next = child;
- paths = paths + 1;
- }
- void print() {
- if (head == NULL) {
- return;
- }
- child_node* temp = head;
- cout << temp->point->name;
- cout << temp->distance;
- while (temp->next != NULL) {
- temp = temp->next;
- cout << temp->point->name;
- cout << temp->distance;
- }
- }
- };
- class Graph {
- private:
- int size;
- public:
- node* head;
- Graph() {
- size = 0;
- head = NULL;
- }
- ~Graph() {
- node* temp = head;
- node* nextup;
- if (head != NULL) {
- if (head->next == NULL) {
- delete nextup;
- }
- else {
- while (temp->next != NULL) {
- nextup = temp;
- temp = temp->next;
- delete nextup;
- }
- }
- }
- head = NULL;
- size = 0;
- }
- void insert(node* city) {
- if (head == NULL) {
- head = city;
- size = size + 1;
- return;
- }
- node* temp = head;
- while (temp->next != NULL) {
- temp = temp->next;
- }
- size = size + 1;
- temp->next = city;
- }
- node* find_key(string city_name) {
- if (head == NULL) {
- return NULL;
- }
- node* temp = head;
- if (temp->name == city_name) {
- return temp;
- }
- while (temp->next != NULL) {
- temp = temp->next;
- if (temp->name == city_name) {
- return temp;
- }
- }
- return NULL;
- }
- int return_size() {
- return size;
- }
- };
- class Heap {
- private:
- public:
- void insert(child_node* heap_array[], int index) {
- int temp = index + 1;
- int half;
- child_node* swap;
- while (temp > 1) {
- half = temp / 2;
- if (heap_array[temp - 1]->shortest < heap_array[half - 1]->shortest) {
- child_node* swap = heap_array[half - 1];
- heap_array[half - 1] = heap_array[temp - 1];
- heap_array[temp - 1] = swap;
- }
- temp = temp / 2;
- }
- }
- void relaxation(node* smallest, child_node* heap_array[], int& current_size, bool& already_found, int size, node*& found_distance, string city) {
- int index = size;
- node* temp = smallest;
- child_node* start = temp->children->head;
- child_node* current_min = heap_array[0];
- if (current_min->point->name == city) {
- found_distance = current_min->parent;
- already_found = true;
- }
- delete_min(heap_array, index, current_size, already_found);
- bool check = false;
- if (temp->children->head == NULL) {
- temp = smallest;
- }
- else {
- bool dupl = false;
- bool check = false;
- for (int i = 0; i < current_size; i++) {
- if (heap_array[i]->point == start->point) {
- if (current_min->shortest + start->shortest < heap_array[i]->shortest) {
- heap_array[i]->shortest = current_min->shortest + start->shortest;
- heap_array[i]->path_parent = current_min;
- insert(heap_array, i);
- }
- dupl = true;
- }
- }
- if (start->point->colour == "black") {
- check = true;
- }
- if (dupl == false && check == false) {
- heap_array[current_size] = start;
- heap_array[current_size]->path_parent = current_min;
- current_size = current_size + 1;
- start->shortest = current_min->shortest + start->shortest;
- insert(heap_array, current_size - 1);
- }
- dupl = false;
- check = false;
- while (start->next != NULL) {
- start = start->next;
- for (int i = 0; i < current_size; i++) {
- if (heap_array[i]->point == start->point) {
- if (current_min->shortest + start->shortest < heap_array[i]->shortest) {
- heap_array[i]->shortest = current_min->shortest + start->shortest;
- heap_array[i]->path_parent = current_min;
- insert(heap_array, i);
- }
- dupl = true;
- }
- }
- if (start->point->colour == "black") {
- check = true;
- }
- if (dupl == false && check == false) {
- heap_array[current_size] = start;
- heap_array[current_size]->path_parent = current_min;
- current_size = current_size + 1;
- start->shortest = current_min->shortest + start->shortest;
- insert(heap_array, current_size - 1);
- }
- dupl = false;
- check = false;
- }
- }
- if (current_min->point->colour == "white") {
- current_min->point->colour = "black";
- }
- }
- void delete_min(child_node* heap_array[], int& index, int& current_size, bool& already_found) {
- heap_array[0] = heap_array[current_size - 1];
- heap_array[current_size - 1] = NULL;
- current_size = current_size - 1;
- child_node* l;
- child_node* r;
- child_node* previous;
- int cycle = 1;
- while (cycle <= current_size) {
- previous = heap_array[cycle - 1];
- if (heap_array[(cycle * 2) - 1] == NULL || cycle * 2 > current_size) {
- break;
- }
- heapify(heap_array, index, current_size, already_found, cycle);
- l = heap_array[(cycle * 2) - 1];
- r = heap_array[cycle * 2];
- if (previous == l) {
- cycle = cycle * 2;
- }
- else if (previous == r) {
- cycle = cycle * 2 + 1;
- }
- else {
- break;
- }
- }
- }
- void heapify(child_node* heap_array[], int& index, int& current_size, bool& already_found, int half) {
- int left = half * 2;
- int right = (half * 2) + 1;
- if (heap_array[left - 1] == NULL || left > current_size) {
- return;
- }
- else if (heap_array[right - 1] == NULL) {
- if (heap_array[half - 1]->shortest > heap_array[left - 1]->shortest) {
- child_node* swap = heap_array[left - 1];
- heap_array[left - 1] = heap_array[half - 1];
- heap_array[half - 1] = swap;
- }
- return;
- }
- else {
- //which one is smaller
- if (heap_array[left - 1]->shortest < heap_array[right - 1]->shortest) {
- if (heap_array[left - 1]->shortest < heap_array[half - 1]->shortest) {
- child_node* swap = heap_array[left - 1];
- heap_array[left - 1] = heap_array[half - 1];
- heap_array[half - 1] = swap;
- }
- }
- else if (heap_array[right - 1]->shortest < heap_array[left - 1]->shortest) {
- if (heap_array[right - 1]->shortest < heap_array[half - 1]->shortest) {
- child_node* swap = heap_array[right - 1];
- heap_array[right - 1] = heap_array[half - 1];
- heap_array[half - 1] = swap;
- }
- }
- else {
- // even
- if (heap_array[left - 1]->shortest < heap_array[half - 1]->shortest) {
- child_node* swap = heap_array[left - 1];
- heap_array[left - 1] = heap_array[half - 1];
- heap_array[half - 1] = swap;
- }
- }
- }
- }
- void create(node* start, child_node* heap_array[], int& index, int& current_size, bool& already_found) {
- child_node* temp = start->children->head;
- heap_array[index] = temp;
- start->colour = "black";
- index = index + 1;
- current_size = current_size + 1;
- while (temp->next != NULL) {
- temp = temp->next;
- heap_array[index] = temp;
- current_size = current_size + 1;
- index = index + 1;
- }
- int half = current_size / 2;
- for (int i = half + 1; i >= 1; i = i - 1) {
- heapify(heap_array, index, current_size, already_found, i);
- }
- }
- void print(child_node* heap_array[], int size) {
- if (heap_array[0] == NULL) {
- return;
- }
- for (int i = 0; i < size; i++) {
- if (heap_array[i] != NULL) {
- cout << heap_array[i]->point->name << " " << heap_array[i]->shortest << endl;
- }
- }
- }
- };
- void search(node* start, int size, string name, node* BFsearch[], int& index, int& position, bool& already_found) {
- node* temp = start;
- if (temp->name == name) {
- cout << "found " << name << endl;
- already_found = true;
- return;
- }
- BFsearch[index] = temp;
- index = index + 1;
- if (temp->num_children == 0) {
- return;
- }
- bool dupl = false;
- child_node* cycle = temp->children->head;
- BFsearch[index] = cycle->point;
- index = index + 1;
- while (cycle->next != NULL) {
- cycle = cycle->next;
- for (int i = 0; i < index; i++) {
- if (BFsearch[i] == cycle->point) {
- bool dupl = true;
- }
- }
- if (dupl == false) {
- BFsearch[index] = cycle->point;
- index = index + 1;
- }
- dupl = false;
- }
- int new_pos = position + 1;
- if (new_pos > size) {
- return;
- }
- if (BFsearch[new_pos] != NULL) {
- search(BFsearch[new_pos], size, name, BFsearch, index, new_pos, already_found);
- }
- }
- int main() {
- string input = "";
- vector<string> information;
- vector<string> names;
- Graph my_graph;
- while (!cin.eof()) {
- cin >> input;
- if (input == "i") {
- getline(cin, input);
- string current = "";
- int end_value = 1;
- for (int i = 1; i < input.length(); i++) {
- current = current + input[i];
- if (i >= input.length() - end_value) {
- break;
- }
- }
- bool duplicate = false;
- for (int i = 0; i < names.size(); i++) {
- if (names[i] == current) {
- cout << "failure" << endl;
- duplicate = true;
- }
- }
- if (duplicate == true) {
- continue;
- }
- node* city = new node;
- adjlist* children1 = new adjlist;
- city->children = children1;
- city->name = current;
- my_graph.insert(city);
- cout << "success" << endl;
- names.push_back(current);
- }
- else if (input == "setd") {
- getline(cin, input);
- string current = "";
- int end_value = 1;
- for (int i = 1; i < input.length(); i++) {
- if (input[i] == ';') {
- information.push_back(current);
- current = "";
- continue;
- }
- current = current + input[i];
- if (i == input.length() - end_value) {
- information.push_back(current);
- }
- }
- int missing = 0;
- string city1 = information[0];
- string city2 = information[1];
- double distance = stod(information[2]);
- for (int i = 0; i < names.size(); i++) {
- if (names[i] == city1 || names[i] == city2) {
- missing = missing + 1;
- }
- }
- if (missing != 2) {
- cout << "failure" << endl;
- }
- else {
- cout << "success" << endl;
- node* first = my_graph.find_key(city1);
- node* second = my_graph.find_key(city2);
- first->children->insert(second, distance, first);
- second->children->insert(first, distance, second);
- first->num_children = 1;
- second->num_children = 1;
- }
- information.clear();
- }
- else if (input == "s") {
- getline(cin, input);
- int size = my_graph.return_size();
- string current = "";
- int end_value = 1;
- for (int i = 1; i < input.length(); i++) {
- current = current + input[i];
- if (i >= input.length() - end_value) {
- break;
- }
- }
- bool found = false;
- for (int i = 0; i < names.size(); i++) {
- if (names[i] == current) {
- found = true;
- }
- }
- if (found == true) {
- cout << "found " << current << endl;
- }
- else {
- cout << "not found" << endl;
- }
- }
- else if (input == "graph_nodes") {
- int size = my_graph.return_size();
- cout << "number of nodes " << size << endl;
- getline(cin, input);
- }
- else if (input == "graph_edges") {
- int total = 0;
- if (my_graph.head == NULL) {
- cout << "number of edges " << total << endl;
- }
- else {
- node* start = my_graph.head;
- if (start->children != NULL) {
- total = total + start->children->paths;
- }
- while (start->next != NULL) {
- start = start->next;
- if (start->children != NULL) {
- total = total + start->children->paths;
- }
- }
- total = total / 2;
- cout << "number of edges " << total << endl;
- }
- }
- else if (input == "degree") {
- getline(cin, input);
- string current = "";
- int end_value = 1;
- for (int i = 1; i < input.length(); i++) {
- current = current + input[i];
- if (i >= input.length() - end_value) {
- break;
- }
- }
- bool found = false;
- for (int i = 0; i < names.size(); i++) {
- if (names[i] == current) {
- found = true;
- }
- }
- if (found == true) {
- node* start = my_graph.head;
- if (start->name == current) {
- cout << "degree of " << current << " " << start->children->paths << endl;
- }
- else {
- while (start->next != NULL) {
- start = start->next;
- if (start->name == current) {
- cout << "degree of " << current << " " << start->children->paths << endl;
- }
- }
- }
- }
- else {
- cout << "not found" << endl;
- }
- }
- else if (input == "d") {
- getline(cin, input);
- string current = "";
- string city1;
- string city2;
- int end_value = 1;
- for (int i = 1; i < input.length(); i++) {
- if (input[i] == ';') {
- city1 = current;
- current = "";
- continue;
- }
- current = current + input[i];
- if (i == input.length() - end_value) {
- city2 = current;
- }
- }
- double distance = 0;
- bool city2_found = false;
- node* first = my_graph.find_key(city1);
- if (city2 == city1) {
- cout << "direct distance " << city1 << " to " << city1 << " " << distance << endl;
- city2_found = true;
- }
- else if (first == NULL) {
- cout << "failure" << endl;
- }
- else {
- child_node* start = first->children->head;
- if (start == NULL) {
- cout << "failure" << endl;
- }
- else {
- if (start->point->name == city2) {
- cout << "direct distance " << city1 << " to " << city2 << " " << start->distance << endl;
- city2_found = true;
- }
- while (start->next != NULL) {
- start = start->next;
- if (start->point->name == city2) {
- cout << "direct distance " << city1 << " to " << city2 << " " << start->distance << endl;
- city2_found = true;
- }
- }
- if (city2_found == false) {
- cout << "failure" << endl;
- }
- }
- }
- }
- else if (input == "shortest_d") {
- getline(cin, input);
- int end_value = 1;
- string current = "";
- string city1;
- string city2;
- for (int i = 1; i < input.length(); i++) {
- if (input[i] == ';') {
- city1 = current;
- current = "";
- continue;
- }
- current = current + input[i];
- if (i == input.length() - end_value) {
- city2 = current;
- }
- }
- //check existence
- double distance = 0;
- bool city2_found = false;
- int index = 0;
- int current_size = 0;
- int size = my_graph.return_size();
- node* first = my_graph.find_key(city1);
- if (city2 == city1) {
- cout << "shortest distance " << city1 << " to " << city1 << " " << distance << endl;
- city2_found = true;
- }
- else if (first == NULL) {
- cout << "failure" << endl;
- }
- else {
- child_node* start = first->children->head;
- if (start == NULL) {
- cout << "failure" << endl;
- }
- else {
- if (city2_found == false) {
- child_node* heap_array[size];
- for (int i = 0; i < size; i++) {
- heap_array[i] = NULL;
- }
- Heap my_heap;
- node* found_distance = NULL;
- my_heap.create(first, heap_array, index, current_size, city2_found);
- while (current_size >= 1) {
- node* pass = heap_array[0]->point;
- my_heap.relaxation(pass, heap_array, current_size, city2_found, size, found_distance, city2);
- }
- if (found_distance != NULL) {
- child_node* start = found_distance->children->head;
- while (start != NULL) {
- if (start->point->name == city2) {
- cout << "shortest distance " << city1 << " to " << city2 << " " << start->shortest << endl;
- city2_found = true;
- }
- start = start->next;
- }
- }
- else {
- cout << "failure" << endl;
- }
- }
- }
- }
- //reset
- node* start = my_graph.head;
- while (start != NULL) {
- start->colour = "white";
- child_node* copyback = start->children->head;
- while (copyback != NULL) {
- copyback->path_parent = NULL;
- copyback->shortest = copyback->distance;
- copyback = copyback->next;
- }
- start = start->next;
- }
- }
- else if (input == "print_path") {
- getline(cin, input);
- int end_value = 1;
- string current = "";
- string city1;
- string city2;
- for (int i = 1; i < input.length(); i++) {
- if (input[i] == ';') {
- city1 = current;
- current = "";
- continue;
- }
- current = current + input[i];
- if (i == input.length() - end_value) {
- city2 = current;
- }
- }
- double distance = 0;
- bool city2_found = false;
- int index = 0;
- int current_size = 0;
- int size = my_graph.return_size();
- node* first = my_graph.find_key(city1);
- if (city2 == city1) {
- cout << city1 << endl;
- city2_found = true;
- }
- else if (first == NULL) {
- cout << "failure" << endl;
- }
- else {
- child_node* start = first->children->head;
- if (start == NULL) {
- cout << "failure" << endl;
- }
- else {
- if (city2_found == false) {
- child_node* heap_array[size];
- for (int i = 0; i < size; i++) {
- heap_array[i] = NULL;
- }
- Heap my_heap;
- node* found_distance = NULL;
- my_heap.create(first, heap_array, index, current_size, city2_found);
- while (current_size >= 1) {
- node* pass = heap_array[0]->point;
- my_heap.relaxation(pass, heap_array, current_size, city2_found, size, found_distance, city2);
- }
- if (found_distance != NULL) {
- node* citypath[size];
- for (int i = 0; i < size; i++) {
- citypath[i] = NULL;
- }
- int cycle = 0;
- child_node* start = found_distance->children->head;
- while (start != NULL) {
- if (start->point->name == city2) {
- city2_found = true;
- break;
- }
- start = start->next;
- }
- citypath[cycle] = start->point;
- cycle = cycle + 1;
- //path print
- while (start->path_parent != NULL) {
- citypath[cycle] = start->path_parent->point;
- cycle = cycle + 1;
- if (start->path_parent == NULL) {
- break;
- }
- start = start->path_parent;
- }
- citypath[cycle] = start->parent;
- string current = "";
- for (int i = cycle; i >= 0; i--) {
- if (citypath[i] != NULL) {
- current = current + citypath[i]->name + " ";
- }
- }
- cout << current << endl;
- }
- else {
- cout << "failure" << endl;
- }
- }
- }
- }
- //reset
- node* start = my_graph.head;
- while (start != NULL) {
- start->colour = "white";
- child_node* copyback = start->children->head;
- while (copyback != NULL) {
- copyback->path_parent = NULL;
- copyback->shortest = copyback->distance;
- copyback = copyback->next;
- }
- start = start->next;
- }
- }
- else if (input == "clear") {
- my_graph.~Graph();
- names.clear();
- cout << "success" << endl;
- }
- if (cin.eof()) {
- break;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement