From 9d4394e359e69010114c1ddbef8a9e7fb53c5f9e Mon Sep 17 00:00:00 2001 From: Jakob Lykke Andersen Date: Sat, 29 Nov 2025 17:01:50 +0100 Subject: Add/update/reset files --- data/graphmatrix-1.txt | 6 +++ data/graphmatrix-10.txt | 101 ++++++++++++++++++++++++++++++++++++++++++++++++ data/graphmatrix-2.txt | 4 ++ data/graphmatrix-3.txt | 11 ++++++ data/graphmatrix-4.txt | 26 +++++++++++++ data/graphmatrix-5.txt | 101 ++++++++++++++++++++++++++++++++++++++++++++++++ data/graphmatrix-6.txt | 26 +++++++++++++ data/graphmatrix-7.txt | 51 ++++++++++++++++++++++++ data/graphmatrix-8.txt | 5 +++ data/graphmatrix-9.txt | 3 ++ src/Graph.h | 40 +++++++++++++++++++ src/LinkedList.h | 50 ++++++++++++++++++++++++ src/cycleDetection.h | 13 +++++++ src/main.c | 19 +++++++++ 14 files changed, 456 insertions(+) create mode 100644 data/graphmatrix-1.txt create mode 100644 data/graphmatrix-10.txt create mode 100644 data/graphmatrix-2.txt create mode 100644 data/graphmatrix-3.txt create mode 100644 data/graphmatrix-4.txt create mode 100644 data/graphmatrix-5.txt create mode 100644 data/graphmatrix-6.txt create mode 100644 data/graphmatrix-7.txt create mode 100644 data/graphmatrix-8.txt create mode 100644 data/graphmatrix-9.txt create mode 100644 src/Graph.h create mode 100644 src/LinkedList.h create mode 100644 src/cycleDetection.h create mode 100644 src/main.c diff --git a/data/graphmatrix-1.txt b/data/graphmatrix-1.txt new file mode 100644 index 0000000..13582d3 --- /dev/null +++ b/data/graphmatrix-1.txt @@ -0,0 +1,6 @@ +5 +01000 +00010 +00000 +00100 +10100 diff --git a/data/graphmatrix-10.txt b/data/graphmatrix-10.txt new file mode 100644 index 0000000..d5b31d4 --- /dev/null +++ b/data/graphmatrix-10.txt @@ -0,0 +1,101 @@ +100 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000 +0010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000100000000000000000000000000000000000000000000000000000001000000000000 +0000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000010000000000000000000000000000000010000000000000000000000000000000000 +1000010000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000100100000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000100000100000000000000000000000000 +0000000001000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000 +0000000000000000000000000000000000000000000000000000000000000000010000000000000000000000001000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000001000000000010000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000100001000000000000000000000000000 +0000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000100000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000010000000000000000000000000000000010000000001000000000100000000000 +0000001000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000 +0000000000000000000000000000000000000000000000000000000001000000000000000000000100000000000000000000 +0000001100000000000000000000000000000000000000000001000000000000000000000000000000000000000000000001 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000 +0000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000 +0000000000000000000000000000000000000000000000000000000000000000100010100000000001000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000 +0000001000000000000000000000100000000000000000000000000000000000000000000000000000100000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000 +0100000000000000000100000000000000000000000000000000000000000000000000000000000001000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000 +0000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000001000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000 +1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0100000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000 +0100100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000100000000000000000000000000000000000000000001000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000010000000000000000000000000000000000000100000000000000000000100000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000100010000000000000000000000000000000000000000000000000001000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000100000010000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000001000000000000000000000000000000000000000000000000001000000000000000000000000000000 +0000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000 +0000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000 +0000000010010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000 +0010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000001000000100000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000100000000000000000000000000000000000000000000001000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000000000000000000100000000000000000000000000000000000000 +0000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000 diff --git a/data/graphmatrix-2.txt b/data/graphmatrix-2.txt new file mode 100644 index 0000000..1f5eada --- /dev/null +++ b/data/graphmatrix-2.txt @@ -0,0 +1,4 @@ +3 +010 +001 +100 diff --git a/data/graphmatrix-3.txt b/data/graphmatrix-3.txt new file mode 100644 index 0000000..92d0bc0 --- /dev/null +++ b/data/graphmatrix-3.txt @@ -0,0 +1,11 @@ +10 +0111111111 +0011111111 +0001111111 +0000111111 +0000011111 +0000001111 +0000000111 +0000000011 +0000000001 +0000000000 diff --git a/data/graphmatrix-4.txt b/data/graphmatrix-4.txt new file mode 100644 index 0000000..c9a0145 --- /dev/null +++ b/data/graphmatrix-4.txt @@ -0,0 +1,26 @@ +25 +0111111111111111111111111 +0011111111111111111111111 +0001111111111111111111111 +0000111111111111111111111 +0000011111111111111111111 +0000001111111111111111111 +0000000111111111111111111 +0000000011111111111111111 +0000000001111111111111111 +0000000000111111111111111 +0000000000011111111111111 +0000000000001111111111111 +0000000000000111111111111 +0000000000000011111111111 +0000000000000001111111111 +0000000000000000111111111 +0000000000000000011111111 +0000000000000000001111111 +0000000000000000000111111 +0000000000000000000011111 +0000000000000000000001111 +0000000000000000000000111 +0000000000000000000000011 +0000000000000000000000001 +0000000000000000000000000 diff --git a/data/graphmatrix-5.txt b/data/graphmatrix-5.txt new file mode 100644 index 0000000..62f589a --- /dev/null +++ b/data/graphmatrix-5.txt @@ -0,0 +1,101 @@ +100 +0111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 +0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 diff --git a/data/graphmatrix-6.txt b/data/graphmatrix-6.txt new file mode 100644 index 0000000..de730d9 --- /dev/null +++ b/data/graphmatrix-6.txt @@ -0,0 +1,26 @@ +25 +0010001001000001100000000 +1000000001010100110010000 +0000010110100110000001000 +1100000010001000010010001 +0100010000000000110100000 +0000110110011100100100000 +0100100011000000000000110 +0000100000010010011110110 +0010000100010011010100001 +0001000000000010001011011 +0011000000100011000000000 +1100010000100000100001000 +0101000000001011101101010 +0000000100100001100000001 +1011011000000011010000100 +0000000110001110000101010 +1000000000000101000010110 +0000000000011111010000010 +0000010011001000001000110 +0000010000000100010011000 +0011010000001000011010110 +0011100110000001010000000 +0010101000000000001100000 +0000000100000001001001100 +0010010000100010010000100 diff --git a/data/graphmatrix-7.txt b/data/graphmatrix-7.txt new file mode 100644 index 0000000..c86feeb --- /dev/null +++ b/data/graphmatrix-7.txt @@ -0,0 +1,51 @@ +50 +01000000000000100000000000000000000000000000000000 +00000000000001000000000100000000000000100000100001 +00000100000000000000000000000000000001001000000000 +00000100000000000000000100000010000000010010000000 +00000000000000000000000000001100110000010110000000 +00000000000000000001000100000000000001101100000000 +00000000100000001000000010000000001000000000101000 +00000000000110000000000000000000000000000000000000 +00000000000001000000000000000010000100000000000100 +10000000000000000001000000000000000000000000000000 +00000000000000000000000000000000000000000000001000 +00000000000000000000000000001000000000000000000000 +00000000000000000100000000000000000000010000000000 +00000000000110000000000000000000000000000000000001 +10000000000000000000000000000000010010000000000000 +00000000000000000000110010000000000000000000100000 +00000000000000000000100000000000000000000111000000 +00000000000000000010000000000001000000000000000000 +00000000000000001000000000010010000000000000000000 +00000010100000000000000001000001010000000000000000 +01000000000000000000000000000000000000001000000000 +00000000000100000000000000000000000001000000000000 +00000000000010000000000000000000000000000001000000 +10000000000000000000100000000000000000001000000000 +00000000000000000000000000000000000000000000000000 +00001000000000100000000010000000000000000010001000 +00101000010000000000010000000100100000000100010000 +00000000000010000000000000000000000000000000100000 +00000000000001000000000000000000000000000000000000 +00000000000000000100000000100000000000001010000000 +00000000000000000000000000000000000000000100000000 +00000000010000000000100000000000100000000000001000 +00000010000000000010000010000000000000000010100000 +00000000000000010100000000000000000000000001000001 +00000000000000010001001100000100000001000001000000 +00000000000000000000000000100000000000000000000000 +00000000000000000100000010000000000000001000000000 +00100000010100000000000001000000000010000000000000 +00000000000000000000001000000000000001000000000000 +00000000000101000000000000000000000000000000000000 +00010100000001000000000000000000000000000000000000 +00000000000000000000100000000010000000000000000100 +10000000001010000000000000000000000000000000010000 +00000000000000000011000100101000000000000010000000 +00000110000000000000110000000000000000000000000000 +00000000000000000000000000000000000000000000000000 +00000000000000000000000000000000000000010000010000 +00000000001000000101000000000000000000000000000000 +01000000000000000000110000000000000000100000000000 +00000001000000000000000000100000000000000000000000 diff --git a/data/graphmatrix-8.txt b/data/graphmatrix-8.txt new file mode 100644 index 0000000..2bbcd58 --- /dev/null +++ b/data/graphmatrix-8.txt @@ -0,0 +1,5 @@ +4 +0100 +0010 +1000 +0000 diff --git a/data/graphmatrix-9.txt b/data/graphmatrix-9.txt new file mode 100644 index 0000000..a4e855b --- /dev/null +++ b/data/graphmatrix-9.txt @@ -0,0 +1,3 @@ +2 +01 +10 diff --git a/src/Graph.h b/src/Graph.h new file mode 100644 index 0000000..a0087ce --- /dev/null +++ b/src/Graph.h @@ -0,0 +1,40 @@ +#ifndef GRAPH_H +#define GRAPH_H + +#include "LinkedList.h" + +typedef struct Vertex Vertex; +typedef struct Graph Graph; +struct Vertex { + int id; // a number in [0; numVertices[ + LinkedList *outNeighbours; // A linked list of vertices. + LinkedList *inNeighbours; // A linked list of vertices +}; + +struct Graph { + int numVertices; + int numEdges; + Vertex *vertices; // An array of numVertices vertices +}; + +// Allocates and constructs a new graph with n vertices. +// Returns a pointer to the new graph, or NULL on error. +// Post: the caller owns the graph. +Graph *Graph_new(int n); + +// Adds an edge from the i'th to the j'th vertex (0-indexed). +void Graph_addEdge(Graph *g, int i, int j); + +// Reads a graph from the given file and returns a newly +// constructed Graph representing it. +// Returns a pointer to the read graph, or NULL on error. +// Post: the caller owns the graph. +Graph *Graph_read(const char *filename); + +// Deallocates the given graph and all its associated memory. +void Graph_delete(Graph *g); + +// Prints some useful information about the given graph. +void Graph_print(Graph *g); + +#endif // GRAPH_H diff --git a/src/LinkedList.h b/src/LinkedList.h new file mode 100644 index 0000000..f30d44b --- /dev/null +++ b/src/LinkedList.h @@ -0,0 +1,50 @@ +#ifndef LINKEDLIST_H +#define LINKEDLIST_H + +// A linked list containing any type of pointer. +// The linked list does _not_ own its elements. + +typedef struct LinkedList LinkedList; +typedef struct LinkedListNode LinkedListNode; + +struct LinkedList { + LinkedListNode *head; + LinkedListNode *tail; + int size; +}; + +struct LinkedListNode { + LinkedListNode *next; + LinkedListNode *prev; + void *data; +}; + +// Allocate and initialize an empty linked list. +// Returns: a pointer to the new linked list, or NULL on error. +// Post: the caller owns the linked list. +LinkedList *LinkedList_new(); + +// Deallocate the given linked list, including all nodes +// (but _not_ the data they point to, the user owns that). +void LinkedList_delete(LinkedList *ll); + +// Append a the given element to the list. +// The linked list does _not_ take ownership over the element +// (only the linked list node). +// Returns: a pointer to the node with the new element, or NULL on error. +LinkedListNode *LinkedList_append(LinkedList *ll, void *elem); + +// Remove and return the first element from the given list. +// Pre: ll->size != 0 +void *LinkedList_popFront(LinkedList *ll); + +// Find the linked list node containing the given element. +// Returns: a pointer to the found node, or NULL if the element was not found. +LinkedListNode *LinkedList_find(LinkedList *ll, void *elem); + +// Remove the given node from the given linked list (and deallocate it). +// Pre: node must belong to ll +// Returns: node->data +void *LinkedList_remove(LinkedList *ll, LinkedListNode *node); + +#endif // LINKEDLIST_H diff --git a/src/cycleDetection.h b/src/cycleDetection.h new file mode 100644 index 0000000..e1b62e0 --- /dev/null +++ b/src/cycleDetection.h @@ -0,0 +1,13 @@ +#ifndef CYCLEDETECTION_H +#define CYCLEDETECTION_H + +#include "Graph.h" + +// Runs Kahn's algorithm on the graph, and outputs 'CYCLE DETECTED!\n' +// if a DAG cannot be created, or the vertices as a list fx. '4, 0, 1, 3, 2\n' +// representing an ordering in the DAG. +// The output is printed to stdout. +// The input may be altered in the process. +void cycleDetection(Graph *g); + +#endif // CYCLEDETECTION_H diff --git a/src/main.c b/src/main.c new file mode 100644 index 0000000..1ab1ebc --- /dev/null +++ b/src/main.c @@ -0,0 +1,19 @@ +#include "cycleDetection.h" + +#include +#include + +int main(int argc, char **argv) { + if(argc < 2) { + printf("Missing argument: input file\n"); + printf("Usage:\n"); + printf("%s \n", argv[0]); + return 1; + } + + Graph *g = Graph_read(argv[1]); + if(!g) return 2; + cycleDetection(g); + Graph_delete(g); + return 0; +} -- cgit v1.2.3-70-g09d2