[1]create a graph(based on adjacent matrix) and implement an DFS iterator

#[test]fn debug() {    let mut g: Graph<usize> = Graph::new();    g.add_edge(1, 3, 1);    g.add_edge(1, 4, 2);    g.add_edge(4, 6, 2);    g.add_edge(2, 5, 2);    g.add_edge(2, 4, 3);    g.add_edge(3, 4, 3);    g.add_edge(1, 2, 6);    g.add_edge(4, 5, 6);    g.add_edge(3, 6, 7);    g.print();    // we can use for because we implemented iterator for our graph!!    for e in g.dfs_iter() {        println!("{e}")    }}

running 1 test * 1  2  3  4  5  6  1|.  6  1  2  .  .   2|6  .  .  3  2  .   3|1  .  .  3  .  7   4|2  3  3  .  6  2   5|.  2  .  6  .  .   6|.  .  7  2  .  .  {(1, 2): 6, (1, 3): 1, (1, 4): 2, (2, 4): 3, (2, 5): 2, (3, 4): 3, (3, 6): 7, (4, 5): 6, (4, 6): 2}:32146352

 cargo new rust-graph                     

pub struct Graph<T> {    pub matrix: Vec<Vec<Option<usize>>>,    pub edge_list: BTreeMap<Edge, Weight>,    pub nodes: BTreeMap<usize, Option<T>>,}

   pub fn new() -> Self {        Self {            matrix: vec![],            nodes: BTreeMap::new(),            edge_list: BTreeMap::new(),        }    }

    pub fn add_node(&mut self, index: usize) {        self.nodes.insert(index, None);        self.fix_length(index);    }    pub fn add_node_with_value(&mut self, index: usize, value: T) {        self.nodes.insert(index, Some(value));        self.fix_length(index);    }

    pub fn fix_length(&mut self, index: usize) -> bool {        if self.matrix.len() > index {            false        } else {            // this enlargement algorithm can be changed on your own.             let target_len = (index as f32 * 1.3) as usize + 2;            while self.matrix.len() < target_len {                self.matrix.push(vec![]);            }            for i in 0..target_len {                while self.matrix[i].len() < target_len {                    self.matrix[i].push(None)                }            }            true        }    }

 pub fn add_edge(&mut self, from: usize, to: usize, weight: usize) {    // make edge_list .0 less than .1    // update edge_list,matrix and nodes        if from > to {            self.edge_list.insert((to, from), weight);        } else {            self.edge_list.insert((from, to), weight);        }        if !self.nodes.contains_key(&from) {            self.add_node(from);        }        if !self.nodes.contains_key(&to) {            self.add_node(to);        }        self.matrix[from][to] = Some(weight);        self.matrix[to][from] = Some(weight);    }

    pub fn get_sum_weight(&self) -> usize {        let sum: usize = self.edge_list.iter().map(|(_, &x)| x).sum();        sum    }

    pub fn bound(&self) -> usize {        match self.nodes.iter().max() {            Some((&e, _)) => e,            None => 0,        }    }

  pub fn debug(&self) -> String {        let bound = self.bound();        let mut paint = " *".to_string();        (1..=bound).for_each(|x| paint.push_str(&format!("{:2} ", x)));        paint.push_str("
");        for i in 1..=bound {            paint.push_str(&format!("{:2}|", i));            for j in 1..=bound {                paint.push_str(&format!(                    "{:2} ",                    (match self.matrix[i][j] {                        Some(e) => format!("{}", e),                        None => String::from("."),                    })                ))            }            paint.push_str("
");        }        paint    }  pub fn debug_edge_list(&self) -> String {      format!("{:?}", self.edge_list)  }

  pub fn print(&self) {        println!("{}", self.debug());        println!("{}", self.debug_edge_list());        println!(":{}", self.get_sum_weight());    }

    pub fn rm_node(&mut self, index: usize) -> bool {        if !self.nodes.contains_key(&index) {            false        } else {            // when we remove node, we need to delete the edges connected to it.             self.remove_relative_edge(index);            self.nodes.remove(&index);            //update matrix.             self.matrix[index].fill(None);            for i in 1..=self.bound() {                self.matrix[i][index] = None;            }            true        }    }// remove_relative_edge    fn remove_relative_edge(&mut self, index: usize) {        //  3   (1,2) /* (2,3) (3,4) */ (2,4)        // BTreeMap        for e in self.neighbour(index) {            if e < index {                self.edge_list.remove(&(e, index));            } else {                self.edge_list.remove(&(index, e));            }        }    }

   pub fn rm_edge_single(&mut self, from: usize, to: usize) -> bool {        if from.max(to) > self.bound() {            false        } else {            self.matrix[from][to] = None;            true        }    }    pub fn rm_edge(&mut self, from: usize, to: usize) -> bool {        /*  */        if from > to {            self.edge_list.remove(&(to, from));        } else {            self.edge_list.remove(&(from, to));        }        self.rm_edge_single(from, to) && self.rm_edge_single(to, from)    }

    pub fn is_empty(&self) -> bool {        self.nodes.len() == 0    }

pub struct DFSIterator<'a, T: Ord + Debug> {    pub graph: &'a Graph<T>,    pub stk: Vec<usize>,    pub visited: Vec<bool>,}

impl<T: Debug + Ord> Graph<T> {    pub fn dfs_iter(&self) -> DFSIterator<T> {        let stk = match self.get_first() {            Some(e) => vec![e],            None => vec![],        };        DFSIterator {            graph: self,            stk,            visited: vec![false; self.bound() + 1],        }    }}

impl<'a, T: Ord + Debug> Iterator for BFSIterator<'a, T> {    type Item = usize;    fn next(&mut self) -> Option<Self::Item> {        if self.graph.is_empty() {            return None;        } else {            while !self.que.is_empty() {                let v = self.que.pop_front().unwrap();                if self.visited[v] {                    continue;                }                self.visited[v] = true;                for e in self.graph.neighbour(v) {                    if !self.visited[e] {                        self.que.push_back(e)                    }                }                return Some(v);            }            None        }    }}

running 1 test * 1  2  3  4  5  6  1|.  6  1  2  .  .   2|6  .  .  3  2  .   3|1  .  .  3  .  7   4|2  3  3  .  6  2   5|.  2  .  6  .  .   6|.  .  7  2  .  .  {(1, 2): 6, (1, 3): 1, (1, 4): 2, (2, 4): 3, (2, 5): 2, (3, 4): 3, (3, 6): 7, (4, 5): 6, (4, 6): 2}:32146352