petgraph/graph6/
graph6_encoder.rs

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

petgraph/graph6/
graph6_encoder.rs
