#include <fstream>
#include <map>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/incremental_components.hpp>
#include <boost/property_map.hpp>
#include <boost/foreach.hpp>
using namespace boost;
typedef boost::adjacency_list<vecS, vecS, undirectedS> ImplGraph_t;
typedef ImplGraph_t::vertex_descriptor vertex_t;
typedef ImplGraph_t::edge_descriptor edge_t;
typedef graph_traits<ImplGraph_t>::vertices_size_type size_type;
int main(int argc, char** argv)
{
std::ifstream ifs(argv[1]);
std::ofstream logstream("TClog.txt");
int sid, did;
ImplGraph_t gg;
int numNodes = atoi(argv[2]);
std::map<int, vertex_t> forwardMap;
for(int i = 0; i < numNodes; i++)
{
vertex_t k = add_vertex(gg);
//logstream<<i<<" "<<k<<std::endl;
forwardMap[i] = k;
}
ifs>>sid>>did;
while(ifs)
{
vertex_t src = forwardMap[sid];
vertex_t des = forwardMap[did];
add_edge(src, des, gg);
ifs>>sid>>did;
}
std::cout<<" "<<num_vertices(gg)<<" "<<num_edges(gg)<<std::endl;
std::map<vertex_t, size_type> rank;
boost::associative_property_map< std::map<vertex_t, size_type> > rank_map(rank);
// std::map<vertex_t, vertex_t> parent;
// boost::associative_property_map< std::map<vertex_t, vertex_t> > parent_map(parent);
std::vector<vertex_t> parent(num_vertices(gg));
typedef vertex_t* Parent_t;
disjoint_sets< boost::associative_property_map<std::map<vertex_t, size_type> >, Parent_t > ds(rank_map, &parent[0]);
initialize_incremental_components(gg, ds);
incremental_components(gg, ds);
edge_t e;
vertex_t src;
vertex_t des;
typedef component_index<unsigned int> Components_t;
Components_t components(&parent[0], &parent[0]+parent.size());
for (Components_t::size_type c = 0; c < components.size(); ++c) {
std::cout << "component " << c << " contains: ";
Components_t::value_type::iterator
j = components[c].begin(),
jend = components[c].end();
for ( ; j != jend; ++j)
std::cout << *j << " ";
std::cout << std::endl;
}
return 0;
}