diff options
| -rw-r--r-- | CMakeLists.txt | 5 | ||||
| -rw-r--r-- | include/dfs.h | 1 | ||||
| -rw-r--r-- | include/random_heuristic.h | 1 | ||||
| -rw-r--r-- | include/structs.h | 5 | ||||
| -rw-r--r-- | src/dfs.c | 73 | ||||
| -rw-r--r-- | src/main/online.c | 64 | ||||
| -rw-r--r-- | src/random_heuristic.c | 92 |
7 files changed, 239 insertions, 2 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index dca0a4d..03d1063 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -57,10 +57,13 @@ set(MAIN_SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src/main) include_directories (${INCLUDE_DIR}) add_library(uknapsack STATIC ${SRC_FILES}) -add_executable(uknapsack_bin ${MAIN_SRC_DIR}/uknapsack) +add_executable(uknapsack_bin ${MAIN_SRC_DIR}/uknapsack.c) +add_executable(online ${MAIN_SRC_DIR}/online.c) target_link_libraries(uknapsack_bin uknapsack) +target_link_libraries(online uknapsack) install(TARGETS uknapsack_bin DESTINATION bin) +install(TARGETS online DESTINATION bin) install(TARGETS uknapsack DESTINATION lib) install(FILES ${INCLUDE_FILES} DESTINATION include) diff --git a/include/dfs.h b/include/dfs.h index 340f5c8..2a2c187 100644 --- a/include/dfs.h +++ b/include/dfs.h @@ -4,5 +4,6 @@ #include "structs.h" struct front_item * dfs(struct data *); +struct online_return dfs_online(struct data *, struct front_item *, struct tree_item *, long int); #endif diff --git a/include/random_heuristic.h b/include/random_heuristic.h index 586777e..9e9dac6 100644 --- a/include/random_heuristic.h +++ b/include/random_heuristic.h @@ -4,5 +4,6 @@ #include "structs.h" struct front_item * random_heuristic(struct data *); +struct online_return random_heuristic_online(struct data *, struct front_item *, struct tree_item *); #endif diff --git a/include/structs.h b/include/structs.h index 7c39b4d..1d15084 100644 --- a/include/structs.h +++ b/include/structs.h @@ -30,4 +30,9 @@ struct tree_item { struct tree_item * next; }; +struct online_return { + struct front_item * front; + struct tree_item * tree; +}; + #endif @@ -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; } |