hpdg 0.1.0

//! Graph containers and random graph generators.
//!
//! This module covers both representation and construction. You can build graphs manually,
//! generate structured families such as trees or DAGs, inspect adjacency representations,
//! and merge or relabel existing graphs.
//!
//! # Example
//!
//! ```rust
//! use hpdg::graph::Graph;
//!
//! let graph = Graph::chain(5, None, false, None);
//! assert_eq!(graph.node_count(), 5);
//! assert_eq!(graph.edge_count(), 4);
//! ```
//!
//! ## Display-Oriented Output
//!
//! Many graph utilities in this module can be inspected directly as text:
//!
//! - [`crate::graph::Edge`] and [`crate::graph::Graph`] implement [`std::fmt::Display`].
//! - [`crate::graph::Graph::to_string`] and [`crate::graph::Graph::to_string_with`] produce edge-list text.
//! - [`crate::graph::Graph::to_adj_list_string`] produces adjacency-list text.
//! - [`crate::graph::GraphMatrix`] implements [`std::fmt::Display`] for matrix output.
//! - [`crate::graph::Merger::to_string`] renders merged graph views directly.

use rand::{
    Rng,
    distr::{Distribution, weighted::WeightedIndex},
    rng,
    rngs::ThreadRng,
    seq::SliceRandom,
};
use std::{
    collections::{HashMap, hash_map::Entry},
    fmt,
};

/// Graph edge with an optional integral weight.
///
/// # Example
///
/// ```rust
/// use hpdg::graph::Edge;
///
/// let plain = Edge::new(1, 2, None);
/// let weighted = Edge::new(2, 3, Some(7));
/// assert_eq!(plain.to_string(), "1 2");
/// assert_eq!(weighted.to_string(), "2 3 7");
/// ```
#[derive(Clone, Debug)]
pub struct Edge {
    u: usize,
    v: usize,
    w: i64,
    weighted: bool,
}

impl Edge {
    /// Create a weighted or unweighted edge.
    pub fn new(u: usize, v: usize, w: Option<i64>) -> Edge {
        if let Some(w) = w {
            Edge {
                u,
                v,
                w,
                weighted: true,
            }
        } else {
            Edge {
                u,
                v,
                w: 0,
                weighted: false,
            }
        }
    }

    /// Return `true` if this edge stores a weight.
    pub fn is_weighted(&self) -> bool {
        self.weighted
    }

    /// Return the edge weight if the edge is weighted.
    pub fn weight(&self) -> Option<i64> {
        if self.weighted { Some(self.w) } else { None }
    }

    /// Format the edge as `u v`.
    ///
    /// ```rust
    /// use hpdg::graph::Edge;
    ///
    /// let edge = Edge::new(1, 2, None);
    /// assert_eq!(edge.format_unweighted(), "1 2");
    /// ```
    pub fn format_unweighted(&self) -> String {
        format!("{} {}", self.u, self.v)
    }

    /// Format the edge as `u v w`.
    ///
    /// ```rust
    /// use hpdg::graph::Edge;
    ///
    /// let edge = Edge::new(1, 2, Some(9));
    /// assert_eq!(edge.format_weighted(), "1 2 9");
    /// ```
    pub fn format_weighted(&self) -> String {
        format!("{} {} {}", self.u, self.v, self.w)
    }

    /// Format the edge using weighted or unweighted output automatically.
    ///
    /// ```rust
    /// use hpdg::graph::Edge;
    ///
    /// assert_eq!(Edge::new(1, 2, None).format_default(), "1 2");
    /// assert_eq!(Edge::new(1, 2, Some(5)).format_default(), "1 2 5");
    /// ```
    pub fn format_default(&self) -> String {
        if self.weighted {
            self.format_weighted()
        } else {
            self.format_unweighted()
        }
    }
}

// impl Edge {
//     pub fn unweighted_edge(&self) -> String {
//         format!("{} {}", self.u, self.v)
//     }
// }

impl fmt::Display for Edge {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.format_default())
    }
}

impl From<Edge> for (usize, usize) {
    fn from(val: Edge) -> Self {
        (val.u, val.v)
    }
}

impl From<(usize, usize)> for Edge {
    fn from(value: (usize, usize)) -> Self {
        Edge {
            u: value.0,
            v: value.1,
            w: 0,
            weighted: false,
        }
    }
}

impl From<(usize, usize, i64)> for Edge {
    fn from(value: (usize, usize, i64)) -> Self {
        Edge {
            u: value.0,
            v: value.1,
            w: value.2,
            weighted: true,
        }
    }
}

impl From<(u64, u64)> for Edge {
    fn from(value: (u64, u64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: 0,
            weighted: false,
        }
    }
}

impl From<(u64, u64, i64)> for Edge {
    fn from(value: (u64, u64, i64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: value.2,
            weighted: true,
        }
    }
}

impl From<(u32, u32)> for Edge {
    fn from(value: (u32, u32)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: 0,
            weighted: false,
        }
    }
}

impl From<(u32, u32, i64)> for Edge {
    fn from(value: (u32, u32, i64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: value.2,
            weighted: true,
        }
    }
}

impl From<(isize, isize)> for Edge {
    fn from(value: (isize, isize)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: 0,
            weighted: false,
        }
    }
}

impl From<(isize, isize, i64)> for Edge {
    fn from(value: (isize, isize, i64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: value.2,
            weighted: true,
        }
    }
}

impl From<(i64, i64)> for Edge {
    fn from(value: (i64, i64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: 0,
            weighted: false,
        }
    }
}

impl From<(i64, i64, i64)> for Edge {
    fn from(value: (i64, i64, i64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: value.2,
            weighted: true,
        }
    }
}

impl From<(i32, i32)> for Edge {
    fn from(value: (i32, i32)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: 0,
            weighted: false,
        }
    }
}

impl From<(i32, i32, i64)> for Edge {
    fn from(value: (i32, i32, i64)) -> Self {
        Edge {
            u: value.0 as usize,
            v: value.1 as usize,
            w: value.2,
            weighted: true,
        }
    }
}

/// A switchable multigraph to perform edge-switch operations.
pub struct SwitchGraph {
    directed: bool,
    edges: HashMap<(usize, usize), usize>,
}

impl SwitchGraph {
    #[allow(private_bounds)]
    /// Build a switchable graph from an edge list.
    pub fn new<I, E>(edges: I, directed: bool) -> SwitchGraph
    where
        I: IntoIterator<Item = E>,
        E: Into<Edge>,
    {
        let mut graph = SwitchGraph {
            directed,
            edges: HashMap::new(),
        };

        for (u, v) in edges.into_iter().map(|e: E| Into::<Edge>::into(e).into()) {
            graph.insert(u, v);
        }

        graph
    }

    /// Insert an edge, mirroring it automatically for undirected graphs.
    pub fn insert(&mut self, u: usize, v: usize) {
        self.insert_single(u, v);

        if !self.directed && u != v {
            self.insert_single(v, u);
        }
    }

    /// Remove an edge, mirroring it automatically for undirected graphs.
    pub fn remove(&mut self, u: usize, v: usize) {
        self.remove_single(u, v);

        if !self.directed && u != v {
            self.remove_single(v, u);
        }
    }

    fn insert_single(&mut self, u: usize, v: usize) {
        *self.edges.entry((u, v)).or_insert(0) += 1;
    }

    fn remove_single(&mut self, u: usize, v: usize) {
        if let Entry::Occupied(mut entry) = self.edges.entry((u, v)) {
            *entry.get_mut() -= 1;
            if *entry.get() == 0 {
                entry.remove();
            }
        }
    }

    /// Perform a random edge switch if a valid switch can be found.
    pub fn switch(&mut self, self_loop: bool, repeated_edges: bool) -> bool {
        let normalized_edges: Vec<((usize, usize), usize)> = self.get_normalized_edges();

        if normalized_edges.len() < 2 {
            return false;
        }

        let weights: Vec<usize> = normalized_edges.iter().map(|(_, count)| *count).collect();
        let total_weight: usize = weights.iter().sum();

        if total_weight < 2 {
            return false;
        }

        let mut rng = rng();

        let first_index = WeightedIndex::new(&weights)
            .ok()
            .map(|dist| dist.sample(&mut rng))
            .unwrap_or(0);
        let &(mut e1, _) = &normalized_edges[first_index];

        let mut second_index = first_index;
        if normalized_edges.len() > 1 {
            for _ in 0..5 {
                second_index = WeightedIndex::new(&weights)
                    .ok()
                    .map(|dist| dist.sample(&mut rng))
                    .unwrap_or(first_index);
                if second_index != first_index {
                    break;
                }
            }
            if second_index == first_index {
                second_index = (first_index + 1) % normalized_edges.len();
            }
        }
        let &(mut e2, _) = &normalized_edges[second_index];

        if !self.directed {
            e1 = (e1.0.min(e1.1), e1.0.max(e1.1));
            e2 = (e2.0.min(e2.1), e2.0.max(e2.1));
        }

        let (x1, y1) = e1;
        let (x2, y2) = e2;

        if self_loop {
            if x1 == x2 || y1 == y2 {
                return false;
            }
        } else {
            let set1 = [x1, y1];
            let set2 = [x2, y2];
            if set1.iter().any(|v| set2.contains(v)) {
                return false;
            }
        }

        if !repeated_edges
            && (self.edges.contains_key(&(x1, y2)) || self.edges.contains_key(&(x2, y1)))
        {
            return false;
        }

        self.remove(x1, y1);
        self.insert(x1, y2);
        self.remove(x2, y2);
        self.insert(x2, y1);

        true
    }

    fn get_normalized_edges(&self) -> Vec<((usize, usize), usize)> {
        self.edges
            .iter()
            .map(|(&(u, v), &count)| {
                if self.directed {
                    ((u, v), count)
                } else {
                    ((u.min(v), u.max(v)), count)
                }
            })
            .collect()
    }

    /// Construct a directed multigraph from `(out_degree, in_degree)` pairs.
    pub fn from_directed_degree_sequence(
        degree_sequence: &[(usize, usize)],
        self_loop: bool,
        repeated_edges: bool,
    ) -> Result<Self, &'static str> {
        Self::validate_directed_degree_sequence(degree_sequence)?;

        if degree_sequence.is_empty() {
            return Ok(SwitchGraph::new(Vec::<(usize, usize)>::new(), true));
        }

        let mut vertices: Vec<(usize, usize, usize)> = degree_sequence
            .iter()
            .enumerate()
            .map(|(i, &(out, in_))| (out, in_, i))
            .collect();

        vertices.sort_by(|a, b| b.0.cmp(&a.0).then(b.1.cmp(&a.1)));

        let mut graph = SwitchGraph::new(Vec::<(usize, usize)>::new(), true);

        loop {
            let candidate = vertices.iter_mut().find(|(_, in_deg, _)| *in_deg > 0);

            let (_, in_deg, vto) = match candidate {
                Some(tuple) => tuple,
                None => break,
            };

            let in_deg_val = *in_deg;
            let vto_val = *vto;
            *in_deg = 0;

            let mut current_in_deg = in_deg_val;
            let mut j = 0;

            while current_in_deg > 0 && j < vertices.len() {
                let (out_deg, _, vfrom) = &mut vertices[j];

                if *out_deg == 0 {
                    j += 1;
                    continue;
                }

                if !self_loop && *vfrom == vto_val {
                    j += 1;
                    continue;
                }

                graph.insert(*vfrom, vto_val);
                *out_deg -= 1;
                current_in_deg -= 1;

                if !repeated_edges {
                    j += 1;
                }
            }

            if current_in_deg > 0 {
                return Err("Degree sequence is not graphical...");
            }

            vertices.sort_by(|a, b| b.0.cmp(&a.0).then(b.1.cmp(&a.1)));
        }

        Ok(graph)
    }

    /// Convenience wrapper for directed degree-sequence construction without
    /// self-loops or repeated edges.
    pub fn from_directed_degree_sequence_simple(
        degree_sequence: &[(usize, usize)],
    ) -> Result<Self, &'static str> {
        Self::from_directed_degree_sequence(degree_sequence, false, false)
    }

    /// Construct an undirected multigraph from degree counts.
    pub fn from_undirected_degree_sequence(
        degree_sequence: &[usize],
        self_loop: bool,
        repeated_edges: bool,
    ) -> Result<Self, &'static str> {
        Self::validate_undirected_degree_sequence(degree_sequence)?;

        if degree_sequence.is_empty() {
            return Ok(SwitchGraph::new(Vec::<(usize, usize)>::new(), false));
        }

        let mut vertices: Vec<(usize, usize)> = degree_sequence
            .iter()
            .enumerate()
            .map(|(i, &deg)| (deg, i))
            .collect();

        vertices.sort_by(|a, b| b.0.cmp(&a.0));

        let mut edges = Vec::new();

        while !vertices.is_empty() && vertices[0].0 > 0 {
            let (deg, v) = vertices[0];
            vertices[0].0 = 0;

            let mut current_deg = deg;
            let mut j = 1;

            if self_loop && current_deg > 1 {
                while current_deg > 1 {
                    edges.push((v, v));
                    current_deg -= 2;

                    if !repeated_edges {
                        break;
                    }
                }
            }

            while current_deg > 0 && j < vertices.len() {
                let (other_deg, other_v) = &mut vertices[j];

                if *other_deg == 0 {
                    j += 1;
                    continue;
                }

                edges.push((v, *other_v));
                current_deg -= 1;
                *other_deg -= 1;

                if !repeated_edges {
                    j += 1;
                }
            }

            if current_deg > 0 {
                return Err(
                    "Degree sequence is not graphical: unable to satisfy degree requirements",
                );
            }

            vertices.retain(|&(deg, _)| deg > 0);
            vertices.sort_by(|a, b| b.0.cmp(&a.0));
        }

        Ok(SwitchGraph::new(edges, false))
    }

    /// Validate a directed degree sequence before construction.
    pub fn validate_directed_degree_sequence(
        degree_sequence: &[(usize, usize)],
    ) -> Result<(), &'static str> {
        if degree_sequence
            .iter()
            .any(|&(out, in_)| out == 0 && in_ > 0)
        {
            return Err(
                "Degree sequence is not graphical: some vertices have zero out-degree but positive in-degree",
            );
        }

        if degree_sequence
            .iter()
            .any(|&(out, in_)| in_ == 0 && out > 0)
        {
            return Err(
                "Degree sequence is not graphical: some vertices have zero in-degree but positive out-degree",
            );
        }

        let total_out: usize = degree_sequence.iter().map(|&(out, _)| out).sum();
        let total_in: usize = degree_sequence.iter().map(|&(_, in_)| in_).sum();

        if total_out != total_in {
            return Err("Degree sequence is not graphical: total out-degree != total in-degree");
        }
        Ok(())
    }

    /// Validate an undirected degree sequence before construction.
    pub fn validate_undirected_degree_sequence(
        degree_sequence: &[usize],
    ) -> Result<(), &'static str> {
        let total_degree: usize = degree_sequence.iter().sum();
        if total_degree % 2 != 0 {
            return Err("Degree sequence is not graphical: total degree must be even");
        }
        Ok(())
    }

    /// Convenience wrapper for undirected degree-sequence construction without
    /// self-loops or repeated edges.
    pub fn from_undirected_degree_sequence_simple(
        degree_sequence: &[usize],
    ) -> Result<Self, &'static str> {
        Self::from_undirected_degree_sequence(degree_sequence, false, false)
    }

    /// Iterate over edges, repeating parallel edges according to multiplicity.
    pub fn iter_edges(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
        self.edges
            .iter()
            .flat_map(|(&(u, v), &count)| std::iter::repeat_n((u, v), count))
    }

    /// Iterate over unique edge endpoints, ignoring multiplicity.
    pub fn iter_edges_unique(&self) -> impl Iterator<Item = (usize, usize)> + '_ {
        self.edges.keys().cloned()
    }

    /// Count edges including multiplicity.
    pub fn edge_count(&self) -> usize {
        self.edges.values().sum()
    }

    /// Count unique endpoint pairs, ignoring multiplicity.
    pub fn edge_count_unique(&self) -> usize {
        self.edges.len()
    }
}

/// Adjacency-list graph container used by most graph APIs in the crate.
///
/// `Display` renders one visible edge per line using the default edge formatter.
///
/// ```rust
/// use hpdg::graph::Graph;
///
/// let graph = Graph::chain(3, None, false, None);
/// let rendered = format!("{}", graph);
/// let mut lines: Vec<_> = rendered.lines().collect();
/// lines.sort();
/// assert_eq!(lines, vec!["1 2", "2 3"]);
/// ```
pub struct Graph {
    directed: bool,
    edges: HashMap<usize, Vec<Edge>>,
}

/// Summary statistics for a [`Graph`].
#[derive(Debug, Clone)]
pub struct GraphStats {
    /// Number of nodes.
    pub node_count: usize,
    /// Number of edges as reported by [`Graph::edge_count`].
    pub edge_count: usize,
    /// Whether the graph is directed.
    pub directed: bool,
    /// Minimum out-degree (or stored degree for undirected graphs).
    pub min_degree: usize,
    /// Maximum out-degree (or stored degree for undirected graphs).
    pub max_degree: usize,
    /// Average out-degree (or stored degree for undirected graphs).
    pub avg_degree: f64,
}

/// Options shared by some graph-generation helpers.
#[derive(Debug, Clone)]
pub struct GraphGenOptions {
    /// Whether the generated graph is directed.
    pub directed: bool,
    /// Whether self-loops are allowed.
    pub self_loop: bool,
    /// Whether repeated edges are allowed.
    pub repeated_edges: bool,
}

impl Default for GraphGenOptions {
    fn default() -> Self {
        Self {
            directed: false,
            self_loop: false,
            repeated_edges: false,
        }
    }
}

/// Degree-sequence input accepted by [`Graph::from_degree_sequence`].
pub enum DegreeSequence<'a> {
    /// Directed degree sequence as `(out_degree, in_degree)` pairs.
    Directed(&'a [(usize, usize)]),
    /// Undirected degree sequence.
    Undirected(&'a [usize]),
}

impl Graph {
    /// Create a graph with nodes `1..=point_count`.
    pub fn new(point_count: usize, directed: bool) -> Graph {
        let mut graph = Graph {
            directed,
            edges: HashMap::new(),
        };

        for point in 1..=point_count {
            graph.edges.insert(point, Vec::new());
        }

        graph
    }

    /// Return whether the graph is directed.
    pub fn is_directed(&self) -> bool {
        self.directed
    }

    /// Create a graph from an explicit node set.
    pub fn with_nodes<I: IntoIterator<Item = usize>>(nodes: I, directed: bool) -> Graph {
        let mut graph = Graph {
            directed,
            edges: HashMap::new(),
        };
        for node in nodes {
            graph.edges.insert(node, Vec::new());
        }
        graph
    }

    /// Return the number of nodes in the graph.
    pub fn node_count(&self) -> usize {
        self.edges.len()
    }

    /// Check whether every edge endpoint appears in the node set.
    pub fn is_valid(&self) -> bool {
        let nodes: std::collections::HashSet<usize> = self.edges.keys().cloned().collect();
        for edge in self.iter_edges_all() {
            if !nodes.contains(&edge.u) || !nodes.contains(&edge.v) {
                return false;
            }
        }
        true
    }

    /// Compute basic summary statistics.
    pub fn stats(&self) -> GraphStats {
        let node_count = self.node_count();
        let edge_count = self.edge_count();
        let mut min_degree = usize::MAX;
        let mut max_degree = 0usize;
        let mut total_degree = 0usize;

        for (_node, edges) in &self.edges {
            let degree = edges.len();
            min_degree = min_degree.min(degree);
            max_degree = max_degree.max(degree);
            total_degree += degree;
        }

        if node_count == 0 {
            min_degree = 0;
        }

        let avg_degree = if node_count == 0 {
            0.0
        } else {
            total_degree as f64 / node_count as f64
        };

        GraphStats {
            node_count,
            edge_count,
            directed: self.directed,
            min_degree,
            max_degree,
            avg_degree,
        }
    }

    /// Export the graph as adjacency-list text.
    ///
    /// # Example
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::chain(3, None, false, None);
    /// assert_eq!(graph.to_adj_list_string(","), "1: 2\n2: 1,3\n3: 2");
    /// ```
    pub fn to_adj_list_string(&self, sep: &str) -> String {
        let mut nodes: Vec<usize> = self.edges.keys().cloned().collect();
        nodes.sort_unstable();
        let mut lines = Vec::with_capacity(nodes.len());

        for node in nodes {
            let mut items = Vec::new();
            if let Some(edges) = self.edges.get(&node) {
                for edge in edges {
                    if edge.weighted {
                        items.push(format!("{}:{}", edge.v, edge.w));
                    } else {
                        items.push(edge.v.to_string());
                    }
                }
            }
            lines.push(format!("{}: {}", node, items.join(sep)));
        }

        lines.join("\n")
    }

    /// Export the graph as an adjacency matrix together with sorted node labels.
    ///
    /// # Example
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::chain(3, None, false, None);
    /// let (nodes, matrix) = graph.to_matrix(0);
    /// assert_eq!(nodes, vec![1, 2, 3]);
    /// assert_eq!(matrix, vec![
    ///     vec![0, 1, 0],
    ///     vec![1, 0, 1],
    ///     vec![0, 1, 0],
    /// ]);
    /// ```
    pub fn to_matrix(&self, default: i64) -> (Vec<usize>, Vec<Vec<i64>>) {
        let mut nodes: Vec<usize> = self.edges.keys().cloned().collect();
        nodes.sort_unstable();
        let n = nodes.len();
        let mut index = HashMap::new();
        for (i, node) in nodes.iter().enumerate() {
            index.insert(*node, i);
        }

        let mut matrix = vec![vec![default; n]; n];
        for edge in self.iter_edges_all() {
            if let (Some(&i), Some(&j)) = (index.get(&edge.u), index.get(&edge.v)) {
                let value = if edge.weighted { edge.w } else { 1 };
                matrix[i][j] = value;
            }
        }

        (nodes, matrix)
    }
}

impl Graph {
    /// Iterate over visible edges, counting undirected edges only once.
    pub fn iter_edges(&self) -> impl Iterator<Item = &Edge> {
        self.edges
            .values()
            .flat_map(|v| v.iter())
            .filter(|e| e.v >= e.u || self.directed)
    }

    /// Iterate over every stored adjacency entry.
    pub fn iter_edges_all(&self) -> impl Iterator<Item = &Edge> {
        self.edges.values().flat_map(|v| v.iter())
    }

    /// Mutably iterate over visible edges, counting undirected edges only once.
    pub fn iter_edges_mut(&mut self) -> impl Iterator<Item = &mut Edge> {
        self.edges
            .values_mut()
            .flat_map(|v| v.iter_mut())
            .filter(|e| e.v >= e.u || self.directed)
    }

    /// Mutably iterate over every stored adjacency entry.
    pub fn iter_edges_all_mut(&mut self) -> impl Iterator<Item = &mut Edge> {
        self.edges.values_mut().flat_map(|v| v.iter_mut())
    }

    /// Count undirected edges once, or all edges for directed graphs.
    pub fn edge_count(&self) -> usize {
        self.iter_edges().count()
    }

    /// Count all stored adjacency-list edges.
    pub fn edge_count_all(&self) -> usize {
        self.iter_edges_all().count()
    }

    /// Insert a single adjacency entry without automatic mirroring.
    pub fn add_single_edge(&mut self, u: usize, v: usize, w: Option<i64>) {
        self.edges
            .entry(u)
            .and_modify(|g| g.push(Edge::new(u, v, w)))
            .or_insert(vec![Edge::new(u, v, w)]);
    }

    fn add_directed_edge(&mut self, u: usize, v: usize, w: Option<i64>) {
        self.add_single_edge(u, v, w);
    }

    fn add_undirected_edge(&mut self, u: usize, v: usize, w: Option<i64>) {
        self.add_single_edge(u, v, w);
        if u != v {
            self.add_single_edge(v, u, w);
        }
    }

    /// Insert an edge, mirroring it automatically for undirected graphs.
    pub fn add_edge(&mut self, u: usize, v: usize, w: Option<i64>) {
        if self.directed {
            self.add_directed_edge(u, v, w);
        } else {
            self.add_undirected_edge(u, v, w);
        }
    }

    /// Insert multiple edges from any iterator of edge-like items.
    pub fn add_edges<I, E>(&mut self, edges: I)
    where
        I: IntoIterator<Item = E>,
        E: Into<Edge>,
    {
        for edge in edges {
            let edge: Edge = edge.into();
            if edge.weighted {
                self.add_edge(edge.u, edge.v, Some(edge.w));
            } else {
                self.add_edge(edge.u, edge.v, None);
            }
        }
    }

    /// Insert an edge using a custom weight generator.
    pub fn add_edge_with_weight<F>(&mut self, u: usize, v: usize, mut weight_gen: F)
    where
        F: FnMut() -> i64,
    {
        let w = weight_gen();
        self.add_edge(u, v, Some(w));
    }

    /// Insert multiple edges using a custom weight generator.
    pub fn add_edges_with_weight<I, F>(&mut self, edges: I, mut weight_gen: F)
    where
        I: IntoIterator<Item = (usize, usize)>,
        F: FnMut() -> i64,
    {
        for (u, v) in edges {
            let w = weight_gen();
            self.add_edge(u, v, Some(w));
        }
    }

    /// Build a chain graph on `point_count` nodes.
    ///
    /// `weight_limit` provides an inclusive weight range when no custom generator is supplied.
    /// `directed` controls whether each edge is stored once or mirrored.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::chain(4, None, false, None);
    /// let rendered = graph.to_string(false, None, None);
    /// let mut lines: Vec<_> = rendered.lines().collect();
    /// lines.sort();
    /// assert_eq!(lines, vec!["1 2", "2 3", "3 4"]);
    /// ```
    pub fn chain(
        point_count: usize,
        weight_limit: Option<(i64, i64)>,
        directed: bool,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        let mut rng = rng();
        let is_unweighted = weight_limit.is_none();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) = weight_limit.unwrap();
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::new(point_count, directed);
        for i in 2..=point_count {
            let weight = if is_unweighted {
                None
            } else {
                Some(weight_gen(&mut rng))
            };
            graph.add_edge(i - 1, i, weight);
        }
        graph
    }

    /// Build a flower graph with node `1` as the center.
    ///
    /// For undirected graphs, node `1` is connected to every other node.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::flower(4, None, false, None);
    /// let rendered = graph.to_string(false, None, None);
    /// let mut lines: Vec<_> = rendered.lines().collect();
    /// lines.sort();
    /// assert_eq!(lines, vec!["1 2", "1 3", "1 4"]);
    /// ```
    pub fn flower(
        point_count: usize,
        weight_limit: Option<(i64, i64)>,
        directed: bool,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        let mut rng = rng();
        let is_unweighted = weight_limit.is_none();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) = weight_limit.unwrap();
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::new(point_count, directed);
        for i in 2..=point_count {
            let weight = if is_unweighted {
                None
            } else {
                Some(weight_gen(&mut rng))
            };
            graph.add_edge(1, i, weight);
        }
        graph
    }

    /// Render the graph as newline-separated edge text.
    ///
    /// - `shuffle`: if `true`, randomize labels and edge order before rendering.
    /// - `line_reserve`: capacity hint used only for internal preallocation.
    /// - `edge_display_function`: custom line formatter; if `None`, the default edge format is used.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::chain(3, None, false, None);
    /// let rendered = graph.to_string(false, None, None);
    /// let mut lines: Vec<_> = rendered.lines().collect();
    /// lines.sort();
    /// assert_eq!(lines, vec!["1 2", "2 3"]);
    /// ```
    pub fn to_string(
        &self,
        shuffle: bool,
        line_reserve: Option<usize>,
        edge_display_function: Option<Box<dyn Fn(&Edge) -> String>>,
    ) -> String {
        let mut rng = rng();
        let edge_display_function =
            edge_display_function.unwrap_or_else(|| Box::new(|e: &Edge| e.format_default()));
        let mut buf: Vec<String> = Vec::new();
        buf.reserve(self.edge_count() * line_reserve.unwrap_or(6));

        if shuffle {
            let mut new_node_id: Vec<usize> = (1..=self.edges.keys().count()).collect();
            new_node_id.shuffle(&mut rng);
            let mut edge_buf: Vec<Edge> = Vec::new();
            for edge in self.iter_edges() {
                edge_buf.push(Edge::new(
                    new_node_id[edge.u - 1],
                    new_node_id[edge.v - 1],
                    if edge.weighted { Some(edge.w) } else { None },
                ));
            }
            edge_buf.shuffle(&mut rng);
            // for edge in edge_buf {
            //     if !self.directed && rng.random_bool(0.5) {

            //     }
            // }
            edge_buf.iter_mut().for_each(|e| {
                if !self.directed && rng.random_bool(0.5) {
                    let tmpu = e.u;
                    let tmpv = e.v;
                    e.u = tmpv;
                    e.v = tmpu;
                }
            });
            for edge in &edge_buf {
                buf.push(edge_display_function(edge));
            }
        } else {
            for edge in self.iter_edges() {
                buf.push(edge_display_function(edge));
            }
        }
        buf.join("\n")
    }

    /// Render the graph with a custom edge formatter closure.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::chain(3, None, false, None);
    /// let rendered = graph.to_string_with(false, None, |e| format!("edge({})", e.format_default()));
    /// let mut lines: Vec<_> = rendered.lines().collect();
    /// lines.sort();
    /// assert_eq!(lines, vec!["edge(1 2)", "edge(2 3)"]);
    /// ```
    pub fn to_string_with<F>(
        &self,
        shuffle: bool,
        line_reserve: Option<usize>,
        edge_display_function: F,
    ) -> String
    where
        F: Fn(&Edge) -> String + 'static,
    {
        self.to_string(shuffle, line_reserve, Some(Box::new(edge_display_function)))
    }

    /// Shuffle the internal edge order of each adjacency list.
    pub fn shuffle_edges(&mut self) {
        let mut rng = rng();
        for edges in self.edges.values_mut() {
            edges.shuffle(&mut rng);
        }
    }

    /// Shuffle node labels while keeping graph structure intact.
    pub fn shuffle_labels(&self) -> Graph {
        let mut rng = rng();
        let nodes: Vec<usize> = self.edges.keys().cloned().collect();
        let mut new_nodes = nodes.clone();
        new_nodes.shuffle(&mut rng);

        let mapping: HashMap<usize, usize> = nodes
            .iter()
            .zip(new_nodes.iter())
            .map(|(&old, &new)| (old, new))
            .collect();

        let mut graph = Graph::with_nodes(new_nodes, self.directed);
        for edge in self.iter_edges_all() {
            let u = mapping[&edge.u];
            let v = mapping[&edge.v];
            let w = if edge.weighted { Some(edge.w) } else { None };
            graph.add_single_edge(u, v, w);
        }

        graph
    }

    /// Return an edge list where undirected edges are randomly oriented.
    pub fn edges_random_oriented(&self) -> Vec<Edge> {
        let mut rng = rng();
        let mut edges: Vec<Edge> = self.iter_edges().cloned().collect();
        if !self.directed {
            for edge in edges.iter_mut() {
                if rng.random_bool(0.5) {
                    let tmp = edge.u;
                    edge.u = edge.v;
                    edge.v = tmp;
                }
            }
        }
        edges
    }

    /// Rebuild the graph by remapping each node label through `f`.
    pub fn relabel<F>(&self, mut f: F) -> Graph
    where
        F: FnMut(usize) -> usize,
    {
        let mut nodes: std::collections::HashSet<usize> = std::collections::HashSet::new();
        for &node in self.edges.keys() {
            nodes.insert(f(node));
        }
        let mut graph = Graph::with_nodes(nodes.into_iter(), self.directed);
        for edge in self.iter_edges_all() {
            let u = f(edge.u);
            let v = f(edge.v);
            let weight = if edge.weighted { Some(edge.w) } else { None };
            graph.add_edge(u, v, weight);
        }
        graph
    }

    /// Shift every node label by `offset`.
    pub fn offset_labels(&self, offset: usize) -> Graph {
        self.relabel(|node| node + offset)
    }

    /// Extract the induced subgraph on the given node set.
    pub fn subgraph_by_nodes(&self, nodes: &std::collections::HashSet<usize>) -> Graph {
        let mut graph = Graph::with_nodes(nodes.iter().cloned(), self.directed);
        for edge in self.iter_edges_all() {
            if nodes.contains(&edge.u) && nodes.contains(&edge.v) {
                let weight = if edge.weighted { Some(edge.w) } else { None };
                graph.add_edge(edge.u, edge.v, weight);
            }
        }
        graph
    }

    /// Build a graph containing only edges accepted by `predicate`.
    pub fn filter_edges<F>(&self, mut predicate: F) -> Graph
    where
        F: FnMut(&Edge) -> bool,
    {
        let nodes: Vec<usize> = self.edges.keys().cloned().collect();
        let mut graph = Graph::with_nodes(nodes, self.directed);
        for edge in self.iter_edges_all() {
            if predicate(edge) {
                let weight = if edge.weighted { Some(edge.w) } else { None };
                graph.add_edge(edge.u, edge.v, weight);
            }
        }
        graph
    }

    /// Remove repeated edges while keeping one copy of each unique edge.
    pub fn dedup_edges(&mut self) {
        for edges in self.edges.values_mut() {
            let mut seen: std::collections::HashSet<(usize, usize, i64, bool)> =
                std::collections::HashSet::new();
            edges.retain(|edge| {
                let key = (edge.u, edge.v, edge.w, edge.weighted);
                if seen.contains(&key) {
                    false
                } else {
                    seen.insert(key);
                    true
                }
            });
        }
    }

    /// Normalize undirected graphs so every edge is stored with `u <= v`, then mirror again.
    pub fn normalize_undirected(&mut self) {
        if self.directed {
            return;
        }
        for edges in self.edges.values_mut() {
            for edge in edges.iter_mut() {
                if edge.u > edge.v {
                    let tmp = edge.u;
                    edge.u = edge.v;
                    edge.v = tmp;
                }
            }
        }
    }

    /// Create a weighted edge generator with uniform distribution.
    pub fn weight_uniform(min_weight: i64, max_weight: i64) -> impl FnMut(&mut ThreadRng) -> i64 {
        move |rng: &mut ThreadRng| rng.random_range(min_weight..=max_weight)
    }

    /// Create a weighted edge generator with exponentially biased weights.
    pub fn weight_exponential(
        min_weight: i64,
        max_weight: i64,
        lambda: f64,
    ) -> impl FnMut(&mut ThreadRng) -> i64 {
        let lambda = lambda.max(1e-6);
        move |rng: &mut ThreadRng| {
            let u: f64 = rng.random();
            let t = 1.0 - (1.0 - u).powf(lambda);
            let value = min_weight as f64 + t * (max_weight - min_weight) as f64;
            value.round() as i64
        }
    }
}

impl fmt::Display for Graph {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.to_string(false, None, None))
    }
}

// impl Graph {
//     fn tree(
//         point_count: usize,
//         chain: f64,
//         flower: f64,
//         weight_limit: (i64, i64),
//         directed: bool,
//         weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
//         father_gen: Option<Box<dyn FnMut(&mut ThreadRng, usize) -> usize>>
//     ) -> Graph {
//         todo!()
//     }
// }

impl Graph {
    /// Generate a random tree.
    ///
    /// The `chain` and `flower` parameters bias how many edges are reserved for a path-like
    /// prefix and a star-like prefix before the remaining nodes are attached randomly.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::tree(6, 0.3, 0.2, None, true, None, None);
    /// assert_eq!(graph.node_count(), 6);
    /// assert_eq!(graph.edge_count(), 5);
    /// ```
    pub fn tree(
        point_count: usize,
        chain: f64,
        flower: f64,
        weight_limit: Option<(i64, i64)>,
        directed: bool,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
        father_gen: Option<Box<dyn FnMut(&mut ThreadRng, usize) -> usize>>,
    ) -> Graph {
        assert!(
            (0.0..=1.0).contains(&chain) && (0.0..=1.0).contains(&flower),
            "chain and flower must be between 0.0 and 1.0"
        );
        assert!(
            chain + flower <= 1.0,
            "chain plus flower must be less than or equal to 1.0"
        );

        let mut rng = rng();
        let is_unweighted = weight_limit.is_none();
        let use_custom_weight_gen = weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) = weight_limit.unwrap();
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let default_father_gen = |rng: &mut ThreadRng, cur| {
            if cur <= 1 {
                1
            } else {
                rng.random_range(1..cur)
            }
        };
        let mut father_gen =
            father_gen.unwrap_or_else(|| Box::new(move |rng, cur| default_father_gen(rng, cur)));

        let total_edges = point_count.saturating_sub(1);
        let chain_count = ((total_edges as f64) * chain).round() as usize;
        let flower_count = ((total_edges as f64) * flower).round() as usize;

        let mut graph = Graph::new(point_count, directed);

        let chain_end = chain_count + 1;
        let flower_start = chain_end + 1;
        let flower_end = (flower_start + flower_count).min(point_count + 1);

        if !use_custom_weight_gen {
            let chain_graph = Graph::chain(chain_end, weight_limit, directed, None);
            graph.add_edges(chain_graph.iter_edges_all().cloned());

            if flower_count > 0 {
                let flower_graph = Graph::flower(flower_count + 1, weight_limit, directed, None);
                let offset = chain_end.saturating_sub(1);
                for edge in flower_graph.iter_edges_all() {
                    let mut u = edge.u;
                    let mut v = edge.v;
                    if u != 1 {
                        u += offset;
                    }
                    if v != 1 {
                        v += offset;
                    }
                    let weight = if edge.weighted { Some(edge.w) } else { None };
                    graph.add_edge(u, v, weight);
                }
            }
        } else {
            for i in 2..=chain_end {
                let weight = if is_unweighted {
                    None
                } else {
                    Some(weight_gen(&mut rng))
                };
                graph.add_edge(i - 1, i, weight);
            }

            for i in flower_start..flower_end {
                let weight = if is_unweighted {
                    None
                } else {
                    Some(weight_gen(&mut rng))
                };
                graph.add_edge(1, i, weight);
            }
        }

        let random_start = flower_end;
        for i in random_start..=point_count {
            if i == 1 {
                continue;
            }
            let father = father_gen(&mut rng, i);
            let weight = if is_unweighted {
                None
            } else {
                Some(weight_gen(&mut rng))
            };
            graph.add_edge(father, i, weight);
        }

        graph
    }

    /// Generate a binary tree on `point_count` nodes.
    ///
    /// The `left` and `right` parameters bias whether a new node is attached as a left child
    /// or right child when both choices are available.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::binary_tree(7, 0.5, 0.5, None, false, None);
    /// assert_eq!(graph.node_count(), 7);
    /// assert_eq!(graph.edge_count(), 6);
    /// ```
    pub fn binary_tree(
        point_count: usize,
        left: f64,
        right: f64,
        weight_limit: Option<(i64, i64)>,
        directed: bool,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            (0.0..=1.0).contains(&left) && (0.0..=1.0).contains(&right),
            "left and right must be between 0.0 and 1.0"
        );
        assert!(
            left + right <= 1.0,
            "left plus right must be less than or equal to 1.0"
        );

        let mut rng = rng();
        let is_unweighted = weight_limit.is_none();

        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) = weight_limit.unwrap();
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::new(point_count, directed);

        let mut can_left = vec![1];
        let mut can_right = vec![1];

        for node_id in 2..=point_count {
            let edge_pos: f64 = rng.random();

            let is_left = if edge_pos < left {
                true
            } else if edge_pos < left + right {
                false
            } else {
                let mid = left + right + (1.0 - left - right) / 2.0;
                edge_pos <= mid
            };

            let parent = if is_left {
                let idx = rng.random_range(0..can_left.len());
                can_left.swap_remove(idx)
            } else {
                let idx = rng.random_range(0..can_right.len());
                can_right.swap_remove(idx)
            };

            let weight = if is_unweighted {
                None
            } else {
                Some(weight_gen(&mut rng))
            };
            graph.add_edge(parent, node_id, weight);
            can_left.push(node_id);
            can_right.push(node_id);
        }

        graph
    }

    /// Generate a binary tree where left and right edges can use different weight policies.
    pub fn binary_tree_with_side_weights(
        point_count: usize,
        left: f64,
        right: f64,
        left_weight_limit: Option<(i64, i64)>,
        right_weight_limit: Option<(i64, i64)>,
        directed: bool,
        left_weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
        right_weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            (0.0..=1.0).contains(&left) && (0.0..=1.0).contains(&right),
            "left and right must be between 0.0 and 1.0"
        );
        assert!(
            left + right <= 1.0,
            "left plus right must be less than or equal to 1.0"
        );

        let mut rng = rng();
        let default_left_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) = left_weight_limit.unwrap();
            rng.random_range(min_weight..=max_weight)
        };
        let default_right_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) = right_weight_limit.unwrap();
            rng.random_range(min_weight..=max_weight)
        };
        let mut left_weight_gen = left_weight_gen.unwrap_or_else(|| Box::new(default_left_gen));
        let mut right_weight_gen = right_weight_gen.unwrap_or_else(|| Box::new(default_right_gen));

        let mut graph = Graph::new(point_count, directed);

        let mut can_left = vec![1];
        let mut can_right = vec![1];

        for node_id in 2..=point_count {
            let edge_pos: f64 = rng.random();

            let is_left = if edge_pos < left {
                true
            } else if edge_pos < left + right {
                false
            } else {
                let mid = left + right + (1.0 - left - right) / 2.0;
                edge_pos <= mid
            };

            let parent = if is_left {
                let idx = rng.random_range(0..can_left.len());
                can_left.swap_remove(idx)
            } else {
                let idx = rng.random_range(0..can_right.len());
                can_right.swap_remove(idx)
            };

            let weight = if is_left {
                left_weight_limit.map(|_| left_weight_gen(&mut rng))
            } else {
                right_weight_limit.map(|_| right_weight_gen(&mut rng))
            };
            graph.add_edge(parent, node_id, weight);
            can_left.push(node_id);
            can_right.push(node_id);
        }

        graph
    }

    /// Generate a binary tree with full control over edge weights based on `(parent, child)`.
    pub fn binary_tree_with_weight_gen<F>(
        point_count: usize,
        left: f64,
        right: f64,
        directed: bool,
        mut weight_gen: F,
    ) -> Graph
    where
        F: FnMut(&mut ThreadRng, usize, usize) -> i64,
    {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            (0.0..=1.0).contains(&left) && (0.0..=1.0).contains(&right),
            "left and right must be between 0.0 and 1.0"
        );
        assert!(
            left + right <= 1.0,
            "left plus right must be less than or equal to 1.0"
        );

        let mut rng = rng();
        let mut graph = Graph::new(point_count, directed);

        let mut can_left = vec![1];
        let mut can_right = vec![1];

        for node_id in 2..=point_count {
            let edge_pos: f64 = rng.random();

            let is_left = if edge_pos < left {
                true
            } else if edge_pos < left + right {
                false
            } else {
                let mid = left + right + (1.0 - left - right) / 2.0;
                edge_pos <= mid
            };

            let parent = if is_left {
                let idx = rng.random_range(0..can_left.len());
                can_left.swap_remove(idx)
            } else {
                let idx = rng.random_range(0..can_right.len());
                can_right.swap_remove(idx)
            };

            let weight = weight_gen(&mut rng, parent, node_id);
            graph.add_edge(parent, node_id, Some(weight));
            can_left.push(node_id);
            can_right.push(node_id);
        }

        graph
    }

    /// Generate a random graph with the requested edge count.
    ///
    /// Set `self_loop` and `repeated_edges` to control whether loops and parallel edges are
    /// allowed. Weighted graphs can be produced either by `weight_limit` or `weight_gen`.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::graph(5, 4, false, false, false, None, None);
    /// assert_eq!(graph.node_count(), 5);
    /// assert_eq!(graph.edge_count(), 4);
    /// ```
    pub fn graph(
        point_count: usize,
        edge_count: usize,
        directed: bool,
        self_loop: bool,
        repeated_edges: bool,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        Graph::validate_graph_params(point_count, edge_count, directed, self_loop, repeated_edges);
        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::new(point_count, directed);
        let mut used: std::collections::HashSet<(usize, usize)> =
            std::collections::HashSet::with_capacity(edge_count.saturating_mul(2));
        let mut count = 0usize;

        while count < edge_count {
            let mut u = rng.random_range(1..=point_count);
            let mut v = rng.random_range(1..=point_count);
            if !self_loop && u == v {
                continue;
            }

            let key = if directed {
                (u, v)
            } else {
                if u > v {
                    std::mem::swap(&mut u, &mut v);
                }
                (u, v)
            };

            if !repeated_edges && used.contains(&key) {
                continue;
            }

            let weight = if use_weight {
                Some(weight_gen(&mut rng))
            } else {
                None
            };
            graph.add_edge(u, v, weight);
            used.insert(key);
            count += 1;
        }

        graph
    }

    /// Generate a random graph using explicit generation options.
    pub fn graph_with_options(
        point_count: usize,
        edge_count: usize,
        options: GraphGenOptions,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        Graph::graph(
            point_count,
            edge_count,
            options.directed,
            options.self_loop,
            options.repeated_edges,
            weight_limit,
            weight_gen,
        )
    }

    /// Convenience wrapper for weighted random graph generation with a fixed weight range.
    pub fn graph_with_weight_limit(
        point_count: usize,
        edge_count: usize,
        options: GraphGenOptions,
        weight_limit: (i64, i64),
    ) -> Graph {
        Graph::graph_with_options(point_count, edge_count, options, Some(weight_limit), None)
    }

    /// Generate a simple graph without repeated edges.
    pub fn simple_graph(point_count: usize, edge_count: usize, directed: bool) -> Graph {
        Graph::graph(point_count, edge_count, directed, false, false, None, None)
    }

    /// Generate a graph that may contain repeated edges.
    pub fn multigraph(
        point_count: usize,
        edge_count: usize,
        directed: bool,
        self_loop: bool,
    ) -> Graph {
        Graph::graph(
            point_count,
            edge_count,
            directed,
            self_loop,
            true,
            None,
            None,
        )
    }

    /// Generate a complete graph.
    pub fn complete_graph(
        point_count: usize,
        directed: bool,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::new(point_count, directed);
        for u in 1..=point_count {
            let start = if directed { 1 } else { u + 1 };
            for v in start..=point_count {
                if u == v {
                    continue;
                }
                let weight = if use_weight {
                    Some(weight_gen(&mut rng))
                } else {
                    None
                };
                graph.add_edge(u, v, weight);
            }
        }
        graph
    }

    /// Generate a complete bipartite graph.
    pub fn complete_bipartite(
        left_count: usize,
        right_count: usize,
        directed: bool,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(
            left_count > 0 && right_count > 0,
            "partition sizes must be above zero"
        );
        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let total = left_count + right_count;
        let mut graph = Graph::new(total, directed);
        let left_nodes: Vec<usize> = (1..=left_count).collect();
        let right_nodes: Vec<usize> = ((left_count + 1)..=total).collect();

        for &u in &left_nodes {
            for &v in &right_nodes {
                let weight = if use_weight {
                    Some(weight_gen(&mut rng))
                } else {
                    None
                };
                graph.add_edge(u, v, weight);
            }
        }

        if directed {
            for &u in &right_nodes {
                for &v in &left_nodes {
                    let weight = if use_weight {
                        Some(weight_gen(&mut rng))
                    } else {
                        None
                    };
                    graph.add_edge(u, v, weight);
                }
            }
        }

        graph
    }

    /// Generate an approximate `k`-regular graph by random stub pairing.
    ///
    /// For directed graphs this samples `k` outgoing edges per node; for undirected graphs
    /// this pairs shuffled stubs and may be only approximate when invalid pairs are skipped.
    pub fn k_regular_approx(
        point_count: usize,
        k: usize,
        directed: bool,
        self_loop: bool,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        let mut rng = rng();
        let mut graph = Graph::new(point_count, directed);

        if directed {
            for u in 1..=point_count {
                for _ in 0..k {
                    let v = rng.random_range(1..=point_count);
                    if !self_loop && u == v {
                        continue;
                    }
                    graph.add_edge(u, v, None);
                }
            }
            return graph;
        }

        let mut stubs = Vec::with_capacity(point_count.saturating_mul(k));
        for u in 1..=point_count {
            for _ in 0..k {
                stubs.push(u);
            }
        }
        stubs.shuffle(&mut rng);

        for pair in stubs.chunks(2) {
            if pair.len() < 2 {
                break;
            }
            let u = pair[0];
            let v = pair[1];
            if !self_loop && u == v {
                continue;
            }
            graph.add_edge(u, v, None);
        }

        graph
    }

    /// Generate a random DAG.
    ///
    /// Edges are oriented from smaller labels to larger labels so the result is acyclic.
    pub fn dag(
        point_count: usize,
        edge_count: usize,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        Self::dag_with_options(point_count, edge_count, false, weight_limit, weight_gen)
    }

    /// Generate a random DAG using explicit generation options.
    pub fn dag_with_options(
        point_count: usize,
        edge_count: usize,
        self_loop: bool,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(!self_loop, "DAG does not allow self loops");
        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::new(point_count, true);
        let mut used: std::collections::HashSet<(usize, usize)> = std::collections::HashSet::new();
        let mut count = 0usize;

        while count < edge_count {
            let u = rng.random_range(1..=point_count);
            let v = rng.random_range(1..=point_count);
            if u == v {
                continue;
            }
            let (from, to) = if u < v { (u, v) } else { (v, u) };
            if used.contains(&(from, to)) {
                continue;
            }
            let weight = if use_weight {
                Some(weight_gen(&mut rng))
            } else {
                None
            };
            graph.add_edge(from, to, weight);
            used.insert((from, to));
            count += 1;
        }

        graph
    }

    /// Generate an undirected acyclic graph by filtering a DAG construction order.
    pub fn udag(
        point_count: usize,
        edge_count: usize,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            edge_count <= point_count.saturating_sub(1),
            "edge_count must be <= point_count - 1 for UDAG"
        );
        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut parent: Vec<usize> = (0..=point_count).collect();
        fn find(parent: &mut [usize], x: usize) -> usize {
            if parent[x] != x {
                parent[x] = find(parent, parent[x]);
            }
            parent[x]
        }
        fn union(parent: &mut [usize], a: usize, b: usize) {
            let ra = find(parent, a);
            let rb = find(parent, b);
            if ra != rb {
                parent[rb] = ra;
            }
        }

        let mut graph = Graph::new(point_count, false);
        let mut count = 0usize;
        while count < edge_count {
            let u = rng.random_range(1..=point_count);
            let v = rng.random_range(1..=point_count);
            if u == v {
                continue;
            }
            let ru = find(&mut parent, u);
            let rv = find(&mut parent, v);
            if ru == rv {
                continue;
            }
            let weight = if use_weight {
                Some(weight_gen(&mut rng))
            } else {
                None
            };
            graph.add_edge(u, v, weight);
            union(&mut parent, u, v);
            count += 1;
        }

        graph
    }

    /// Generate a connected graph.
    ///
    /// This starts from a random tree and then adds random extra edges until `edge_count`
    /// visible edges are present.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::connected(6, 7, false, None, None);
    /// assert_eq!(graph.node_count(), 6);
    /// assert_eq!(graph.edge_count(), 7);
    /// ```
    pub fn connected(
        point_count: usize,
        edge_count: usize,
        directed: bool,
        weight_limit: Option<(i64, i64)>,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            edge_count >= point_count.saturating_sub(1),
            "edge_count must be >= point_count - 1 for connected graph"
        );

        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut graph = Graph::tree(point_count, 0.0, 0.0, weight_limit, directed, None, None);
        let mut used: std::collections::HashSet<(usize, usize)> = std::collections::HashSet::new();
        for edge in graph.iter_edges() {
            let mut u = edge.u;
            let mut v = edge.v;
            if !directed && u > v {
                std::mem::swap(&mut u, &mut v);
            }
            used.insert((u, v));
        }

        let mut count = graph.edge_count();
        while count < edge_count {
            let mut u = rng.random_range(1..=point_count);
            let mut v = rng.random_range(1..=point_count);
            if u == v {
                continue;
            }
            let key = if directed {
                (u, v)
            } else {
                if u > v {
                    std::mem::swap(&mut u, &mut v);
                }
                (u, v)
            };
            if used.contains(&key) {
                continue;
            }
            let weight = if use_weight {
                Some(weight_gen(&mut rng))
            } else {
                None
            };
            graph.add_edge(u, v, weight);
            used.insert(key);
            count += 1;
        }

        graph
    }

    /// Add edges until the graph becomes connected.
    pub fn ensure_connected(&mut self) {
        let mut parent: HashMap<usize, usize> = self.edges.keys().map(|&k| (k, k)).collect();

        fn find(parent: &mut HashMap<usize, usize>, x: usize) -> usize {
            let p = *parent.get(&x).unwrap();
            if p != x {
                let root = find(parent, p);
                parent.insert(x, root);
            }
            *parent.get(&x).unwrap()
        }

        fn union(parent: &mut HashMap<usize, usize>, a: usize, b: usize) {
            let ra = find(parent, a);
            let rb = find(parent, b);
            if ra != rb {
                parent.insert(rb, ra);
            }
        }

        for edge in self.iter_edges() {
            union(&mut parent, edge.u, edge.v);
        }

        let mut components: HashMap<usize, Vec<usize>> = HashMap::new();
        for &node in self.edges.keys() {
            let root = find(&mut parent, node);
            components.entry(root).or_default().push(node);
        }

        let mut reps: Vec<usize> = components.values().map(|v| v[0]).collect();
        if reps.len() <= 1 {
            return;
        }
        let mut rng = rng();
        reps.shuffle(&mut rng);
        for pair in reps.windows(2) {
            let u = pair[0];
            let v = pair[1];
            self.add_edge(u, v, None);
        }
    }

    /// Add edges to heuristically increase connectivity to at least `k`.
    pub fn make_k_connected(&mut self, k: usize) {
        if k == 0 {
            return;
        }
        self.ensure_connected();
        if k == 1 {
            return;
        }
        let mut rng = rng();
        let nodes: Vec<usize> = self.edges.keys().cloned().collect();
        for _ in 0..(k - 1) * nodes.len().saturating_sub(1) {
            if nodes.len() < 2 {
                break;
            }
            let u = nodes[rng.random_range(0..nodes.len())];
            let v = nodes[rng.random_range(0..nodes.len())];
            if u == v {
                continue;
            }
            self.add_edge(u, v, None);
        }
    }

    /// Generate a forest.
    ///
    /// The result contains exactly `tree_count` connected components.
    ///
    /// ```rust
    /// use hpdg::graph::Graph;
    ///
    /// let graph = Graph::forest(6, 2, None, false, None);
    /// assert_eq!(graph.node_count(), 6);
    /// assert_eq!(graph.edge_count(), 4);
    /// ```
    pub fn forest(
        point_count: usize,
        tree_count: usize,
        weight_limit: Option<(i64, i64)>,
        directed: bool,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            tree_count >= 1 && tree_count <= point_count,
            "invalid tree_count"
        );

        let mut rng = rng();
        let use_weight = weight_limit.is_some() || weight_gen.is_some();
        let default_weight_gen = |rng: &mut ThreadRng| {
            let (min_weight, max_weight) =
                weight_limit.expect("weight_limit required for default generator");
            rng.random_range(min_weight..=max_weight)
        };
        let mut weight_gen = weight_gen.unwrap_or_else(|| Box::new(default_weight_gen));

        let mut parent: Vec<usize> = (0..=point_count).collect();
        fn find(parent: &mut [usize], x: usize) -> usize {
            if parent[x] != x {
                parent[x] = find(parent, parent[x]);
            }
            parent[x]
        }
        fn union(parent: &mut [usize], a: usize, b: usize) {
            let ra = find(parent, a);
            let rb = find(parent, b);
            if ra != rb {
                parent[rb] = ra;
            }
        }

        let mut graph = Graph::new(point_count, directed);
        let mut components = point_count;
        while components > tree_count {
            let u = rng.random_range(1..=point_count);
            let v = rng.random_range(1..=point_count);
            if u == v {
                continue;
            }
            let ru = find(&mut parent, u);
            let rv = find(&mut parent, v);
            if ru == rv {
                continue;
            }
            let weight = if use_weight {
                Some(weight_gen(&mut rng))
            } else {
                None
            };
            graph.add_edge(u, v, weight);
            union(&mut parent, u, v);
            components -= 1;
        }

        graph
    }

    /// Generate a forest and then duplicate randomly chosen edges `repeat_times` times.
    pub fn forest_with_repeats(
        point_count: usize,
        tree_count: usize,
        weight_limit: Option<(i64, i64)>,
        directed: bool,
        weight_gen: Option<Box<dyn FnMut(&mut ThreadRng) -> i64>>,
        repeat_times: usize,
    ) -> Graph {
        let mut graph = Graph::forest(point_count, tree_count, weight_limit, directed, weight_gen);
        if repeat_times == 0 {
            return graph;
        }

        let mut rng = rng();
        let edges: Vec<Edge> = graph.iter_edges().cloned().collect();
        if edges.is_empty() {
            return graph;
        }

        for _ in 0..repeat_times {
            let edge = edges[rng.random_range(0..edges.len())].clone();
            let weight = if edge.weighted { Some(edge.w) } else { None };
            graph.add_edge(edge.u, edge.v, weight);
        }

        graph
    }

    /// Graph-level wrapper around [`SwitchGraph::from_directed_degree_sequence`].
    pub fn from_directed_degree_sequence(
        degree_sequence: &[(usize, usize)],
        self_loop: bool,
        repeated_edges: bool,
    ) -> Result<Graph, &'static str> {
        let switch =
            SwitchGraph::from_directed_degree_sequence(degree_sequence, self_loop, repeated_edges)?;
        let mut graph = Graph::new(degree_sequence.len(), true);
        for (u, v) in switch.iter_edges() {
            graph.add_edge(u, v, None);
        }
        Ok(graph)
    }

    /// Graph-level wrapper around [`SwitchGraph::from_undirected_degree_sequence`].
    pub fn from_undirected_degree_sequence(
        degree_sequence: &[usize],
        self_loop: bool,
        repeated_edges: bool,
    ) -> Result<Graph, &'static str> {
        let switch = SwitchGraph::from_undirected_degree_sequence(
            degree_sequence,
            self_loop,
            repeated_edges,
        )?;
        let mut graph = Graph::new(degree_sequence.len(), false);
        for (u, v) in switch.iter_edges() {
            graph.add_edge(u, v, None);
        }
        Ok(graph)
    }

    /// Build a graph from a degree sequence.
    pub fn from_degree_sequence(
        degree_sequence: DegreeSequence<'_>,
        self_loop: bool,
        repeated_edges: bool,
    ) -> Result<Graph, &'static str> {
        match degree_sequence {
            DegreeSequence::Directed(seq) => {
                Graph::from_directed_degree_sequence(seq, self_loop, repeated_edges)
            }
            DegreeSequence::Undirected(seq) => {
                Graph::from_undirected_degree_sequence(seq, self_loop, repeated_edges)
            }
        }
    }

    /// Return an upper bound on the number of edges for the given graph type.
    pub fn max_edge_count(point_count: usize, directed: bool, self_loop: bool) -> usize {
        if directed {
            if self_loop {
                point_count * point_count
            } else {
                point_count.saturating_mul(point_count.saturating_sub(1))
            }
        } else if self_loop {
            point_count.saturating_mul(point_count.saturating_add(1)) / 2
        } else {
            point_count.saturating_mul(point_count.saturating_sub(1)) / 2
        }
    }

    /// Validate generic graph-generation parameters before sampling edges.
    pub fn validate_graph_params(
        point_count: usize,
        edge_count: usize,
        directed: bool,
        self_loop: bool,
        repeated_edges: bool,
    ) {
        if !repeated_edges {
            let max_edges = Graph::max_edge_count(point_count, directed, self_loop);
            assert!(
                edge_count <= max_edges,
                "edge_count exceeds max possible edges for this configuration"
            );
        }
    }

    /// Estimate the binomial coefficient `C(n, k)` in floating-point form.
    pub fn estimate_comb(n: usize, k: usize) -> f64 {
        if k > n {
            return 0.0;
        }
        if k == 0 || k == n {
            return 1.0;
        }
        let k = k.min(n - k);
        let mut res = 1.0f64;
        for i in 1..=k {
            res *= (n + 1 - i) as f64 / i as f64;
        }
        res
    }

    /// Estimate the maximum possible edge count for the given graph type.
    pub fn estimate_upperbound(point_count: usize, directed: bool, self_loop: bool) -> f64 {
        Graph::max_edge_count(point_count, directed, self_loop) as f64
    }

    /// Generate a graph layout commonly used to stress SPFA-like algorithms.
    pub fn hack_spfa(point_count: usize, weight_limit: Option<(i64, i64)>) -> Graph {
        assert!(point_count > 1, "point_count must be above one");
        let mut graph = Graph::new(point_count, true);
        let (min_w, max_w) = weight_limit.unwrap_or((-1, 1));

        for i in 1..point_count {
            let forward_w = 0.clamp(min_w, max_w);
            let backward_w = (-1).clamp(min_w, max_w);
            graph.add_edge(i, i + 1, Some(forward_w));
            graph.add_edge(i + 1, i, Some(backward_w));
        }

        graph
    }

    /// Generate a configurable SPFA-stressing graph with extra shortcut edges.
    pub fn hack_spfa_with_options(
        point_count: usize,
        forward_weight: i64,
        backward_weight: i64,
        extra_edges: usize,
    ) -> Graph {
        assert!(point_count > 1, "point_count must be above one");
        let mut rng = rng();
        let mut graph = Graph::new(point_count, true);

        for i in 1..point_count {
            graph.add_edge(i, i + 1, Some(forward_weight));
            graph.add_edge(i + 1, i, Some(backward_weight));
        }

        for _ in 0..extra_edges {
            let v = rng.random_range(2..=point_count);
            graph.add_edge(1, v, Some(forward_weight));
        }

        graph
    }
}

/// Dense adjacency-matrix helper.
///
/// `Display` renders rows separated by newlines and cells separated by spaces.
///
/// ```rust
/// use hpdg::graph::GraphMatrix;
///
/// let mut matrix = GraphMatrix::new(2, 0);
/// matrix.set(0, 1, 7);
/// matrix.set(1, 0, 9);
/// assert_eq!(format!("{}", matrix), "0 7\n9 0");
/// ```
pub struct GraphMatrix<T> {
    matrix: Vec<Vec<T>>,
    default: T,
}

impl<T: Clone> GraphMatrix<T> {
    /// Create an `n x n` matrix filled with `default`.
    pub fn new(n: usize, default: T) -> Self {
        let matrix = vec![vec![default.clone(); n]; n];
        Self { matrix, default }
    }

    /// Return the matrix dimension.
    pub fn size(&self) -> usize {
        self.matrix.len()
    }

    /// Return the configured default value.
    pub fn default_value(&self) -> &T {
        &self.default
    }

    /// Borrow a matrix cell by `(row, column)`.
    pub fn get(&self, u: usize, v: usize) -> &T {
        &self.matrix[u][v]
    }

    /// Overwrite a matrix cell by `(row, column)`.
    pub fn set(&mut self, u: usize, v: usize, value: T) {
        self.matrix[u][v] = value;
    }

    /// Iterate over matrix rows.
    pub fn iter(&self) -> impl Iterator<Item = &[T]> {
        self.matrix.iter().map(|row| row.as_slice())
    }

    /// Mutably iterate over matrix rows.
    pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut [T]> {
        self.matrix.iter_mut().map(|row| row.as_mut_slice())
    }
}

impl<T> std::ops::Index<(usize, usize)> for GraphMatrix<T> {
    type Output = T;

    fn index(&self, index: (usize, usize)) -> &Self::Output {
        &self.matrix[index.0][index.1]
    }
}

impl<T> std::ops::IndexMut<(usize, usize)> for GraphMatrix<T> {
    fn index_mut(&mut self, index: (usize, usize)) -> &mut Self::Output {
        &mut self.matrix[index.0][index.1]
    }
}

/// Merge multiple graphs into one graph view.
///
/// This is useful when several generators independently build components that should later
/// be combined into one printable graph.
pub struct Merger {
    directed: bool,
    graphs: Vec<Graph>,
}

impl Merger {
    /// Create a merger from existing graph components.
    pub fn new<I: IntoIterator<Item = Graph>>(graphs: I, directed: bool) -> Self {
        Self {
            directed,
            graphs: graphs.into_iter().collect(),
        }
    }

    /// Add a one-edge component to the merger.
    pub fn add_edge(&mut self, u: usize, v: usize, w: Option<i64>) {
        let mut graph = Graph::new(u.max(v), self.directed);
        graph.add_edge(u, v, w);
        self.graphs.push(graph);
    }

    /// Render the merged graph as edge text.
    ///
    /// ```rust
    /// use hpdg::graph::{Graph, Merger};
    ///
    /// let a = Graph::chain(2, None, false, None);
    /// let b = Graph::chain(3, None, false, None).offset_labels(1);
    /// let merger = Merger::new([a, b], false);
    /// assert!(merger.to_string().contains("1 2"));
    /// ```
    pub fn to_string(&self) -> String {
        self.to_graph().to_string(false, None, None)
    }

    /// Materialize the merged graph.
    pub fn to_graph(&self) -> Graph {
        let mut max_node = 0usize;
        for graph in &self.graphs {
            max_node = max_node.max(graph.node_count());
        }
        let mut merged = Graph::new(max_node, self.directed);
        for graph in &self.graphs {
            for edge in graph.iter_edges_all() {
                let weight = if edge.weighted { Some(edge.w) } else { None };
                merged.add_edge(edge.u, edge.v, weight);
            }
        }
        merged
    }

    /// Generate a graph with a requested number of connected components.
    pub fn component(
        point_count: usize,
        edge_count: usize,
        component_count: usize,
        directed: bool,
    ) -> Graph {
        assert!(point_count > 0, "point_count must be above zero");
        assert!(
            component_count >= 1 && component_count <= point_count,
            "invalid component_count"
        );
        assert!(
            edge_count >= point_count - component_count,
            "edge_count too small for requested components"
        );

        let mut sizes = vec![point_count / component_count; component_count];
        for i in 0..(point_count % component_count) {
            sizes[i] += 1;
        }

        let base_edges = point_count - component_count;
        let mut extra_edges = edge_count - base_edges;
        let mut graphs = Vec::new();

        for size in sizes {
            let extra = if extra_edges == 0 { 0 } else { 1 };
            if extra_edges > 0 {
                extra_edges -= 1;
            }
            let edges_for_component = size.saturating_sub(1) + extra;
            let graph = Graph::connected(size, edges_for_component, directed, None, None);
            graphs.push(graph);
        }

        let mut merged = Graph::new(point_count, directed);
        let mut offset = 0usize;
        for graph in graphs {
            for edge in graph.iter_edges_all() {
                let weight = if edge.weighted { Some(edge.w) } else { None };
                merged.add_edge(edge.u + offset, edge.v + offset, weight);
            }
            offset += graph.node_count();
        }

        merged
    }
}

impl<T: std::fmt::Display> std::fmt::Display for GraphMatrix<T> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for (i, row) in self.matrix.iter().enumerate() {
            for (j, item) in row.iter().enumerate() {
                if j > 0 {
                    write!(f, " ")?;
                }
                write!(f, "{}", item)?;
            }
            if i + 1 < self.matrix.len() {
                writeln!(f)?;
            }
        }
        Ok(())
    }
}