A linear-time algorithm for detecting cycles in directed dependency graphs by bidirectional source-sink peeling.
Core idea: A vertex on a directed cycle must have at least one incoming edge and at least one outgoing edge. Therefore, any vertex with zero in-degree or zero out-degree cannot participate in a cycle and can be safely removed.
This project provides a C implementation of a graph-reduction algorithm for detecting whether a directed graph is a Directed Acyclic Graph (DAG).
The algorithm was originally derived from a practical engineering problem: in a large-scale offline batch processing system, the execution order between tasks is configured manually, so mistakes are inevitable and the configuration has to be validated by a program. Such a program cannot guarantee that the dependencies are logically correct, but it can at least guarantee the physical property that no circular dependency exists.
Instead of traversing paths and maintaining traversal state, the algorithm repeatedly removes vertices that are provably unable to participate in any cycle:
- Source: a vertex with
in-degree == 0 - Sink: a vertex with
out-degree == 0
Both are safe to remove.
The process continues until no more removable vertices exist.
- If all vertices are removed, the graph is a DAG.
- If vertices remain, the residual graph contains at least one directed cycle.
The implementation maintains both incoming and outgoing adjacency relationships so that removal can propagate efficiently from both directions.
Characteristics of bidirectional source-sink peeling:
- Structural elimination instead of traversal. The algorithm never selects a path to walk. It repeatedly deletes vertices that are provably outside every cycle, and stops when nothing more can be deleted.
- Local degree state instead of path state. The only question asked about a vertex is
inDegree == 0 OR outDegree == 0, so there is no recursion stack and no current-path bookkeeping. - Peeling from both ends. Removing only zero-in-degree vertices already decides DAG-ness — that is the structural idea behind Kahn's algorithm. Peeling sources and sinks simultaneously shrinks the graph from both sides toward the part that neither direction can eliminate.
- Linear cost. With adjacency lists and incremental degree maintenance, each vertex is removed at most once and each edge is processed a constant number of times, giving
O(|V| + |E|)time andO(|V| + |E|)space. - The residual graph is a region, not an exact answer. A non-empty residual graph is guaranteed to contain a cycle, but not every surviving vertex lies on one — a connector path between two cyclic regions also survives. Applying strongly connected component (SCC) decomposition to the residual graph yields the exact cyclic components.
For the full derivation, correctness proof, complexity analysis, pseudocode and the relation to existing graph algorithms, see:
- Bidirectional Source-Sink Peeling (English)
- 双向源汇剥离 (中文)
.
├── dag_check.c # Main program with DAG detection logic
├── graph_point.h # Graph node data structure definitions
├── graph_point.c # Graph node operations implementation
├── linked_deque.h # Double-ended queue definitions
├── linked_deque.c # Double-ended queue implementation
├── Makefile # Build configuration
└── README.md # This file
typedef struct point_s {
int num; // Node identifier
deque_t *from; // Incoming edges (source nodes)
deque_t *to; // Outgoing edges (destination nodes)
int queued; // Queue status flag
} point_t;Each graph node maintains both directions of adjacency:
from— incoming relationshipsto— outgoing relationships
This makes it possible to remove a vertex and efficiently update both its predecessors and successors.
A linked-list-based double-ended queue is used for:
- storing incoming graph edges,
- storing outgoing graph edges,
- managing vertices waiting to be eliminated.
- GCC compiler
- Make build tool
makemake cleanRun the compiled program:
./dag_checkThe demonstration program includes two test cases:
- A DAG (Directed Acyclic Graph)
- A graph containing a directed cycle
find_term_point done
point address : 0x...
clean point 1
point 1 delete relation ok
...
This graph is a Directed Acyclic Graph (DAG).
find_term_point done
point address : 0x...
clean point 1
point 1 delete relation fail
...
This graph is a Directed Cyclic Graph (DCG).
| Function | Description |
|---|---|
point_init(int num) |
Initialize a node with the given identifier |
point_free(point_t *p) |
Free a node and its memory |
point_add_edge(point_t *pa[], int from, int to) |
Add a directed edge between two nodes |
point_in_degree(point_t *p) |
Get the in-degree of a node |
point_out_degree(point_t *p) |
Get the out-degree of a node |
point_find_term(point_t *pa[], int len, deque_t *q) |
Find all source/sink vertices |
point_del_rel(point_t *p, deque_t *q) |
Delete a node's relationships |
| Function | Description |
|---|---|
deque_init(deque_t *) |
Initialize an empty deque |
deque_free(deque_t *) |
Free deque memory |
deque_empty(deque_t *) |
Check if deque is empty |
deque_enqueue(deque_t *, void *) |
Add element to rear |
deque_dequeue(deque_t *) |
Remove and return front element |
deque_first(deque_t *) |
Get front element without removing |
deque_last(deque_t *) |
Get rear element without removing |
This project should be understood primarily as an exploration of structural cycle elimination, rather than as a claim of a new graph-theoretic cycle-detection primitive.
The underlying source/sink elimination idea is closely related to established graph algorithms and graph-reduction techniques. The algorithm in this repository was independently derived from the dependency-validation problem described above.
The interesting design perspective is:
Do not search for a cycle directly.
Instead:
remove everything that cannot possibly be part of one.
This makes the approach particularly natural for dependency graphs where the primary requirement is to validate whether the configuration is structurally acyclic.
MIT License
Copyright (C) 2024 张懿曦(Zhang Yixi)
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.