dimacs.hpp 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310
  1. // Copyright 2005 The Trustees of Indiana University.
  2. // Use, modification and distribution is subject to the Boost Software
  3. // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  4. // http://www.boost.org/LICENSE_1_0.txt)
  5. // Authors: Alex Breuer
  6. // Andrew Lumsdaine
  7. #ifndef BOOST_GRAPH_DIMACS_HPP
  8. #define BOOST_GRAPH_DIMACS_HPP
  9. #include <string>
  10. #include <sstream>
  11. #include <iostream>
  12. #include <fstream>
  13. #include <iterator>
  14. #include <exception>
  15. #include <vector>
  16. #include <queue>
  17. namespace boost { namespace graph {
  18. class dimacs_exception : public std::exception {};
  19. class dimacs_basic_reader {
  20. public:
  21. typedef std::size_t vertices_size_type;
  22. typedef std::size_t edges_size_type;
  23. typedef double vertex_weight_type;
  24. typedef double edge_weight_type;
  25. typedef std::pair<vertices_size_type,
  26. vertices_size_type> edge_type;
  27. enum incr_mode {edge, edge_weight};
  28. dimacs_basic_reader( std::istream& in, bool want_weights = true ) :
  29. inpt( in ), seen_edges( 0 ), want_weights(want_weights)
  30. {
  31. while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
  32. if( buf[0] != 'p' ) {
  33. boost::throw_exception(dimacs_exception());
  34. }
  35. std::stringstream instr( buf );
  36. std::string junk;
  37. instr >> junk >> junk >> num_vertices >> num_edges;
  38. read_edge_weights.push( -1 );
  39. incr( edge_weight );
  40. }
  41. //for a past the end iterator
  42. dimacs_basic_reader() : inpt( std::cin ), num_vertices( 0 ),
  43. num_edges( 0 ), seen_edges( 0 ), want_weights(false) {}
  44. edge_type edge_deref() {
  45. assert( !read_edges.empty() );
  46. return read_edges.front();
  47. }
  48. inline edge_type* edge_ref() {
  49. assert( !read_edges.empty() );
  50. return &read_edges.front();
  51. }
  52. inline edge_weight_type edge_weight_deref() {
  53. assert( !read_edge_weights.empty() );
  54. return read_edge_weights.front();
  55. }
  56. inline dimacs_basic_reader incr( incr_mode mode ) {
  57. if( mode == edge ) {
  58. assert( !read_edges.empty() );
  59. read_edges.pop();
  60. }
  61. else if( mode == edge_weight ) {
  62. assert( !read_edge_weights.empty() );
  63. read_edge_weights.pop();
  64. }
  65. if( (mode == edge && read_edges.empty()) ||
  66. (mode == edge_weight && read_edge_weights.empty() )) {
  67. if( seen_edges > num_edges ) {
  68. boost::throw_exception(dimacs_exception());
  69. }
  70. while( getline( inpt, buf ) && !buf.empty() && buf[0] == 'c' );
  71. if( !inpt.eof() ) {
  72. int source, dest, weight;
  73. read_edge_line((char*) buf.c_str(), source, dest, weight);
  74. seen_edges++;
  75. source--;
  76. dest--;
  77. read_edges.push( edge_type( source, dest ) );
  78. if (want_weights) {
  79. read_edge_weights.push( weight );
  80. }
  81. }
  82. assert( read_edges.size() < 100 );
  83. assert( read_edge_weights.size() < 100 );
  84. }
  85. // the 1000000 just happens to be about how many edges can be read in
  86. // 10s
  87. // if( !(seen_edges % 1000000) && !process_id( pg ) && mode == edge ) {
  88. // std::cout << "read " << seen_edges << " edges" << std::endl;
  89. // }
  90. return *this;
  91. }
  92. inline bool done_edges() {
  93. return inpt.eof() && read_edges.size() == 0;
  94. }
  95. inline bool done_edge_weights() {
  96. return inpt.eof() && read_edge_weights.size() == 0;
  97. }
  98. inline vertices_size_type n_vertices() {
  99. return num_vertices;
  100. }
  101. inline vertices_size_type processed_edges() {
  102. return seen_edges - read_edges.size();
  103. }
  104. inline vertices_size_type processed_edge_weights() {
  105. return seen_edges - read_edge_weights.size();
  106. }
  107. inline vertices_size_type n_edges() {
  108. return num_edges;
  109. }
  110. protected:
  111. bool read_edge_line(char *linebuf, int &from, int &to, int &weight)
  112. {
  113. char *fs = NULL, *ts = NULL, *ws = NULL;
  114. char *tmp = linebuf + 2;
  115. fs = tmp;
  116. if ('e' == linebuf[0]) {
  117. while (*tmp != '\n' && *tmp != '\0') {
  118. if (*tmp == ' ') {
  119. *tmp = '\0';
  120. ts = ++tmp;
  121. break;
  122. }
  123. tmp++;
  124. }
  125. *tmp = '\0';
  126. if (NULL == fs || NULL == ts) return false;
  127. from = atoi(fs); to = atoi(ts); weight = 0;
  128. } else if ('a' == linebuf[0]) {
  129. while (*tmp != '\n' && *tmp != '\0') {
  130. if (*tmp == ' ') {
  131. *tmp = '\0';
  132. ts = ++tmp;
  133. break;
  134. }
  135. tmp++;
  136. }
  137. while (*tmp != '\n' && *tmp != '\0') {
  138. if (*tmp == ' ') {
  139. *tmp = '\0';
  140. ws = ++tmp;
  141. break;
  142. }
  143. tmp++;
  144. }
  145. while (*tmp != '\n' && *tmp != '\0') tmp++;
  146. *tmp = '\0';
  147. if (fs == NULL || ts == NULL || ws == NULL) return false;
  148. from = atoi(fs); to = atoi(ts) ;
  149. if (want_weights) weight = atoi(ws); else weight = 0;
  150. } else {
  151. return false;
  152. }
  153. return true;
  154. }
  155. std::queue<edge_type> read_edges;
  156. std::queue<edge_weight_type> read_edge_weights;
  157. std::istream& inpt;
  158. std::string buf;
  159. vertices_size_type num_vertices, num_edges, seen_edges;
  160. bool want_weights;
  161. };
  162. template<typename T>
  163. class dimacs_edge_iterator {
  164. public:
  165. typedef dimacs_basic_reader::edge_type edge_type;
  166. typedef dimacs_basic_reader::incr_mode incr_mode;
  167. typedef std::input_iterator_tag iterator_category;
  168. typedef edge_type value_type;
  169. typedef value_type reference;
  170. typedef edge_type* pointer;
  171. typedef std::ptrdiff_t difference_type;
  172. dimacs_edge_iterator( T& reader ) :
  173. reader( reader ) {}
  174. inline dimacs_edge_iterator& operator++() {
  175. reader.incr( dimacs_basic_reader::edge );
  176. return *this;
  177. }
  178. inline edge_type operator*() {
  179. return reader.edge_deref();
  180. }
  181. inline edge_type* operator->() {
  182. return reader.edge_ref();
  183. }
  184. // don't expect this to do the right thing if you're not comparing against a
  185. // general past-the-end-iterator made with the default constructor for
  186. // dimacs_basic_reader
  187. inline bool operator==( dimacs_edge_iterator arg ) {
  188. if( reader.n_vertices() == 0 ) {
  189. return arg.reader.done_edges();
  190. }
  191. else if( arg.reader.n_vertices() == 0 ) {
  192. return reader.done_edges();
  193. }
  194. else {
  195. return false;
  196. }
  197. return false;
  198. }
  199. inline bool operator!=( dimacs_edge_iterator arg ) {
  200. if( reader.n_vertices() == 0 ) {
  201. return !arg.reader.done_edges();
  202. }
  203. else if( arg.reader.n_vertices() == 0 ) {
  204. return !reader.done_edges();
  205. }
  206. else {
  207. return true;
  208. }
  209. return true;
  210. }
  211. private:
  212. T& reader;
  213. };
  214. template<typename T>
  215. class dimacs_edge_weight_iterator {
  216. public:
  217. typedef dimacs_basic_reader::edge_weight_type edge_weight_type;
  218. typedef dimacs_basic_reader::incr_mode incr_mode;
  219. dimacs_edge_weight_iterator( T& reader ) : reader( reader ) {}
  220. inline dimacs_edge_weight_iterator& operator++() {
  221. reader.incr( dimacs_basic_reader::edge_weight );
  222. return *this;
  223. }
  224. inline edge_weight_type operator*() {
  225. return reader.edge_weight_deref();
  226. }
  227. // don't expect this to do the right thing if you're not comparing against a
  228. // general past-the-end-iterator made with the default constructor for
  229. // dimacs_basic_reader
  230. inline bool operator==( dimacs_edge_weight_iterator arg ) {
  231. if( reader.n_vertices() == 0 ) {
  232. return arg.reader.done_edge_weights();
  233. }
  234. else if( arg.reader.n_vertices() == 0 ) {
  235. return reader.done_edge_weights();
  236. }
  237. else {
  238. return false;
  239. }
  240. return false;
  241. }
  242. inline bool operator!=( dimacs_edge_weight_iterator arg ) {
  243. if( reader.n_vertices() == 0 ) {
  244. return !arg.reader.done_edge_weights();
  245. }
  246. else if( arg.reader.n_vertices() == 0 ) {
  247. return !reader.done_edge_weights();
  248. }
  249. else {
  250. return true;
  251. }
  252. return true;
  253. }
  254. private:
  255. T& reader;
  256. };
  257. } } // end namespace boost::graph
  258. #endif