rust_igraph/algorithms/constructors/
realize_directed_degree_sequence.rs

1//! Directed degree sequence realization (ALGO-CO-034).
2//!
3//! Counterpart of the directed branch of `igraph_realize_degree_sequence()`
4//! from `references/igraph/src/misc/degree_sequence.cpp`.
5//!
6//! Constructs a directed simple graph from given out-degree and in-degree
7//! sequences using the Kleitman-Wang algorithm.
8
9use crate::algorithms::constructors::realize_degree_sequence::RealizeDegseqMethod;
10use crate::core::error::IgraphError;
11use crate::core::{Graph, IgraphResult, VertexId};
12
13/// Realize a directed simple graph from out-degree and in-degree sequences.
14///
15/// Uses the Kleitman-Wang algorithm: repeatedly select a vertex, then
16/// connect its out-stubs to the vertices with the highest remaining
17/// in-degrees (lexicographically by (in, out) degree pairs).
18///
19/// # Arguments
20///
21/// * `outdeg` — the target out-degree for each vertex.
22/// * `indeg` — the target in-degree for each vertex. Must have the same
23///   length as `outdeg`.
24/// * `method` — vertex selection order (see [`RealizeDegseqMethod`]).
25///
26/// # Errors
27///
28/// Returns `InvalidArgument` if:
29/// - `outdeg` and `indeg` have different lengths.
30/// - The sums of out-degrees and in-degrees differ.
31/// - Any out-degree exceeds `n - 1` (no simple realization exists).
32/// - The sequence is not digraphical (Kleitman-Wang fails).
33///
34/// # Examples
35///
36/// ```
37/// use rust_igraph::{realize_directed_degree_sequence, RealizeDegseqMethod};
38///
39/// // Realize a directed cycle: each vertex has in=1, out=1
40/// let g = realize_directed_degree_sequence(
41///     &[1, 1, 1], &[1, 1, 1], RealizeDegseqMethod::Smallest,
42/// ).unwrap();
43/// assert_eq!(g.vcount(), 3);
44/// assert_eq!(g.ecount(), 3);
45/// assert!(g.is_directed());
46/// ```
47pub fn realize_directed_degree_sequence(
48    outdeg: &[u32],
49    indeg: &[u32],
50    method: RealizeDegseqMethod,
51) -> IgraphResult<Graph> {
52    let n = outdeg.len();
53
54    if indeg.len() != n {
55        return Err(IgraphError::InvalidArgument(
56            "in- and out-degree sequences must have the same length".to_string(),
57        ));
58    }
59
60    if n == 0 {
61        return Graph::new(0, true);
62    }
63
64    let n_u32 = u32::try_from(n)
65        .map_err(|_| IgraphError::InvalidArgument("vertex count exceeds u32::MAX".to_string()))?;
66
67    let out_sum: u64 = outdeg.iter().map(|&d| u64::from(d)).sum();
68    let in_sum: u64 = indeg.iter().map(|&d| u64::from(d)).sum();
69
70    if out_sum != in_sum {
71        return Err(IgraphError::InvalidArgument(format!(
72            "out-degree sum ({out_sum}) differs from in-degree sum ({in_sum})"
73        )));
74    }
75
76    for (i, &d) in outdeg.iter().enumerate() {
77        if d >= n_u32 {
78            return Err(IgraphError::InvalidArgument(format!(
79                "outdeg[{i}] = {d} >= n = {n_u32}, cannot realize as simple directed graph"
80            )));
81        }
82    }
83
84    let num_edges = usize::try_from(out_sum)
85        .map_err(|_| IgraphError::InvalidArgument("edge count overflows usize".to_string()))?;
86
87    if num_edges == 0 {
88        return Graph::new(n_u32, true);
89    }
90
91    let edges = match method {
92        RealizeDegseqMethod::Smallest => kleitman_wang(outdeg, indeg, n, true)?,
93        RealizeDegseqMethod::Largest => kleitman_wang(outdeg, indeg, n, false)?,
94        RealizeDegseqMethod::Index => kleitman_wang_index(outdeg, indeg, n)?,
95    };
96
97    let mut graph = Graph::new(n_u32, true)?;
98    graph.add_edges(edges)?;
99    Ok(graph)
100}
101
102/// (vertex, `in_degree`, `out_degree`) triple.
103#[derive(Clone, Copy)]
104struct Vbd {
105    vertex: u32,
106    ind: u32,
107    outd: u32,
108}
109
110impl Vbd {
111    fn bideg_key(&self) -> (u32, u32) {
112        (self.ind, self.outd)
113    }
114}
115
116fn kleitman_wang(
117    outdeg: &[u32],
118    indeg: &[u32],
119    n: usize,
120    smallest: bool,
121) -> IgraphResult<Vec<(VertexId, VertexId)>> {
122    let mut vertices: Vec<Vbd> = (0..n)
123        .map(|i| {
124            #[allow(clippy::cast_possible_truncation)]
125            let idx = i as u32;
126            Vbd {
127                vertex: idx,
128                ind: indeg[i],
129                outd: outdeg[i],
130            }
131        })
132        .collect();
133
134    let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
135
136    loop {
137        // Sort by (in, out) descending
138        vertices.sort_unstable_by_key(|v| std::cmp::Reverse(v.bideg_key()));
139
140        // Remove (0,0)-degree vertices from the tail
141        while let Some(last) = vertices.last() {
142            if last.ind == 0 && last.outd == 0 {
143                vertices.pop();
144            } else {
145                break;
146            }
147        }
148
149        if vertices.is_empty() {
150            break;
151        }
152
153        // Find a vertex with non-zero out-degree
154        let vdp_idx = if smallest {
155            vertices.iter().rposition(|v| v.outd > 0).ok_or_else(|| {
156                IgraphError::InvalidArgument("directed degree sequence not digraphical".to_string())
157            })?
158        } else {
159            vertices.iter().position(|v| v.outd > 0).ok_or_else(|| {
160                IgraphError::InvalidArgument("directed degree sequence not digraphical".to_string())
161            })?
162        };
163
164        let hub_vertex = vertices[vdp_idx].vertex;
165        let hub_outd = vertices[vdp_idx].outd;
166
167        // Check sufficient vertices to connect to (excluding self)
168        let available = vertices.iter().filter(|v| v.vertex != hub_vertex).count();
169        if (hub_outd as usize) > available {
170            return Err(IgraphError::InvalidArgument(
171                "directed degree sequence not digraphical (insufficient vertices)".to_string(),
172            ));
173        }
174
175        // Connect hub's out-stubs to vertices with highest in-degree
176        let mut k: u32 = 0;
177        for vbd in &mut vertices {
178            if k >= hub_outd {
179                break;
180            }
181            if vbd.vertex == hub_vertex {
182                continue;
183            }
184            if vbd.ind == 0 {
185                return Err(IgraphError::InvalidArgument(
186                    "directed degree sequence not digraphical".to_string(),
187                ));
188            }
189            vbd.ind -= 1;
190            edges.push((hub_vertex, vbd.vertex));
191            k += 1;
192        }
193
194        vertices[vdp_idx].outd = 0;
195    }
196
197    Ok(edges)
198}
199
200fn kleitman_wang_index(
201    outdeg: &[u32],
202    indeg: &[u32],
203    n: usize,
204) -> IgraphResult<Vec<(VertexId, VertexId)>> {
205    // Build vertices with their original indices for index-order traversal
206    let mut vertices: Vec<Vbd> = (0..n)
207        .map(|i| {
208            #[allow(clippy::cast_possible_truncation)]
209            let idx = i as u32;
210            Vbd {
211                vertex: idx,
212                ind: indeg[i],
213                outd: outdeg[i],
214            }
215        })
216        .collect();
217
218    let mut edges: Vec<(VertexId, VertexId)> = Vec::new();
219
220    #[allow(clippy::cast_possible_truncation)]
221    let n_u32 = n as u32;
222    for vi in 0..n_u32 {
223        // Sort by (in, out) descending
224        vertices.sort_unstable_by_key(|v| std::cmp::Reverse(v.bideg_key()));
225
226        // Find this vertex in the sorted list
227        let Some(vdp_idx) = vertices.iter().position(|v| v.vertex == vi) else {
228            continue;
229        };
230
231        let hub_outd = vertices[vdp_idx].outd;
232        if hub_outd == 0 {
233            continue;
234        }
235
236        let hub_vertex = vertices[vdp_idx].vertex;
237
238        // Connect hub's out-stubs to vertices with highest in-degree
239        let mut k: u32 = 0;
240        for vbd in &mut vertices {
241            if k >= hub_outd {
242                break;
243            }
244            if vbd.vertex == hub_vertex {
245                continue;
246            }
247            if vbd.ind == 0 {
248                return Err(IgraphError::InvalidArgument(
249                    "directed degree sequence not digraphical".to_string(),
250                ));
251            }
252            vbd.ind -= 1;
253            edges.push((hub_vertex, vbd.vertex));
254            k += 1;
255        }
256
257        if k < hub_outd {
258            return Err(IgraphError::InvalidArgument(
259                "directed degree sequence not digraphical".to_string(),
260            ));
261        }
262
263        vertices[vdp_idx].outd = 0;
264    }
265
266    Ok(edges)
267}
268
269#[cfg(test)]
270mod tests {
271    use super::*;
272
273    fn verify_directed_degrees(graph: &Graph, outdeg: &[u32], indeg: &[u32]) {
274        let n = graph.vcount();
275        assert_eq!(n as usize, outdeg.len());
276        assert_eq!(n as usize, indeg.len());
277        for v in 0..n {
278            let out_d = graph.incident(v).unwrap().len();
279            let in_d = graph.incident_in(v).unwrap().len();
280            assert_eq!(
281                out_d, outdeg[v as usize] as usize,
282                "vertex {v}: out-degree {out_d}, expected {}",
283                outdeg[v as usize]
284            );
285            assert_eq!(
286                in_d, indeg[v as usize] as usize,
287                "vertex {v}: in-degree {in_d}, expected {}",
288                indeg[v as usize]
289            );
290        }
291    }
292
293    #[test]
294    fn empty_sequence() {
295        let g = realize_directed_degree_sequence(&[], &[], RealizeDegseqMethod::Largest).unwrap();
296        assert_eq!(g.vcount(), 0);
297        assert_eq!(g.ecount(), 0);
298        assert!(g.is_directed());
299    }
300
301    #[test]
302    fn all_zeros() {
303        let g =
304            realize_directed_degree_sequence(&[0, 0, 0], &[0, 0, 0], RealizeDegseqMethod::Largest)
305                .unwrap();
306        assert_eq!(g.vcount(), 3);
307        assert_eq!(g.ecount(), 0);
308    }
309
310    #[test]
311    fn single_edge() {
312        let g = realize_directed_degree_sequence(&[1, 0], &[0, 1], RealizeDegseqMethod::Largest)
313            .unwrap();
314        assert_eq!(g.vcount(), 2);
315        assert_eq!(g.ecount(), 1);
316        verify_directed_degrees(&g, &[1, 0], &[0, 1]);
317    }
318
319    #[test]
320    fn directed_cycle() {
321        let g =
322            realize_directed_degree_sequence(&[1, 1, 1], &[1, 1, 1], RealizeDegseqMethod::Smallest)
323                .unwrap();
324        assert_eq!(g.vcount(), 3);
325        assert_eq!(g.ecount(), 3);
326        verify_directed_degrees(&g, &[1, 1, 1], &[1, 1, 1]);
327    }
328
329    #[test]
330    fn complete_directed_k3() {
331        // K3 directed: each vertex has out=2, in=2
332        let g =
333            realize_directed_degree_sequence(&[2, 2, 2], &[2, 2, 2], RealizeDegseqMethod::Largest)
334                .unwrap();
335        assert_eq!(g.vcount(), 3);
336        assert_eq!(g.ecount(), 6);
337        verify_directed_degrees(&g, &[2, 2, 2], &[2, 2, 2]);
338    }
339
340    #[test]
341    fn star_out() {
342        // Star: vertex 0 sends to all others
343        let g = realize_directed_degree_sequence(
344            &[3, 0, 0, 0],
345            &[0, 1, 1, 1],
346            RealizeDegseqMethod::Largest,
347        )
348        .unwrap();
349        assert_eq!(g.vcount(), 4);
350        assert_eq!(g.ecount(), 3);
351        verify_directed_degrees(&g, &[3, 0, 0, 0], &[0, 1, 1, 1]);
352    }
353
354    #[test]
355    fn mismatched_sums() {
356        let result =
357            realize_directed_degree_sequence(&[1, 1], &[1, 2], RealizeDegseqMethod::Largest);
358        assert!(result.is_err());
359    }
360
361    #[test]
362    fn different_lengths() {
363        let result = realize_directed_degree_sequence(&[1, 1], &[1], RealizeDegseqMethod::Largest);
364        assert!(result.is_err());
365    }
366
367    #[test]
368    fn non_digraphical() {
369        // out=[2,0,0], in=[0,0,2]: vertex 0 needs 2 targets but vertex 2
370        // can only receive 2, and vertex 0 can only send to 2 others.
371        // Actually this IS graphical: 0->2, 0->2 would be multi-edge.
372        // For simple: 0 can send to vertex 1 and 2, but vertex 1 has in=0.
373        let result =
374            realize_directed_degree_sequence(&[2, 0, 0], &[0, 0, 2], RealizeDegseqMethod::Largest);
375        assert!(result.is_err());
376    }
377
378    #[test]
379    fn method_index() {
380        let g =
381            realize_directed_degree_sequence(&[1, 1, 1], &[1, 1, 1], RealizeDegseqMethod::Index)
382                .unwrap();
383        assert_eq!(g.ecount(), 3);
384        verify_directed_degrees(&g, &[1, 1, 1], &[1, 1, 1]);
385    }
386
387    #[test]
388    fn method_smallest() {
389        let g =
390            realize_directed_degree_sequence(&[2, 1, 1], &[1, 1, 2], RealizeDegseqMethod::Smallest)
391                .unwrap();
392        assert_eq!(g.ecount(), 4);
393        verify_directed_degrees(&g, &[2, 1, 1], &[1, 1, 2]);
394    }
395
396    #[test]
397    fn larger_directed() {
398        let outdeg = [2, 2, 1, 1, 0];
399        let indeg = [1, 1, 1, 1, 2];
400        let g = realize_directed_degree_sequence(&outdeg, &indeg, RealizeDegseqMethod::Largest)
401            .unwrap();
402        assert_eq!(g.vcount(), 5);
403        assert_eq!(g.ecount(), 6);
404        verify_directed_degrees(&g, &outdeg, &indeg);
405    }
406
407    #[test]
408    fn degree_too_large() {
409        let result =
410            realize_directed_degree_sequence(&[3, 0, 0], &[0, 1, 2], RealizeDegseqMethod::Largest);
411        assert!(result.is_err());
412    }
413
414    #[test]
415    fn all_methods_produce_valid_graph() {
416        let outdeg = [2, 1, 1, 2];
417        let indeg = [1, 2, 2, 1];
418        for method in [
419            RealizeDegseqMethod::Largest,
420            RealizeDegseqMethod::Smallest,
421            RealizeDegseqMethod::Index,
422        ] {
423            let g = realize_directed_degree_sequence(&outdeg, &indeg, method).unwrap();
424            verify_directed_degrees(&g, &outdeg, &indeg);
425        }
426    }
427}
rust_igraph/algorithms/constructors/realize_directed_degree_sequence.rs

rust_igraph/algorithms/constructors/
realize_directed_degree_sequence.rs
