petgraph/graph6/
graph6_decoder.rs

1//! [graph6 format](https://users.cecs.anu.edu.au/~bdm/data/formats.txt) decoder for undirected graphs.
2
3use crate::{csr::Csr, graph::IndexType, Graph, Undirected};
4
5#[cfg(feature = "graphmap")]
6use crate::graphmap::GraphMap;
7
8#[cfg(feature = "graphmap")]
9use std::hash::BuildHasher;
10
11#[cfg(feature = "matrix_graph")]
12use crate::matrix_graph::{MatrixGraph, Nullable};
13
14#[cfg(feature = "stable_graph")]
15use crate::stable_graph::{StableGraph, StableUnGraph};
16
17const N: usize = 63;
18
19/// A graph that can be converted from graph6 format string.
20pub trait FromGraph6 {
21    fn from_graph6_string(graph6_string: String) -> Self;
22}
23
24/// Converts a graph6 format string into data can be used to construct an undirected graph.
25/// Returns a tuple containing the graph order and its edges.
26pub fn from_graph6_representation<Ix>(graph6_representation: String) -> (usize, Vec<(Ix, Ix)>)
27where
28    Ix: IndexType,
29{
30    let (order_bytes, adj_matrix_bytes) =
31        get_order_bytes_and_adj_matrix_bytes(graph6_representation);
32
33    let order_bits = bytes_vector_to_bits_vector(order_bytes);
34    let adj_matrix_bits = bytes_vector_to_bits_vector(adj_matrix_bytes);
35
36    let graph_order = get_bits_as_decimal(order_bits);
37    let edges = get_edges(graph_order, adj_matrix_bits);
38
39    (graph_order, edges)
40}
41
42// Converts a graph6 format string into a vector of bytes, converted from ASCII characters,
43// split into two parts, the first representing the graph order, and the second its adjacency matrix.
44fn get_order_bytes_and_adj_matrix_bytes(graph6_representation: String) -> (Vec<usize>, Vec<usize>) {
45    let bytes: Vec<usize> = graph6_representation
46        .chars()
47        .map(|c| (c as usize) - N)
48        .collect();
49
50    let mut order_bytes = vec![];
51    let mut adj_matrix_bytes = vec![];
52
53    let first_byte = *bytes.first().unwrap();
54    if first_byte == N {
55        order_bytes.extend_from_slice(&bytes[1..=3]);
56        adj_matrix_bytes.extend_from_slice(&bytes[4..]);
57    } else {
58        order_bytes.push(first_byte);
59        adj_matrix_bytes.extend_from_slice(&bytes[1..]);
60    };
61
62    (order_bytes, adj_matrix_bytes)
63}
64
65// Converts a bytes vector into a bits vector.
66fn bytes_vector_to_bits_vector(bytes: Vec<usize>) -> Vec<u8> {
67    bytes
68        .iter()
69        .flat_map(|&byte| get_number_as_bits(byte, 6))
70        .collect()
71}
72
73// Get binary representation of `n` as a vector of bits with `bits_length` length.
74fn get_number_as_bits(n: usize, bits_length: usize) -> Vec<u8> {
75    let mut bits = Vec::new();
76    for i in (0..bits_length).rev() {
77        bits.push(((n >> i) & 1) as u8);
78    }
79    bits
80}
81
82// Convert a bits vector into its decimal representation.
83fn get_bits_as_decimal(bits: Vec<u8>) -> usize {
84    let bits_str = bits
85        .iter()
86        .map(|bit| bit.to_string())
87        .collect::<Vec<String>>()
88        .join("");
89
90    usize::from_str_radix(&bits_str, 2).unwrap()
91}
92
93// Get graph edges from its order and bits vector representation of its adjacency matrix.
94fn get_edges<Ix>(order: usize, adj_matrix_bits: Vec<u8>) -> Vec<(Ix, Ix)>
95where
96    Ix: IndexType,
97{
98    let mut edges = vec![];
99
100    let mut i = 0;
101    for col in 1..order {
102        for lin in 0..col {
103            let is_adjacent = adj_matrix_bits[i] == 1;
104
105            if is_adjacent {
106                edges.push((Ix::new(lin), Ix::new(col)));
107            };
108
109            i += 1;
110        }
111    }
112
113    edges
114}
115
116impl<Ix: IndexType> FromGraph6 for Graph<(), (), Undirected, Ix> {
117    fn from_graph6_string(graph6_string: String) -> Self {
118        let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
119
120        let mut graph: Graph<(), (), Undirected, Ix> = Graph::with_capacity(order, edges.len());
121        for _ in 0..order {
122            graph.add_node(());
123        }
124        graph.extend_with_edges(edges);
125
126        graph
127    }
128}
129
130#[cfg(feature = "stable_graph")]
131impl<Ix: IndexType> FromGraph6 for StableGraph<(), (), Undirected, Ix> {
132    fn from_graph6_string(graph6_string: String) -> Self {
133        let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
134
135        let mut graph: StableGraph<(), (), Undirected, Ix> =
136            StableUnGraph::with_capacity(order, edges.len());
137        for _ in 0..order {
138            graph.add_node(());
139        }
140        graph.extend_with_edges(edges);
141
142        graph
143    }
144}
145
146#[cfg(feature = "graphmap")]
147impl<Ix: IndexType, S: BuildHasher + Default> FromGraph6 for GraphMap<Ix, (), Undirected, S> {
148    fn from_graph6_string(graph6_string: String) -> Self {
149        let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
150
151        let mut graph: GraphMap<Ix, (), Undirected, S> =
152            GraphMap::with_capacity(order, edges.len());
153        for i in 0..order {
154            graph.add_node(Ix::new(i));
155        }
156        for (a, b) in edges {
157            graph.add_edge(a, b, ());
158        }
159
160        graph
161    }
162}
163
164#[cfg(feature = "matrix_graph")]
165impl<Null, Ix> FromGraph6 for MatrixGraph<(), (), Undirected, Null, Ix>
166where
167    Null: Nullable<Wrapped = ()>,
168    Ix: IndexType,
169{
170    fn from_graph6_string(graph6_string: String) -> Self {
171        let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
172
173        let mut graph: MatrixGraph<(), (), Undirected, Null, Ix> =
174            MatrixGraph::with_capacity(order);
175        for _ in 0..order {
176            graph.add_node(());
177        }
178        graph.extend_with_edges(edges.iter());
179
180        graph
181    }
182}
183
184impl<Ix: IndexType> FromGraph6 for Csr<(), (), Undirected, Ix> {
185    fn from_graph6_string(graph6_string: String) -> Self {
186        let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
187
188        let mut graph: Csr<(), (), Undirected, Ix> = Csr::new();
189        let mut nodes = Vec::new();
190        for _ in 0..order {
191            let i = graph.add_node(());
192            nodes.push(i);
193        }
194        for (a, b) in edges {
195            graph.add_edge(a, b, ());
196        }
197
198        graph
199    }
200}
petgraph/graph6/graph6_decoder.rs

petgraph/graph6/
graph6_decoder.rs
