rust_igraph/algorithms/io/
dimacs.rs

1//! DIMACS flow-problem I/O (ALGO-IO-004).
2//!
3//! Reads and writes graphs in the DIMACS network flow format. This is a
4//! line-oriented ASCII format with the following line types:
5//!
6//! - `c ...` — comment (ignored)
7//! - `p max|edge N M` — problem line: type, vertex count, edge count
8//! - `n ID s|t` — (max problems) designate source/target vertex
9//! - `n ID LABEL` — (edge problems) assign integer label to vertex
10//! - `a FROM TO CAP` — (max problems) arc with capacity
11//! - `e FROM TO` — (edge problems) undirected edge
12//!
13//! Vertex IDs in the file are 1-based; internally they are 0-based.
14//!
15//! Counterpart of `igraph_read_graph_dimacs_flow` / `igraph_write_graph_dimacs_flow`.
16
17use std::io::{BufRead, BufReader, Read, Write};
18
19use crate::core::{Graph, IgraphError, IgraphResult};
20
21/// The type of DIMACS problem read from the file.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum DimacsProblem {
24    /// Maximum-flow problem (`p max N M`).
25    Max,
26    /// Edge-coloring/clique problem (`p edge N M`).
27    Edge,
28}
29
30/// Result of reading a DIMACS file.
31#[derive(Debug, Clone)]
32pub struct DimacsGraph {
33    /// The parsed graph.
34    pub graph: Graph,
35    /// Problem type.
36    pub problem: DimacsProblem,
37    /// Source vertex (0-based). Only meaningful for `Max` problems.
38    pub source: Option<u32>,
39    /// Target vertex (0-based). Only meaningful for `Max` problems.
40    pub target: Option<u32>,
41    /// Edge capacities (one per edge, in edge order). Only present for
42    /// `Max` problems.
43    pub capacity: Option<Vec<f64>>,
44    /// Vertex labels (indexed by vertex id). Only present for `Edge`
45    /// problems when at least one `n` line appears.
46    pub labels: Option<Vec<i64>>,
47}
48
49/// Read a graph from DIMACS flow/edge format.
50///
51/// # Examples
52///
53/// ```
54/// use rust_igraph::read_dimacs;
55///
56/// let dimacs = b"c example\np max 4 5\nn 1 s\nn 4 t\na 1 2 10\na 1 3 8\na 2 3 5\na 2 4 7\na 3 4 10\n";
57/// let result = read_dimacs(&dimacs[..], true).unwrap();
58/// assert_eq!(result.graph.vcount(), 4);
59/// assert_eq!(result.graph.ecount(), 5);
60/// assert_eq!(result.source, Some(0));
61/// assert_eq!(result.target, Some(3));
62/// ```
63#[allow(clippy::too_many_lines)]
64pub fn read_dimacs<R: Read>(input: R, directed: bool) -> IgraphResult<DimacsGraph> {
65    let reader = BufReader::new(input);
66
67    let mut problem_type: Option<DimacsProblem> = None;
68    let mut n_vertices: Option<u32> = None;
69    let mut source: Option<u32> = None;
70    let mut target: Option<u32> = None;
71    let mut edges: Vec<(u32, u32)> = Vec::new();
72    let mut capacities: Vec<f64> = Vec::new();
73    let mut labels: Option<Vec<i64>> = None;
74
75    for (line_idx, line_result) in reader.lines().enumerate() {
76        let line = line_result?;
77        let trimmed = line.trim();
78
79        if trimmed.is_empty() {
80            continue;
81        }
82
83        let first_char = trimmed.as_bytes()[0];
84
85        match first_char {
86            b'c' => {
87                // Comment line — skip
88            }
89            b'p' => {
90                if problem_type.is_some() {
91                    return Err(IgraphError::Parse {
92                        line: line_idx.wrapping_add(1),
93                        message: "duplicate problem line".into(),
94                    });
95                }
96                let parts: Vec<&str> = trimmed.split_whitespace().collect();
97                if parts.len() < 4 {
98                    return Err(IgraphError::Parse {
99                        line: line_idx.wrapping_add(1),
100                        message: "problem line needs: p type nodes edges".into(),
101                    });
102                }
103                let parts = parts.as_slice();
104                let ptype = match parts[1] {
105                    "max" => DimacsProblem::Max,
106                    "edge" | "col" => DimacsProblem::Edge,
107                    other => {
108                        return Err(IgraphError::Parse {
109                            line: line_idx.wrapping_add(1),
110                            message: format!(
111                                "unknown problem type '{other}', expected 'max' or 'edge'"
112                            ),
113                        });
114                    }
115                };
116                let n: u32 = parts[2].parse().map_err(|e| IgraphError::Parse {
117                    line: line_idx.wrapping_add(1),
118                    message: format!("invalid vertex count: {e}"),
119                })?;
120                let _m: u32 = parts[3].parse().map_err(|e| IgraphError::Parse {
121                    line: line_idx.wrapping_add(1),
122                    message: format!("invalid edge count: {e}"),
123                })?;
124
125                problem_type = Some(ptype);
126                n_vertices = Some(n);
127
128                if ptype == DimacsProblem::Edge {
129                    // Initialize labels: default = vertex_id + 1 (1-based)
130                    let mut lbl = Vec::with_capacity(n as usize);
131                    for i in 0..n {
132                        lbl.push(i64::from(i) + 1);
133                    }
134                    labels = Some(lbl);
135                }
136            }
137            b'n' => {
138                let ptype = problem_type.ok_or_else(|| IgraphError::Parse {
139                    line: line_idx.wrapping_add(1),
140                    message: "'n' line before problem line".into(),
141                })?;
142                let parts: Vec<&str> = trimmed.split_whitespace().collect();
143                if parts.len() < 3 {
144                    return Err(IgraphError::Parse {
145                        line: line_idx.wrapping_add(1),
146                        message: "node line needs: n ID type_or_label".into(),
147                    });
148                }
149                let parts = parts.as_slice();
150                let vid: u32 = parts[1].parse().map_err(|e| IgraphError::Parse {
151                    line: line_idx.wrapping_add(1),
152                    message: format!("invalid vertex id: {e}"),
153                })?;
154                if vid == 0 {
155                    return Err(IgraphError::Parse {
156                        line: line_idx.wrapping_add(1),
157                        message: "vertex IDs are 1-based in DIMACS".into(),
158                    });
159                }
160                let vid0 = vid.wrapping_sub(1); // 0-based
161
162                match ptype {
163                    DimacsProblem::Max => match parts[2] {
164                        "s" => {
165                            source = Some(vid0);
166                        }
167                        "t" => {
168                            target = Some(vid0);
169                        }
170                        other => {
171                            return Err(IgraphError::Parse {
172                                line: line_idx.wrapping_add(1),
173                                message: format!(
174                                    "invalid node type '{other}', expected 's' or 't'"
175                                ),
176                            });
177                        }
178                    },
179                    DimacsProblem::Edge => {
180                        let lbl: i64 = parts[2].parse().map_err(|e| IgraphError::Parse {
181                            line: line_idx.wrapping_add(1),
182                            message: format!("invalid label: {e}"),
183                        })?;
184                        if let Some(ref mut lab_vec) = labels {
185                            if (vid0 as usize) < lab_vec.len() {
186                                lab_vec[vid0 as usize] = lbl;
187                            }
188                        }
189                    }
190                }
191            }
192            b'a' => {
193                if problem_type != Some(DimacsProblem::Max) {
194                    return Err(IgraphError::Parse {
195                        line: line_idx.wrapping_add(1),
196                        message: "'a' lines only allowed in max problems".into(),
197                    });
198                }
199                let parts: Vec<&str> = trimmed.split_whitespace().collect();
200                if parts.len() < 4 {
201                    return Err(IgraphError::Parse {
202                        line: line_idx.wrapping_add(1),
203                        message: "arc line needs: a FROM TO CAPACITY".into(),
204                    });
205                }
206                let from: u32 = parts[1].parse().map_err(|e| IgraphError::Parse {
207                    line: line_idx.wrapping_add(1),
208                    message: format!("invalid source id: {e}"),
209                })?;
210                let to: u32 = parts[2].parse().map_err(|e| IgraphError::Parse {
211                    line: line_idx.wrapping_add(1),
212                    message: format!("invalid target id: {e}"),
213                })?;
214                let cap: f64 = parts[3].parse().map_err(|e| IgraphError::Parse {
215                    line: line_idx.wrapping_add(1),
216                    message: format!("invalid capacity: {e}"),
217                })?;
218
219                if from == 0 || to == 0 {
220                    return Err(IgraphError::Parse {
221                        line: line_idx.wrapping_add(1),
222                        message: "vertex IDs are 1-based in DIMACS".into(),
223                    });
224                }
225                edges.push((from.wrapping_sub(1), to.wrapping_sub(1)));
226                capacities.push(cap);
227            }
228            b'e' => {
229                if problem_type != Some(DimacsProblem::Edge) {
230                    return Err(IgraphError::Parse {
231                        line: line_idx.wrapping_add(1),
232                        message: "'e' lines only allowed in edge problems".into(),
233                    });
234                }
235                let parts: Vec<&str> = trimmed.split_whitespace().collect();
236                if parts.len() < 3 {
237                    return Err(IgraphError::Parse {
238                        line: line_idx.wrapping_add(1),
239                        message: "edge line needs: e FROM TO".into(),
240                    });
241                }
242                let from: u32 = parts[1].parse().map_err(|e| IgraphError::Parse {
243                    line: line_idx.wrapping_add(1),
244                    message: format!("invalid source id: {e}"),
245                })?;
246                let to: u32 = parts[2].parse().map_err(|e| IgraphError::Parse {
247                    line: line_idx.wrapping_add(1),
248                    message: format!("invalid target id: {e}"),
249                })?;
250
251                if from == 0 || to == 0 {
252                    return Err(IgraphError::Parse {
253                        line: line_idx.wrapping_add(1),
254                        message: "vertex IDs are 1-based in DIMACS".into(),
255                    });
256                }
257                edges.push((from.wrapping_sub(1), to.wrapping_sub(1)));
258            }
259            _ => {
260                return Err(IgraphError::Parse {
261                    line: line_idx.wrapping_add(1),
262                    message: format!(
263                        "unknown line type '{}'",
264                        trimmed.chars().next().unwrap_or('?')
265                    ),
266                });
267            }
268        }
269    }
270
271    let n = n_vertices.ok_or_else(|| IgraphError::Parse {
272        line: 0,
273        message: "no problem line found in DIMACS file".into(),
274    })?;
275
276    let ptype = problem_type.unwrap_or(DimacsProblem::Edge);
277
278    let mut graph = Graph::new(n, directed)?;
279    graph.add_edges(edges)?;
280
281    Ok(DimacsGraph {
282        graph,
283        problem: ptype,
284        source,
285        target,
286        capacity: if ptype == DimacsProblem::Max {
287            Some(capacities)
288        } else {
289            None
290        },
291        labels: if ptype == DimacsProblem::Edge {
292            labels
293        } else {
294            None
295        },
296    })
297}
298
299/// Write a graph in DIMACS max-flow format.
300///
301/// Writes the problem line, source/target node lines, and arc lines
302/// with capacity values.
303///
304/// # Examples
305///
306/// ```
307/// use rust_igraph::{Graph, write_dimacs_flow};
308///
309/// let mut g = Graph::new(4, true).unwrap();
310/// g.add_edge(0, 1).unwrap();
311/// g.add_edge(1, 2).unwrap();
312/// g.add_edge(2, 3).unwrap();
313///
314/// let capacity = vec![10.0, 5.0, 8.0];
315/// let mut buf = Vec::new();
316/// write_dimacs_flow(&g, 0, 3, &capacity, &mut buf).unwrap();
317/// let s = String::from_utf8(buf).unwrap();
318/// assert!(s.contains("p max 4 3"));
319/// assert!(s.contains("n 1 s"));
320/// assert!(s.contains("n 4 t"));
321/// ```
322pub fn write_dimacs_flow<W: Write>(
323    graph: &Graph,
324    source: u32,
325    target: u32,
326    capacity: &[f64],
327    writer: &mut W,
328) -> IgraphResult<()> {
329    if capacity.len() != graph.ecount() {
330        return Err(IgraphError::InvalidArgument(format!(
331            "capacity length {} does not match ecount {}",
332            capacity.len(),
333            graph.ecount()
334        )));
335    }
336    if source >= graph.vcount() {
337        return Err(IgraphError::InvalidArgument(format!(
338            "source {} out of range (vcount = {})",
339            source,
340            graph.vcount()
341        )));
342    }
343    if target >= graph.vcount() {
344        return Err(IgraphError::InvalidArgument(format!(
345            "target {} out of range (vcount = {})",
346            target,
347            graph.vcount()
348        )));
349    }
350
351    writeln!(writer, "c created by rust-igraph")?;
352    writeln!(writer, "p max {} {}", graph.vcount(), graph.ecount())?;
353    writeln!(writer, "n {} s", source + 1)?;
354    writeln!(writer, "n {} t", target + 1)?;
355
356    for (eid, &cap) in capacity.iter().enumerate() {
357        #[allow(clippy::cast_possible_truncation)]
358        let (from, to) = graph.edge(eid as u32)?;
359        writeln!(writer, "a {} {} {cap}", from + 1, to + 1)?;
360    }
361
362    Ok(())
363}
364
365#[cfg(test)]
366mod tests {
367    use super::*;
368
369    #[test]
370    fn test_empty_file_error() {
371        let result = read_dimacs(&b""[..], true);
372        assert!(result.is_err());
373    }
374
375    #[test]
376    fn test_max_problem_basic() {
377        let input = b"c comment\np max 4 3\nn 1 s\nn 4 t\na 1 2 10\na 2 3 5\na 3 4 8\n";
378        let result = read_dimacs(&input[..], true).unwrap();
379        assert_eq!(result.graph.vcount(), 4);
380        assert_eq!(result.graph.ecount(), 3);
381        assert_eq!(result.problem, DimacsProblem::Max);
382        assert_eq!(result.source, Some(0));
383        assert_eq!(result.target, Some(3));
384        let cap = result.capacity.unwrap();
385        assert!((cap[0] - 10.0).abs() < 1e-10);
386        assert!((cap[1] - 5.0).abs() < 1e-10);
387        assert!((cap[2] - 8.0).abs() < 1e-10);
388    }
389
390    #[test]
391    fn test_edge_problem_basic() {
392        let input = b"p edge 5 4\ne 1 2\ne 2 3\ne 3 4\ne 4 5\n";
393        let result = read_dimacs(&input[..], false).unwrap();
394        assert_eq!(result.graph.vcount(), 5);
395        assert_eq!(result.graph.ecount(), 4);
396        assert_eq!(result.problem, DimacsProblem::Edge);
397        assert!(result.capacity.is_none());
398        assert!(!result.graph.is_directed());
399    }
400
401    #[test]
402    fn test_edge_problem_with_labels() {
403        let input = b"p edge 3 2\nn 1 100\nn 3 300\ne 1 2\ne 2 3\n";
404        let result = read_dimacs(&input[..], false).unwrap();
405        let lab = result.labels.unwrap();
406        assert_eq!(lab[0], 100);
407        assert_eq!(lab[1], 2); // default = 1-based id
408        assert_eq!(lab[2], 300);
409    }
410
411    #[test]
412    fn test_comments_ignored() {
413        let input = b"c first comment\nc second comment\np max 2 1\nn 1 s\nn 2 t\na 1 2 5\n";
414        let result = read_dimacs(&input[..], true).unwrap();
415        assert_eq!(result.graph.vcount(), 2);
416        assert_eq!(result.graph.ecount(), 1);
417    }
418
419    #[test]
420    fn test_directed_graph() {
421        let input = b"p max 3 2\nn 1 s\nn 3 t\na 1 2 10\na 2 3 20\n";
422        let result = read_dimacs(&input[..], true).unwrap();
423        assert!(result.graph.is_directed());
424    }
425
426    #[test]
427    fn test_zero_capacity() {
428        let input = b"p max 2 1\nn 1 s\nn 2 t\na 1 2 0\n";
429        let result = read_dimacs(&input[..], true).unwrap();
430        let cap = result.capacity.unwrap();
431        assert!((cap[0] - 0.0).abs() < 1e-10);
432    }
433
434    #[test]
435    fn test_float_capacity() {
436        let input = b"p max 2 1\nn 1 s\nn 2 t\na 1 2 7.25\n";
437        let result = read_dimacs(&input[..], true).unwrap();
438        let cap = result.capacity.unwrap();
439        assert!((cap[0] - 7.25).abs() < 1e-10);
440    }
441
442    #[test]
443    fn test_duplicate_problem_line_error() {
444        let input = b"p max 2 1\np max 3 2\n";
445        let result = read_dimacs(&input[..], true);
446        assert!(result.is_err());
447    }
448
449    #[test]
450    fn test_unknown_problem_type_error() {
451        let input = b"p foo 2 1\n";
452        let result = read_dimacs(&input[..], true);
453        assert!(result.is_err());
454    }
455
456    #[test]
457    fn test_arc_in_edge_problem_error() {
458        let input = b"p edge 2 1\na 1 2 5\n";
459        let result = read_dimacs(&input[..], false);
460        assert!(result.is_err());
461    }
462
463    #[test]
464    fn test_edge_in_max_problem_error() {
465        let input = b"p max 2 1\ne 1 2\n";
466        let result = read_dimacs(&input[..], true);
467        assert!(result.is_err());
468    }
469
470    #[test]
471    fn test_zero_vertex_id_error() {
472        let input = b"p max 2 1\na 0 1 5\n";
473        let result = read_dimacs(&input[..], true);
474        assert!(result.is_err());
475    }
476
477    #[test]
478    fn test_col_alias_for_edge() {
479        let input = b"p col 3 2\ne 1 2\ne 2 3\n";
480        let result = read_dimacs(&input[..], false).unwrap();
481        assert_eq!(result.problem, DimacsProblem::Edge);
482        assert_eq!(result.graph.ecount(), 2);
483    }
484
485    #[test]
486    fn test_write_max_flow() {
487        let mut g = Graph::new(3, true).unwrap();
488        g.add_edge(0, 1).unwrap();
489        g.add_edge(1, 2).unwrap();
490
491        let capacity = vec![10.0, 20.0];
492        let mut buf = Vec::new();
493        write_dimacs_flow(&g, 0, 2, &capacity, &mut buf).unwrap();
494        let s = String::from_utf8(buf).unwrap();
495        assert!(s.contains("p max 3 2"));
496        assert!(s.contains("n 1 s"));
497        assert!(s.contains("n 3 t"));
498        assert!(s.contains("a 1 2 10"));
499        assert!(s.contains("a 2 3 20"));
500    }
501
502    #[test]
503    fn test_write_capacity_mismatch_error() {
504        let mut g = Graph::new(2, true).unwrap();
505        g.add_edge(0, 1).unwrap();
506        let capacity = vec![1.0, 2.0]; // 2 capacities but 1 edge
507        let mut buf = Vec::new();
508        assert!(write_dimacs_flow(&g, 0, 1, &capacity, &mut buf).is_err());
509    }
510
511    #[test]
512    fn test_write_source_out_of_range_error() {
513        let g = Graph::new(2, true).unwrap();
514        let mut buf = Vec::new();
515        assert!(write_dimacs_flow(&g, 5, 1, &[], &mut buf).is_err());
516    }
517
518    #[test]
519    fn test_round_trip() {
520        let input = b"p max 4 4\nn 1 s\nn 4 t\na 1 2 10\na 1 3 8\na 2 4 7\na 3 4 9\n";
521        let result = read_dimacs(&input[..], true).unwrap();
522
523        let mut buf = Vec::new();
524        write_dimacs_flow(
525            &result.graph,
526            result.source.unwrap(),
527            result.target.unwrap(),
528            result.capacity.as_deref().unwrap(),
529            &mut buf,
530        )
531        .unwrap();
532
533        let result2 = read_dimacs(&buf[..], true).unwrap();
534        assert_eq!(result2.graph.vcount(), result.graph.vcount());
535        assert_eq!(result2.graph.ecount(), result.graph.ecount());
536        assert_eq!(result2.source, result.source);
537        assert_eq!(result2.target, result.target);
538    }
539
540    #[test]
541    fn test_blank_lines_skipped() {
542        let input = b"\n\np max 2 1\n\nn 1 s\nn 2 t\n\na 1 2 5\n\n";
543        let result = read_dimacs(&input[..], true).unwrap();
544        assert_eq!(result.graph.ecount(), 1);
545    }
546}
rust_igraph/algorithms/io/dimacs.rs

rust_igraph/algorithms/io/
dimacs.rs
