Posted By

dirkchang on 01/25/11


Tagged


Versions (?)

liarliar version B (using boost::graph, based on Kevin Bacon example)


 / Published in: C++
 

  1. /*
  2.  * main.cpp
  3.  *
  4.  * Created on: 2011/1/24
  5.  * Author: dirk
  6.  */
  7.  
  8. #include <iostream>
  9. #include <fstream>
  10. #include <map>
  11. #include <vector>
  12. #include <string>
  13.  
  14. #include <boost/graph/adjacency_list.hpp>
  15. #include <boost/graph/visitors.hpp>
  16. #include <boost/graph/breadth_first_search.hpp>
  17.  
  18. // we use bundled property here
  19. typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> Graph;
  20.  
  21. typedef std::pair<size_t, size_t> Edge;
  22. typedef std::map<std::string, size_t> NameVertexMap;
  23. typedef std::vector<Edge> EdgeArray;
  24.  
  25. template <typename DistanceMap>
  26. class bacon_number_recorder : public boost::default_bfs_visitor {
  27. public:
  28. bacon_number_recorder(DistanceMap d) : _d(d) {}
  29.  
  30. // overloading tree_edge function
  31. template <typename Edge, typename Graph>
  32. void tree_edge(Edge e, const Graph &g) const {
  33. typename Graph::vertex_descriptor u = boost::source(e, g), v = boost::target(e, g);
  34. _d[v] = _d[u] + 1;
  35. }
  36.  
  37. private:
  38. DistanceMap _d;
  39. };
  40.  
  41. template <typename DistanceMap>
  42. static bacon_number_recorder<DistanceMap> record_bacon_number(DistanceMap d) {
  43. return bacon_number_recorder<DistanceMap>(d);
  44. }
  45.  
  46. int main(int argc, char **argv) {
  47. // preparing the data
  48. std::ifstream fin(argv[1]);
  49. if(!fin) {
  50. std::cerr << "Can't open data file, leaving...\n";
  51. return EXIT_FAILURE;
  52. }
  53.  
  54. // reading the file
  55. int i_no_chunks(0), i_no_accused(0);
  56. NameVertexMap nvm_members;
  57. NameVertexMap::iterator nvm_it;
  58. bool b_inserted;
  59. std::string str_accuser, str_accused;
  60. EdgeArray edge_array;
  61. size_t max_id(0), u(0), v(0);
  62.  
  63. fin >> i_no_chunks;
  64. edge_array.reserve(i_no_chunks * 5);
  65. for(int i = 0; i < i_no_chunks; ++i) {
  66. fin >> str_accuser >> i_no_accused;
  67.  
  68. boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accuser, max_id));
  69. if(b_inserted) {
  70. u = max_id;
  71. ++max_id;
  72. } else {
  73. u = nvm_it->second;
  74. }
  75.  
  76. for(int j = 0; j < i_no_accused; ++j) {
  77. fin >> str_accused;
  78.  
  79. boost::tie(nvm_it, b_inserted) = nvm_members.insert(std::make_pair(str_accused, max_id));
  80. if(b_inserted) {
  81. v = max_id;
  82. ++max_id;
  83. } else {
  84. v = nvm_it->second;
  85. }
  86. edge_array.push_back(std::make_pair(u,v));
  87. }
  88. }
  89. Graph graph(&edge_array[0], &edge_array[edge_array.size()-1], nvm_members.size());
  90.  
  91. // processing the data
  92. std::vector<int> bacon_number(boost::num_vertices(graph), 0);
  93. bacon_number[0] = 0;
  94. boost::breadth_first_search(graph, 0, boost::visitor(record_bacon_number(&bacon_number[0])));
  95.  
  96. // output the results
  97. int i_groups[2] = {0,0};
  98. Graph::vertex_iterator i, end;
  99. for(boost::tie(i, end) = boost::vertices(graph); i != end; ++i) {
  100. ++i_groups[bacon_number[*i]%2];
  101. }
  102.  
  103. if(i_groups[0]>i_groups[1]) {
  104. std::cout << i_groups[0] << ' ' << i_groups[1] << '\n';
  105. } else {
  106. std::cout << i_groups[1] << ' ' << i_groups[0] << '\n';
  107. }
  108. }

Report this snippet  

You need to login to post a comment.