search:

boost::disjoint_sets 사용방법

26 Aug 2014

다음과 같은 골치 아픈 문제가 있었는데 boost::disjoint_sets를 쓰니 한방에 해결이 된다.

Disjoint Set이란

한국말로 하면 ‘교집합이 없는 집합’으로 해석할 수 있다. 이런 자료구조 설명에 약하니 위키 문서를 참고하세요.

boost::disjoint_sets 사용방법

역시 Stackoverflow에서 사용 방법을 찾을 수 있었다. 애석하게도 우리 같은 일반인들은 boost 메뉴얼만 봐서는 사용 방법을 알기 어렵다;;

다음 예제는 위의 Q&A를 보고 좀 더 쉽게 변경해 본 예이다.

#include <iostream>
#include <vector>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>

int main(int argc, char* argv[])
{
    typedef std::vector<int> VecInt;
    typedef std::vector<std::pair<int, int> > VecPair;

    VecPair winners_losers;

    // 2 = 3 = 4 = 10
    winners_losers.push_back(std::pair<int, int>(3, 2));
    winners_losers.push_back(std::pair<int, int>(3, 4));
    winners_losers.push_back(std::pair<int, int>(10, 2));

    // 5 = 6 = 8
    winners_losers.push_back(std::pair<int, int>(5, 6));
    winners_losers.push_back(std::pair<int, int>(5, 8));
    
    // size를 얼마를 줘야하는지 모르겠다.
    // 넘 적게 주면 seg. fault 발생
    VecInt rank(winners_losers.size() * winners_losers.size());
    VecInt parent(winners_losers.size() * winners_losers.size());

    boost::disjoint_sets<int*, int*> ds(&rank[0], &parent[0]);

    // create singletons
    for (VecPair::const_iterator it = winners_losers.begin()
         ; it != winners_losers.end(); ++it)
    {
        ds.make_set(it->first);
        ds.make_set(it->second);
    }

    // union
    for (VecPair::const_iterator it = winners_losers.begin()
         ; it != winners_losers.end(); ++it)
    {
        ds.union_set(it->first, it->second);
    }

    // 결과 출력
    for (VecPair::const_iterator it = winners_losers.begin()
         ; it != winners_losers.end(); ++it)
    {
        std::cout << it->first << " => " << ds.find_set(it->second) << std::endl;
    }

    return 0;
}

실행 예는 다음과 같다

3 => 2
3 => 2
10 => 2
5 => 6
5 => 6

기본 예제의 한계 및 한계 극복하기

위에서 사용된 기본 예제는 아쉽게도 int 형 밖에 처리를 못 한다. primitive data type 중 long 형도 처리할 수 없고, 당연히 좀 더 복잡한 자료 구조, 즉, struct나 Class는 사용할 수 없다.

이를 극복하기 위한 방법도 있는 듯 하다.

이 방법은 std::map을 사용하여 data type을 매핑시켜주는 듯 하다. data type이 long 처럼 primitive한 경우 사용 가능한 듯…

다른 방법으로는 Class 멤버 변수에 저장하고자 하는 변수를 만들고, Class에는 몇 가지 Operator를 overloading하는 듯 한데 관심있는 분은 직접 테스트하고 그 결과를 알려주면 고맙겠다.