blob: e5e0220e6e22981d4b7abb2ccc862f5814ffe6db (
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
|
/**
* @file cycle_detection.h
* @brief Cycle detection and topological sorting for directed graphs.
* @details This module implements Kahn's algorithm to detect cycles in
* directed graphs and perform topological sorting. A topological
* sort is only possible for acyclic graphs (DAGs).
*/
#ifndef CYCLE_DETECTION_H
#define CYCLE_DETECTION_H
#include "graph.h"
/**
* @brief Detects cycles in a directed graph and performs topological sorting.
*
* @param g Pointer to the directed graph to analyze.
* Must not be NULL.
*
* @details Prints to stdout whether the given graph has a cycle. In that case
* in prints 'CYCLE DETECTED!', else it prints the graph in
* topological sorting i.e. '4, 0, 1, 3, 2'.
*
* @note The input graph @p g may be modified during execution. The function
* alters vertex in-degree counts and neighbor lists as part of the
* algorithm. If the original graph structure must be preserved, the
* caller should provide a copy.
*
* @see Graph
* @see Vertex
*/
void cycle_detection(Graph *g);
#endif // !CYCLE_DETECTION_H
|