commit c4da12abd7159d383d5c5aa9d004fc35d98e07b0 Author: sej <sej@sejdt.localhost> Date: Sun, 13 Oct 2024 22:32:24 +0200 Initial Commit Diffstat:
| A | .gitignore | | | 2 | ++ |
| A | README | | | 5 | +++++ |
| A | data/graphmatrix-1.txt | | | 6 | ++++++ |
| A | data/graphmatrix-10.txt | | | 101 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | data/graphmatrix-2.txt | | | 4 | ++++ |
| A | data/graphmatrix-3.txt | | | 11 | +++++++++++ |
| A | data/graphmatrix-4.txt | | | 26 | ++++++++++++++++++++++++++ |
| A | data/graphmatrix-5.txt | | | 101 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | data/graphmatrix-6.txt | | | 26 | ++++++++++++++++++++++++++ |
| A | data/graphmatrix-7.txt | | | 51 | +++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | data/graphmatrix-8.txt | | | 5 | +++++ |
| A | data/graphmatrix-9.txt | | | 3 | +++ |
| A | src/Graph.c | | | 84 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/Graph.h | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
| A | src/LinkedList.c | | | 83 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/LinkedList.h | | | 49 | +++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/Makefile | | | 10 | ++++++++++ |
| A | src/cycleDetection.c | | | 70 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/cycleDetection.h | | | 13 | +++++++++++++ |
| A | src/main.c | | | 19 | +++++++++++++++++++ |
20 files changed, 709 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore @@ -0,0 +1,2 @@ +src/.gdb_history +src/detectCycles diff --git a/README b/README @@ -0,0 +1,5 @@ +# Cycle Detection with Kahn's algorithm + +Assignment for DM548 + +Reupload diff --git a/data/graphmatrix-1.txt 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 @@ -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 @@ -0,0 +1,4 @@ +3 +010 +001 +100 diff --git a/data/graphmatrix-3.txt 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 @@ -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 @@ -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 @@ -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 @@ -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 @@ -0,0 +1,5 @@ +4 +0100 +0010 +1000 +0000 diff --git a/data/graphmatrix-9.txt b/data/graphmatrix-9.txt @@ -0,0 +1,3 @@ +2 +01 +10 diff --git a/src/Graph.c b/src/Graph.c @@ -0,0 +1,84 @@ +#include "cycleDetection.h" +#include "LinkedList.h" + +#include <stdlib.h> +#include <stdio.h> + +Graph *Graph_new( int n ) { + Graph *g = malloc( sizeof( Graph ) ); + if ( !g ) // allocation failed + return NULL; + g->numVertices = n; + g->numEdges = 0; + g->vertices = malloc( sizeof( Vertex[n] ) ); + for ( int i = 0; i < n; i = i + 1 ) { + g->vertices[i].id = i; + g->vertices[i].outNeighbours = LinkedList_new(); + g->vertices[i].inNeighbours = LinkedList_new(); + } + + return g; +} + +void Graph_addEdge( Graph *g, int i, int j ) { + LinkedList_append( g->vertices[i].outNeighbours, &g->vertices[j] ); + LinkedList_append( g->vertices[j].inNeighbours, &g->vertices[i] ); +} + +void Graph_delete( Graph *g ) { + for ( int i = 0; i < g->numVertices; i += 1 ) { + Vertex v = g->vertices[i]; + LinkedList_delete( v.outNeighbours ); + LinkedList_delete( v.inNeighbours ); + } + free( g->vertices ); + free( g ); +} + +Graph *Graph_read( const char *filename ) { + FILE *f = fopen( filename, "r" ); + size_t n = 1024; // max size of graph is thus 1023 vertices + char *line = malloc( n ); + getline( &line, &n, f ); + + int size = atoi( line ); + Graph *g = Graph_new( size ); + if ( !g ) // allocation failed + return NULL; + + for ( int i = 0; i < size; i += 1 ) { + getline( &line, &n, f ); + for ( int j = 0; j < size; j += 1 ) { + if ( line[j] == '1' ) { + //printf( "i:%i j:%i\n", i, j ); + Graph_addEdge( g, i, j ); + } + } + } + free( line ); + fclose( f ); + return g; +} + +void Graph_print( Graph *g ) { + for ( int i = 0; i < g->numVertices; i += 1 ) { + Vertex v = g->vertices[i]; + //printf( "node id %i\tin:%i\tout:%i\n", g->vertices[i].id, g->vertices[i].inNeighbours->size, g->vertices[i].outNeighbours->size ); + printf( "id: %i\n", v.id ); + printf( " out:\n" ); + LinkedListNode *p = v.outNeighbours->tail; + while ( p ) { + Vertex *u = p->data; + printf( " %i\n", u->id ); + p = p->next; + } + printf( " in:\n" ); + p = v.inNeighbours->tail; + while ( p ) { + Vertex *u = p->data; + printf( " %i\n", u->id ); + p = p->next; + } + printf( "\n" ); + } +} diff --git a/src/Graph.h 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.c b/src/LinkedList.c @@ -0,0 +1,83 @@ +#include "LinkedList.h" +#include "Graph.h" +#include <stdio.h> +#include <stdlib.h> +#include <assert.h> + +LinkedList *LinkedList_new() { + LinkedList *ll = malloc( sizeof( LinkedList ) ); + if ( !ll ) + return NULL; + ll->head = NULL; + ll->tail = NULL; + ll->size = 0; + return ll; +} + +LinkedListNode *LinkedList_append( LinkedList *ll, void *elem ) { + LinkedListNode *node = malloc( sizeof( LinkedListNode ) ); + if ( !node ) + return NULL; + node->data = elem; + if ( ll->size == 0 ) + ll->head = node; + node->next = ll->tail; + if( node->next ) + node->next->prev = node; + node->prev = NULL; + ll->tail = node; + ll->size += 1; + return node; +} + +/* + * Den her funktion er muligvis lidt buggy + */ +void *LinkedList_popFront( LinkedList *ll ) { + assert( ll->size > 0 ); + LinkedListNode *front = ll->head; + if ( ll->size == 1 ) + ll->head = ll->tail = NULL; + else { // ll->size > 1 + ll->head = front->prev; + ll->head->next = NULL; + } + ll->size -= 1; + void *elem = front->data; + free( front ); + return elem; +} + +void LinkedList_delete( LinkedList *ll ) { + LinkedListNode *p = ll->tail; + LinkedListNode *pt; + while ( p ) { + pt = p->next; + free( p ); + p = pt; + } + free( ll ); +} + +void *LinkedList_remove( LinkedList *ll, LinkedListNode *node ) { + if ( node->next ) + node->next->prev = node->prev; + else // first element + ll->head = node->prev; + if ( node->prev ) + node->prev->next = node->next; + else // last element + ll->tail = node->next; + void *elem = node->data; + free( node ); + ll->size -= 1; + return elem; +} + +LinkedListNode *LinkedList_find( LinkedList *ll, void *elem ) { + LinkedListNode *p = ll->tail; + while ( p && p->data != elem ) { + p = p->next; + } + return p; +} diff --git a/src/LinkedList.h b/src/LinkedList.h @@ -0,0 +1,49 @@ +#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. +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/Makefile b/src/Makefile @@ -0,0 +1,10 @@ +SAN_FLAGS = -fsanitize=address -fsanitize=leak -fsanitize=undefined +CFLAGS = -Wall -Wextra -g +CFILES = main.c Graph.c cycleDetection.c LinkedList.c + +detectCycles: + $(CC) $(CFLAGS) $(CFILES) -o detectCycles + +.PHONY: clean +clean: + rm detectCycles diff --git a/src/cycleDetection.c b/src/cycleDetection.c @@ -0,0 +1,70 @@ +#include "cycleDetection.h" +#include "LinkedList.h" +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> + +void cycleDetection( Graph *g ) { + LinkedList *L = LinkedList_new(); // Empty list of vertiecs + LinkedList *S = LinkedList_new(); // A set of all vertices of g with no incoming edges + for ( int i = 0; i < g->numVertices; i += 1 ) + if ( g->vertices[i].inNeighbours->size == 0 ) + LinkedList_append( S, &g->vertices[i] ); + + // print S + /* + LinkedListNode *n = S->head; + while ( n ) { + Vertex *v = n->data; + printf( "S: %i\n", v->id ); + n = n->prev; + }*/ + + + //printf( "S size: %i\n", S->size ); + while ( S->size > 0 ) { // While s is non-empty + + Vertex *u = LinkedList_popFront( S ); // A node removed from S + LinkedList_append( L, u ); // Append u to the tail of L + // printf( "L->size: %i\n", L->size ); + // printf( "u out: %i\n", u->outNeighbours->size ); + + while ( u->outNeighbours->size > 0 ) { // For each vertex v in g with an edge from u to v + Vertex *v = LinkedList_popFront( u->outNeighbours ); + // printf( "v: %i\n", v->id ); + if ( v->inNeighbours->size == 1 ) { // If v has no other incoming edges than e + LinkedList_append( S, v ); // Insert v in S + // printf( "no other in e: %i\n", v->id ); + } + // Remove edge from graph + // v already popped from u->outneighbours + LinkedListNode *n = LinkedList_find( v->inNeighbours, u ); + LinkedList_remove( v->inNeighbours, n ); + } + } + + bool noEdges = true; + int i = 0; + while ( i < g->numVertices && noEdges ) { + Vertex v = g->vertices[i]; + // printf( "in: %i, out: %i\n", v.inNeighbours->size, v.outNeighbours->size ); + if ( v.inNeighbours->size > 0 || v.outNeighbours->size > 0 ) + noEdges = false; + i = i + 1; + } + + if ( !noEdges ) + printf( "CYCLE DETECTED!\n" ); + else { + Vertex *v = LinkedList_popFront( L ); + printf( "%i", v->id ); + while ( L->size > 0 ) { + v = LinkedList_popFront( L ); + printf( ", %i", v->id ); + } + printf( "\n" ); + } + + LinkedList_delete( S ); + LinkedList_delete( L ); +} diff --git a/src/cycleDetection.h 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 @@ -0,0 +1,19 @@ +#include "cycleDetection.h" + +#include <stdio.h> +#include <stdlib.h> + +int main(int argc, char **argv) { + if(argc < 2) { + printf("Missing argument: input file\n"); + printf("Usage:\n"); + printf("%s <filename>\n", argv[0]); + return 1; + } + + Graph *g = Graph_read(argv[1]); + if(!g) return 2; + cycleDetection(g); + Graph_delete(g); + return 0; +}