This program demonstrate how to use boost graph library to calculate Disjoint Components in a graph

djc.cpp

#include <cstdlib>
#include <vector>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/undirected_dfs.hpp>
#include <boost/graph/connected_components.hpp>

// this class can be used to randomly decide if two
// RandomMatcher objects match or not
template<unsigned N>
class RandomMatcher
{
    private:
        const unsigned m_x;

    public:
        RandomMatcher() : m_x(std::rand()) {}

        unsigned GetX() const {return m_x;}

        bool Match(const RandomMatcher<N>& e) const
        {
            return ((m_x+e.GetX())%N == 0);
        }
};


// this program demonstarte how to use boost graph library to calculate Disjoint Components in a graph
// more information here: http://www.boost.org/doc/libs/1_66_0/libs/graph/doc/index.html
// to build use: g++ -Wall -std=c++11 -o djc djc.cpp
int main(int argc, char** argv)
{
    if (argc < 2)
    {
        std::cout << "usage: " << argv[0] << " <number of elements>" << std::endl;
        return -1;
    }

    const auto number_of_elemnets = std::strtoul(argv[1], nullptr, 0);

    if (number_of_elemnets == 0)
    {
        std::cout << "nothing to do" << std::endl;
        return 0;
    }

    using Element = RandomMatcher<7>;

    std::vector<Element> element_list;

    // populate elements
    for (unsigned i = 0; i < number_of_elemnets; ++i)
    {
        element_list.push_back(Element());
    }
 // fill graph
    boost::adjacency_matrix<boost::undirectedS> graph(number_of_elemnets);

    for (unsigned i = 0; i < number_of_elemnets-1; ++i)
    {
        for (unsigned j = i+1; j < number_of_elemnets; ++j)
        {
            if (element_list[i].Match(element_list[j]))
            {
                boost::add_edge(i, j, graph);
            }
        }
    }

    std::cout << "adjecency matrix" << std::endl;
    boost::print_graph(graph);

    // find connected components
    std::vector<unsigned> component(number_of_elemnets);
    const auto num = boost::connected_components(graph, &component[0]);

    std::cout << "number of components: " << num << std::endl;
    unsigned v = 0;
    for (auto c : component)
    {
        std::cout << "vertex " << v <<" is in component " << c << std::endl;
        ++v;
    }
    return 0;
}