Union-Find 구현이 상위 태그를 업데이트하지 않습니다.

Question

일부 세트를 만들고이 세트 중 일부를 병합하여 동일한 태그 (usize)를 갖도록하려고합니다. 내가지도를 초기화하면, 나는 문자열을 추가하기 시작 :

self.clusters.make_set("a"); 
self.clusters.make_set("b"); 

내가 self.clusters.find("a")과 self.clusters.find("b")가 서로 다른 값이 반환 호출 할 때, 나는 아직 세트를 병합되지 않았기 때문에 괜찮있다. 그럼 나도 같은 가치를, 두 세트

let _ = self.clusters.union("a", "b"); 

지금 self.clusters.find("a") 및 self.clusters.find("b")를 호출하는 경우

을 병합하려면 다음 메서드를 호출합니다. 그러나 finalize() 메서드를 호출하고지도를 반복 할 때 세트를 병합하지 않은 것처럼 원래 태그가 반환됩니다.

self.clusters.finalize(); 

for (address, tag) in &self.clusters.map { 
    self.clusterizer_writer.write_all(format!("{};{}\n", address, 
    self.clusters.parent[*tag]).as_bytes()).unwrap(); 
} 

// to output all keys with the same tag as a list. 
let a: Vec<(usize, Vec<String>)> = { 
    let mut x = HashMap::new(); 
    for (k, v) in self.clusters.map.clone() { 
     x.entry(v).or_insert_with(Vec::new).push(k) 
    } 
    x.into_iter().collect() 
}; 

왜 그런지 알 수는 없지만 나는 녹이기가 비교적 쉽다. 어쩌면 포인터 문제일까요?

"a"와 "b"대신 실제로 utils::arr_to_hex(&input.outpoint.txid)String과 같은 것을 사용하고 있습니다. 내가 사용하고 그

이것은의 녹 구현 알고리즘을 연합-찾기 :

/// Tarjan's Union-Find data structure. 
#[derive(RustcDecodable, RustcEncodable)] 
pub struct DisjointSet<T: Clone + Hash + Eq> { 
    set_size: usize, 
    parent: Vec<usize>, 
    rank: Vec<usize>, 
    map: HashMap<T, usize>, // Each T entry is mapped onto a usize tag. 
} 

impl<T> DisjointSet<T> 
where 
    T: Clone + Hash + Eq, 
{ 
    pub fn new() -> Self { 
     const CAPACITY: usize = 1000000; 
     DisjointSet { 
      set_size: 0, 
      parent: Vec::with_capacity(CAPACITY), 
      rank: Vec::with_capacity(CAPACITY), 
      map: HashMap::with_capacity(CAPACITY), 
     } 
    } 

    pub fn make_set(&mut self, x: T) { 
     if self.map.contains_key(&x) { 
      return; 
     } 

     let len = &mut self.set_size; 
     self.map.insert(x, *len); 
     self.parent.push(*len); 
     self.rank.push(0); 

     *len += 1; 
    } 

    /// Returns Some(num), num is the tag of subset in which x is. 
    /// If x is not in the data structure, it returns None. 
    pub fn find(&mut self, x: T) -> Option<usize> { 
     let pos: usize; 
     match self.map.get(&x) { 
      Some(p) => { 
       pos = *p; 
      } 
      None => return None, 
     } 

     let ret = DisjointSet::<T>::find_internal(&mut self.parent, pos); 
     Some(ret) 
    } 

    /// Implements path compression. 
    fn find_internal(p: &mut Vec<usize>, n: usize) -> usize { 
     if p[n] != n { 
      let parent = p[n]; 
      p[n] = DisjointSet::<T>::find_internal(p, parent); 
      p[n] 
     } else { 
      n 
     } 
    } 

    /// Union the subsets to which x and y belong. 
    /// If it returns Ok<u32>, it is the tag for unified subset. 
    /// If it returns Err(), at least one of x and y is not in the disjoint-set. 
    pub fn union(&mut self, x: T, y: T) -> Result<usize,()> { 
     let x_root; 
     let y_root; 
     let x_rank; 
     let y_rank; 
     match self.find(x) { 
      Some(x_r) => { 
       x_root = x_r; 
       x_rank = self.rank[x_root]; 
      } 
      None => { 
       return Err(()); 
      } 
     } 

     match self.find(y) { 
      Some(y_r) => { 
       y_root = y_r; 
       y_rank = self.rank[y_root]; 
      } 
      None => { 
       return Err(()); 
      } 
     } 

     // Implements union-by-rank optimization. 
     if x_root == y_root { 
      return Ok(x_root); 
     } 

     if x_rank > y_rank { 
      self.parent[y_root] = x_root; 
      return Ok(x_root); 
     } else { 
      self.parent[x_root] = y_root; 
      if x_rank == y_rank { 
       self.rank[y_root] += 1; 
      } 
      return Ok(y_root); 
     } 
    } 

    /// Forces all laziness, updating every tag. 
    pub fn finalize(&mut self) { 
     for i in 0..self.set_size { 
      DisjointSet::<T>::find_internal(&mut self.parent, i); 
     } 
    } 
} 

Answer 1

나는 당신이 당신의 DisjointSet가 제대로 구조체에서 정보를 추출하지 않을 생각합니다.

나는 이것으로 sniped을 얻었고 통합 검색을 구현했습니다. 첫째, 기본 usize를 실현하는 것이로 : 더 일반적인 유형의 래퍼와 그 다음

pub struct UnionFinderImpl { 
    parent: Vec<usize>, 
} 

:

pub struct UnionFinder<T: Hash> { 
    rev: Vec<Rc<T>>, 
    fwd: HashMap<Rc<T>, usize>, 
    uf: UnionFinderImpl, 
} 

두 구조체는 그룹의 Vec<Vec<>>을 반환하는 groups() 방법을 구현한다. Rc을 사용했기 때문에 Clone이 필요하지 않습니다. 내가 볼 수없는

Playground