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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
//! DAG predicate (ALGO-PR-020).
//!
//! Counterpart of `igraph_is_dag()` from
//! `references/igraph/src/properties/dag.c:151`. Returns `true` iff
//! `graph` is a directed acyclic graph. Undirected graphs are
//! always `false` (a DAG must be directed by definition — matches
//! upstream).
//!
//! Algorithm: Kahn's topological-sort. Repeatedly peel off
//! zero-in-degree vertices until either the graph is empty (DAG)
//! or every remaining vertex has at least one incoming edge
//! (a cycle exists). Self-loops are detected as an early
//! short-circuit because they contribute a vertex with
//! `in-degree >= 1` that can never be peeled.
//!
//! Time complexity: `O(V + E)`.
use std::collections::VecDeque;
use crate::core::Graph;
use crate::core::cache::CachedProperty;
use crate::core::graph::VertexId;
/// Returns `true` iff `graph` is a directed acyclic graph.
///
/// Undirected graphs return `false` unconditionally (matches
/// upstream — DAGs are directed by definition). Empty graphs and
/// graphs with isolated vertices but no edges return `true`.
///
/// Algorithm: Kahn's topological-sort peel. Start with vertices
/// whose in-degree is 0 in a queue; pop one, "remove" it by
/// decrementing the in-degree of its out-neighbours. If any
/// neighbour reaches 0, queue it. A self-loop is short-circuited
/// to `false` because the loop's tail can never have its in-degree
/// reduced past itself.
///
/// Counterpart of `igraph_is_dag` from
/// `references/igraph/src/properties/dag.c:151`.
///
/// # Examples
///
/// ```
/// use rust_igraph::{Graph, is_dag};
///
/// // Linear chain 0 → 1 → 2 — a DAG.
/// let mut g = Graph::new(3, true).unwrap();
/// g.add_edge(0, 1).unwrap();
/// g.add_edge(1, 2).unwrap();
/// assert!(is_dag(&g));
///
/// // Cycle 0 → 1 → 2 → 0 — not a DAG.
/// let mut g = Graph::new(3, true).unwrap();
/// g.add_edge(0, 1).unwrap();
/// g.add_edge(1, 2).unwrap();
/// g.add_edge(2, 0).unwrap();
/// assert!(!is_dag(&g));
/// ```
#[must_use]
pub fn is_dag(graph: &Graph) -> bool {
if !graph.is_directed() {
return false;
}
if let Some(v) = graph.cache_get(CachedProperty::IsDag) {
return v;
}
let n = graph.vcount();
let n_us = n as usize;
// In-degree of every vertex. `incident_in(v)` returns the in-edges
// on a directed graph; its length is the in-degree.
let mut in_deg: Vec<u32> = Vec::with_capacity(n_us);
for v in 0..n {
let deg = u32::try_from(
graph
.incident_in(v)
.expect("incident_in on valid vertex")
.len(),
)
.unwrap_or(u32::MAX);
in_deg.push(deg);
}
// Queue of vertices with current in-degree 0.
let mut sources: VecDeque<VertexId> = VecDeque::new();
for v in 0..n {
if in_deg[v as usize] == 0 {
sources.push_back(v);
}
}
let mut peeled: u32 = 0;
while let Some(v) = sources.pop_front() {
peeled = peeled.saturating_add(1);
// Walk out-edges; for each neighbour, drop its in-degree.
let out_eids = graph.incident(v).expect("incident on valid vertex");
for eid in out_eids {
let nei = graph.edge_other(eid, v).expect("edge_other on valid edge");
if nei == v {
// Self-loop: vertex v depends on itself; it can
// never be peeled away. The graph has a cycle.
return false;
}
let nei_idx = nei as usize;
in_deg[nei_idx] = in_deg[nei_idx].saturating_sub(1);
if in_deg[nei_idx] == 0 {
sources.push_back(nei);
}
}
}
let result = peeled == n;
graph.cache_set(CachedProperty::IsDag, result);
result
}
#[cfg(test)]
mod tests {
use super::*;
use crate::core::Graph;
#[test]
fn empty_directed_graph_is_dag() {
let g = Graph::new(0, true).unwrap();
assert!(is_dag(&g));
}
#[test]
fn isolated_vertices_only_is_dag() {
let g = Graph::new(5, true).unwrap();
assert!(is_dag(&g));
}
#[test]
fn linear_chain_is_dag() {
let mut g = Graph::new(4, true).unwrap();
g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 3)]).unwrap();
assert!(is_dag(&g));
}
#[test]
fn binary_tree_is_dag() {
// 0 → 1, 0 → 2, 1 → 3, 1 → 4.
let mut g = Graph::new(5, true).unwrap();
g.add_edges(vec![(0u32, 1u32), (0, 2), (1, 3), (1, 4)])
.unwrap();
assert!(is_dag(&g));
}
#[test]
fn three_cycle_is_not_dag() {
let mut g = Graph::new(3, true).unwrap();
g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 0)]).unwrap();
assert!(!is_dag(&g));
}
#[test]
fn self_loop_is_not_dag() {
let mut g = Graph::new(2, true).unwrap();
g.add_edge(0, 0).unwrap();
g.add_edge(0, 1).unwrap();
assert!(!is_dag(&g));
}
#[test]
fn undirected_graph_is_not_dag_even_if_acyclic() {
// Undirected path 0-1-2 — acyclic as a graph but the
// upstream contract is "DAGs are directed".
let mut g = Graph::with_vertices(3);
g.add_edges(vec![(0u32, 1u32), (1, 2)]).unwrap();
assert!(!is_dag(&g));
}
#[test]
fn dag_with_multiple_roots() {
// Two disjoint DAG branches feeding into a sink.
// 0 → 2, 1 → 2.
let mut g = Graph::new(3, true).unwrap();
g.add_edges(vec![(0u32, 2u32), (1, 2)]).unwrap();
assert!(is_dag(&g));
}
#[test]
fn dag_with_parallel_edges_still_dag() {
// Parallel edges 0→1 don't introduce a cycle.
let mut g = Graph::new(2, true).unwrap();
g.add_edge(0, 1).unwrap();
g.add_edge(0, 1).unwrap();
assert!(is_dag(&g));
}
#[test]
fn cycle_with_extra_tail_branches_not_dag() {
// Cycle 0→1→2→0 plus a tail 3→0. The tail can be peeled
// but the cycle remains, so the graph is not a DAG.
let mut g = Graph::new(4, true).unwrap();
g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 0), (3, 0)])
.unwrap();
assert!(!is_dag(&g));
}
#[test]
fn back_edge_to_root_is_not_dag() {
// 0 → 1 → 2 → 0 (3-cycle) — different framing of the
// three_cycle case, double-check the back edge is detected.
let mut g = Graph::new(3, true).unwrap();
g.add_edges(vec![(0u32, 1u32), (1, 2), (2, 0)]).unwrap();
assert!(!is_dag(&g));
}
#[test]
fn two_disjoint_dags_is_dag() {
// Two unrelated 2-vertex DAGs in the same graph.
let mut g = Graph::new(4, true).unwrap();
g.add_edges(vec![(0u32, 1u32), (2, 3)]).unwrap();
assert!(is_dag(&g));
}
}