Union-Find実装で親タグが更新されない

Question

私はStringのいくつかのセットを作成し、これらのセットの一部を（usizeの）同じタグを持つようにマージしようとしています。私はマップを初期化したら、私は、文字列の追加を開始：

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

私はself.clusters.find("a")とself.clusters.find("b")は、異なる値が返される呼び出すと、私はまだセットがマージされていないので罰金です。それから私は私が今self.clusters.find("a")とself.clusters.find("b")を呼び出す場合、私は同じ値を取得する2組の

let _ = self.clusters.union("a", "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() 
}; 

私はこれがなぜそのようなのか理解できませんが、私はRustに比較的新しいです。多分ポインターの問題？

"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のimplementionで：より一般的な型のラッパーとその後

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