Skip to content

Instantly share code, notes, and snippets.

@yuvalif
Created January 8, 2018 09:43
Show Gist options
  • Save yuvalif/8ed3e1f74242c756d7aa43582b11cebb to your computer and use it in GitHub Desktop.
Save yuvalif/8ed3e1f74242c756d7aa43582b11cebb to your computer and use it in GitHub Desktop.
This program demonstrate how to use boost graph library to calculate Disjoint Components in a graph
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment