くちもちとくらの重み付き最大マッチング実装日記 - priority queue 2の実装

http://kutimoti.hatenablog.com/entry/2018/11/14/194510

前回です

今回でわかったんですけど,日記なので前回の実装ミスったとか普通にあります

p.q.2 とは

p.q.2(priority queue 2)も重み付き最大マッチングで高速化に使われるものです.p.q.1を使って実装します.

p.q.2ではp.q.1とは違ってグループに要素が優先度付きで挿入されていきます.

それぞれのグループにはactivenonactiveの設定がされていて

p.q.2ではactiveなグループに含まれている要素の中で一番優先度の低いものを答えるクエリを捌きます

操作は以下です.

  1. [insert]要素iを優先度p_iでグループgに挿入する.
  2. [erase]要素iを削除する.
  3. [find]activeなグループに含まれている要素の中で優先度の一番小さい要素を見つける.
  4. [subtract_delta]activeなグループに挿入されているすべての要素の優先度をδだけ小さくする.
  5. [generate new group]新しいグループを作る
  6. [delete group]グループを削除する.
  7. [change active status]グループのactive状態を変更する.
  8. [split]要素iを含んでいるグループをi以下の要素のグループとiより大きいグループで分ける.

p.q.2 の実装方針

まず,グループを追加していくのは面倒臭いので,必要なグループの数をコンストラクタで指定させることにしました.

(5),(6)の削除の操作も処理が多くなるので,(5),(6)を併合してclear()としました.

  1. pqA[g]はグループgに属する要素を管理するp.q.1です.
  2. _isActive[g]はグループgがactiveかどうかをboolで持ったものです.
  3. pqBはそれぞれのactiveなグループからfindした値を入れたものです(つまりこれをfindすれば,p.q.2のfindが達成できます)
  4. delta_last[g]は操作1,2,7,8を行ったときのpqB::delta(論文中ではΔと表現されている)の値です.これを保持することで,操作4によるグループ間の値の変化をうまく処理することが出来ます.(処理しているのはeval_delta)
  5. group[i]は要素iが属しているグループです.
  6. erase_from_BでpqBからグループgの最小の優先度の要素を取り除き,insert_to_BでpqBにグループgの最小の優先度の要素を挿入します.これにより,active状態を変更したときの挙動や,グループにinsert,eraseしたときのpqBに対する処理が出来ます.

注意

この実装のために,前回のsplay_mqpq_1を変更しました.

splay_mq

mq_index()の返す型をKeyからPに変えました(p.q.2で最小の優先度を取得する必要があったため)

pq_1

それに伴ってfind()の返す型を::std::pair<priority_type,element_type>に変えました.

実装

pq_2

#include <vector>

class pq_2{
  using element_type = int;
  using priority_type = long long;
  using group_type = ::std::size_t;
  priority_type delta;

  const ::std::size_t N;
  const ::std::size_t G;

  ::std::vector<pq_1*> pqA;
  ::std::vector<bool> _isActive;
  ::std::vector<priority_type> delta_last;
  ::std::vector<group_type> group;
  pq_1 pqB;
  void eval_delta(group_type g){
    if(_isActive[g]){
      pqA[g]->delta = pqA[g]->delta + pqB.delta - delta_last[g];
    }
    delta_last[g] = pqB.delta;
  }
  void erase_from_B(group_type g){
    if(_isActive[g]){
      auto p = pqA[g]->find();
      if(p.second == -1) return;
      pqB.erase(p.second);
    }
  }
  void insert_to_B(group_type g){
    if(_isActive[g]){
      auto p = pqA[g]->find();
      if(p.second == -1) return;
      pqB.insert(p.second , p.first - pqA[g]->delta);
    }
  }
public:
  pq_2(::std::size_t ele_num , ::std::size_t group_num) : N(ele_num) , G(group_num){
    pqA.assign(G , nullptr);
    _isActive.assign(G , false);
    delta_last.assign(G , 0);
    group.assign(N , -1);
    for(int i = 0;i < G;i++){
      pqA[i] = new pq_1();
    }
  }
  ~pq_2(){
    for(auto & pqa : pqA){
      if(pqa) delete pqa , pqa = nullptr;
    }
  }
  // (1) insert an element i with priority pi to group g
  void insert(group_type g , element_type  i , priority_type pi){
    eval_delta(g);
    erase_from_B(g);
    pqA[g]->insert(i,pi);
    group[i] = g;
    insert_to_B(g);
  }
  // (2) delete an element i
  void erase(element_type i){
    pqA[group[i]]->erase(i);
    group_type g = group[i];
    erase_from_B(g);
    pqB.erase(i);
    group[i] = -1;
    insert_to_B(g);
  }
  // (3) find an active element with the minimal priority
  ::std::pair<priority_type,element_type> find(){
    return pqB.find();
  }
  // (4) decrease the priorityies of all the active elements by some real numbers delta
  void subtract_delta(priority_type d){
    pqB.subtract_delta(d);
  }
  // (5) and (6) delete a group g and generate a new empty group(nonactive)
  void clear(group_type g){
    erase_from_B(g);
    delete pqA[g] , pqA[g] = nullptr;
    pqA[g] = new pq_1();
    _isActive[g] = false;
    delta_last[g] = pqB.delta;
  }
  // (7.1) change the status of a group from nonactive to active
  void activate(group_type g){
    eval_delta(g);
    _isActive[g] = true;
    insert_to_B(g);
  }

  // (7.2) change the status of a group from active to nonactive
  void nonactivate(group_type g){
    eval_delta(g);
    erase_from_B(g);
    _isActive[g] = false;
  }

  // (8) split a group according to an element in it
  void split(element_type i , group_type save_to){
    group_type g = group[i];
    if(g == -1) return;
    eval_delta(g);
    auto p = pqA[g]->tree->split(i);
    delete pqA[g]->tree;
    pqA[g]->tree = p.first;
    pqA[save_to]->tree = p.second;
  }
};

次回

何もわかっていないので僕が論文を読んでからのお楽しみ