blob: 4581aa90ed37a75a2c14b571d0f0fa4dec6b5eaa (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
# Cycle Detection in C
A C program for detecting cycles in graphs.
---
## Compiling the Program
The project includes a `Makefile` which enables easy compilation
with `gcc` using a variety of flags.
To compile the program with default flags:
```bash
make
```
To compile the program with debugging symbols and no optimization:
```bash
make debug
```
To compile an optimized release version:
```bash
make release
```
To remove all build artifacts:
```bash
make clean
```
## Generating Documentation
Documentation will be generated to `docs/`
where a reference manual is available
in both `HTML` for viewing in a browser and `LaTeX` format.
The `LaTeX` output includes a `Makefile` for compiling the reference manual
`refman.pdf` with `pdflatex`.
> [!IMPORTANT]
> In order to generate the reference manual,
> the program [Doxygen](https://www.doxygen.nl/) is required.
To generate Doxygen documentation:
```bash
make docs
```
To remove generated documentation:
```bash
make clean-docs
```
## Available Targets
| Target | Description |
|--------|-------------|
| `all` | Build the project (default) |
| `debug` | Build with debug symbols and no optimization |
| `release` | Build optimized release version |
| `docs` | Generate Doxygen documentation |
| `clean` | Remove all build artifacts |
| `clean-docs` | Remove generated documentation |
| `help` | Display all available targets |
To list all available build targets and their descriptions:
```bash
make help
```
## Adjacency List Storage: Linked List vs Array
Two approaches for storing graph neighbors: linked lists and dynamic arrays.
Benchmarks show no measurable performance difference
despite vectors offering better cache locality.
Why? Kahn's algorithm is $O(V+E) $, so memory access patterns
likely isn't the bottleneck.
Cache locality could become a bottleneck on huge graphs
|