COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/lgf_writer.h @ 148:4e2581021300

Last change on this file since 148:4e2581021300 was 148:4e2581021300, checked in by Balazs Dezso <deba@…>, 17 years ago

Revert 356930927a71 and add TEMPLATE_GRAPH_TYPEDEFS instead (ticket #89)

File size: 15.6 KB
Line 
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
39namespace 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    TEMPLATE_DIGRAPH_TYPEDEFS(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
Note: See TracBrowser for help on using the repository browser.