petgraph/graph6/
graph6_encoder.rs

Help
1//! [graph6 format](https://users.cecs.anu.edu.au/~bdm/data/formats.txt) encoder for undirected graphs.
2
3use alloc::{
4    string::{String, ToString},
5    vec,
6    vec::Vec,
7};
8
9use crate::{
10    csr::Csr,
11    graph::IndexType,
12    visit::{GetAdjacencyMatrix, IntoNodeIdentifiers},
13    Graph, Undirected,
14};
15
16#[cfg(feature = "graphmap")]
17use crate::graphmap::{GraphMap, NodeTrait};
18
19#[cfg(feature = "graphmap")]
20use core::hash::BuildHasher;
21
22#[cfg(feature = "matrix_graph")]
23use crate::matrix_graph::{MatrixGraph, Nullable};
24
25#[cfg(feature = "stable_graph")]
26use crate::stable_graph::StableGraph;
27
28const N: usize = 63;
29
30/// A graph that can be converted to graph6 format string.
31pub trait ToGraph6 {
32    fn graph6_string(&self) -> String;
33}
34
35/// Converts a graph that implements GetAdjacencyMatrix and IntoNodeIdentifers
36/// into a graph6 format string.
37pub fn get_graph6_representation<G>(graph: G) -> String
38where
39    G: GetAdjacencyMatrix + IntoNodeIdentifiers,
40{
41    let (graph_order, mut upper_diagonal_as_bits) = get_adj_matrix_upper_diagonal_as_bits(graph);
42    let mut graph_order_as_bits = get_graph_order_as_bits(graph_order);
43
44    let mut graph_as_bits = vec![];
45    graph_as_bits.append(&mut graph_order_as_bits);
46    graph_as_bits.append(&mut upper_diagonal_as_bits);
47
48    bits_to_ascii(graph_as_bits)
49}
50
51// Traverse graph nodes and construct the upper diagonal of its adjacency matrix as a vector of bits.
52// Returns a tuple containing:
53// - `n`: graph order (number of nodes in graph)
54// - `bits`: a vector of 0s and 1s encoding the upper diagonal of the graphs adjacency matrix.
55fn get_adj_matrix_upper_diagonal_as_bits<G>(graph: G) -> (usize, Vec<usize>)
56where
57    G: GetAdjacencyMatrix + IntoNodeIdentifiers,
58{
59    let node_ids_iter = graph.node_identifiers();
60    let mut node_ids_vec = vec![];
61
62    let adj_matrix = graph.adjacency_matrix();
63    let mut bits = vec![];
64    let mut n = 0;
65    for node_id in node_ids_iter {
66        node_ids_vec.push(node_id);
67
68        for i in 1..=n {
69            let is_adjacent: bool =
70                graph.is_adjacent(&adj_matrix, node_ids_vec[i - 1], node_ids_vec[n]);
71            bits.push(if is_adjacent { 1 } else { 0 });
72        }
73
74        n += 1;
75    }
76
77    (n, bits)
78}
79
80// Converts graph order to a bits vector.
81fn get_graph_order_as_bits(order: usize) -> Vec<usize> {
82    let to_convert_to_bits = if order < N {
83        vec![(order, 6)]
84    } else if order <= 258047 {
85        vec![(N, 6), (order, 18)]
86    } else {
87        panic!("Graph order not supported.")
88    };
89
90    to_convert_to_bits
91        .iter()
92        .flat_map(|&(n, n_of_bits)| get_number_as_bits(n, n_of_bits))
93        .collect()
94}
95
96// Get binary representation of `n` as a vector of bits with `bits_length` length.
97fn get_number_as_bits(n: usize, bits_length: usize) -> Vec<usize> {
98    let mut bits = Vec::new();
99    for i in (0..bits_length).rev() {
100        bits.push((n >> i) & 1);
101    }
102    bits
103}
104
105// Convert a vector of bits to a String using ASCII encoding.
106// Each 6 bits will be converted to a single ASCII character.
107fn bits_to_ascii(mut bits: Vec<usize>) -> String {
108    while bits.len() % 6 != 0 {
109        bits.push(0);
110    }
111
112    let bits_strs = bits.iter().map(|bit| bit.to_string()).collect::<Vec<_>>();
113
114    let bytes = bits_strs
115        .chunks(6)
116        .map(|bits_chunk| bits_chunk.join(""))
117        .map(|bits_str| usize::from_str_radix(&bits_str, 2));
118
119    bytes
120        .map(|byte| char::from((N + byte.unwrap()) as u8))
121        .collect()
122}
123
124impl<N, E, Ix: IndexType> ToGraph6 for Graph<N, E, Undirected, Ix> {
125    fn graph6_string(&self) -> String {
126        get_graph6_representation(self)
127    }
128}
129
130#[cfg(feature = "stable_graph")]
131impl<N, E, Ix: IndexType> ToGraph6 for StableGraph<N, E, Undirected, Ix> {
132    fn graph6_string(&self) -> String {
133        get_graph6_representation(self)
134    }
135}
136
137#[cfg(feature = "graphmap")]
138impl<N: NodeTrait, E, S: BuildHasher> ToGraph6 for GraphMap<N, E, Undirected, S> {
139    fn graph6_string(&self) -> String {
140        get_graph6_representation(self)
141    }
142}
143
144#[cfg(feature = "matrix_graph")]
145impl<N, E, S, Null, Ix> ToGraph6 for MatrixGraph<N, E, S, Undirected, Null, Ix>
146where
147    N: NodeTrait,
148    Null: Nullable<Wrapped = E>,
149    Ix: IndexType,
150    S: BuildHasher + Default,
151{
152    fn graph6_string(&self) -> String {
153        get_graph6_representation(self)
154    }
155}
156
157impl<N, E, Ix: IndexType> ToGraph6 for Csr<N, E, Undirected, Ix> {
158    fn graph6_string(&self) -> String {
159        get_graph6_representation(self)
160    }
161}
petgraph/graph6/graph6_encoder.rs

petgraph/graph6/
graph6_encoder.rs
