chore: add vendor directory

1 files changed, 200 insertions, 0 deletions

diff --git a/vendor/petgraph/src/graph6/graph6_decoder.rs b/vendor/petgraph/src/graph6/graph6_decoder.rs
new file mode 100644
index 00000000..c0d6ecfa
--- /dev/null
+++ b/vendor/petgraph/src/graph6/graph6_decoder.rs
@@ -0,0 +1,200 @@
+//! [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
+    }
+}