3 files changed, 361 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
+    }
+}
diff --git a/vendor/petgraph/src/graph6/graph6_encoder.rs b/vendor/petgraph/src/graph6/graph6_encoder.rs
new file mode 100644
index 00000000..41ba530a
--- /dev/null
+++ b/vendor/petgraph/src/graph6/graph6_encoder.rs
@@ -0,0 +1,154 @@
+//! [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
new file mode 100644
index 00000000..0d16f0c7
--- /dev/null
+++ b/vendor/petgraph/src/graph6/mod.rs
@@ -0,0 +1,7 @@
+//! 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;