libgraph 0.1.0

use itertools::Itertools;
use rand::prelude::*;
use serde::Deserialize;
use serde::Serialize;
use std::collections::BinaryHeap;
use std::collections::HashMap;
use std::iter;

/// Represents a vertex in the graph, identified by a `usize`.
pub type Vertex = usize;
/// Represents an undirected edge between two vertices `(u, v)`.
pub type Edge = (Vertex, Vertex);

/// A generic undirected graph data structure.
///
/// The graph is represented using an adjacency list, where each vertex
/// maps to a `HashMap` of its neighbors. The `Metadata` type parameter
/// allows associating arbitrary data with each edge. If no metadata is
/// needed, `()` can be used as the `Metadata` type.
///
/// # Examples
///
/// ```
/// use libgraph::Graph;
///
/// let graph: Graph<()> = Graph::new(3)
///     .add_edge((0, 1))
///     .add_edge((1, 2));
///
/// assert_eq!(graph.num_vertices(), 3);
/// assert!(graph.has_edge((0, 1)));
/// ```
///
/// Graph with metadata:
///
/// ```
/// use libgraph::Graph;
///
/// let graph_with_weights = Graph::new(3)
///     .add_edge_with_metadata((0, 1), 10)
///     .add_edge_with_metadata((1, 2), 20);
///
/// assert_eq!(graph_with_weights.get_edge_metadata((0, 1)), Some(&10));
/// ```
#[derive(Serialize, Deserialize)]
pub struct Graph<Metadata = ()> {
    pub adj_list: Vec<HashMap<usize, Metadata>>,
}

impl<T> Graph<T> {
    /// Creates a new graph with `num_vertices` vertices and no edges.
    ///
    /// Each vertex is initially isolated.
    ///
    /// # Arguments
    ///
    /// * `num_vertices` - The number of vertices this graph should contain.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph: Graph<()> = Graph::new(5);
    /// assert_eq!(graph.num_vertices(), 5);
    /// assert_eq!(graph.edges().count(), 0);
    /// ```
    pub fn new(num_vertices: usize) -> Self {
        Self {
            adj_list: std::iter::repeat_with(|| HashMap::new())
                .take(num_vertices)
                .collect(),
        }
    }

    /// Returns an iterator over all unique undirected edges in the graph.
    ///
    /// Each edge `(u, v)` is returned only once, where `u < v`.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::new(3)
    ///     .add_edge((0, 1))
    ///     .add_edge((1, 2));
    ///
    /// let mut edges: Vec<(usize, usize)> = graph.edges().collect();
    /// edges.sort();
    /// assert_eq!(edges, vec![(0, 1), (1, 2)]);
    /// ```
    pub fn edges(&self) -> impl Iterator<Item = Edge> {
        self.adj_list
            .iter()
            .enumerate()
            .map(|(u, vs)| vs.keys().map(move |&v| (u, v)))
            .flatten()
            .filter(|(u, v)| u < v)
    }

    /// Returns the number of vertices in the graph.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph: Graph<()> = Graph::new(10);
    /// assert_eq!(graph.num_vertices(), 10);
    /// ```
    pub fn num_vertices(&self) -> usize {
        self.adj_list.len()
    }

    /// Checks if an undirected edge `(u, v)` exists in the graph.
    ///
    /// The order of `u` and `v` does not matter, i.e., `has_edge((u, v))`
    /// is equivalent to `has_edge((v, u))`.
    ///
    /// # Arguments
    ///
    /// * `edge` - A tuple `(u, v)` representing the two vertices of the edge.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::new(3).add_edge((0, 1));
    ///
    /// assert!(graph.has_edge((0, 1)));
    /// assert!(graph.has_edge((1, 0))); // Order does not matter
    /// assert!(!graph.has_edge((0, 2)));
    /// ```
    pub fn has_edge(&self, edge: Edge) -> bool {
        self.get_edge_metadata(edge).is_some()
    }

    /// Returns a reference to the metadata associated with the edge `(u, v)`,
    /// if the edge exists.
    ///
    /// The order of `u` and `v` does not matter.
    ///
    /// # Arguments
    ///
    /// * `edge` - A tuple `(u, v)` representing the two vertices of the edge.
    ///
    /// # Returns
    ///
    /// An `Option<&T>` which is `Some(metadata)` if the edge exists,
    /// and `None` otherwise.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::new(3).add_edge_with_metadata((0, 1), "weight_1".to_string());
    ///
    /// assert_eq!(graph.get_edge_metadata((0, 1)), Some(&"weight_1".to_string()));
    /// assert_eq!(graph.get_edge_metadata((1, 0)), Some(&"weight_1".to_string()));
    /// assert_eq!(graph.get_edge_metadata((0, 2)), None);
    /// ```
    pub fn get_edge_metadata(&self, edge: Edge) -> Option<&T> {
        let (u, v) = edge;
        self.adj_list.get(u).and_then(|ns| ns.get(&v))
    }
}

impl<Metadata> Graph<Metadata>
where
    Metadata: Clone,
{
    /// Adds an undirected edge between vertices `u` and `v` with associated `metadata`.
    ///
    /// If an edge already exists between `u` and `v`, its metadata will be updated.
    /// Self-loops (edges from a vertex to itself) are not supported and will be ignored.
    ///
    /// # Arguments
    ///
    /// * `edge` - A tuple `(u, v)` representing the two vertices of the edge.
    /// * `metadata` - The metadata to associate with the edge.
    ///
    /// # Returns
    ///
    /// The `Graph` instance, allowing for method chaining.
    ///
    /// # Panics
    ///
    /// Panics if `u` or `v` are out of bounds for the graph's number of vertices.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::new(3)
    ///     .add_edge_with_metadata((0, 1), 10)
    ///     .add_edge_with_metadata((1, 2), 20);
    ///
    /// assert_eq!(graph.get_edge_metadata((0, 1)), Some(&10));
    /// assert_eq!(graph.get_edge_metadata((1, 2)), Some(&20));
    ///
    /// // Update metadata for an existing edge
    /// let updated_graph = graph.add_edge_with_metadata((0, 1), 100);
    /// assert_eq!(updated_graph.get_edge_metadata((0, 1)), Some(&100));
    /// ```
    pub fn add_edge_with_metadata(mut self, (u, v): Edge, metadata: Metadata) -> Self {
        if u != v {
            self.adj_list[u].insert(v, metadata.clone());
            self.adj_list[v].insert(u, metadata);
        }
        self
    }

    /// Returns an iterator over all unique undirected edges and their associated metadata.
    ///
    /// Each edge `(u, v)` and its metadata is returned only once, where `u < v`.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::new(3)
    ///     .add_edge_with_metadata((0, 1), 10)
    ///     .add_edge_with_metadata((1, 2), 20);
    ///
    /// let mut edges_with_meta: Vec<((usize, usize), i32)> = graph.edges_with_metadata().collect();
    /// edges_with_meta.sort_by_key(|k| k.0);
    /// assert_eq!(edges_with_meta, vec![((0, 1), 10), ((1, 2), 20)]);
    /// ```
    pub fn edges_with_metadata(&self) -> impl Iterator<Item = (Edge, Metadata)> {
        self.adj_list
            .iter()
            .enumerate()
            .map(|(u, vs)| {
                vs.iter()
                    .map(move |(&v, metadata)| ((u, v), metadata.clone()))
            })
            .flatten()
            .filter(|((u, v), _)| u < v)
    }
}

impl Graph<()> {
    /// Generates a graph that forms a Hamiltonian cycle with `num_vertices` vertices.
    ///
    /// A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex.
    ///
    /// # Arguments
    ///
    /// * `num_vertices` - The number of vertices in the cycle.
    /// * `rng` - A mutable reference to a random number generator implementing `rand::Rng`.
    ///
    /// # Returns
    ///
    /// A `Graph<()>` instance representing a Hamiltonian cycle.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    /// use rand::rngs::StdRng;
    /// use rand::SeedableRng;
    ///
    /// let mut rng = StdRng::seed_from_u64(42);
    /// let graph = Graph::hamiltonian_cycle(5, &mut rng);
    /// assert_eq!(graph.num_vertices(), 5);
    /// assert_eq!(graph.edges().count(), 5);
    /// // Further checks could ensure it's a valid cycle.
    /// ```
    pub fn hamiltonian_cycle(num_vertices: usize, rng: &mut impl Rng) -> Self {
        if num_vertices <= 1 {
            return Self::new(num_vertices);
        }
        let mut vertices: Vec<_> = (0..num_vertices).collect();
        vertices.shuffle(rng);
        (0..num_vertices)
            .map(|i| (vertices[i], vertices[(i + 1) % num_vertices]))
            .fold(Self::new(num_vertices), |graph, edge| graph.add_edge(edge))
    }

    /// Generates a minimum spanning tree (MST) graph with `num_vertices` vertices
    /// using a randomized Prufer sequence approach.
    ///
    /// A minimum spanning tree connects all vertices with the minimum possible total
    /// edge weight. In this unweighted context, it's any tree spanning all vertices.
    ///
    /// # Arguments
    ///
    /// * `num_vertices` - The number of vertices in the tree.
    /// * `rng` - A mutable reference to a random number generator implementing `rand::Rng`.
    ///
    /// # Returns
    ///
    /// A `Graph<()>` instance representing a minimum spanning tree.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    /// use rand::rngs::StdRng;
    /// use rand::SeedableRng;
    ///
    /// let mut rng = StdRng::seed_from_u64(42);
    /// let graph = Graph::minimum_spanning_tree(5, &mut rng);
    /// assert_eq!(graph.num_vertices(), 5);
    /// assert_eq!(graph.edges().count(), 4); // A tree with N vertices has N-1 edges
    /// ```
    pub fn minimum_spanning_tree(num_vertices: usize, rng: &mut impl Rng) -> Self {
        if num_vertices <= 2 {
            return Self::full(num_vertices);
        }
        let prufer_seq = iter::repeat_with(|| rng.random_range(0..num_vertices))
            .take(num_vertices - 2)
            .collect_vec();
        let mut degrees = prufer_seq
            .iter()
            .fold(vec![0; num_vertices], |mut degrees, &node| {
                degrees[node] += 1;
                degrees
            });
        let mut leaves = degrees.iter().enumerate().filter(|(_, d)| **d == 0).fold(
            BinaryHeap::new(),
            |mut heap, (node, _)| {
                heap.push(node);
                heap
            },
        );
        let mut edges = Vec::new();
        for v in prufer_seq {
            let Some(u) = leaves.pop() else {
                continue;
            };
            edges.push((u, v));
            degrees[v] -= 1;
            if degrees[v] == 0 {
                leaves.push(v);
            }
        }
        let u = leaves.pop().unwrap();
        let v = leaves.pop().unwrap();
        edges.push((u, v));
        edges
            .into_iter()
            .fold(Self::new(num_vertices), |graph, edge| graph.add_edge(edge))
    }

    /// Generates a full (complete) graph with `num_vertices` vertices.
    ///
    /// In a complete graph, every distinct pair of vertices is connected by a unique edge.
    ///
    /// # Arguments
    ///
    /// * `num_vertices` - The number of vertices in the graph.
    ///
    /// # Returns
    ///
    /// A `Graph<()>` instance representing a complete graph.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::full(4);
    /// assert_eq!(graph.num_vertices(), 4);
    /// // A complete graph with N vertices has N*(N-1)/2 edges
    /// assert_eq!(graph.edges().count(), 6); // 4 * 3 / 2 = 6
    /// ```
    pub fn full(num_vertices: usize) -> Self {
        (0..num_vertices)
            .cartesian_product(0..num_vertices)
            .filter(|(u, v)| u < v)
            .fold(Self::new(num_vertices), |graph, edge| graph.add_edge(edge))
    }

    /// Generates a random graph using the Erdos-Renyi G(n, p) model.
    ///
    /// Each possible edge is included in the graph with probability `density`.
    ///
    /// # Arguments
    ///
    /// * `num_vertices` - The number of vertices in the graph.
    /// * `density` - The probability `p` (between 0.0 and 1.0) for each edge to exist.
    /// * `rng` - A mutable reference to a random number generator implementing `rand::Rng`.
    ///
    /// # Returns
    ///
    /// A `Graph<()>` instance representing a random graph.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    /// use rand::rngs::StdRng;
    /// use rand::SeedableRng;
    ///
    /// let mut rng = StdRng::seed_from_u64(42);
    /// let graph = Graph::random(10, 0.3, &mut rng);
    /// assert_eq!(graph.num_vertices(), 10);
    /// // Number of edges will vary based on random generation, but can be checked.
    /// println!("Random graph with 10 vertices and 0.3 density has {} edges.", graph.edges().count());
    /// ```
    pub fn random(num_vertices: usize, density: f64, rng: &mut impl Rng) -> Self {
        (0..num_vertices)
            .flat_map(|u| (u + 1..num_vertices).map(move |v| (u, v)))
            .filter(|_| rng.random_bool(density))
            .fold(Self::new(num_vertices), |graph, edge| graph.add_edge(edge))
    }

    /// Adds an undirected edge between vertices `u` and `v` without any metadata.
    ///
    /// This is a convenience method for `Graph<()>` instances.
    /// If an edge already exists, this method does nothing.
    /// Self-loops (edges from a vertex to itself) are not supported and will be ignored.
    ///
    /// # Arguments
    ///
    /// * `edge` - A tuple `(u, v)` representing the two vertices of the edge.
    ///
    /// # Returns
    ///
    /// The `Graph` instance, allowing for method chaining.
    ///
    /// # Panics
    ///
    /// Panics if `u` or `v` are out of bounds for the graph's number of vertices.
    ///
    /// # Examples
    ///
    /// ```
    /// use libgraph::Graph;
    ///
    /// let graph = Graph::new(3)
    ///     .add_edge((0, 1))
    ///     .add_edge((1, 2));
    ///
    /// assert!(graph.has_edge((0, 1)));
    /// assert!(graph.has_edge((1, 2)));
    /// assert!(!graph.has_edge((0, 2)));
    /// ```
    pub fn add_edge(mut self, (u, v): Edge) -> Self {
        if u != v {
            self.adj_list[u].insert(v, ());
            self.adj_list[v].insert(u, ());
        }
        self
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::rngs::StdRng; // For deterministic tests

    fn get_sorted_edges(graph: &Graph) -> Vec<Edge> {
        graph.edges().sorted().collect()
    }

    #[test]
    fn test_new() {
        let graph = Graph::new(0);
        assert_eq!(graph.adj_list.len(), 0);
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        let graph = Graph::new(3);
        assert_eq!(graph.adj_list.len(), 3);
        for i in 0..3 {
            assert!(graph.adj_list[i].is_empty());
        }
        assert_eq!(get_sorted_edges(&graph).len(), 0);
    }

    #[test]
    fn test_num_vertices() {
        let graph: Graph<()> = Graph::new(0);
        assert_eq!(graph.num_vertices(), 0);

        let graph: Graph<()> = Graph::new(1);
        assert_eq!(graph.num_vertices(), 1);

        let graph: Graph<()> = Graph::new(5);
        assert_eq!(graph.num_vertices(), 5);
    }

    #[test]
    fn test_add_edge() {
        let graph = Graph::new(3).add_edge((0, 1));
        assert!(graph.adj_list[0].contains_key(&1));
        assert!(graph.adj_list[1].contains_key(&0));
        assert_eq!(get_sorted_edges(&graph), vec![(0, 1)]);

        let graph = Graph::new(3).add_edge((0, 1)).add_edge((0, 2));
        assert!(graph.adj_list[0].contains_key(&2));
        assert!(graph.adj_list[2].contains_key(&0));
        assert_eq!(get_sorted_edges(&graph), vec![(0, 1), (0, 2)]);

        let graph = Graph::new(3)
            .add_edge((0, 1))
            .add_edge((0, 2))
            .add_edge((1, 2));
        assert!(graph.adj_list[1].contains_key(&2));
        assert!(graph.adj_list[2].contains_key(&1));
        assert_eq!(get_sorted_edges(&graph), vec![(0, 1), (0, 2), (1, 2)]);

        // Add existing edge (should not change anything)
        let graph = Graph::new(3)
            .add_edge((0, 1))
            .add_edge((0, 2))
            .add_edge((1, 2))
            .add_edge((0, 1));
        assert_eq!(get_sorted_edges(&graph), vec![(0, 1), (0, 2), (1, 2)]);

        // Self loop not supported.
        let graph = Graph::new(1).add_edge((0, 0));
        assert!(graph.adj_list[0].is_empty());
        assert_eq!(get_sorted_edges(&graph), vec![]);
    }

    #[test]
    fn test_has_edge() {
        let graph = Graph::new(4)
            .add_edge((0, 1))
            .add_edge((1, 2))
            .add_edge((2, 3));

        assert!(graph.has_edge((0, 1)));
        assert!(graph.has_edge((1, 0))); // Check reverse direction
        assert!(graph.has_edge((1, 2)));
        assert!(graph.has_edge((2, 1)));
        assert!(graph.has_edge((2, 3)));
        assert!(graph.has_edge((3, 2)));

        assert!(!graph.has_edge((0, 2)));
        assert!(!graph.has_edge((0, 3)));
        assert!(!graph.has_edge((1, 3)));
    }

    #[test]
    fn test_edges() {
        let graph = Graph::new(4)
            .add_edge((0, 1))
            .add_edge((1, 2))
            .add_edge((2, 3))
            .add_edge((0, 3));

        assert_eq!(
            get_sorted_edges(&graph),
            vec![(0, 1), (0, 3), (1, 2), (2, 3)]
        );
    }

    #[test]
    fn test_new_full_graph() {
        let graph = Graph::full(0);
        assert!(get_sorted_edges(&graph).is_empty());

        let graph = Graph::full(1);
        assert!(get_sorted_edges(&graph).is_empty());

        let graph = Graph::full(3);
        assert_eq!(get_sorted_edges(&graph), vec![(0, 1), (0, 2), (1, 2)]);

        let graph = Graph::full(4);
        assert_eq!(
            get_sorted_edges(&graph),
            vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
        );
    }

    #[test]
    fn test_new_hamiltonian_cycle() {
        let mut rng = StdRng::seed_from_u64(42); // Deterministic RNG for testing

        let graph = Graph::hamiltonian_cycle(0, &mut rng);
        assert_eq!(graph.adj_list.len(), 0);
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        let graph = Graph::hamiltonian_cycle(1, &mut rng);
        assert_eq!(graph.adj_list.len(), 1);
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        let graph = Graph::hamiltonian_cycle(2, &mut rng);
        assert_eq!(graph.adj_list.len(), 2);
        assert_eq!(get_sorted_edges(&graph).len(), 1); // One edge (v0, v1)
        for i in 0..2 {
            assert_eq!(
                graph.adj_list[i].len(),
                1,
                "Vertex {} in 2-cycle should have degree 1",
                i
            );
        }

        // Test case: 3 vertices (triangle)
        let graph = Graph::hamiltonian_cycle(3, &mut rng);
        assert_eq!(graph.adj_list.len(), 3);
        assert_eq!(get_sorted_edges(&graph).len(), 3); // 3 edges in a 3-cycle
        for i in 0..3 {
            assert_eq!(
                graph.adj_list[i].len(),
                2,
                "Vertex {} in 3-cycle should have degree 2",
                i
            );
        }

        // Test case: 5 vertices
        let graph = Graph::hamiltonian_cycle(5, &mut rng);
        assert_eq!(graph.adj_list.len(), 5);
        assert_eq!(get_sorted_edges(&graph).len(), 5); // 5 edges in a 5-cycle
        for i in 0..5 {
            assert_eq!(
                graph.adj_list[i].len(),
                2,
                "Vertex {} in 5-cycle should have degree 2",
                i
            );
        }
    }

    #[test]
    fn test_new_minimum_spanning_tree() {
        let mut rng = StdRng::seed_from_u64(42); // Deterministic RNG

        // Test case: 0 vertices
        let graph = Graph::minimum_spanning_tree(0, &mut rng);
        assert_eq!(graph.adj_list.len(), 0);
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        // Test case: 1 vertex (0 edges)
        let graph = Graph::minimum_spanning_tree(1, &mut rng);
        assert_eq!(graph.adj_list.len(), 1);
        assert!(graph.adj_list[0].is_empty());
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        // Test case: 2 vertices (1 edge)
        let graph = Graph::minimum_spanning_tree(2, &mut rng);
        assert_eq!(graph.adj_list.len(), 2);
        assert_eq!(get_sorted_edges(&graph).len(), 1); // N-1 edges
        let degrees: Vec<usize> = graph.adj_list.iter().map(|n| n.len()).collect();
        assert_eq!(degrees.iter().filter(|&&d| d == 1).count(), 2); // Both vertices have degree 1

        // Test case: 5 vertices (4 edges for a tree)
        let graph = Graph::minimum_spanning_tree(5, &mut rng);
        assert_eq!(graph.adj_list.len(), 5);
        assert_eq!(get_sorted_edges(&graph).len(), 4); // N-1 edges
        // Check degrees: A path graph (which this creates) on N>=2 vertices has 2 nodes of degree 1 (endpoints)
        // and N-2 nodes of degree 2 (internal).
        let degrees: Vec<usize> = graph.adj_list.iter().map(|n| n.len()).collect();
        assert_eq!(
            degrees.iter().filter(|&&d| d == 1).count(),
            2,
            "MST on 5 vertices (path) should have 2 degree-1 nodes"
        );
        assert_eq!(
            degrees.iter().filter(|&&d| d == 2).count(),
            3,
            "MST on 5 vertices (path) should have 3 degree-2 nodes"
        );
    }

    #[test]
    fn test_random_graph() {
        let mut rng = StdRng::seed_from_u64(42);

        // Test case: 0 vertices
        let graph = Graph::random(0, 1.0, &mut rng);
        assert_eq!(graph.num_vertices(), 0);
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        // Test case: 0.0 density (no edges)
        let graph = Graph::random(5, 0.0, &mut rng);
        assert_eq!(graph.num_vertices(), 5);
        assert_eq!(get_sorted_edges(&graph).len(), 0);

        // Test case: 1.0 density (full graph)
        let graph = Graph::random(4, 1.0, &mut rng);
        assert_eq!(graph.num_vertices(), 4);
        assert_eq!(get_sorted_edges(&graph).len(), 6);
        assert_eq!(
            get_sorted_edges(&graph),
            vec![(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
        );

        // Test case: 0.5 density (should have some edges)
        let graph = Graph::random(10, 0.5, &mut rng);
        assert_eq!(graph.num_vertices(), 10);
        assert_eq!(get_sorted_edges(&graph).len(), 23);
    }

    #[test]
    fn test_add_edge_with_metadata() {
        let graph = Graph::new(3).add_edge_with_metadata((0, 1), 10);
        assert_eq!(graph.adj_list[0].get(&1), Some(&10));
        assert_eq!(graph.adj_list[1].get(&0), Some(&10));

        let mut edges = graph.edges_with_metadata().collect::<Vec<_>>();
        edges.sort_by_key(|k| k.0);
        assert_eq!(edges, vec![((0, 1), 10)]);

        let graph = graph.add_edge_with_metadata((0, 2), 20);
        assert_eq!(graph.adj_list[0].get(&2), Some(&20));
        assert_eq!(graph.adj_list[2].get(&0), Some(&20));

        let mut edges = graph.edges_with_metadata().collect::<Vec<_>>();
        edges.sort_by_key(|k| k.0);
        assert_eq!(edges, vec![((0, 1), 10), ((0, 2), 20)]);

        // Test updating metadata
        let graph = graph.add_edge_with_metadata((0, 1), 100);
        assert_eq!(graph.adj_list[0].get(&1), Some(&100));
        assert_eq!(graph.adj_list[1].get(&0), Some(&100));

        let mut edges = graph.edges_with_metadata().collect::<Vec<_>>();
        edges.sort_by_key(|k| k.0);
        assert_eq!(edges, vec![((0, 1), 100), ((0, 2), 20)]);

        // Self loop not supported.
        let graph = Graph::new(1).add_edge_with_metadata((0, 0), 5);
        assert!(graph.adj_list[0].is_empty());
        assert!(graph.edges_with_metadata().next().is_none());
    }

    #[test]
    fn test_get_edge_metadata() {
        // Test with i32 metadata
        let graph_i32 = Graph::new(3)
            .add_edge_with_metadata((0, 1), 10)
            .add_edge_with_metadata((1, 2), 20);

        // Existing edge
        assert_eq!(graph_i32.get_edge_metadata((0, 1)), Some(&10));
        // Reverse direction of existing edge (should return metadata)
        assert_eq!(graph_i32.get_edge_metadata((1, 0)), Some(&10));
        // Another existing edge
        assert_eq!(graph_i32.get_edge_metadata((1, 2)), Some(&20));

        // Non-existent edge
        assert_eq!(graph_i32.get_edge_metadata((0, 2)), None);
        // Edge with out-of-bounds vertex
        assert_eq!(graph_i32.get_edge_metadata((0, 99)), None);
        assert_eq!(graph_i32.get_edge_metadata((99, 0)), None);

        // Test with unit metadata `()`
        let graph_unit = Graph::new(3).add_edge((0, 1)).add_edge((1, 2));

        // Existing edge
        assert_eq!(graph_unit.get_edge_metadata((0, 1)), Some(&()));
        assert_eq!(graph_unit.get_edge_metadata((1, 0)), Some(&()));
        // Non-existent edge
        assert_eq!(graph_unit.get_edge_metadata((0, 2)), None);

        // Test on an empty graph
        let empty_graph: Graph<i32> = Graph::new(0);
        assert_eq!(empty_graph.get_edge_metadata((0, 1)), None);

        // Test on a graph with vertices but no edges
        let no_edge_graph: Graph<i32> = Graph::new(1);
        assert_eq!(no_edge_graph.get_edge_metadata((0, 0)), None);
    }
}