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