|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 ///\ingroup lemon_io |
|
20 ///\file |
|
21 ///\brief Lemon Graph Format writer. |
|
22 |
|
23 |
|
24 #ifndef LEMON_LGF_WRITER_H |
|
25 #define LEMON_LGF_WRITER_H |
|
26 |
|
27 #include <iostream> |
|
28 #include <fstream> |
|
29 #include <sstream> |
|
30 |
|
31 #include <algorithm> |
|
32 |
|
33 #include <vector> |
|
34 #include <functional> |
|
35 |
|
36 #include <lemon/assert.h> |
|
37 #include <lemon/graph_utils.h> |
|
38 |
|
39 namespace lemon { |
|
40 |
|
41 namespace _writer_bits { |
|
42 |
|
43 template <typename Value> |
|
44 struct DefaultConverter { |
|
45 std::string operator()(const Value& value) { |
|
46 std::ostringstream os; |
|
47 os << value; |
|
48 return os.str(); |
|
49 } |
|
50 }; |
|
51 |
|
52 template <typename T> |
|
53 bool operator<(const T&, const T&) { |
|
54 throw DataFormatError("Label map is not comparable"); |
|
55 } |
|
56 |
|
57 template <typename _Map> |
|
58 class MapLess { |
|
59 public: |
|
60 typedef _Map Map; |
|
61 typedef typename Map::Key Item; |
|
62 |
|
63 private: |
|
64 const Map& _map; |
|
65 |
|
66 public: |
|
67 MapLess(const Map& map) : _map(map) {} |
|
68 |
|
69 bool operator()(const Item& left, const Item& right) { |
|
70 return _map[left] < _map[right]; |
|
71 } |
|
72 }; |
|
73 |
|
74 template <typename _Item> |
|
75 class MapStorageBase { |
|
76 public: |
|
77 typedef _Item Item; |
|
78 |
|
79 public: |
|
80 MapStorageBase() {} |
|
81 virtual ~MapStorageBase() {} |
|
82 |
|
83 virtual std::string get(const Item& item) = 0; |
|
84 virtual void sort(std::vector<Item>&) = 0; |
|
85 }; |
|
86 |
|
87 template <typename _Item, typename _Map, |
|
88 typename _Converter = DefaultConverter<typename _Map::Value> > |
|
89 class MapStorage : public MapStorageBase<_Item> { |
|
90 public: |
|
91 typedef _Map Map; |
|
92 typedef _Converter Converter; |
|
93 typedef _Item Item; |
|
94 |
|
95 private: |
|
96 const Map& _map; |
|
97 Converter _converter; |
|
98 |
|
99 public: |
|
100 MapStorage(const Map& map, const Converter& converter = Converter()) |
|
101 : _map(map), _converter(converter) {} |
|
102 virtual ~MapStorage() {} |
|
103 |
|
104 virtual std::string get(const Item& item) { |
|
105 return _converter(_map[item]); |
|
106 } |
|
107 virtual void sort(std::vector<Item>& items) { |
|
108 MapLess<Map> less(_map); |
|
109 std::sort(items.begin(), items.end(), less); |
|
110 } |
|
111 }; |
|
112 |
|
113 class ValueStorageBase { |
|
114 public: |
|
115 ValueStorageBase() {} |
|
116 virtual ~ValueStorageBase() {} |
|
117 |
|
118 virtual std::string get() = 0; |
|
119 }; |
|
120 |
|
121 template <typename _Value, typename _Converter = DefaultConverter<_Value> > |
|
122 class ValueStorage : public ValueStorageBase { |
|
123 public: |
|
124 typedef _Value Value; |
|
125 typedef _Converter Converter; |
|
126 |
|
127 private: |
|
128 const Value& _value; |
|
129 Converter _converter; |
|
130 |
|
131 public: |
|
132 ValueStorage(const Value& value, const Converter& converter = Converter()) |
|
133 : _value(value), _converter(converter) {} |
|
134 |
|
135 virtual std::string get() { |
|
136 return _converter(_value); |
|
137 } |
|
138 }; |
|
139 |
|
140 template <typename Value> |
|
141 struct MapLookUpConverter { |
|
142 const std::map<Value, std::string>& _map; |
|
143 |
|
144 MapLookUpConverter(const std::map<Value, std::string>& map) |
|
145 : _map(map) {} |
|
146 |
|
147 std::string operator()(const Value& str) { |
|
148 typename std::map<Value, std::string>::const_iterator it = |
|
149 _map.find(str); |
|
150 if (it == _map.end()) { |
|
151 throw DataFormatError("Item not found"); |
|
152 } |
|
153 return it->second; |
|
154 } |
|
155 }; |
|
156 |
|
157 bool isWhiteSpace(char c) { |
|
158 return c == ' ' || c == '\t' || c == '\v' || |
|
159 c == '\n' || c == '\r' || c == '\f'; |
|
160 } |
|
161 |
|
162 bool isEscaped(char c) { |
|
163 return c == '\\' || c == '\"' || c == '\'' || |
|
164 c == '\a' || c == '\b'; |
|
165 } |
|
166 |
|
167 static void writeEscape(std::ostream& os, char c) { |
|
168 switch (c) { |
|
169 case '\\': |
|
170 os << "\\\\"; |
|
171 return; |
|
172 case '\"': |
|
173 os << "\\\""; |
|
174 return; |
|
175 case '\a': |
|
176 os << "\\a"; |
|
177 return; |
|
178 case '\b': |
|
179 os << "\\b"; |
|
180 return; |
|
181 case '\f': |
|
182 os << "\\f"; |
|
183 return; |
|
184 case '\r': |
|
185 os << "\\r"; |
|
186 return; |
|
187 case '\n': |
|
188 os << "\\n"; |
|
189 return; |
|
190 case '\t': |
|
191 os << "\\t"; |
|
192 return; |
|
193 case '\v': |
|
194 os << "\\v"; |
|
195 return; |
|
196 default: |
|
197 if (c < 0x20) { |
|
198 os << '\\' << std::oct << static_cast<int>(c); |
|
199 } else { |
|
200 os << c; |
|
201 } |
|
202 return; |
|
203 } |
|
204 } |
|
205 |
|
206 bool requireEscape(const std::string& str) { |
|
207 std::istringstream is(str); |
|
208 char c; |
|
209 while (is.get(c)) { |
|
210 if (isWhiteSpace(c) || isEscaped(c)) { |
|
211 return true; |
|
212 } |
|
213 } |
|
214 return false; |
|
215 } |
|
216 |
|
217 std::ostream& writeToken(std::ostream& os, const std::string& str) { |
|
218 |
|
219 if (requireEscape(str)) { |
|
220 os << '\"'; |
|
221 for (std::string::const_iterator it = str.begin(); |
|
222 it != str.end(); ++it) { |
|
223 writeEscape(os, *it); |
|
224 } |
|
225 os << '\"'; |
|
226 } else { |
|
227 os << str; |
|
228 } |
|
229 return os; |
|
230 } |
|
231 |
|
232 } |
|
233 |
|
234 /// \e |
|
235 template <typename _Digraph> |
|
236 class DigraphWriter { |
|
237 public: |
|
238 |
|
239 typedef _Digraph Digraph; |
|
240 GRAPH_TYPEDEFS(typename Digraph); |
|
241 |
|
242 private: |
|
243 |
|
244 |
|
245 std::ostream* _os; |
|
246 bool local_os; |
|
247 |
|
248 Digraph& _digraph; |
|
249 |
|
250 std::string _nodes_caption; |
|
251 std::string _arcs_caption; |
|
252 std::string _attributes_caption; |
|
253 |
|
254 typedef std::map<Node, std::string> NodeIndex; |
|
255 NodeIndex _node_index; |
|
256 typedef std::map<Arc, std::string> ArcIndex; |
|
257 ArcIndex _arc_index; |
|
258 |
|
259 typedef std::vector<std::pair<std::string, |
|
260 _writer_bits::MapStorageBase<Node>* > > NodeMaps; |
|
261 NodeMaps _node_maps; |
|
262 |
|
263 typedef std::vector<std::pair<std::string, |
|
264 _writer_bits::MapStorageBase<Arc>* > >ArcMaps; |
|
265 ArcMaps _arc_maps; |
|
266 |
|
267 typedef std::vector<std::pair<std::string, |
|
268 _writer_bits::ValueStorageBase*> > Attributes; |
|
269 Attributes _attributes; |
|
270 |
|
271 bool _skip_nodes; |
|
272 bool _skip_arcs; |
|
273 |
|
274 public: |
|
275 |
|
276 /// \e |
|
277 DigraphWriter(std::ostream& is, Digraph& digraph) |
|
278 : _os(&is), local_os(false), _digraph(digraph), |
|
279 _skip_nodes(false), _skip_arcs(false) {} |
|
280 |
|
281 /// \e |
|
282 DigraphWriter(const std::string& fn, Digraph& digraph) |
|
283 : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph), |
|
284 _skip_nodes(false), _skip_arcs(false) {} |
|
285 |
|
286 /// \e |
|
287 DigraphWriter(const char* fn, Digraph& digraph) |
|
288 : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph), |
|
289 _skip_nodes(false), _skip_arcs(false) {} |
|
290 |
|
291 DigraphWriter(DigraphWriter& other) |
|
292 : _os(other._os), local_os(other.local_os), _digraph(other._digraph), |
|
293 _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) { |
|
294 |
|
295 other.is = 0; |
|
296 other.local_os = false; |
|
297 |
|
298 _node_index.swap(other._node_index); |
|
299 _arc_index.swap(other._arc_index); |
|
300 |
|
301 _node_maps.swap(other._node_maps); |
|
302 _arc_maps.swap(other._arc_maps); |
|
303 _attributes.swap(other._attributes); |
|
304 |
|
305 _nodes_caption = other._nodes_caption; |
|
306 _arcs_caption = other._arcs_caption; |
|
307 _attributes_caption = other._attributes_caption; |
|
308 } |
|
309 |
|
310 /// \e |
|
311 ~DigraphWriter() { |
|
312 for (typename NodeMaps::iterator it = _node_maps.begin(); |
|
313 it != _node_maps.end(); ++it) { |
|
314 delete it->second; |
|
315 } |
|
316 |
|
317 for (typename ArcMaps::iterator it = _arc_maps.begin(); |
|
318 it != _arc_maps.end(); ++it) { |
|
319 delete it->second; |
|
320 } |
|
321 |
|
322 for (typename Attributes::iterator it = _attributes.begin(); |
|
323 it != _attributes.end(); ++it) { |
|
324 delete it->second; |
|
325 } |
|
326 |
|
327 if (local_os) { |
|
328 delete _os; |
|
329 } |
|
330 } |
|
331 |
|
332 private: |
|
333 |
|
334 DigraphWriter& operator=(const DigraphWriter&); |
|
335 |
|
336 public: |
|
337 |
|
338 /// \e |
|
339 template <typename Map> |
|
340 DigraphWriter& nodeMap(const std::string& caption, const Map& map) { |
|
341 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>(); |
|
342 _writer_bits::MapStorageBase<Node>* storage = |
|
343 new _writer_bits::MapStorage<Node, Map>(map); |
|
344 _node_maps.push_back(std::make_pair(caption, storage)); |
|
345 return *this; |
|
346 } |
|
347 |
|
348 /// \e |
|
349 template <typename Map, typename Converter> |
|
350 DigraphWriter& nodeMap(const std::string& caption, const Map& map, |
|
351 const Converter& converter = Converter()) { |
|
352 checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>(); |
|
353 _writer_bits::MapStorageBase<Node>* storage = |
|
354 new _writer_bits::MapStorage<Node, Map, Converter>(map, converter); |
|
355 _node_maps.push_back(std::make_pair(caption, storage)); |
|
356 return *this; |
|
357 } |
|
358 |
|
359 /// \e |
|
360 template <typename Map> |
|
361 DigraphWriter& arcMap(const std::string& caption, const Map& map) { |
|
362 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>(); |
|
363 _writer_bits::MapStorageBase<Arc>* storage = |
|
364 new _writer_bits::MapStorage<Arc, Map>(map); |
|
365 _arc_maps.push_back(std::make_pair(caption, storage)); |
|
366 return *this; |
|
367 } |
|
368 |
|
369 /// \e |
|
370 template <typename Map, typename Converter> |
|
371 DigraphWriter& arcMap(const std::string& caption, const Map& map, |
|
372 const Converter& converter = Converter()) { |
|
373 checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>(); |
|
374 _writer_bits::MapStorageBase<Arc>* storage = |
|
375 new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter); |
|
376 _arc_maps.push_back(std::make_pair(caption, storage)); |
|
377 return *this; |
|
378 } |
|
379 |
|
380 /// \e |
|
381 template <typename Value> |
|
382 DigraphWriter& attribute(const std::string& caption, const Value& value) { |
|
383 _writer_bits::ValueStorageBase* storage = |
|
384 new _writer_bits::ValueStorage<Value>(value); |
|
385 _attributes.push_back(std::make_pair(caption, storage)); |
|
386 return *this; |
|
387 } |
|
388 |
|
389 /// \e |
|
390 template <typename Value, typename Converter> |
|
391 DigraphWriter& attribute(const std::string& caption, const Value& value, |
|
392 const Converter& converter = Converter()) { |
|
393 _writer_bits::ValueStorageBase* storage = |
|
394 new _writer_bits::ValueStorage<Value, Converter>(value, converter); |
|
395 _attributes.push_back(std::make_pair(caption, storage)); |
|
396 return *this; |
|
397 } |
|
398 |
|
399 /// \e |
|
400 DigraphWriter& node(const std::string& caption, const Node& node) { |
|
401 typedef _writer_bits::MapLookUpConverter<Node> Converter; |
|
402 Converter converter(_node_index); |
|
403 _writer_bits::ValueStorageBase* storage = |
|
404 new _writer_bits::ValueStorage<Node, Converter>(node, converter); |
|
405 _attributes.push_back(std::make_pair(caption, storage)); |
|
406 return *this; |
|
407 } |
|
408 |
|
409 /// \e |
|
410 DigraphWriter& arc(const std::string& caption, const Arc& arc) { |
|
411 typedef _writer_bits::MapLookUpConverter<Arc> Converter; |
|
412 Converter converter(_arc_index); |
|
413 _writer_bits::ValueStorageBase* storage = |
|
414 new _writer_bits::ValueStorage<Arc, Converter>(arc, converter); |
|
415 _attributes.push_back(std::make_pair(caption, storage)); |
|
416 return *this; |
|
417 } |
|
418 |
|
419 /// \e |
|
420 DigraphWriter& nodes(const std::string& caption) { |
|
421 _nodes_caption = caption; |
|
422 return *this; |
|
423 } |
|
424 |
|
425 /// \e |
|
426 DigraphWriter& arcs(const std::string& caption) { |
|
427 _arcs_caption = caption; |
|
428 return *this; |
|
429 } |
|
430 |
|
431 /// \e |
|
432 DigraphWriter& attributes(const std::string& caption) { |
|
433 _attributes_caption = caption; |
|
434 return *this; |
|
435 } |
|
436 |
|
437 DigraphWriter& skipNodes() { |
|
438 LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member"); |
|
439 return *this; |
|
440 } |
|
441 |
|
442 DigraphWriter& skipArcs() { |
|
443 LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member"); |
|
444 return *this; |
|
445 } |
|
446 |
|
447 private: |
|
448 |
|
449 void writeNodes() { |
|
450 _writer_bits::MapStorageBase<Node>* label = 0; |
|
451 for (typename NodeMaps::iterator it = _node_maps.begin(); |
|
452 it != _node_maps.end(); ++it) { |
|
453 if (it->first == "label") { |
|
454 label = it->second; |
|
455 break; |
|
456 } |
|
457 } |
|
458 |
|
459 *_os << "@nodes"; |
|
460 if (!_nodes_caption.empty()) { |
|
461 *_os << ' ' << _nodes_caption; |
|
462 } |
|
463 *_os << std::endl; |
|
464 |
|
465 if (label == 0) { |
|
466 *_os << "label" << '\t'; |
|
467 } |
|
468 for (typename NodeMaps::iterator it = _node_maps.begin(); |
|
469 it != _node_maps.end(); ++it) { |
|
470 *_os << it->first << '\t'; |
|
471 } |
|
472 *_os << std::endl; |
|
473 |
|
474 std::vector<Node> nodes; |
|
475 for (NodeIt n(_digraph); n != INVALID; ++n) { |
|
476 nodes.push_back(n); |
|
477 } |
|
478 |
|
479 if (label == 0) { |
|
480 IdMap<Digraph, Node> id_map(_digraph); |
|
481 _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map); |
|
482 std::sort(nodes.begin(), nodes.end(), id_less); |
|
483 } else { |
|
484 label->sort(nodes); |
|
485 } |
|
486 |
|
487 for (int i = 0; i < static_cast<int>(nodes.size()); ++i) { |
|
488 Node n = nodes[i]; |
|
489 if (label == 0) { |
|
490 std::ostringstream os; |
|
491 os << _digraph.id(n); |
|
492 _writer_bits::writeToken(*_os, os.str()); |
|
493 *_os << '\t'; |
|
494 _node_index.insert(std::make_pair(n, os.str())); |
|
495 } |
|
496 for (typename NodeMaps::iterator it = _node_maps.begin(); |
|
497 it != _node_maps.end(); ++it) { |
|
498 std::string value = it->second->get(n); |
|
499 _writer_bits::writeToken(*_os, value); |
|
500 if (it->first == "label") { |
|
501 _node_index.insert(std::make_pair(n, value)); |
|
502 } |
|
503 *_os << '\t'; |
|
504 } |
|
505 *_os << std::endl; |
|
506 } |
|
507 } |
|
508 |
|
509 void writeArcs() { |
|
510 _writer_bits::MapStorageBase<Arc>* label = 0; |
|
511 for (typename ArcMaps::iterator it = _arc_maps.begin(); |
|
512 it != _arc_maps.end(); ++it) { |
|
513 if (it->first == "label") { |
|
514 label = it->second; |
|
515 break; |
|
516 } |
|
517 } |
|
518 |
|
519 *_os << "@arcs"; |
|
520 if (!_arcs_caption.empty()) { |
|
521 *_os << ' ' << _arcs_caption; |
|
522 } |
|
523 *_os << std::endl; |
|
524 |
|
525 *_os << '\t' << '\t'; |
|
526 if (label == 0) { |
|
527 *_os << "label" << '\t'; |
|
528 } |
|
529 for (typename ArcMaps::iterator it = _arc_maps.begin(); |
|
530 it != _arc_maps.end(); ++it) { |
|
531 *_os << it->first << '\t'; |
|
532 } |
|
533 *_os << std::endl; |
|
534 |
|
535 std::vector<Arc> arcs; |
|
536 for (ArcIt n(_digraph); n != INVALID; ++n) { |
|
537 arcs.push_back(n); |
|
538 } |
|
539 |
|
540 if (label == 0) { |
|
541 IdMap<Digraph, Arc> id_map(_digraph); |
|
542 _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map); |
|
543 std::sort(arcs.begin(), arcs.end(), id_less); |
|
544 } else { |
|
545 label->sort(arcs); |
|
546 } |
|
547 |
|
548 for (int i = 0; i < static_cast<int>(arcs.size()); ++i) { |
|
549 Arc a = arcs[i]; |
|
550 _writer_bits::writeToken(*_os, _node_index. |
|
551 find(_digraph.source(a))->second); |
|
552 *_os << '\t'; |
|
553 _writer_bits::writeToken(*_os, _node_index. |
|
554 find(_digraph.target(a))->second); |
|
555 *_os << '\t'; |
|
556 if (label == 0) { |
|
557 std::ostringstream os; |
|
558 os << _digraph.id(a); |
|
559 _writer_bits::writeToken(*_os, os.str()); |
|
560 *_os << '\t'; |
|
561 _arc_index.insert(std::make_pair(a, os.str())); |
|
562 } |
|
563 for (typename ArcMaps::iterator it = _arc_maps.begin(); |
|
564 it != _arc_maps.end(); ++it) { |
|
565 std::string value = it->second->get(a); |
|
566 _writer_bits::writeToken(*_os, value); |
|
567 if (it->first == "label") { |
|
568 _arc_index.insert(std::make_pair(a, value)); |
|
569 } |
|
570 *_os << '\t'; |
|
571 } |
|
572 *_os << std::endl; |
|
573 } |
|
574 } |
|
575 |
|
576 void writeAttributes() { |
|
577 if (_attributes.empty()) return; |
|
578 *_os << "@attributes"; |
|
579 if (!_attributes_caption.empty()) { |
|
580 *_os << ' ' << _attributes_caption; |
|
581 } |
|
582 *_os << std::endl; |
|
583 for (typename Attributes::iterator it = _attributes.begin(); |
|
584 it != _attributes.end(); ++it) { |
|
585 *_os << it->first << ' '; |
|
586 _writer_bits::writeToken(*_os, it->second->get()); |
|
587 *_os << std::endl; |
|
588 } |
|
589 } |
|
590 |
|
591 public: |
|
592 |
|
593 /// \e |
|
594 void run() { |
|
595 if (!_skip_nodes) { |
|
596 writeNodes(); |
|
597 } |
|
598 if (!_skip_arcs) { |
|
599 writeArcs(); |
|
600 } |
|
601 writeAttributes(); |
|
602 } |
|
603 |
|
604 /// \e |
|
605 std::ostream& stream() { |
|
606 return *_os; |
|
607 } |
|
608 }; |
|
609 |
|
610 template <typename Digraph> |
|
611 DigraphWriter<Digraph> digraphWriter(std::istream& is, Digraph& digraph) { |
|
612 return DigraphWriter<Digraph>(is, digraph); |
|
613 } |
|
614 |
|
615 template <typename Digraph> |
|
616 DigraphWriter<Digraph> digraphWriter(const std::string& fn, |
|
617 Digraph& digraph) { |
|
618 return DigraphWriter<Digraph>(fn, digraph); |
|
619 } |
|
620 |
|
621 template <typename Digraph> |
|
622 DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) { |
|
623 return DigraphWriter<Digraph>(fn, digraph); |
|
624 } |
|
625 } |
|
626 |
|
627 #endif |