From 90999d01eff3b197001739ee3ee9ff6dd64217ce Mon Sep 17 00:00:00 2001
From: Julian T <julian@jtle.dk>
Date: Fri, 22 Nov 2019 11:06:21 +0100
Subject: Added bench

---
 sem1/algo/workshop2/dfs/dfs     | Bin 24400 -> 24960 bytes
 sem1/algo/workshop2/dfs/dfs.c   |  47 +++++++++++++++++++++++++++++++++-------
 sem1/algo/workshop2/dfs/graph.c |  11 ++++++----
 3 files changed, 46 insertions(+), 12 deletions(-)

diff --git a/sem1/algo/workshop2/dfs/dfs b/sem1/algo/workshop2/dfs/dfs
index f608d28..0d9ff14 100755
Binary files a/sem1/algo/workshop2/dfs/dfs and b/sem1/algo/workshop2/dfs/dfs differ
diff --git a/sem1/algo/workshop2/dfs/dfs.c b/sem1/algo/workshop2/dfs/dfs.c
index 8c4faf6..1244895 100644
--- a/sem1/algo/workshop2/dfs/dfs.c
+++ b/sem1/algo/workshop2/dfs/dfs.c
@@ -1,6 +1,8 @@
 #include <stdio.h>
 #include <stdbool.h>
 #include <time.h>
+#include <string.h>
+#include <stdlib.h>
 
 #include "graph.h"
 
@@ -10,7 +12,7 @@ int step;
 
 void dfs_visit(graph_t *g, vertex_t *u, bool doprint) {
 	if( doprint ) {
-		printf("dfs_visit( %c )\n", u->ref);
+		printf("dfs_visit( %s )\n", u->ref);
 	}
 	step++;
 	u->dtime = step;
@@ -22,7 +24,6 @@ void dfs_visit(graph_t *g, vertex_t *u, bool doprint) {
 		vertex_t *v = e->to;
 		if( v->color == COLOR_WHITE ) {
 			graph_edge(&newg, v->ref, u->ref, 1);
-			v->p = u;
 			dfs_visit(g, v, doprint);
 		}
 		e = e->next;
@@ -47,16 +48,46 @@ void dfs(graph_t *g, bool doprint) {
 	}
 }
 
+#define BENCH 9999
+
 int main() {
+
+	// benchmark
+
+	// Start by generating
+	for(int i = 0; i < BENCH; i++) {
+		char from[5];
+		char to[5];
+		sprintf(from, "%d", i);
+		sprintf(to, "%d", rand() % BENCH);
+		graph_edge(&g, from, to, 1);
+	}
+	FILE *f = fopen("hej.dot", "w");
+	graph_to_dot(f, &g);
+
+	{
+		// Timing start
+		clock_t t;
+		t = clock();
+
+		dfs(&g, true);
+
+		// Timing stop
+		t = clock() - t;
+		double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
+		printf("Dfs took %f seconds\n", time_taken);
+	}
+	
+	return 0;
 	
-	graph_edge(&g, 'M', 'O', 1);
-	graph_edge(&g, 'O', 'P', 1);
-	graph_edge(&g, 'P', 'F', 1);
+	graph_edge(&g, "hej", "med", 1);
+	graph_edge(&g, "med", "dig", 1);
+	graph_edge(&g, "dig", "hvordan", 1);
 
-	graph_edge(&g, 'C', 'F', 1);
-	graph_edge(&g, 'F', 'c', 1);
+	graph_edge(&g, "det", "hvordan", 1);
+	graph_edge(&g, "hvordan", "det", 1);
 
-	//graph_to_dot(stdout, &g);
+	graph_to_dot(stdout, &g);
 	
 	// Timing start
 	clock_t t;
diff --git a/sem1/algo/workshop2/dfs/graph.c b/sem1/algo/workshop2/dfs/graph.c
index 11ee07f..0f5048c 100644
--- a/sem1/algo/workshop2/dfs/graph.c
+++ b/sem1/algo/workshop2/dfs/graph.c
@@ -50,7 +50,7 @@ static vertex_t *create_vertex(char *ref) {
 	vertex_t *v = malloc(sizeof(vertex_t));
 
 	// Set values
-	v->ref = ref;
+	v->ref = strdup(ref);
 	v->color = COLOR_WHITE;
 	v->next = NULL;
 	v->adj = NULL;
@@ -90,10 +90,13 @@ edge_t *edge_next(graph_t *g, edge_t *e) {
 
 		// Find next vertex
 		v = vertex_next(g, v);
+		while( v ) {
+			// Check if found
+			if( v->adj ) {
+				return v->adj;
+			}
 
-		// Check if found
-		if( v ) {
-			return v->adj;
+			v = vertex_next(g, v);
 		}
 
 		// No next vertex
-- 
cgit v1.2.3