From cbc20066c9b321b4502cbda1e43812f78c9c2388 Mon Sep 17 00:00:00 2001 From: mo khan Date: Sat, 26 Sep 2020 17:33:30 -0600 Subject: Extract adjacency matrix into separate files --- src/03/05/README.md | 82 +++++++++++++++++++++++++++++++++++++++++++++++--- src/03/Makefile | 4 +-- src/03/avl_tree_test.c | 6 ++-- src/03/graph_test.c | 75 --------------------------------------------- src/03/matrix.c | 50 ++++++++++++++++++++++++++++++ src/03/matrix.h | 3 ++ src/03/matrix_test.c | 42 ++++++++++++++++++++++++++ 7 files changed, 179 insertions(+), 83 deletions(-) create mode 100644 src/03/matrix.c create mode 100644 src/03/matrix.h create mode 100644 src/03/matrix_test.c diff --git a/src/03/05/README.md b/src/03/05/README.md index 72831f2..939f794 100644 --- a/src/03/05/README.md +++ b/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| +``` diff --git a/src/03/Makefile b/src/03/Makefile index 6bb32b2..dfaa109 100644 --- a/src/03/Makefile +++ b/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) $< diff --git a/src/03/avl_tree_test.c b/src/03/avl_tree_test.c index 2c375cc..0d280ae 100644 --- a/src/03/avl_tree_test.c +++ b/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()); } diff --git a/src/03/graph_test.c b/src/03/graph_test.c index 55ee588..eb2cf7e 100644 --- a/src/03/graph_test.c +++ b/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; } diff --git a/src/03/matrix.c b/src/03/matrix.c new file mode 100644 index 0000000..752eabd --- /dev/null +++ b/src/03/matrix.c @@ -0,0 +1,50 @@ +#include +#include + +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"); + } +} diff --git a/src/03/matrix.h b/src/03/matrix.h new file mode 100644 index 0000000..a44e0d8 --- /dev/null +++ b/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]); diff --git a/src/03/matrix_test.c b/src/03/matrix_test.c new file mode 100644 index 0000000..0958df7 --- /dev/null +++ b/src/03/matrix_test.c @@ -0,0 +1,42 @@ +#include "matrix.h" +#include +#include + +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; +} -- cgit v1.2.3