c++ - Comprender boost:: disjoint_sets

disjoint-sets

Question

Necesito usar boost :: disjoint_sets, pero la documentación no está clara para mí. ¿Puede alguien explicar por qué significa cada parámetro de plantilla, y quizás dar un pequeño código de ejemplo para crear un disjoint_sets?

Según la solicitud, estoy usando disjoint_sets para implementar el algoritmo de ancestros menos comunes fuera de línea de Tarjan , es decir, el tipo de valor debe ser vertex_descriptor.

Answer 1

Lo que puedo entender de la documentación:

Necesidad disjunta de asociar un rango y un elemento primario (en el árbol forestal) a cada elemento. Dado que es posible que desee trabajar con cualquier tipo de datos, puede que, por ejemplo, no siempre quiera utilizar un mapa para el padre: con enteros, una matriz es suficiente. También necesita un rango enemigo para cada elemento (el rango necesario para el descubrimiento de unión).

Necesitarás dos "propiedades":

• uno para asociar un número entero a cada elemento (primer argumento de plantilla), el rango
• uno para asociar un elemento a otro (argumento de la segunda plantilla), los padres

En un ejemplo:

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

Las matrices se utilizan &rank[0], &parent[0] para el tipo en la plantilla es int*

Para un ejemplo más complejo (usando mapas) puedes mirar la respuesta de Ugo.

Simplemente le está dando al algoritmo dos estructuras para almacenar los datos (rango / padre) que necesita.

Answer 2

Para aquellos de ustedes que no pueden pagar la sobrecarga de std::map (o no pueden usarlo porque no tienen un constructor predeterminado en su clase), pero cuyos datos no son tan simples como int , escribí una guía a una solución usando std::vector , que es algo óptimo cuando se conoce el número total de elementos de antemano.

La guía incluye un código de muestra totalmente funcional que puede descargar y probar por su cuenta.

La solución mencionada allí supone que tienes el control del código de la clase para que, en particular, puedas agregar algunos atributos. Si esto aún no es posible, siempre puede agregar un contenedor a su alrededor:

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

Además, si sabe que la cantidad de elementos es pequeña, no es necesario size_t , en cuyo caso puede agregar alguna plantilla para el tipo UnsignedInt y decidir en tiempo de ejecución crear una instancia con uint8_t , uint16_t , uint32_t o uint64_t , que puede obtener con <cstdint> en C ++ 11 o con boost::cstdint caso contrario.

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

Aquí está el enlace nuevamente en caso de que lo hayas perdido: http://janoma.cl/post/using-disjoint-sets-with-a-vector/

Answer 3

disjoint_sets<Rank, Parent, FindCompress>

• Rank PropertyMap utilizado para almacenar el tamaño de un conjunto (elemento -> std :: size_t). Ver unión por rango
• Parent PropertyMap usado para almacenar el padre de un elemento (elemento -> elemento). Ver la compresión de ruta
• FindCompress Argumento opcional que define el método de búsqueda. Predeterminado para find_with_full_path_compression Consulte here (El valor predeterminado debería ser el que necesita).

Ejemplo:

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);
}

Tenga en cuenta que "La Biblioteca de mapas de propiedades de Boost contiene algunos adaptadores que convierten estructuras de datos de uso común que implementan una operación de asignación, como matrices incorporadas (punteros), iteradores y std :: map, para tener la interfaz del mapa de propiedades"

Esta lista de estos adaptadores (como boost :: asociative_property_map) se puede encontrar here .