🦀ракообразные
мой гитхаб: star_evan


вступление:

Раздел информатики, известный как структуры данных, использует графы для представления сетей связи, организации данных, вычислительных устройств, потока вычислений и т. д. Например, ссылочная структура веб-сайта может быть представлена ​​ориентированным графом, в котором вершины представляют собой веб-страницы, а направленные ребра представляют собой ссылки с одной страницы на другую. Аналогичный подход можно применить к проблемам в социальных сетях, путешествиях, биологии, разработке компьютерных чипов, картировании прогрессирования нейродегенеративных заболеваний и многих других областях. Поэтому разработка алгоритмов для обработки графов представляет большой интерес для информатики. Преобразование графов часто формализуется и представляется системами перезаписи графов. Дополнением к системам преобразования графов, ориентированным на манипулирование графами в памяти на основе правил, являются базы данных графов, ориентированные на безопасное для транзакций, постоянное хранение и запросы структурированных графом данных.


Теперь давайте создадим ГРАФИК в rust!


🦀цель:

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

Войти в полноэкранный режим

Выйти из полноэкранного режима


1. инициализировать граф:



1. создать новый проект

 cargo new rust-graph                     
Войти в полноэкранный режим

Выйти из полноэкранного режима


2. объявить структуру графа

pub struct Graph<T> {
    pub matrix: Vec<Vec<Option<usize>>>,
    pub edge_list: BTreeMap<Edge, Weight>,
    pub nodes: BTreeMap<usize, Option<T>>,
}
Войти в полноэкранный режим

Выйти из полноэкранного режима


3. новый метод

написать конструктор для Graph

   pub fn new() -> Self {
        Self {
            matrix: vec![],
            nodes: BTreeMap::new(),
            edge_list: BTreeMap::new(),
        }
    }
Войти в полноэкранный режим

Выйти из полноэкранного режима


4. добавить узел

один добавляет узел без значения, другой добавляет узел со значением (поскольку значение может быть Никто)

    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. исправить длину

Мы хотим, чтобы эта матрица смежности изменялась в размере по мере добавления узлов.

    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. добавить край

 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. суммирование выходных весов

    pub fn get_sum_weight(&self) -> usize {
        let sum: usize = self.edge_list.iter().map(|(_, &x)| x).sum();
        sum
    }
Войти в полноэкранный режим

Выйти из полноэкранного режима


8. доступ к максимальному индексу всех узлов

Этот метод очень полезен, мы воспользуемся им позже.

    pub fn bound(&self) -> usize {
        match self.nodes.iter().max() {
            Some((&e, _)) => e,
            None => 0,
        }
    }
Войти в полноэкранный режим

Выйти из полноэкранного режима


9. красивый принт

  1. напишите метод, который возвращает строку для печати.
  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)
  }
Войти в полноэкранный режим

Выйти из полноэкранного режима

  1. метод печати:
  pub fn print(&self) {
        println!("{}", self.debug());
        println!("{}", self.debug_edge_list());
        println!("总权值和:{}", self.get_sum_weight());
    }
Войти в полноэкранный режим

Выйти из полноэкранного режима


10. удалить узел, ребро

  1. удалить узел:
    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));
            }
        }
    }
Войти в полноэкранный режим

Выйти из полноэкранного режима

  1. удалить край:
   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. пусто?



    pub fn is_empty(&self) -> bool {
        self.nodes.len() == 0
    }
Войти в полноэкранный режим

Выйти из полноэкранного режима



2. реализовать итератор DFS:


1. объявить итератор для графа:

Нам нужно создать стек для хранения временных значений.

pub struct DFSIterator<'a, T: Ord + Debug> {
    pub graph: &'a Graph<T>,
    pub stk: Vec<usize>,
    pub visited: Vec<bool>,
}
Войти в полноэкранный режим

Выйти из полноэкранного режима


2. внедрить в метод iter:

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 для пользовательского итератора:

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. тест:


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
Войти в полноэкранный режим

Выйти из полноэкранного режима