rust_igraph/algorithms/io/
lgl.rs

1//! LGL (Large Graph Layout) adjacency-list I/O (ALGO-IO-003).
2//!
3//! Reads and writes graphs in the `.lgl` format used by the Large Graph
4//! Layout program. The format encodes an adjacency list where each hub
5//! vertex is introduced by a `# vertexname` header, followed by lines
6//! listing its neighbours (one per line), optionally with a weight.
7//!
8//! ```text
9//! # vertex1
10//! vertex2 weight
11//! vertex3
12//! # vertex2
13//! vertex4 weight
14//! ```
15//!
16//! The resulting graph is always **undirected**. Vertex names are mapped to
17//! internal indices in first-occurrence order.
18//!
19//! Counterpart of `igraph_read_graph_lgl` / `igraph_write_graph_lgl`.
20
21use std::collections::HashMap;
22use std::io::{BufRead, BufReader, Read, Write};
23
24use crate::core::attributes::AttributeValue;
25use crate::core::{Graph, IgraphError, IgraphResult};
26
27/// Result of reading an LGL file: the graph plus optional metadata.
28#[derive(Debug, Clone)]
29pub struct LglGraph {
30    /// The parsed graph (always undirected).
31    pub graph: Graph,
32    /// Vertex names in index order.
33    pub names: Vec<String>,
34    /// Edge weights (one per edge, in edge order). `None` if no edge had
35    /// a weight specified. Missing weights default to 0.0.
36    pub weights: Option<Vec<f64>>,
37}
38
39/// Read a graph from LGL (`.lgl`) format.
40///
41/// Lines starting with `# ` introduce a hub vertex. Subsequent lines
42/// (until the next hub or EOF) list neighbours, optionally followed by
43/// a weight. Empty lines are skipped.
44///
45/// # Examples
46///
47/// ```
48/// use rust_igraph::read_lgl;
49///
50/// let lgl = b"# Alice\nBob 1.0\nCarol\n# Bob\nCarol 2.5\n";
51/// let result = read_lgl(&lgl[..]).unwrap();
52/// assert_eq!(result.graph.vcount(), 3);
53/// assert_eq!(result.graph.ecount(), 3);
54/// assert_eq!(result.names, vec!["Alice", "Bob", "Carol"]);
55/// ```
56pub fn read_lgl<R: Read>(input: R) -> IgraphResult<LglGraph> {
57    let reader = BufReader::new(input);
58    let mut name_map: HashMap<String, u32> = HashMap::new();
59    let mut names: Vec<String> = Vec::new();
60    let mut edges: Vec<(u32, u32)> = Vec::new();
61    let mut weights: Vec<f64> = Vec::new();
62    let mut has_any_weight = false;
63
64    let mut current_hub: Option<u32> = None;
65
66    for (line_idx, line_result) in reader.lines().enumerate() {
67        let line = line_result?;
68        let trimmed = line.trim();
69
70        if trimmed.is_empty() {
71            continue;
72        }
73
74        if let Some(hub_name) = trimmed.strip_prefix('#') {
75            let hub_name = hub_name.trim();
76            if hub_name.is_empty() {
77                return Err(IgraphError::Parse {
78                    line: line_idx.wrapping_add(1),
79                    message: "hub line '#' has no vertex name".into(),
80                });
81            }
82            let hub_id = get_or_insert_name(hub_name, &mut name_map, &mut names);
83            current_hub = Some(hub_id);
84        } else {
85            let hub_id = current_hub.ok_or_else(|| IgraphError::Parse {
86                line: line_idx.wrapping_add(1),
87                message: "neighbour line before any hub definition".into(),
88            })?;
89
90            let mut parts = trimmed.split_whitespace();
91            let neighbour_name = parts.next().ok_or_else(|| IgraphError::Parse {
92                line: line_idx.wrapping_add(1),
93                message: "empty neighbour line".into(),
94            })?;
95
96            let neighbour_id = get_or_insert_name(neighbour_name, &mut name_map, &mut names);
97            edges.push((hub_id, neighbour_id));
98
99            let weight = if let Some(w_str) = parts.next() {
100                let w = w_str.parse::<f64>().map_err(|e| IgraphError::Parse {
101                    line: line_idx.wrapping_add(1),
102                    message: format!("invalid weight '{w_str}': {e}"),
103                })?;
104                has_any_weight = true;
105                w
106            } else {
107                0.0
108            };
109            weights.push(weight);
110        }
111    }
112
113    #[allow(clippy::cast_possible_truncation)]
114    let n = names.len() as u32;
115    let mut graph = Graph::with_vertices(n);
116    graph.add_edges(edges)?;
117
118    let has_any_label = names.iter().any(|l| !l.is_empty());
119    if has_any_label {
120        graph.set_vertex_attribute_all(
121            "name",
122            names
123                .iter()
124                .map(|l| AttributeValue::String(l.clone()))
125                .collect(),
126        )?;
127    }
128    if has_any_weight {
129        graph.set_edge_attribute_all(
130            "weight",
131            weights
132                .iter()
133                .map(|&w| AttributeValue::Numeric(w))
134                .collect(),
135        )?;
136    }
137
138    Ok(LglGraph {
139        graph,
140        names,
141        weights: if has_any_weight { Some(weights) } else { None },
142    })
143}
144
145/// Write a graph in LGL format.
146///
147/// Each vertex is written as a hub (`# name`) followed by its neighbours.
148/// If `names` is provided, uses them as vertex labels; otherwise uses
149/// numeric ids. If `weights` is provided (one per edge), appends the weight.
150///
151/// To avoid duplicate edges in the undirected representation, each edge is
152/// emitted only once: under the endpoint with the smaller index.
153///
154/// # Examples
155///
156/// ```
157/// use rust_igraph::{Graph, write_lgl};
158///
159/// let mut g = Graph::with_vertices(3);
160/// g.add_edge(0, 1).unwrap();
161/// g.add_edge(0, 2).unwrap();
162///
163/// let names = vec!["A".to_string(), "B".to_string(), "C".to_string()];
164/// let mut buf = Vec::new();
165/// write_lgl(&g, Some(&names), None, &mut buf).unwrap();
166/// let s = String::from_utf8(buf).unwrap();
167/// assert!(s.contains("# A"));
168/// assert!(s.contains("B"));
169/// assert!(s.contains("C"));
170/// ```
171pub fn write_lgl<W: Write>(
172    graph: &Graph,
173    names: Option<&[String]>,
174    weights: Option<&[f64]>,
175    writer: &mut W,
176) -> IgraphResult<()> {
177    if let Some(n) = names {
178        if n.len() != graph.vcount() as usize {
179            return Err(IgraphError::InvalidArgument(format!(
180                "names length {} does not match vcount {}",
181                n.len(),
182                graph.vcount()
183            )));
184        }
185    }
186    if let Some(w) = weights {
187        if w.len() != graph.ecount() {
188            return Err(IgraphError::InvalidArgument(format!(
189                "weights length {} does not match ecount {}",
190                w.len(),
191                graph.ecount()
192            )));
193        }
194    }
195
196    // Build adjacency lists: for each vertex, collect (neighbour, edge_id).
197    // Only emit each edge once — under the endpoint with the smaller index.
198    let vcount = graph.vcount() as usize;
199    let mut adj: Vec<Vec<(u32, usize)>> = vec![Vec::new(); vcount];
200
201    for eid in 0..graph.ecount() {
202        #[allow(clippy::cast_possible_truncation)]
203        let (src, tgt) = graph.edge(eid as u32)?;
204        // For self-loops, emit under the vertex itself
205        let hub = src.min(tgt);
206        let neighbour = src.max(tgt);
207        adj[hub as usize].push((neighbour, eid));
208    }
209
210    for v in 0..vcount {
211        if adj[v].is_empty() {
212            continue;
213        }
214
215        #[allow(clippy::cast_possible_truncation)]
216        let v_u32 = v as u32;
217        let hub_name = match names {
218            Some(n) => n[v].as_str().to_owned(),
219            None => graph
220                .vertex_attribute("name", v_u32)
221                .and_then(AttributeValue::as_str)
222                .map_or_else(|| v.to_string(), str::to_owned),
223        };
224        writeln!(writer, "# {hub_name}")?;
225
226        for &(neighbour, eid) in &adj[v] {
227            let nbr_name = match names {
228                Some(n) => n[neighbour as usize].as_str().to_owned(),
229                None => graph
230                    .vertex_attribute("name", neighbour)
231                    .and_then(AttributeValue::as_str)
232                    .map_or_else(|| neighbour.to_string(), str::to_owned),
233            };
234            #[allow(clippy::cast_possible_truncation)]
235            let eid_u32 = eid as u32;
236            match weights {
237                Some(w) => writeln!(writer, "{nbr_name} {}", w[eid])?,
238                None => {
239                    if let Some(w) = graph
240                        .edge_attribute("weight", eid_u32)
241                        .and_then(AttributeValue::as_f64)
242                    {
243                        writeln!(writer, "{nbr_name} {w}")?;
244                    } else {
245                        writeln!(writer, "{nbr_name}")?;
246                    }
247                }
248            }
249        }
250    }
251
252    Ok(())
253}
254
255fn get_or_insert_name(name: &str, map: &mut HashMap<String, u32>, names: &mut Vec<String>) -> u32 {
256    if let Some(&id) = map.get(name) {
257        id
258    } else {
259        #[allow(clippy::cast_possible_truncation)]
260        let id = names.len() as u32;
261        map.insert(name.to_owned(), id);
262        names.push(name.to_owned());
263        id
264    }
265}
266
267#[cfg(test)]
268mod tests {
269    use super::*;
270
271    #[test]
272    fn test_empty() {
273        let result = read_lgl(&b""[..]).unwrap();
274        assert_eq!(result.graph.vcount(), 0);
275        assert_eq!(result.graph.ecount(), 0);
276        assert!(result.names.is_empty());
277        assert!(result.weights.is_none());
278    }
279
280    #[test]
281    fn test_single_hub_no_neighbours() {
282        let input = b"# Alice\n";
283        let result = read_lgl(&input[..]).unwrap();
284        assert_eq!(result.graph.vcount(), 1);
285        assert_eq!(result.graph.ecount(), 0);
286        assert_eq!(result.names, vec!["Alice"]);
287    }
288
289    #[test]
290    fn test_basic_unweighted() {
291        let input = b"# a\nb\nc\n# b\nc\n";
292        let result = read_lgl(&input[..]).unwrap();
293        assert_eq!(result.graph.vcount(), 3);
294        assert_eq!(result.graph.ecount(), 3);
295        assert_eq!(result.names, vec!["a", "b", "c"]);
296        assert!(result.weights.is_none());
297    }
298
299    #[test]
300    fn test_weighted() {
301        let input = b"# x\ny 1.5\nz 2.0\n";
302        let result = read_lgl(&input[..]).unwrap();
303        assert_eq!(result.graph.ecount(), 2);
304        let w = result.weights.unwrap();
305        assert!((w[0] - 1.5).abs() < 1e-10);
306        assert!((w[1] - 2.0).abs() < 1e-10);
307    }
308
309    #[test]
310    fn test_mixed_weights() {
311        let input = b"# a\nb 3.0\nc\n";
312        let result = read_lgl(&input[..]).unwrap();
313        let w = result.weights.unwrap();
314        assert!((w[0] - 3.0).abs() < 1e-10);
315        assert!((w[1] - 0.0).abs() < 1e-10);
316    }
317
318    #[test]
319    fn test_blank_lines_skipped() {
320        let input = b"\n# a\n\nb\n\n";
321        let result = read_lgl(&input[..]).unwrap();
322        assert_eq!(result.graph.vcount(), 2);
323        assert_eq!(result.graph.ecount(), 1);
324    }
325
326    #[test]
327    fn test_multiple_hubs() {
328        let input = b"# Alice\nBob\nCarol\n# Bob\nCarol\n";
329        let result = read_lgl(&input[..]).unwrap();
330        assert_eq!(result.graph.vcount(), 3);
331        assert_eq!(result.graph.ecount(), 3);
332    }
333
334    #[test]
335    fn test_self_loop() {
336        let input = b"# a\na\n";
337        let result = read_lgl(&input[..]).unwrap();
338        assert_eq!(result.graph.vcount(), 1);
339        assert_eq!(result.graph.ecount(), 1);
340    }
341
342    #[test]
343    fn test_always_undirected() {
344        let input = b"# x\ny\n# y\nx\n";
345        let result = read_lgl(&input[..]).unwrap();
346        assert!(!result.graph.is_directed());
347    }
348
349    #[test]
350    fn test_negative_weight() {
351        let input = b"# a\nb -1.5\n";
352        let result = read_lgl(&input[..]).unwrap();
353        let w = result.weights.unwrap();
354        assert!((w[0] - (-1.5)).abs() < 1e-10);
355    }
356
357    #[test]
358    fn test_scientific_notation_weight() {
359        let input = b"# a\nb 2.5e-3\n";
360        let result = read_lgl(&input[..]).unwrap();
361        let w = result.weights.unwrap();
362        assert!((w[0] - 0.0025).abs() < 1e-10);
363    }
364
365    #[test]
366    fn test_invalid_weight_error() {
367        let input = b"# a\nb notanumber\n";
368        let result = read_lgl(&input[..]);
369        assert!(result.is_err());
370    }
371
372    #[test]
373    fn test_no_hub_before_neighbour_error() {
374        let input = b"b\n";
375        let result = read_lgl(&input[..]);
376        assert!(result.is_err());
377    }
378
379    #[test]
380    fn test_empty_hub_name_error() {
381        let input = b"#\n";
382        let result = read_lgl(&input[..]);
383        assert!(result.is_err());
384    }
385
386    #[test]
387    fn test_write_unweighted() {
388        let mut g = Graph::with_vertices(3);
389        g.add_edge(0, 1).unwrap();
390        g.add_edge(0, 2).unwrap();
391
392        let names = vec!["A".to_string(), "B".to_string(), "C".to_string()];
393        let mut buf = Vec::new();
394        write_lgl(&g, Some(&names), None, &mut buf).unwrap();
395        let s = String::from_utf8(buf).unwrap();
396        assert!(s.contains("# A\n"));
397        assert!(s.contains("B\n"));
398        assert!(s.contains("C\n"));
399    }
400
401    #[test]
402    fn test_write_weighted() {
403        let mut g = Graph::with_vertices(2);
404        g.add_edge(0, 1).unwrap();
405
406        let names = vec!["x".to_string(), "y".to_string()];
407        let weights = vec![2.75];
408        let mut buf = Vec::new();
409        write_lgl(&g, Some(&names), Some(&weights), &mut buf).unwrap();
410        let s = String::from_utf8(buf).unwrap();
411        assert!(s.contains("# x\n"));
412        assert!(s.contains("y 2.75"));
413    }
414
415    #[test]
416    fn test_write_numeric_names() {
417        let mut g = Graph::with_vertices(2);
418        g.add_edge(0, 1).unwrap();
419
420        let mut buf = Vec::new();
421        write_lgl(&g, None, None, &mut buf).unwrap();
422        let s = String::from_utf8(buf).unwrap();
423        assert!(s.contains("# 0\n"));
424        assert!(s.contains("1\n"));
425    }
426
427    #[test]
428    fn test_round_trip() {
429        let input = b"# Alice\nBob 1.0\nCarol 2.0\n# Bob\nCarol 3.0\n";
430        let result = read_lgl(&input[..]).unwrap();
431
432        let mut buf = Vec::new();
433        write_lgl(
434            &result.graph,
435            Some(&result.names),
436            result.weights.as_deref(),
437            &mut buf,
438        )
439        .unwrap();
440
441        let result2 = read_lgl(&buf[..]).unwrap();
442        assert_eq!(result2.graph.vcount(), result.graph.vcount());
443        assert_eq!(result2.graph.ecount(), result.graph.ecount());
444    }
445
446    #[test]
447    fn test_write_names_length_mismatch() {
448        let g = Graph::with_vertices(3);
449        let names = vec!["A".to_string()];
450        let mut buf = Vec::new();
451        assert!(write_lgl(&g, Some(&names), None, &mut buf).is_err());
452    }
453
454    #[test]
455    fn test_write_weights_length_mismatch() {
456        let mut g = Graph::with_vertices(2);
457        g.add_edge(0, 1).unwrap();
458        let weights = vec![1.0, 2.0];
459        let mut buf = Vec::new();
460        assert!(write_lgl(&g, None, Some(&weights), &mut buf).is_err());
461    }
462
463    #[test]
464    fn test_isolated_vertex_not_in_output() {
465        // Isolated vertices with no edges don't appear in LGL output
466        let mut g = Graph::with_vertices(3);
467        g.add_edge(0, 1).unwrap();
468        // vertex 2 is isolated
469
470        let names = vec!["A".to_string(), "B".to_string(), "C".to_string()];
471        let mut buf = Vec::new();
472        write_lgl(&g, Some(&names), None, &mut buf).unwrap();
473        let s = String::from_utf8(buf).unwrap();
474        assert!(s.contains("# A\n"));
475        assert!(s.contains("B\n"));
476        assert!(!s.contains('C'));
477    }
478
479    // --- Attribute integration tests ---
480
481    #[test]
482    fn test_read_stores_name_attribute() {
483        let input = b"# Alice\nBob\nCarol\n";
484        let result = read_lgl(&input[..]).unwrap();
485        let g = &result.graph;
486
487        assert_eq!(
488            g.vertex_attribute("name", 0)
489                .and_then(AttributeValue::as_str),
490            Some("Alice")
491        );
492        assert_eq!(
493            g.vertex_attribute("name", 1)
494                .and_then(AttributeValue::as_str),
495            Some("Bob")
496        );
497        assert_eq!(
498            g.vertex_attribute("name", 2)
499                .and_then(AttributeValue::as_str),
500            Some("Carol")
501        );
502    }
503
504    #[test]
505    fn test_read_stores_weight_attribute() {
506        let input = b"# x\ny 1.5\nz 2.0\n";
507        let result = read_lgl(&input[..]).unwrap();
508        let g = &result.graph;
509
510        let w0 = g
511            .edge_attribute("weight", 0)
512            .and_then(AttributeValue::as_f64)
513            .unwrap();
514        let w1 = g
515            .edge_attribute("weight", 1)
516            .and_then(AttributeValue::as_f64)
517            .unwrap();
518        assert!((w0 - 1.5).abs() < 1e-10);
519        assert!((w1 - 2.0).abs() < 1e-10);
520    }
521
522    #[test]
523    fn test_read_no_weight_attribute_when_unweighted() {
524        let input = b"# a\nb\nc\n";
525        let result = read_lgl(&input[..]).unwrap();
526        assert!(result.graph.edge_attribute("weight", 0).is_none());
527    }
528
529    #[test]
530    fn test_write_fallback_to_name_attribute() {
531        let mut g = Graph::with_vertices(2);
532        g.add_edge(0, 1).unwrap();
533        g.set_vertex_attribute("name", 0, AttributeValue::String("X".into()))
534            .unwrap();
535        g.set_vertex_attribute("name", 1, AttributeValue::String("Y".into()))
536            .unwrap();
537
538        let mut buf = Vec::new();
539        write_lgl(&g, None, None, &mut buf).unwrap();
540        let s = String::from_utf8(buf).unwrap();
541        assert!(s.contains("# X\n"));
542        assert!(s.contains("Y\n"));
543    }
544
545    #[test]
546    fn test_write_fallback_to_weight_attribute() {
547        let mut g = Graph::with_vertices(2);
548        g.add_edge(0, 1).unwrap();
549        g.set_edge_attribute("weight", 0, AttributeValue::Numeric(4.25))
550            .unwrap();
551
552        let mut buf = Vec::new();
553        write_lgl(&g, None, None, &mut buf).unwrap();
554        let s = String::from_utf8(buf).unwrap();
555        assert!(s.contains("4.25"));
556    }
557
558    #[test]
559    fn test_roundtrip_via_attributes() {
560        let input = b"# Alice\nBob 1.5\nCarol 2.5\n# Bob\nCarol 3.0\n";
561        let result = read_lgl(&input[..]).unwrap();
562
563        // Write using attribute fallback (no explicit names/weights)
564        let mut buf = Vec::new();
565        write_lgl(&result.graph, None, None, &mut buf).unwrap();
566
567        let result2 = read_lgl(&buf[..]).unwrap();
568        assert_eq!(result2.graph.vcount(), 3);
569        assert_eq!(result2.graph.ecount(), 3);
570        assert!(result2.weights.is_some());
571    }
572
573    #[test]
574    fn test_explicit_params_override_attributes() {
575        let mut g = Graph::with_vertices(2);
576        g.add_edge(0, 1).unwrap();
577        g.set_vertex_attribute("name", 0, AttributeValue::String("attr_A".into()))
578            .unwrap();
579        g.set_vertex_attribute("name", 1, AttributeValue::String("attr_B".into()))
580            .unwrap();
581        g.set_edge_attribute("weight", 0, AttributeValue::Numeric(9.0))
582            .unwrap();
583
584        let names = vec!["explicit_A".to_string(), "explicit_B".to_string()];
585        let weights = vec![1.0];
586        let mut buf = Vec::new();
587        write_lgl(&g, Some(&names), Some(&weights), &mut buf).unwrap();
588        let s = String::from_utf8(buf).unwrap();
589        assert!(s.contains("# explicit_A"));
590        assert!(s.contains("explicit_B 1"));
591        assert!(!s.contains("attr_A"));
592        assert!(!s.contains('9'));
593    }
594}
rust_igraph/algorithms/io/lgl.rs

rust_igraph/algorithms/io/
lgl.rs
