feat: work on algorithm to find path that traverses each edges in both directions

2 files changed, 99 insertions, 2 deletions

diff --git a/src/03/05/README.md b/src/03/05/README.md
index 3601f76..eae128c 100644
--- a/src/03/05/README.md
+++ b/src/03/05/README.md
@@ -464,7 +464,7 @@ Order: [b, a, f, c, e, j, d, i, g, m, n, h, k, o, p, l]
 (m)  \(n)---(o)---(p)
 
 (a) -> [b, e, f]
-(b) -> [a, c, f]
+(b) -> [a, f]
 (c) -> [b, d, f]
 (d) -> [c, g]
 (e) -> [a, i]
@@ -481,6 +481,14 @@ Order: [b, a, f, c, e, j, d, i, g, m, n, h, k, o, p, l]
 (p) -> [l, o]
 ```
 
+Good:
+
+* Space efficient because no space is wasted for edges that do not exist.
+
+Bad:
+
+* A lookup to determine if two vertexes are connected requires a linear time lookup due to the size of the list for a single edge. `O(n)`.
+
 # Adjacency Matrix
 
 ```plaintext
@@ -500,7 +508,7 @@ Order: [b, a, f, c, e, j, d, i, g, m, n, h, k, o, p, l]
 -----------------------------------
 | |a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|
 |a|0|1|0|0|1|1|0|0|0|0|0|0|0|0|0|0|
-|b|1|0|1|0|0|1|0|0|0|0|0|0|0|0|0|0|
+|b|1|0|1|0|0|0|0|0|0|0|0|0|0|0|0|0|
 |c|0|1|0|1|0|1|0|0|0|0|0|0|0|0|0|0|
 |d|0|0|1|0|0|0|1|0|0|0|0|0|0|0|0|0|
 |e|1|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|
@@ -518,4 +526,26 @@ Order: [b, a, f, c, e, j, d, i, g, m, n, h, k, o, p, l]
 -----------------------------------
 ```
 
+Good:
+
+* constant time lookup to see if two vertexes are connected `O(1)`
+
+Bad:
+
+* space inefficient `O(n^2)`
+
+
+An adjacency matrix might be a better choice when space is less important
+than fast lookups. An adjacency list may be a better choice if space is
+a higher priority concern than time.
+
 # Traverse Every Edge
+
+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
+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.
diff --git a/src/03/graph_test.c b/src/03/graph_test.c
index eb2cf7e..e833573 100644
--- a/src/03/graph_test.c
+++ b/src/03/graph_test.c
@@ -62,6 +62,72 @@ Ensure(has_edge_returns_false) {
 
   assert_that(graph_has_edge(graph, a, c), is_equal_to(false));
 }
+int graph[16][16] = {
+  {0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,0},
+  {1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
+  {0,1,0,1,0,1,0,0,0,0,0,0,0,0,0,0},
+  {0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0},
+  {1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
+  {1,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0},
+  {0,0,0,1,0,0,0,1,0,1,1,0,0,0,0,0},
+  {0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0},
+  {0,0,0,0,1,0,0,0,0,1,0,0,1,1,0,0},
+  {0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0},
+  {0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0},
+  {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
+  {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
+  {0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0},
+  {0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1},
+  {0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0},
+};
+char labels[16] = {
+  'a', 'b', 'c', 'd',
+  'e', 'f', 'g', 'h',
+  'i', 'j', 'k', 'l',
+  'm', 'n', 'o', 'p'
+};
+int visited[16] = {0};
+
+void traverse(int vertex) {
+  printf("->(%c)", labels[vertex]);
+  visited[vertex] = 1;
+
+  for (int edge = 0; edge < 16; ++edge) {
+    if (!visited[edge] && graph[vertex][edge] > 0) {
+      graph[vertex][edge] = 0;
+      traverse(edge);
+      graph[edge][vertex] = 0;
+      printf("->(%c)", labels[vertex]);
+    }
+  }
+}
+
+void inspect_graph() {
+  printf("\n");
+
+  printf("| ");
+  for (int i = 0; i < 16; ++i)
+    printf("|%c", labels[i]);
+  printf("|\n");
+
+  for (int i = 0; i < 16; ++i) {
+    printf("|%c|", labels[i]);
+    for (int j = 0; j < 16; ++j)
+      printf("%d|", graph[i][j]);
+    printf("\n");
+  }
+}
+
+Ensure(every_edge_is_traversed_in_both_directions_at_least_once) {
+  traverse(0);
+  inspect_graph();
+
+  for (int i = 0; i < 16; ++i) {
+    for (int j = 0; j < 16; ++j) {
+      assert_that(graph[i][j], is_equal_to(0));
+    }
+  }
+}
 
 TestSuite *graph_tests() {
   TestSuite *x = create_test_suite();
@@ -73,5 +139,6 @@ TestSuite *graph_tests() {
   add_test(x, has_edge_returns_false);
   add_test(x, initialize_returns_a_new_graph);
 
+  add_test(x, every_edge_is_traversed_in_both_directions_at_least_once);
   return x;
 }