DEV Community

Cover image for [#1]create a graph(based on adjacent matrix) and implement an DFS iterator
starevan
starevan

Posted on

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

🦀crustacean
my github: star_evan

intro:

The branch of computer science known as data structures uses graphs to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from one page to another. A similar approach can be taken to problems in social media, travel, biology, computer chip design, mapping the progression of neuro-degenerative diseases, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science. The transformation of graphs is often formalized and represented by graph rewrite systems. Complementary to graph transformation systems focusing on rule-based in-memory manipulation of graphs are graph databases geared towards transaction-safe, persistent storing and querying of graph-structured data.

now let's create a GRAPH in rust !

🦀target:

#[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}")
    }

}
Enter fullscreen mode Exit fullscreen mode

😀target output:


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}
总权值和:32
1
4
6
3
5
2

Enter fullscreen mode Exit fullscreen mode

1. initialize graph:


1. create a new project

 cargo new rust-graph                     
Enter fullscreen mode Exit fullscreen mode

2. declare graph struct

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

3. new method

write a constructor for Graph

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

4. add node

one is add node without value, another is add node with value.(because the value can be None)

    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);
    }
Enter fullscreen mode Exit fullscreen mode

5. fix length

We want this adjacency matrix to change in size as nodes are added

    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
        }
    }
Enter fullscreen mode Exit fullscreen mode

6. add edge

 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);
    }
Enter fullscreen mode Exit fullscreen mode

7. output weight summation

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

8. access maximum index of all the nodes

This method is very useful, we will use it later.

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

9. pretty print

  1. write a method which returns string for print.
  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("\n");
        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("\n");
        }
        paint
    }

  pub fn debug_edge_list(&self) -> String {
      format!("{:?}", self.edge_list)
  }
Enter fullscreen mode Exit fullscreen mode
  1. print method:
  pub fn print(&self) {
        println!("{}", self.debug());
        println!("{}", self.debug_edge_list());
        println!("总权值和:{}", self.get_sum_weight());
    }
Enter fullscreen mode Exit fullscreen mode

10. delete node, edge

  1. remove node:
    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));
            }
        }
    }
Enter fullscreen mode Exit fullscreen mode
  1. remove edge:
   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)
    }
Enter fullscreen mode Exit fullscreen mode

11. is empty?



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

2. implement DFS iterator:

1. declare an iterator for graph:

We need to create a stack for store temp values.

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

2. impl into iter method:

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],
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

3. impl next for the custom iterator:

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
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

3. test:


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}
总权值和:32
1
4
6
3
5
2
Enter fullscreen mode Exit fullscreen mode

Top comments (0)