summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/dfs.c73
-rw-r--r--src/main/online.c64
-rw-r--r--src/random_heuristic.c92
3 files changed, 228 insertions, 1 deletions
diff --git a/src/dfs.c b/src/dfs.c
index 3e14362..b0bda53 100644
--- a/src/dfs.c
+++ b/src/dfs.c
@@ -1,4 +1,5 @@
#include <stdlib.h>
+#include <stdio.h>
#include "dfs.h"
#include "structs.h"
#include "common.h"
@@ -64,3 +65,75 @@ struct front_item * dfs(struct data * data) {
return front;
}
+
+
+struct online_return dfs_online(struct data * data, struct front_item * front, struct tree_item * tree, long int change_at){
+ if(front == NULL) {
+ front = new_front_item(0, 0, NULL, NULL);
+ }
+ struct front_item * front_last = front;
+ for(;front_last->next != NULL; front_last=front_last->next);
+
+ if(tree == NULL) {
+ tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
+ }
+
+ long int change=0;
+
+ /* Iterative dfs */
+ do {
+ /* Check if tree is leaf. If true:
+ * Add item to front_item;
+ * Update tree to tree->next;
+ * Free leaf;
+ * Continue;
+ */
+ if(tree->depth == data->N) {
+ front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL);
+ front_last = front_last->next;
+
+ struct tree_item * old = tree;
+ tree = tree->next;
+ if(tree != NULL) {
+ tree->prev = old->prev;
+ }
+ free(old);
+
+ change++;
+
+ continue;
+ }
+
+ /* Make left node (select item) */
+ struct tree_item * left = new_tree_item(
+ tree->depth + 1,
+ tree->itemi + 1,
+ tree->values.w + data->items[tree->itemi].w,
+ tree->values.p + data->items[tree->itemi].p,
+ tree->prev,
+ tree
+ );
+ /* Make right node (do not select item) */
+ struct tree_item * right = new_tree_item(
+ tree->depth + 1,
+ tree->itemi + 1,
+ tree->values.w,
+ tree->values.p,
+ left,
+ tree->next
+ );
+ /* Update left next */
+ left->next = right;
+
+ /* Update tree to left node and free old node */
+ struct tree_item * old = tree;
+ tree = left;
+ free(old);
+ } while(tree != NULL && change < change_at);
+
+ struct online_return ret;
+ ret.front = front;
+ ret.tree = tree;
+
+ return ret;
+}
diff --git a/src/main/online.c b/src/main/online.c
new file mode 100644
index 0000000..ba8a94c
--- /dev/null
+++ b/src/main/online.c
@@ -0,0 +1,64 @@
+#include <stdio.h>
+#include <time.h>
+#include <stdlib.h>
+#include <string.h>
+#include "common.h"
+#include "structs.h"
+#include "dfs.h"
+#include "random_heuristic.h"
+#include "nem_ull.h"
+
+int main(int argc, char * argv[]){
+ struct data * data;
+ struct front_item * front = NULL;
+ struct online_return ret;
+
+ if(argc!=5){
+ printf("Wrong number of arguments!\n");
+ printf("Example usage: %s algorithm1 algorithm2 sort_method data_file\n",argv[0]);
+ return 0;
+ }
+
+ data = input(argv[4]);
+
+ /* Sort data */
+ srand(time(NULL));
+ if(strcmp(argv[3], "random") == 0) {
+ qsort(data->items, data->N, sizeof(struct item), cmp_items_random);
+ } else if(strcmp(argv[3], "ratio") == 0) {
+ qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio);
+ }
+
+ clock_t t = clock();
+ /* Choose algorithm1 */
+ if(strcmp(argv[1], "dfs") == 0) {
+ ret = dfs_online(data, NULL, NULL, 20);
+ } else if(strcmp(argv[1], "random_heuristic") == 0) {
+ ret = random_heuristic_online(data, NULL, NULL);
+ }
+
+ /* Run algorithm2, if it hasn't finished yet*/
+ if(ret.tree!=NULL){
+ if(strcmp(argv[2], "dfs") == 0) {
+ ret = dfs_online(data, ret.front, ret.tree, 100);
+ } else if(strcmp(argv[2], "random_heuristic") == 0) {
+ ret = random_heuristic_online(data, ret.front, ret.tree);
+ }
+ }
+ front = ret.front;
+
+ /* Remove first item from front (only a placeholder) */
+ front=front->next;
+ free(front->prev);
+ front->prev = NULL;
+
+ t = clock() - t;
+ printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(front));
+
+ print_front(front);
+
+ free_front(front);
+ free_data(data);
+
+ return 0;
+}
diff --git a/src/random_heuristic.c b/src/random_heuristic.c
index bd3efa5..a2d0747 100644
--- a/src/random_heuristic.c
+++ b/src/random_heuristic.c
@@ -2,6 +2,7 @@
#include "random_heuristic.h"
#include "structs.h"
#include "common.h"
+#include <stdio.h>
struct front_item * random_heuristic(struct data * data) {
struct front_item * front = new_front_item(0, 0, NULL, NULL);
@@ -83,5 +84,94 @@ struct front_item * random_heuristic(struct data * data) {
front->prev = NULL;
return front;
- return NULL;
+}
+
+struct online_return random_heuristic_online(struct data * data, struct front_item * front, struct tree_item * tree) {
+
+
+ if(front == NULL) {
+ front = new_front_item(0, 0, NULL, NULL);
+ }
+ struct front_item * front_last = front;
+ for(;front_last->next != NULL; front_last=front_last->next);
+
+ if(tree == NULL) {
+ tree = new_tree_item(0, 0, 0, 0, NULL, NULL);
+ }
+ long int tree_size = 0;
+ for(struct tree_item * tree_node = tree; tree_node != NULL; tree_node = tree_node->next, tree_size++);
+
+ do {
+ /* Choose tree node randomly */
+ long int position = rand() % tree_size;
+ struct tree_item * node = tree;
+ for(int i = 0; i < position; i++,node=node->next);
+
+ /* Check if node is leaf */
+ if(node->depth == data->N) {
+ front_last->next = new_front_item(node->values.p, node->values.w, front_last, NULL);
+ front_last = front_last->next;
+
+ struct tree_item * old = node;
+ if(tree == old) {
+ tree = node->next;
+ }
+
+ if(node->next != NULL) {
+ node->next->prev = node->prev;
+ }
+ if(node->prev != NULL) {
+ node->prev->next = node->next;
+ }
+ free(old);
+ /* Reduce tree_size */
+ tree_size--;
+
+ continue;
+ }
+
+ /* Make left node (select item) */
+ struct tree_item * left = new_tree_item(
+ node->depth + 1,
+ node->itemi + 1,
+ node->values.w + data->items[node->itemi].w,
+ node->values.p + data->items[node->itemi].p,
+ node->prev,
+ node
+ );
+ if(node->prev != NULL){
+ node->prev->next = left;
+ }
+
+ /* Make right node (do not select item) */
+ struct tree_item * right = new_tree_item(
+ node->depth + 1,
+ node->itemi + 1,
+ node->values.w,
+ node->values.p,
+ left,
+ node->next
+ );
+ if(node->next != NULL) {
+ node->next->prev = right;
+ }
+
+ /* Adjust left->next to right */
+ left->next = right;
+
+ struct tree_item * old = node;
+ if(node == tree) {
+ tree = left;
+ }
+ free(old);
+
+ /* Increment tree_size */
+ tree_size++;
+ } while(tree != NULL);
+
+ struct online_return ret;
+ ret.front = front;
+ ret.tree = tree;
+
+ return ret;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-15 18:39:48 +0000