title: Boost Disjoint sets: How to retrieve sets?
body: <p>I am trying to use disjoint sets from Boost but, after swimming all day through StackOverflow and the documentation I could not solve my problem.</p>
  
  <p>The main problem is: given some maps that will act as Rank and Parent, of an int element type (in the future that element type needs to be a pointer to an actual object though), and after doing some <code>union_set</code>s, get a vector of vectors: each outer vector is a connected component number, each inner vector the list of points (or, pointers) that compose that connected component.</p>
  
  <p>E.g.: <code>v[1] -&gt; [0, 30, 234, ...]</code>.</p>
  
  <p>I have looked at <a href="https://stackoverflow.com/questions/4134703/understanding-boostdisjoint-sets/22800273#22800273">this</a>, <a href="http://janoma.cl/post/using-disjoint-sets-with-a-vector/?i=1" rel="nofollow noreferrer">this</a> and <a href="https://www.boost.org/doc/libs/1_69_0/libs/disjoint_sets/disjoint_sets.html" rel="nofollow noreferrer">this</a> + several other questions here in SO and every result in google's front page.</p>
  
  <p>I have created a small example using code from user @janoma. However, his answer, while really good, it's "too customized" to his needs and after tinkering for a while I could not see how to adapt his code to the use of <code>std::maps</code>.</p>
  
  <pre><code>/*!
   * Adapted from
   *   http://janoma.cl/post/using-disjoint-sets-with-a-vector/?i=1
   *   https://github.com/janoma/study/blob/master/disjoint_sets/main.cpp
   *
   */
  
  #include &lt;algorithm&gt;
  #include &lt;map&gt;
  #include &lt;iomanip&gt;
  #include &lt;iostream&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;random&gt;
  #include &lt;vector&gt;
  
  #include &lt;boost/pending/disjoint_sets.hpp&gt;
  #include &lt;boost/pending/property.hpp&gt;
  
  typedef int element_t;
  
  void
  printElements(std::vector&lt;int&gt;&amp; elements, boost::disjoint_sets&lt;boost::associative_property_map&lt;std::map&lt;int,int&gt;&gt;, boost::associative_property_map&lt;std::map&lt;int,int&gt;&gt;&gt; sets)
  {
      std::cout &lt;&lt; "Elements:            ";
      for (size_t i = 0; i &lt; elements.size(); ++i)
      {
          std::cout &lt;&lt; std::setw(4) &lt;&lt; elements[i];
      }
      std::cout &lt;&lt; std::endl;
      std::cout &lt;&lt; "Set representatives: ";
      for (size_t i = 0; i &lt; elements.size(); ++i)
      {
          std::cout &lt;&lt; std::setw(4) &lt;&lt; sets.find_set(elements[i]);
      }
      std::cout &lt;&lt; std::endl;
  }
  
  int main()
  {
      // initialization
      std::vector&lt;element_t&gt; elements;
      elements.reserve(30);
      for (size_t i = 0; i &lt; elements.capacity(); ++i)
      {
          elements.push_back(element_t(rand() % 90));
      }
  
      // disjoint sets
      std::map&lt;element_t,int&gt; rank;
      std::map&lt;element_t,element_t&gt; parent;
  
      boost::disjoint_sets&lt;
          boost::associative_property_map&lt;std::map&lt;element_t,int&gt;&gt;,
          boost::associative_property_map&lt;std::map&lt;element_t,element_t&gt;&gt; &gt; sets(
              boost::make_assoc_property_map(rank),
              boost::make_assoc_property_map(parent));
  
      // initialize disjoint sets
      for (size_t i = 0; i &lt; elements.size(); ++i)
      {
          sets.make_set(elements.at(i));
      }
  
      // unions
      for (size_t i = 0; i &lt; elements.size()/2; ++i)
      {
          // Union between this element and one randomly chosen from the rest
          size_t j = rand() % elements.size();
          sets.union_set(elements[i], elements[j]);
      }
  
      std::cout &lt;&lt; "Found " &lt;&lt; sets.count_sets(elements.begin(), elements.end()) &lt;&lt; " sets:" &lt;&lt; std::endl;
      printElements(elements,sets);
  
      // compression
      sets.compress_sets(elements.begin(), elements.end());
  
      // QUICK &amp; DIRTY
      std::vector&lt;element_t&gt; representatives;
      representatives.reserve(30);
      for (size_t i = 0; i &lt; elements.capacity(); ++i)
          representatives.push_back(sets.find_set(elements[i]));
      // ---
  
      std::cout &lt;&lt; std::endl &lt;&lt; "After path compression:" &lt;&lt; std::endl;
      printElements(elements,sets);
  
      std::sort(elements.begin(),elements.end(), [representatives](auto lhs, auto rhs){ return representatives[lhs] &lt; representatives[rhs]; });
  
      std::cout &lt;&lt; std::endl &lt;&lt; "After path compression and sorting:" &lt;&lt; std::endl;
      printElements(elements,sets);
  }
  </code></pre>
  
  <p>The expected result would be the last part you get if you execute <a href="https://github.com/janoma/study/blob/master/disjoint_sets/main.cpp" rel="nofollow noreferrer">janoma's code</a>, that is:</p>
  
  <pre><code>Alternative, using iterators:
      Sorted set: 1 8 12 16 23 27 32 37 46 46 50 55 60 62 69 73 76 79 87 
      Sorted set: 23 36 
      Sorted set: 62 
      Sorted set: 13 25 25 52 67 69 71 80 
  </code></pre>
  
  <p>Actual result is, well, I didn't get to the point of breaking it into separate lists, but:</p>
  
  <pre><code>After path compression and sorting:
  Elements:              76  55  37  62  80  62  69  87  71  46  52  36  60  73  79  50  67  32  69  46  23   1   8  12  23  27  13  16  25  25
  Set representatives:   76  55  37  62  80  62  50  87  71  55  52  36  60  55  55  50  52  87  50  55  55  87  50  60  55  50  52  50  52  52
  </code></pre>
  
  <p>It's unordered.</p>
  
  <p>At this point I am left without resources to keep looking / learning how to properly use boost disjoint sets.</p>