boost :: disjoint_sets 이해

boost :: disjoint_sets 이해

---

boost :: disjoint_sets를 사용해야하지만 설명서 가 명확하지 않습니다. 누군가 각 템플릿 매개 변수의 의미를 설명하고 disjoint_sets를 생성하기위한 간단한 예제 코드를 제공 할 수 있습니까?

요청에 따라 저는 disjoint_sets를 사용하여 Tarjan의 오프라인 최소 공통 조상 알고리즘 을 구현 합니다 . 즉, 값 유형은 vertex_descriptor 여야합니다.

---

문서에서 이해할 수있는 것 :

Disjoint는 순위와 부모 (포리스트 트리에서)를 각 요소에 연결해야합니다. 모든 종류의 데이터로 작업하고 싶을 수 있기 때문에, 예를 들어 항상 부모에 대한 맵을 사용하고 싶지는 않을 수 있습니다. 정수를 사용하면 배열이면 충분합니다. 또한 각 요소에 대한 순위 적 (조합 찾기에 필요한 순위)이 필요합니다.

두 개의 "속성"이 필요합니다.

• 정수를 각 요소 (첫 번째 템플릿 인수)에 연결하려면 순위
• 하나는 요소를 다른 하나 (두 번째 템플릿 인수)에 연결하기위한 것입니다.

예 :

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

배열은 &rank[0], &parent[0]템플릿의 유형에 사용 됩니다.int*

더 복잡한 예 (지도 사용)는 Ugo의 답변을 볼 수 있습니다.

당신은 그가 필요로하는 데이터 (순위 / 상위)를 저장하기 위해 알고리즘에 두 가지 구조를 제공하고 있습니다.

---

disjoint_sets<Rank, Parent, FindCompress>

• 집합의 크기를 저장하는 데 사용되는 PropertyMap 순위 (요소-> std :: size_t). 등급별 조합 보기
• 요소 (요소-> 요소)의 상위를 저장하는 데 사용되는 상위 PropertyMap. 경로 압축 참조
• FindCompress find 메서드를 정의하는 선택적 인수입니다. 기본값 find_with_full_path_compression은 여기 를 참조 하십시오 (기본값은 필요한 것입니다).

예:

template <typename Rank, typename Parent>
void algo(Rank& r, Parent& p, std::vector<Element>& elements)
{
 boost::disjoint_sets<Rank,Parent> dsets(r, p);
 for (std::vector<Element>::iterator e = elements.begin();
      e != elements.end(); e++)
  dsets.make_set(*e);
  ...
}

int main()
{
  std::vector<Element> elements;
  elements.push_back(Element(...));
  ...

  typedef std::map<Element,std::size_t> rank_t; // => order on Element
  typedef std::map<Element,Element> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);

  algo(rank_pmap, parent_pmap, elements);
}

"Boost Property Map Library에는 기본 배열 (포인터), 반복기 및 std :: map과 같은 매핑 작업을 구현하는 일반적으로 사용되는 데이터 구조를 속성 맵 인터페이스로 변환하는 몇 가지 어댑터가 포함되어 있습니다."

이러한 어댑터 목록 (예 : boost :: associative_property_map)은 여기 에서 찾을 수 있습니다 .

---

오버 헤드를 감당할 수 없지만 std::map(또는 클래스에 기본 생성자가 없어서 사용할 수없는 경우) 데이터가.만큼 간단하지 않은 사용자 를 위해를 사용하여 솔루션에 대한 가이드 를 int작성 했습니다std::vector . 총 요소 수를 미리 알고있을 때 최적입니다.

이 가이드에는 직접 다운로드하고 테스트 할 수 있는 완전히 작동하는 샘플 코드 가 포함되어 있습니다.

여기에 언급 된 솔루션은 특히 일부 속성을 추가 할 수 있도록 클래스의 코드를 제어 할 수 있다고 가정합니다. 그래도 가능하지 않은 경우 항상 주위에 래퍼를 추가 할 수 있습니다.

class Wrapper {
    UntouchableClass const& mInstance;
    size_t dsID;
    size_t dsRank;
    size_t dsParent;
}

Moreover, if you know the number of elements to be small, there's no need for size_t, in which case you can add some template for the UnsignedInt type and decide in runtime to instantiate it with uint8_t, uint16_t, uint32_tor uint64_t, which you can obtain with <cstdint> in C++11 or with boost::cstdint otherwise.

template <typename UnsignedInt>
class Wrapper {
    UntouchableClass const& mInstance;
    UnsignedInt dsID;
    UnsignedInt dsRank;
    UnsignedInt dsParent;
}

Here's the link again in case you missed it: http://janoma.cl/post/using-disjoint-sets-with-a-vector/

ReferenceURL : https://stackoverflow.com/questions/4134703/understanding-boostdisjoint-sets