traitgraph_tsplib_io/
lib.rs

1#![warn(missing_docs)]
2//! This crate offers functions to read and write graphs in TSPLIB format.
3
4use std::io::{BufRead, BufReader, Read, Write};
5use traitgraph::interface::{DynamicGraph, StaticGraph};
6
7/// Write the graph as Hamiltonian circuit problem encoded as ATSP in TSPLIB format (used by concorde).
8pub fn write_hamcircuit_as_tsplib_atsp<Graph: StaticGraph, Writer: Write>(
9    graph: &Graph,
10    writer: &mut Writer,
11) {
12    // NAME:  demo
13    // TYPE: TSP
14    // COMMENT: 4 vertexes asymmetric problem
15    // DIMENSION:  4
16    // EDGE_WEIGHT_TYPE: EXPLICIT
17    // EDGE_WEIGHT_FORMAT: FULL_MATRIX
18    // EDGE_WEIGHT_SECTION
19    // 9999 11 8 4
20    // 10 9999 7 2
21    // 6 5 9999 4
22    // 6 3 9 9999
23    // EOF
24
25    writeln!(writer, "NAME: none\nTYPE: ATSP\nCOMMENT: none\nDIMENSION: {}\nEDGE_WEIGHT_TYPE: EXPLICIT\nEDGE_WEIGHT_FORMAT: FULL_MATRIX\nEDGE_WEIGHT_SECTION", graph.node_count()).unwrap();
26
27    for n1 in graph.node_indices() {
28        for n2 in graph.node_indices() {
29            if n1 == n2 || !graph.contains_edge_between(n1, n2) {
30                write!(writer, " {}", graph.node_count() * 10).unwrap();
31            } else {
32                write!(writer, " 1").unwrap();
33            }
34        }
35
36        writeln!(writer).unwrap();
37    }
38
39    writeln!(writer, "EOF").unwrap();
40}
41
42/// Read a graph as Hamiltonian circuit problem encoded as ATSP in TSPLIB format (used by concorde).
43pub fn read_hamcircuit_from_tsplib_atsp<Graph: DynamicGraph, Reader: Read>(
44    graph: &mut Graph,
45    reader: &mut Reader,
46) where
47    Graph::NodeData: Default,
48    Graph::EdgeData: Default,
49{
50    // NAME:  demo
51    // TYPE: TSP
52    // COMMENT: 4 vertexes asymmetric problem
53    // DIMENSION:  4
54    // EDGE_WEIGHT_TYPE: EXPLICIT
55    // EDGE_WEIGHT_FORMAT: FULL_MATRIX
56    // EDGE_WEIGHT_SECTION
57    // 9999 11 8 4
58    // 10 9999 7 2
59    // 6 5 9999 4
60    // 6 3 9 9999
61    // EOF
62
63    let mut node_count = None;
64
65    let mut reader = BufReader::new(reader);
66    loop {
67        let mut line = String::new();
68        reader.read_line(&mut line).unwrap();
69
70        if line.trim().starts_with("DIMENSION:") {
71            let line = line.trim().split(' ').next_back().unwrap();
72            node_count = Some(line.parse::<usize>().unwrap());
73        }
74
75        if line.trim().starts_with("EDGE_WEIGHT_SECTION") {
76            break;
77        }
78    }
79
80    let node_count = node_count.unwrap();
81
82    for _ in 0..node_count {
83        graph.add_node(Default::default());
84    }
85
86    for n1 in graph.node_indices_copied() {
87        let mut line = String::new();
88        reader.read_line(&mut line).unwrap();
89        let edges = line.trim().split(' ');
90
91        for (n2, edge_weight) in graph.node_indices_copied().zip(edges) {
92            let edge_weight: usize = edge_weight.trim().parse().unwrap();
93            if edge_weight == 1 {
94                graph.add_edge(n1, n2, Default::default());
95            }
96        }
97    }
98
99    let mut line = String::new();
100    reader.read_line(&mut line).unwrap();
101    debug_assert_eq!(line.trim(), "EOF");
102}
103
104/// Write the graph as Hamiltonian circuit problem encoded as TSP in TSPLIB format (used by concorde).
105pub fn write_hamcircuit_as_tsplib_tsp<Graph: StaticGraph, Writer: Write>(
106    graph: &Graph,
107    writer: &mut Writer,
108) {
109    // NAME:  demo
110    // TYPE: TSP
111    // COMMENT: 4 vertexes asymmetric problem
112    // DIMENSION:  4
113    // EDGE_WEIGHT_TYPE: EXPLICIT
114    // EDGE_WEIGHT_FORMAT: FULL_MATRIX
115    // EDGE_WEIGHT_SECTION
116    // 9999 11 8 4
117    // 10 9999 7 2
118    // 6 5 9999 4
119    // 6 3 9 9999
120    // EOF
121
122    writeln!(writer, "NAME: none\nTYPE: TSP\nCOMMENT: none\nDIMENSION: {}\nEDGE_WEIGHT_TYPE: EXPLICIT\nEDGE_WEIGHT_FORMAT: FULL_MATRIX\nEDGE_WEIGHT_SECTION", graph.node_count() * 2).unwrap();
123
124    // First half of the matrix.
125    for n2 in graph.node_indices() {
126        for _ in graph.node_indices() {
127            write!(writer, " {}", graph.node_count() * 10).unwrap();
128        }
129
130        for n1 in graph.node_indices() {
131            if n1 == n2 {
132                write!(writer, " 0").unwrap();
133            } else if graph.contains_edge_between(n1, n2) {
134                write!(writer, " 10").unwrap();
135            } else {
136                write!(writer, " 12").unwrap();
137            }
138        }
139
140        writeln!(writer).unwrap();
141    }
142
143    // Second half of the matrix.
144    for n1 in graph.node_indices() {
145        for n2 in graph.node_indices() {
146            if n1 == n2 {
147                write!(writer, " 0").unwrap();
148            } else if graph.contains_edge_between(n1, n2) {
149                write!(writer, " 10").unwrap();
150            } else {
151                write!(writer, " 12").unwrap();
152            }
153        }
154
155        for _ in graph.node_indices() {
156            write!(writer, " {}", graph.node_count() * 10).unwrap();
157        }
158
159        writeln!(writer).unwrap();
160    }
161
162    writeln!(writer, "EOF").unwrap();
163}
164
165/// Read a graph as Hamiltonian circuit problem encoded as TSP in TSPLIB format (used by concorde).
166pub fn read_hamcircuit_from_tsplib_tsp<Graph: DynamicGraph, Reader: Read>(
167    graph: &mut Graph,
168    reader: &mut Reader,
169) where
170    Graph::NodeData: Default,
171    Graph::EdgeData: Default,
172{
173    // NAME:  demo
174    // TYPE: TSP
175    // COMMENT: 4 vertexes asymmetric problem
176    // DIMENSION:  4
177    // EDGE_WEIGHT_TYPE: EXPLICIT
178    // EDGE_WEIGHT_FORMAT: FULL_MATRIX
179    // EDGE_WEIGHT_SECTION
180    // 9999 11 8 4
181    // 10 9999 7 2
182    // 6 5 9999 4
183    // 6 3 9 9999
184    // EOF
185
186    let mut node_count = None;
187
188    let mut reader = BufReader::new(reader);
189    loop {
190        let mut line = String::new();
191        reader.read_line(&mut line).unwrap();
192
193        if line.trim().starts_with("DIMENSION:") {
194            let line = line.trim().split(' ').next_back().unwrap();
195            node_count = Some(line.parse::<usize>().unwrap());
196            debug_assert_eq!(node_count.unwrap() % 2, 0, "Node count is odd");
197            node_count = Some(node_count.unwrap() / 2);
198        }
199
200        if line.trim().starts_with("EDGE_WEIGHT_SECTION") {
201            break;
202        }
203    }
204
205    let node_count = node_count.unwrap();
206
207    for _ in 0..node_count {
208        graph.add_node(Default::default());
209    }
210
211    for n1 in graph.node_indices_copied() {
212        let mut line = String::new();
213        reader.read_line(&mut line).unwrap();
214        let edges = line.trim().split(' ');
215
216        for (n2, edge_weight) in graph.node_indices_copied().zip(edges.skip(node_count)) {
217            let edge_weight: usize = edge_weight.trim().parse().unwrap();
218            if edge_weight == 10 {
219                graph.add_edge(n2, n1, Default::default());
220            }
221        }
222    }
223
224    for _ in graph.node_indices() {
225        let mut line = String::new();
226        reader.read_line(&mut line).unwrap();
227    }
228
229    let mut line = String::new();
230    reader.read_line(&mut line).unwrap();
231    debug_assert_eq!(line.trim(), "EOF");
232}
233
234#[cfg(test)]
235mod tests {
236    use crate::{read_hamcircuit_from_tsplib_tsp, write_hamcircuit_as_tsplib_tsp};
237    use std::io::{BufReader, BufWriter};
238    use traitgraph::implementation::petgraph_impl::PetGraph;
239    use traitgraph::interface::{ImmutableGraphContainer, MutableGraphContainer, NavigableGraph};
240
241    #[test]
242    fn test_write_read_simple() {
243        let mut graph = PetGraph::new();
244        let n0 = graph.add_node(());
245        let n1 = graph.add_node(());
246        let n2 = graph.add_node(());
247        let n3 = graph.add_node(());
248        graph.add_edge(n0, n1, ());
249        graph.add_edge(n0, n2, ());
250        graph.add_edge(n1, n2, ());
251        graph.add_edge(n1, n3, ());
252        graph.add_edge(n2, n1, ());
253        graph.add_edge(n3, n0, ());
254
255        let mut writer = BufWriter::new(Vec::new());
256        write_hamcircuit_as_tsplib_tsp(&graph, &mut writer);
257        let mut result = PetGraph::<(), ()>::new();
258        let buffer = writer.into_inner().unwrap();
259        let mut reader = BufReader::new(buffer.as_slice());
260        read_hamcircuit_from_tsplib_tsp(&mut result, &mut reader);
261        debug_assert_eq!(graph.node_count(), result.node_count());
262        debug_assert_eq!(graph.edge_count(), result.edge_count());
263
264        for n1 in graph.node_indices() {
265            for n2 in graph.node_indices() {
266                debug_assert_eq!(
267                    graph.contains_edge_between(n1, n2),
268                    result.contains_edge_between(n1, n2)
269                );
270            }
271        }
272    }
273}
traitgraph_tsplib_io/lib.rs

traitgraph_tsplib_io/
lib.rs
