summaryrefslogtreecommitdiff
path: root/vendor/petgraph/src/graph6
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/petgraph/src/graph6')
-rw-r--r--vendor/petgraph/src/graph6/graph6_decoder.rs200
-rw-r--r--vendor/petgraph/src/graph6/graph6_encoder.rs154
-rw-r--r--vendor/petgraph/src/graph6/mod.rs7
3 files changed, 0 insertions, 361 deletions
diff --git a/vendor/petgraph/src/graph6/graph6_decoder.rs b/vendor/petgraph/src/graph6/graph6_decoder.rs
deleted file mode 100644
index c0d6ecfa..00000000
--- a/vendor/petgraph/src/graph6/graph6_decoder.rs
+++ /dev/null
@@ -1,200 +0,0 @@
-//! [graph6 format](https://users.cecs.anu.edu.au/~bdm/data/formats.txt) decoder for undirected graphs.
-
-use crate::{csr::Csr, graph::IndexType, Graph, Undirected};
-
-#[cfg(feature = "graphmap")]
-use crate::graphmap::GraphMap;
-
-#[cfg(feature = "graphmap")]
-use std::hash::BuildHasher;
-
-#[cfg(feature = "matrix_graph")]
-use crate::matrix_graph::{MatrixGraph, Nullable};
-
-#[cfg(feature = "stable_graph")]
-use crate::stable_graph::{StableGraph, StableUnGraph};
-
-const N: usize = 63;
-
-/// A graph that can be converted from graph6 format string.
-pub trait FromGraph6 {
- fn from_graph6_string(graph6_string: String) -> Self;
-}
-
-/// Converts a graph6 format string into data can be used to construct an undirected graph.
-/// Returns a tuple containing the graph order and its edges.
-pub fn from_graph6_representation<Ix>(graph6_representation: String) -> (usize, Vec<(Ix, Ix)>)
-where
- Ix: IndexType,
-{
- let (order_bytes, adj_matrix_bytes) =
- get_order_bytes_and_adj_matrix_bytes(graph6_representation);
-
- let order_bits = bytes_vector_to_bits_vector(order_bytes);
- let adj_matrix_bits = bytes_vector_to_bits_vector(adj_matrix_bytes);
-
- let graph_order = get_bits_as_decimal(order_bits);
- let edges = get_edges(graph_order, adj_matrix_bits);
-
- (graph_order, edges)
-}
-
-// Converts a graph6 format string into a vector of bytes, converted from ASCII characters,
-// split into two parts, the first representing the graph order, and the second its adjacency matrix.
-fn get_order_bytes_and_adj_matrix_bytes(graph6_representation: String) -> (Vec<usize>, Vec<usize>) {
- let bytes: Vec<usize> = graph6_representation
- .chars()
- .map(|c| (c as usize) - N)
- .collect();
-
- let mut order_bytes = vec![];
- let mut adj_matrix_bytes = vec![];
-
- let first_byte = *bytes.first().unwrap();
- if first_byte == N {
- order_bytes.extend_from_slice(&bytes[1..=3]);
- adj_matrix_bytes.extend_from_slice(&bytes[4..]);
- } else {
- order_bytes.push(first_byte);
- adj_matrix_bytes.extend_from_slice(&bytes[1..]);
- };
-
- (order_bytes, adj_matrix_bytes)
-}
-
-// Converts a bytes vector into a bits vector.
-fn bytes_vector_to_bits_vector(bytes: Vec<usize>) -> Vec<u8> {
- bytes
- .iter()
- .flat_map(|&byte| get_number_as_bits(byte, 6))
- .collect()
-}
-
-// Get binary representation of `n` as a vector of bits with `bits_length` length.
-fn get_number_as_bits(n: usize, bits_length: usize) -> Vec<u8> {
- let mut bits = Vec::new();
- for i in (0..bits_length).rev() {
- bits.push(((n >> i) & 1) as u8);
- }
- bits
-}
-
-// Convert a bits vector into its decimal representation.
-fn get_bits_as_decimal(bits: Vec<u8>) -> usize {
- let bits_str = bits
- .iter()
- .map(|bit| bit.to_string())
- .collect::<Vec<String>>()
- .join("");
-
- usize::from_str_radix(&bits_str, 2).unwrap()
-}
-
-// Get graph edges from its order and bits vector representation of its adjacency matrix.
-fn get_edges<Ix>(order: usize, adj_matrix_bits: Vec<u8>) -> Vec<(Ix, Ix)>
-where
- Ix: IndexType,
-{
- let mut edges = vec![];
-
- let mut i = 0;
- for col in 1..order {
- for lin in 0..col {
- let is_adjacent = adj_matrix_bits[i] == 1;
-
- if is_adjacent {
- edges.push((Ix::new(lin), Ix::new(col)));
- };
-
- i += 1;
- }
- }
-
- edges
-}
-
-impl<Ix: IndexType> FromGraph6 for Graph<(), (), Undirected, Ix> {
- fn from_graph6_string(graph6_string: String) -> Self {
- let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
-
- let mut graph: Graph<(), (), Undirected, Ix> = Graph::with_capacity(order, edges.len());
- for _ in 0..order {
- graph.add_node(());
- }
- graph.extend_with_edges(edges);
-
- graph
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<Ix: IndexType> FromGraph6 for StableGraph<(), (), Undirected, Ix> {
- fn from_graph6_string(graph6_string: String) -> Self {
- let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
-
- let mut graph: StableGraph<(), (), Undirected, Ix> =
- StableUnGraph::with_capacity(order, edges.len());
- for _ in 0..order {
- graph.add_node(());
- }
- graph.extend_with_edges(edges);
-
- graph
- }
-}
-
-#[cfg(feature = "graphmap")]
-impl<Ix: IndexType, S: BuildHasher + Default> FromGraph6 for GraphMap<Ix, (), Undirected, S> {
- fn from_graph6_string(graph6_string: String) -> Self {
- let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
-
- let mut graph: GraphMap<Ix, (), Undirected, S> =
- GraphMap::with_capacity(order, edges.len());
- for i in 0..order {
- graph.add_node(Ix::new(i));
- }
- for (a, b) in edges {
- graph.add_edge(a, b, ());
- }
-
- graph
- }
-}
-
-#[cfg(feature = "matrix_graph")]
-impl<Null, Ix> FromGraph6 for MatrixGraph<(), (), Undirected, Null, Ix>
-where
- Null: Nullable<Wrapped = ()>,
- Ix: IndexType,
-{
- fn from_graph6_string(graph6_string: String) -> Self {
- let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
-
- let mut graph: MatrixGraph<(), (), Undirected, Null, Ix> =
- MatrixGraph::with_capacity(order);
- for _ in 0..order {
- graph.add_node(());
- }
- graph.extend_with_edges(edges.iter());
-
- graph
- }
-}
-
-impl<Ix: IndexType> FromGraph6 for Csr<(), (), Undirected, Ix> {
- fn from_graph6_string(graph6_string: String) -> Self {
- let (order, edges): (usize, Vec<(Ix, Ix)>) = from_graph6_representation(graph6_string);
-
- let mut graph: Csr<(), (), Undirected, Ix> = Csr::new();
- let mut nodes = Vec::new();
- for _ in 0..order {
- let i = graph.add_node(());
- nodes.push(i);
- }
- for (a, b) in edges {
- graph.add_edge(a, b, ());
- }
-
- graph
- }
-}
diff --git a/vendor/petgraph/src/graph6/graph6_encoder.rs b/vendor/petgraph/src/graph6/graph6_encoder.rs
deleted file mode 100644
index 41ba530a..00000000
--- a/vendor/petgraph/src/graph6/graph6_encoder.rs
+++ /dev/null
@@ -1,154 +0,0 @@
-//! [graph6 format](https://users.cecs.anu.edu.au/~bdm/data/formats.txt) encoder for undirected graphs.
-
-use crate::{
- csr::Csr,
- graph::IndexType,
- visit::{GetAdjacencyMatrix, IntoNodeIdentifiers},
- Graph, Undirected,
-};
-
-#[cfg(feature = "graphmap")]
-use crate::graphmap::{GraphMap, NodeTrait};
-
-#[cfg(feature = "graphmap")]
-use std::hash::BuildHasher;
-
-#[cfg(feature = "matrix_graph")]
-use crate::matrix_graph::{MatrixGraph, Nullable};
-
-#[cfg(feature = "stable_graph")]
-use crate::stable_graph::StableGraph;
-
-const N: usize = 63;
-
-/// A graph that can be converted to graph6 format string.
-pub trait ToGraph6 {
- fn graph6_string(&self) -> String;
-}
-
-/// Converts a graph that implements GetAdjacencyMatrix and IntoNodeIdentifers
-/// into a graph6 format string.
-pub fn get_graph6_representation<G>(graph: G) -> String
-where
- G: GetAdjacencyMatrix + IntoNodeIdentifiers,
-{
- let (graph_order, mut upper_diagonal_as_bits) = get_adj_matrix_upper_diagonal_as_bits(graph);
- let mut graph_order_as_bits = get_graph_order_as_bits(graph_order);
-
- let mut graph_as_bits = vec![];
- graph_as_bits.append(&mut graph_order_as_bits);
- graph_as_bits.append(&mut upper_diagonal_as_bits);
-
- bits_to_ascii(graph_as_bits)
-}
-
-// Traverse graph nodes and construct the upper diagonal of its adjacency matrix as a vector of bits.
-// Returns a tuple containing:
-// - `n`: graph order (number of nodes in graph)
-// - `bits`: a vector of 0s and 1s encoding the upper diagonal of the graphs adjacency matrix.
-fn get_adj_matrix_upper_diagonal_as_bits<G>(graph: G) -> (usize, Vec<usize>)
-where
- G: GetAdjacencyMatrix + IntoNodeIdentifiers,
-{
- let node_ids_iter = graph.node_identifiers();
- let mut node_ids_vec = vec![];
-
- let adj_matrix = graph.adjacency_matrix();
- let mut bits = vec![];
- let mut n = 0;
- for node_id in node_ids_iter {
- node_ids_vec.push(node_id);
-
- for i in 1..=n {
- let is_adjacent: bool =
- graph.is_adjacent(&adj_matrix, node_ids_vec[i - 1], node_ids_vec[n]);
- bits.push(if is_adjacent { 1 } else { 0 });
- }
-
- n += 1;
- }
-
- (n, bits)
-}
-
-// Converts graph order to a bits vector.
-fn get_graph_order_as_bits(order: usize) -> Vec<usize> {
- let to_convert_to_bits = if order < N {
- vec![(order, 6)]
- } else if order <= 258047 {
- vec![(N, 6), (order, 18)]
- } else {
- panic!("Graph order not supported.")
- };
-
- to_convert_to_bits
- .iter()
- .flat_map(|&(n, n_of_bits)| get_number_as_bits(n, n_of_bits))
- .collect()
-}
-
-// Get binary representation of `n` as a vector of bits with `bits_length` length.
-fn get_number_as_bits(n: usize, bits_length: usize) -> Vec<usize> {
- let mut bits = Vec::new();
- for i in (0..bits_length).rev() {
- bits.push((n >> i) & 1);
- }
- bits
-}
-
-// Convert a vector of bits to a String using ASCII encoding.
-// Each 6 bits will be converted to a single ASCII character.
-fn bits_to_ascii(mut bits: Vec<usize>) -> String {
- while bits.len() % 6 != 0 {
- bits.push(0);
- }
-
- let bits_strs = bits.iter().map(|bit| bit.to_string()).collect::<Vec<_>>();
-
- let bytes = bits_strs
- .chunks(6)
- .map(|bits_chunk| bits_chunk.join(""))
- .map(|bits_str| usize::from_str_radix(&bits_str, 2));
-
- bytes
- .map(|byte| char::from((N + byte.unwrap()) as u8))
- .collect()
-}
-
-impl<N, E, Ix: IndexType> ToGraph6 for Graph<N, E, Undirected, Ix> {
- fn graph6_string(&self) -> String {
- get_graph6_representation(self)
- }
-}
-
-#[cfg(feature = "stable_graph")]
-impl<N, E, Ix: IndexType> ToGraph6 for StableGraph<N, E, Undirected, Ix> {
- fn graph6_string(&self) -> String {
- get_graph6_representation(self)
- }
-}
-
-#[cfg(feature = "graphmap")]
-impl<N: NodeTrait, E, S: BuildHasher> ToGraph6 for GraphMap<N, E, Undirected, S> {
- fn graph6_string(&self) -> String {
- get_graph6_representation(self)
- }
-}
-
-#[cfg(feature = "matrix_graph")]
-impl<N, E, Null, Ix> ToGraph6 for MatrixGraph<N, E, Undirected, Null, Ix>
-where
- N: NodeTrait,
- Null: Nullable<Wrapped = E>,
- Ix: IndexType,
-{
- fn graph6_string(&self) -> String {
- get_graph6_representation(self)
- }
-}
-
-impl<N, E, Ix: IndexType> ToGraph6 for Csr<N, E, Undirected, Ix> {
- fn graph6_string(&self) -> String {
- get_graph6_representation(self)
- }
-}
diff --git a/vendor/petgraph/src/graph6/mod.rs b/vendor/petgraph/src/graph6/mod.rs
deleted file mode 100644
index 0d16f0c7..00000000
--- a/vendor/petgraph/src/graph6/mod.rs
+++ /dev/null
@@ -1,7 +0,0 @@
-//! Traits related to [graph6 format](https://users.cecs.anu.edu.au/~bdm/data/formats.txt) for undirected graphs.
-
-pub use self::graph6_decoder::*;
-pub use self::graph6_encoder::*;
-
-mod graph6_decoder;
-mod graph6_encoder;
generated by cgit v1.2.3 (git 2.39.1) at 2026-02-03 13:05:11 +0000