[#1]그래프 생성(인접 행렬 기반) 및 DFS 반복자 구현

내 github: star_evan

소개:

데이터 구조로 알려진 컴퓨터 과학의 한 분야는 그래프를 사용하여 통신 네트워크, 데이터 조직, 계산 장치, 계산 흐름 등을 나타냅니다. 예를 들어, 웹사이트의 링크 구조는 방향성 그래프로 나타낼 수 있습니다. 정점은 웹 페이지를 나타내고 방향이 있는 가장자리는 한 페이지에서 다른 페이지로의 링크를 나타냅니다. 소셜 미디어, 여행, 생물학, 컴퓨터 칩 설계, 신경 퇴행성 질환의 진행 매핑 및 기타 여러 분야의 문제에 대해서도 유사한 접근 방식을 취할 수 있습니다. 따라서 그래프를 처리하는 알고리즘의 개발은 컴퓨터 과학의 주요 관심사입니다. 그래프의 변환은 종종 그래프 재작성 시스템으로 공식화되고 표현됩니다. 그래프의 규칙 기반 메모리 내 조작에 중점을 둔 그래프 변환 시스템을 보완하는 것은 그래프 구조 데이터의 트랜잭션 안전, 영구 저장 및 쿼리에 맞춰진 그래프 데이터베이스입니다.

이제 Rust에서 GRAPH를 만들어 봅시다!

🦀대상:

#[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. 새로운 방법

write a constructor for Graph

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

4. 노드 추가

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. 고정 길이

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. 가장자리 추가

 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. 모든 노드의 최대 색인에 액세스

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. 예쁜 프린트

인쇄할 문자열을 반환하는 메서드를 작성합니다.

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

인쇄 방법:

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

10. 노드, 에지 삭제

노드 제거:

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

11. 비어 있습니까?

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

2. DFS 반복자를 구현합니다.

1. 그래프에 대한 반복자를 선언합니다.

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