From e7fc8f9de29fbcd28b32d0ad743de9af0751340a Mon Sep 17 00:00:00 2001
From: mo khan <mo.khan@gmail.com>
Date: Sat, 26 Sep 2020 17:05:39 -0600
Subject: feat: implement backtracking algorithm to visit each edge in both
 directions

---
 src/03/05/README.md |  8 +++++++-
 src/03/graph_test.c | 26 +++++++++++++++++---------
 2 files changed, 24 insertions(+), 10 deletions(-)

(limited to 'src')

diff --git a/src/03/05/README.md b/src/03/05/README.md
index eae128c..72831f2 100644
--- a/src/03/05/README.md
+++ b/src/03/05/README.md
@@ -543,9 +543,15 @@ a higher priority concern than time.
 
 To traverse every edge in both directions we can use an adjacency matrix
 and iterate through every cell in the matrix. If the cell contains a 1 to
-indicate a connection than we know that we can traverse from the edge at
+indicate an edge than we know that we can traverse from the edge at
 that row and column. Both directions will be represented in different cells
 in the matrix.
 
 When we visit each cell in the matrix we can flip the 1 to a 0 to ensure that
 we do not revisit a visited edge.
+
+1. Start at any vertex
+2. Iterate through list of edges.
+3. If the vertex on the other end of the edge has not been visited yet then visit it and loop until all edges are exhausted for the vertex.
+4. Backtrack to previous vertex
+5. Visit any edge where you can backtrack safely.
diff --git a/src/03/graph_test.c b/src/03/graph_test.c
index e833573..55ee588 100644
--- a/src/03/graph_test.c
+++ b/src/03/graph_test.c
@@ -100,33 +100,41 @@ void traverse(int vertex) {
       printf("->(%c)", labels[vertex]);
     }
   }
+  for (int edge = 0; edge < 16; ++edge) {
+    if (graph[vertex][edge] > 0 && graph[edge][vertex] > 0) {
+      graph[vertex][edge] = 0;
+      traverse(edge);
+      graph[edge][vertex] = 0;
+      printf("->(%c)", labels[vertex]);
+    }
+  }
 }
 
-void inspect_graph() {
+void graph_inspect(int n) {
   printf("\n");
 
   printf("| ");
-  for (int i = 0; i < 16; ++i)
+  for (int i = 0; i < n; ++i)
     printf("|%c", labels[i]);
   printf("|\n");
 
-  for (int i = 0; i < 16; ++i) {
+  for (int i = 0; i < n; ++i) {
     printf("|%c|", labels[i]);
-    for (int j = 0; j < 16; ++j)
+    for (int j = 0; j < n; ++j)
       printf("%d|", graph[i][j]);
     printf("\n");
   }
 }
 
 Ensure(every_edge_is_traversed_in_both_directions_at_least_once) {
+  int n = 16;
+
   traverse(0);
-  inspect_graph();
+  graph_inspect(n);
 
-  for (int i = 0; i < 16; ++i) {
-    for (int j = 0; j < 16; ++j) {
+  for (int i = 0; i < n; ++i)
+    for (int j = 0; j < n; ++j)
       assert_that(graph[i][j], is_equal_to(0));
-    }
-  }
 }
 
 TestSuite *graph_tests() {
-- 
cgit v1.2.3