starevan

Posted on Aug 28, 2022

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

#programming #rust #algorithms #beginners

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

}

😀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

1. initialize graph:

1. create a new project

 cargo new rust-graph

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

3. new method

write a constructor for Graph

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

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

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

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

7. output weight summation

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

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

9. pretty print

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

print method:

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

10. delete node, edge

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

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

11. is empty?



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

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

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

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

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

DEV Community