codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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::vector<vertex_t> parent(num_vertices(gg)); typedef std::vector<vertex_t>::iterator vv_iter_t; iterator_property_map<vv_iter_t, identity_property_map, vertex_t, vertex_t&> ipm(parent.begin()); // std::map<vertex_t, vertex_t> parent; // boost::associative_property_map< std::map<vertex_t, vertex_t> > parent_map(parent); disjoint_sets< boost::associative_property_map<std::map<vertex_t, size_type> >, iterator_property_map<vv_iter_t, identity_property_map, vertex_t, vertex_t&> > ds(rank_map, ipm); 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.begin(), parent.end()); 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; }
Private
[
?
]
Run code
Submit