Commit cbc2006

mo khan <mo.khan@gmail.com>
2020-09-26 23:33:30
Extract adjacency matrix into separate files
master
1 parent e7fc8f9
Changed files (7)
src
03
05
README.md
avl_tree_test.c
graph_test.c
Makefile
matrix.c
matrix.h
matrix_test.c
src/03/05/README.md
@@ -551,7 +551,81 @@ 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.
+1. Iterate through list of edges.
+1. 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.
+1. Remove the edge from the matrix when visiting a node
+1. Backtrack to previous vertex, and remove the edge.
+1. Visit any edge where you can backtrack safely.
+
+An example of this algorithm can be found in `./matrix.c` with accompanying tests in `./matrix_test.c`.
+
+The graph to traverse is:
+
+```plaintext
+(a)---(b)---(c)---(d)
+ | \       /     /
+ |  \     /     /
+(e)  \(f)/  (g)/--(h)
+ |     |   / |    /
+ |     |  /  |   /
+(i)---(j)/  (k) / (l)
+ | \         | /   |
+ |  \        |/    |
+(m)  \(n)---(o)---(p)
+```
+
+We can build a matrix that will look like the following:
+
+```bash
+| |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|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|
+|f|1|0|1|0|0|0|0|0|0|1|0|0|0|0|0|0|
+|g|0|0|0|1|0|0|0|1|0|1|1|0|0|0|0|0|
+|h|0|0|0|0|0|0|1|0|0|0|0|0|0|0|1|0|
+|i|0|0|0|0|1|0|0|0|0|1|0|0|1|1|0|0|
+|j|0|0|0|0|0|1|1|0|1|0|0|0|0|0|0|0|
+|k|0|0|0|0|0|0|1|0|0|0|0|0|0|0|1|0|
+|l|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|1|
+|m|0|0|0|0|0|0|0|0|1|0|0|0|0|0|0|0|
+|n|0|0|0|0|0|0|0|0|1|0|0|0|0|0|1|0|
+|o|0|0|0|0|0|0|0|0|0|0|1|0|0|1|0|1|
+|p|0|0|0|0|0|0|0|0|0|0|0|1|0|0|1|0|
+```
+
+The order of traversal will be:
+
+```plaintext
+->(a)->(b)->(c)->(d)->(g)->(h)->(o)->(k)->(g)->(j)->(f)->(a)->(e)->(i)->(m)-
+                                                                           |
+|---------------------------------------------------------------------------
+->(i)->(n)->(o)->(p)->(l)->(p)->(o)->(n)->(i)->(j)->(i)->(e)->(a)->(f)->(c)-
+                                                                           |
+|---------------------------------------------------------------------------
+->(f)->(j)->(g)->(k)->(o)->(h)->(g)->(d)->(c)->(b)->(a)
+```
+
+After the traversal the matrix will have zero edges.
+
+```bash
+| |a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|
+|a|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|b|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|c|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|d|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|e|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|f|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|g|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|h|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|i|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|j|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|k|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|l|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|m|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|n|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|o|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+|p|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|
+```
src/03/avl_tree_test.c
@@ -379,15 +379,17 @@ TestSuite *avl_tree_tests() {
   return x;
 }
 
+TestSuite *graph_tests();
+TestSuite *matrix_tests();
 TestSuite *rb_tree_tests();
 TestSuite *sort_tests();
-TestSuite *graph_tests();
 
 int main(int argc, char **argv) {
   TestSuite *suite = create_test_suite();
   add_suite(suite, avl_tree_tests());
+  add_suite(suite, graph_tests());
+  add_suite(suite, matrix_tests());
   add_suite(suite, rb_tree_tests());
   add_suite(suite, sort_tests());
-  add_suite(suite, graph_tests());
   return run_test_suite(suite, create_text_reporter());
 }
src/03/graph_test.c
@@ -62,80 +62,6 @@ 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]);
-    }
-  }
-  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 graph_inspect(int n) {
-  printf("\n");
-
-  printf("| ");
-  for (int i = 0; i < n; ++i)
-    printf("|%c", labels[i]);
-  printf("|\n");
-
-  for (int i = 0; i < n; ++i) {
-    printf("|%c|", labels[i]);
-    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);
-  graph_inspect(n);
-
-  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() {
   TestSuite *x = create_test_suite();
@@ -147,6 +73,5 @@ 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;
 }
src/03/Makefile
@@ -5,8 +5,8 @@ CC=clang
 TEST_LIBS = -lcgreen
 
 BUILDDIR := build
-OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o sort.o graph.o)
-TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o sort_test.o graph_test.o)
+OBJS := $(addprefix $(BUILDDIR)/,avl_tree.o rb_tree.o sort.o graph.o matrix.o)
+TEST_OBJS := $(addprefix $(BUILDDIR)/,avl_tree_test.o rb_tree_test.o sort_test.o graph_test.o matrix_test.o)
 
 $(BUILDDIR)/%.o : %.c
 	$(COMPILE.c) $(OUTPUT_OPTION) $<
src/03/matrix.c
@@ -0,0 +1,50 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+char labels[26] = {
+  'a', 'b', 'c', 'd',
+  'e', 'f', 'g', 'h',
+  'i', 'j', 'k', 'l',
+  'm', 'n', 'o', 'p',
+  'q', 'r', 's', 't',
+  'u', 'v', 'w', 'x',
+  'y', 'z'
+};
+
+void matrix_traverse(int n, int graph[n][n], int visited[n], int vertex) {
+  printf("->(%c)", labels[vertex]);
+  visited[vertex] = 1;
+
+  for (int edge = 0; edge < n; ++edge) {
+    if (!visited[edge] && graph[vertex][edge] > 0) {
+      graph[vertex][edge] = 0;
+      matrix_traverse(n, graph, visited, edge);
+      graph[edge][vertex] = 0;
+      printf("->(%c)", labels[vertex]);
+    }
+  }
+  for (int edge = 0; edge < n; ++edge) {
+    if (graph[vertex][edge] > 0 && graph[edge][vertex] > 0) {
+      graph[vertex][edge] = 0;
+      matrix_traverse(n, graph, visited, edge);
+      graph[edge][vertex] = 0;
+      printf("->(%c)", labels[vertex]);
+    }
+  }
+}
+
+void matrix_inspect(int n, int graph[n][n]) {
+  printf("\n");
+
+  printf("| ");
+  for (int i = 0; i < n; ++i)
+    printf("|%c", labels[i]);
+  printf("|\n");
+
+  for (int i = 0; i < n; ++i) {
+    printf("|%c|", labels[i]);
+    for (int j = 0; j < n; ++j)
+      printf("%d|", graph[i][j]);
+    printf("\n");
+  }
+}
src/03/matrix.h
@@ -0,0 +1,3 @@
+
+void matrix_traverse(int n, int graph[n][n], int visited[n], int vertex);
+void matrix_inspect(int n, int graph[n][n]);
src/03/matrix_test.c
@@ -0,0 +1,42 @@
+#include "matrix.h"
+#include <cgreen/cgreen.h>
+#include <string.h>
+
+Ensure(every_edge_is_traversed_in_both_directions_at_least_once) {
+  int n = 16;
+  int visited[16] = {0};
+  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},
+  };
+
+  matrix_inspect(n, graph);
+  matrix_traverse(n, graph, visited, 0);
+  matrix_inspect(n, graph);
+
+  for (int i = 0; i < n; ++i)
+    for (int j = 0; j < n; ++j)
+      assert_that(graph[i][j], is_equal_to(0));
+}
+
+TestSuite *matrix_tests() {
+  TestSuite *x = create_test_suite();
+
+  add_test(x, every_edge_is_traversed_in_both_directions_at_least_once);
+
+  return x;
+}