/ Published in: C++
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
/* * main.cpp * * Created on: 2011/1/24 * Author: dirk */ #include <iostream> #include <fstream> #include <map> #include <vector> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/visitors.hpp> #include <boost/graph/breadth_first_search.hpp> // we use bundled property here typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph; typedef std::pair<size_t, size_t> Edge; typedef std::map<std::string, size_t> NameVertexMap; typedef std::vector<Edge> EdgeArray; template <typename DistanceMap> class bacon_number_recorder : public boost::default_bfs_visitor { public: bacon_number_recorder(DistanceMap d) : _d(d) {} // overloading tree_edge function template <typename Edge, typename Graph> void tree_edge(Edge e, const Graph &g) const { typename Graph::vertex_descriptor u = boost::source(e, g), v = boost::target(e, g); _d[v] = _d[u] + 1; } private: DistanceMap _d; }; template <typename DistanceMap> static bacon_number_recorder<DistanceMap> record_bacon_number(DistanceMap d) { return bacon_number_recorder<DistanceMap>(d); } int main(int argc, char **argv) { // preparing the data std::ifstream fin(argv[1]); if(!fin) { std::cerr << "Can't open data file, leaving...\n"; return EXIT_FAILURE; } // reading the file int i_no_chunks(0), i_no_accused(0); NameVertexMap nvm_members; NameVertexMap::iterator nvm_it; bool b_inserted; std::string str_accuser, str_accused; EdgeArray edge_array; size_t max_id(0), u(0), v(0); fin >> i_no_chunks; edge_array.reserve(i_no_chunks * 5); for(int i = 0; i < i_no_chunks; ++i) { fin >> str_accuser >> i_no_accused; boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accuser, max_id)); if(b_inserted) { u = max_id; ++max_id; } else { u = nvm_it->second; } for(int j = 0; j < i_no_accused; ++j) { fin >> str_accused; boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accused, max_id)); if(b_inserted) { v = max_id; ++max_id; } else { v = nvm_it->second; } edge_array.push_back(std::make_pair(u,v)); } } Graph graph(&edge_array[0], &edge_array[edge_array.size()-1], nvm_members.size()); // processing the data std::vector<int> bacon_number(boost::num_vertices(graph), 0); bacon_number[0] = 0; boost::breadth_first_search(graph, 0, boost::visitor(record_bacon_number(&bacon_number[0]))); // output the results int i_groups[2] = {0,0}; Graph::vertex_iterator i, end; for(boost::tie(i, end) = boost::vertices(graph); i != end; ++i) { ++i_groups[bacon_number[*i]%2]; } if(i_groups[0]>i_groups[1]) { std::cout << i_groups[0] << ' ' << i_groups[1] << '\n'; } else { std::cout << i_groups[1] << ' ' << i_groups[0] << '\n'; } }