From d8ea8dc5fa670477cb6a3c64a9fe7dbbb0c44898 Mon Sep 17 00:00:00 2001
From: Alexandre Jesus <adbjesus@gmail.com>
Date: Thu, 15 Sep 2016 00:32:24 +0100
Subject: Add dfs

---
 CMakeLists.txt     | 13 ++++++++++---
 include/dfs.h      |  8 ++++++++
 src/dfs.c          | 35 +++++++++++++++++++++++++++++++++++
 src/main/dfs.c     | 31 +++++++++++++++++++++++++++++++
 src/main/nem_ull.c |  2 +-
 5 files changed, 85 insertions(+), 4 deletions(-)
 create mode 100644 include/dfs.h
 create mode 100644 src/dfs.c
 create mode 100644 src/main/dfs.c

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 2c22493..da3c722 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -38,6 +38,7 @@ set(CMAKE_INSTALL_PREFIX ${CMAKE_CURRENT_SOURCE_DIR}/_install)
 set(INCLUDE_DIR ${CMAKE_CURRENT_SOURCE_DIR}/include)
 set(INCLUDE_FILES
   ${INCLUDE_DIR}/nem_ull.h
+  ${INCLUDE_DIR}/dfs.h
   ${INCLUDE_DIR}/structs.h
   ${INCLUDE_DIR}/common.h
 )
@@ -45,6 +46,7 @@ set(INCLUDE_FILES
 set(SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src)
 set(SRC_FILES
   ${SRC_DIR}/nem_ull.c
+  ${SRC_DIR}/dfs.c
   ${SRC_DIR}/common.c
 )
 
@@ -52,10 +54,15 @@ set(MAIN_SRC_DIR ${CMAKE_CURRENT_SOURCE_DIR}/src/main)
 
 include_directories (${INCLUDE_DIR})
 
-add_library(nem_ull_lib STATIC ${SRC_FILES})
+add_library(uknapsack STATIC ${SRC_FILES})
+
 add_executable(nem_ull ${MAIN_SRC_DIR}/nem_ull.c)
-target_link_libraries(nem_ull nem_ull_lib)
+add_executable(dfs ${MAIN_SRC_DIR}/dfs.c)
+
+target_link_libraries(nem_ull uknapsack)
+target_link_libraries(dfs uknapsack)
 
 install(TARGETS nem_ull DESTINATION bin)
-install(TARGETS nem_ull_lib DESTINATION lib)
+install(TARGETS dfs DESTINATION bin)
+install(TARGETS uknapsack DESTINATION lib)
 install(FILES ${INCLUDE_FILES} DESTINATION include)
diff --git a/include/dfs.h b/include/dfs.h
new file mode 100644
index 0000000..340f5c8
--- /dev/null
+++ b/include/dfs.h
@@ -0,0 +1,8 @@
+#ifndef _DFS_H
+#define _DFS_H
+
+#include "structs.h"
+
+struct front_item * dfs(struct data *);
+
+#endif
diff --git a/src/dfs.c b/src/dfs.c
new file mode 100644
index 0000000..3f34001
--- /dev/null
+++ b/src/dfs.c
@@ -0,0 +1,35 @@
+#include <stdlib.h>
+#include "dfs.h"
+#include "structs.h"
+#include "common.h"
+
+struct front_item * rec(struct data * d, int i, struct item * it) {
+  if(i == d->N) {
+    return new_front_item(it->p, it->w, NULL, NULL);
+  }
+
+  // Go left (select item)
+  it->p += d->items[i].p;
+  it->w += d->items[i].w;
+  struct front_item * f1 = rec(d, i+1, it);
+  it->p -= d->items[i].p;
+  it->w -= d->items[i].w;
+  // Go right (do not select item)
+  struct front_item * f2 = rec(d, i+1, it);
+
+  // Merge
+  struct front_item * f1_end = f1;
+  for(;f1_end->next!=NULL; f1_end = f1_end->next);
+  f1_end->next = f2;
+  f2->prev = f1_end;
+  
+  return f1;
+}
+
+struct front_item * dfs(struct data * d) {
+  struct item * it = (struct item *)malloc(sizeof(struct item));
+  it->p = 0;
+  it->w = 0;
+
+  return rec(d, 0, it);
+}
diff --git a/src/main/dfs.c b/src/main/dfs.c
new file mode 100644
index 0000000..36faa25
--- /dev/null
+++ b/src/main/dfs.c
@@ -0,0 +1,31 @@
+#include <stdio.h>
+#include <time.h>
+#include "common.h"
+#include "structs.h"
+#include "dfs.h"
+
+int main(int argc, char * argv[]){
+	struct data * d;
+  struct front_item * b;
+
+	if(argc!=2){
+		printf("Wrong number of arguments!\n");
+		printf("Example usage: %s data_file\n",argv[0]);
+		return 0;
+	}
+
+	d = input(argv[1]);
+
+  clock_t t = clock();
+  b = dfs(d);
+
+  t = clock() - t;
+	printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
+	
+  print_front(b);
+
+  free_front(b);
+  free_data(d);
+
+  return 0;
+}
diff --git a/src/main/nem_ull.c b/src/main/nem_ull.c
index 1bf183a..b267422 100644
--- a/src/main/nem_ull.c
+++ b/src/main/nem_ull.c
@@ -22,7 +22,7 @@ int main(int argc, char * argv[]){
 	t = clock() - t;
 	printf("%f,%d\n",((float)t)/CLOCKS_PER_SEC,len_front(b));
 
-	//print_front(b);
+	print_front(b);
 
 	free_front(b);
 	free_data(d);
-- 
cgit v1.2.3