COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/lgf_writer.h @ 163:c82fd9568d75

Last change on this file since 163:c82fd9568d75 was 163:c82fd9568d75, checked in by Balazs Dezso <deba@…>, 11 years ago

Bug fixes and improvements in LGF IO

File size: 20.0 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          std::ios::fmtflags flags = os.flags();
199          os << '\\' << std::oct << static_cast<int>(c);
200          os.flags(flags);
201        } else {
202          os << c;
203        }
204        return;
205      }     
206    }
207
208    bool requireEscape(const std::string& str) {
209      if (str.empty() || str[0] == '@') return true;
210      std::istringstream is(str);
211      char c;
212      while (is.get(c)) {
213        if (isWhiteSpace(c) || isEscaped(c)) {
214          return true;
215        }
216      }
217      return false;
218    }
219   
220    std::ostream& writeToken(std::ostream& os, const std::string& str) {
221
222      if (requireEscape(str)) {
223        os << '\"';
224        for (std::string::const_iterator it = str.begin();
225             it != str.end(); ++it) {
226          writeEscape(os, *it);
227        }       
228        os << '\"';
229      } else {
230        os << str;
231      }
232      return os;
233    }
234
235  }
236 
237  /// \ingroup lemon_io
238  /// 
239  /// \brief LGF writer for directed graphs
240  ///
241  /// This utility writes an \ref lgf-format "LGF" file.
242  ///
243  /// The writing method does a batch processing. The user creates a
244  /// writer object, then various writing rules can be added to the
245  /// writer, and eventually the writing is executed with the \c run()
246  /// member function. A map writing rule can be added to the writer
247  /// with the \c nodeMap() or \c arcMap() members. An optional
248  /// converter parameter can also be added as a standard functor
249  /// converting from the value type of the map to std::string. If it
250  /// is set, it will determine how the map's value type is written to
251  /// the output stream. If the functor is not set, then a default
252  /// conversion will be used. The \c attribute(), \c node() and \c
253  /// arc() functions are used to add attribute writing rules.
254  ///
255  ///\code
256  ///     DigraphWriter<Digraph>(std::cout, digraph).
257  ///       nodeMap("coordinates", coord_map).
258  ///       nodeMap("size", size).
259  ///       nodeMap("title", title).
260  ///       arcMap("capacity", cap_map).
261  ///       node("source", src).
262  ///       node("target", trg).
263  ///       attribute("caption", caption).
264  ///       run();
265  ///\endcode
266  ///
267  ///
268  /// By default, the writer does not write additional captions to the
269  /// sections, but they can be give as an optional parameter of
270  /// the \c nodes(), \c arcs() or \c
271  /// attributes() functions.
272  ///
273  /// The \c skipNodes() and \c skipArcs() functions forbid the
274  /// writing of the sections. If two arc sections should be written
275  /// to the output, it can be done in two passes, the first pass
276  /// writes the node section and the first arc section, then the
277  /// second pass skips the node section and writes just the arc
278  /// section to the stream. The output stream can be retrieved with
279  /// the \c ostream() function, hence the second pass can append its
280  /// output to the output of the first pass.
281  template <typename _Digraph>
282  class DigraphWriter {
283  public:
284
285    typedef _Digraph Digraph;
286    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
287   
288  private:
289
290
291    std::ostream* _os;
292    bool local_os;
293
294    Digraph& _digraph;
295
296    std::string _nodes_caption;
297    std::string _arcs_caption;
298    std::string _attributes_caption;
299   
300    typedef std::map<Node, std::string> NodeIndex;
301    NodeIndex _node_index;
302    typedef std::map<Arc, std::string> ArcIndex;
303    ArcIndex _arc_index;
304
305    typedef std::vector<std::pair<std::string,
306      _writer_bits::MapStorageBase<Node>* > > NodeMaps;   
307    NodeMaps _node_maps;
308
309    typedef std::vector<std::pair<std::string,
310      _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
311    ArcMaps _arc_maps;
312
313    typedef std::vector<std::pair<std::string,
314      _writer_bits::ValueStorageBase*> > Attributes;
315    Attributes _attributes;
316
317    bool _skip_nodes;
318    bool _skip_arcs;
319
320  public:
321
322    /// \brief Constructor
323    ///
324    /// Construct a directed graph writer, which writes to the given
325    /// output stream.
326    DigraphWriter(std::ostream& is, Digraph& digraph)
327      : _os(&is), local_os(false), _digraph(digraph),
328        _skip_nodes(false), _skip_arcs(false) {}
329
330    /// \brief Constructor
331    ///
332    /// Construct a directed graph writer, which writes to the given
333    /// output file.
334    DigraphWriter(const std::string& fn, Digraph& digraph)
335      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
336        _skip_nodes(false), _skip_arcs(false) {}
337
338    /// \brief Constructor
339    ///
340    /// Construct a directed graph writer, which writes to the given
341    /// output file.
342    DigraphWriter(const char* fn, Digraph& digraph)
343      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
344        _skip_nodes(false), _skip_arcs(false) {}
345
346    /// \brief Copy constructor
347    ///
348    /// The copy constructor transfers all data from the other writer,
349    /// therefore the copied writer will not be usable more.
350    DigraphWriter(DigraphWriter& other)
351      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
352        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
353
354      other._os = 0;
355      other.local_os = false;
356
357      _node_index.swap(other._node_index);
358      _arc_index.swap(other._arc_index);
359
360      _node_maps.swap(other._node_maps);
361      _arc_maps.swap(other._arc_maps);
362      _attributes.swap(other._attributes);
363
364      _nodes_caption = other._nodes_caption;
365      _arcs_caption = other._arcs_caption;
366      _attributes_caption = other._attributes_caption;
367    }
368
369    /// \brief Destructor
370    ~DigraphWriter() {
371      for (typename NodeMaps::iterator it = _node_maps.begin();
372           it != _node_maps.end(); ++it) {
373        delete it->second;
374      }
375
376      for (typename ArcMaps::iterator it = _arc_maps.begin();
377           it != _arc_maps.end(); ++it) {
378        delete it->second;
379      }
380
381      for (typename Attributes::iterator it = _attributes.begin();
382           it != _attributes.end(); ++it) {
383        delete it->second;
384      }
385
386      if (local_os) {
387        delete _os;
388      }
389    }
390
391  private:
392   
393    DigraphWriter& operator=(const DigraphWriter&);
394
395  public:
396
397    /// \name Writing rules
398    /// @{
399   
400    /// \brief Node map reading rule
401    ///
402    /// Add a node map reading rule to the writer.
403    template <typename Map>
404    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
405      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
406      _writer_bits::MapStorageBase<Node>* storage =
407        new _writer_bits::MapStorage<Node, Map>(map);
408      _node_maps.push_back(std::make_pair(caption, storage));
409      return *this;
410    }
411
412    /// \brief Node map writing rule
413    ///
414    /// Add a node map writing rule with specialized converter to the
415    /// writer.
416    template <typename Map, typename Converter>
417    DigraphWriter& nodeMap(const std::string& caption, const Map& map,
418                           const Converter& converter = Converter()) {
419      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
420      _writer_bits::MapStorageBase<Node>* storage =
421        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
422      _node_maps.push_back(std::make_pair(caption, storage));
423      return *this;
424    }
425
426    /// \brief Arc map writing rule
427    ///
428    /// Add an arc map writing rule to the writer.
429    template <typename Map>
430    DigraphWriter& arcMap(const std::string& caption, const Map& map) {
431      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
432      _writer_bits::MapStorageBase<Arc>* storage =
433        new _writer_bits::MapStorage<Arc, Map>(map);
434      _arc_maps.push_back(std::make_pair(caption, storage));
435      return *this;
436    }
437
438    /// \brief Arc map writing rule
439    ///
440    /// Add an arc map writing rule with specialized converter to the
441    /// writer.
442    template <typename Map, typename Converter>
443    DigraphWriter& arcMap(const std::string& caption, const Map& map,
444                          const Converter& converter = Converter()) {
445      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
446      _writer_bits::MapStorageBase<Arc>* storage =
447        new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
448      _arc_maps.push_back(std::make_pair(caption, storage));
449      return *this;
450    }
451
452    /// \brief Attribute writing rule
453    ///
454    /// Add an attribute writing rule to the writer.
455    template <typename Value>
456    DigraphWriter& attribute(const std::string& caption, const Value& value) {
457      _writer_bits::ValueStorageBase* storage =
458        new _writer_bits::ValueStorage<Value>(value);
459      _attributes.push_back(std::make_pair(caption, storage));
460      return *this;
461    }
462
463    /// \brief Attribute writing rule
464    ///
465    /// Add an attribute writing rule with specialized converter to the
466    /// writer.
467    template <typename Value, typename Converter>
468    DigraphWriter& attribute(const std::string& caption, const Value& value,
469                             const Converter& converter = Converter()) {
470      _writer_bits::ValueStorageBase* storage =
471        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
472      _attributes.push_back(std::make_pair(caption, storage));
473      return *this;
474    }
475
476    /// \brief Node writing rule
477    ///
478    /// Add a node writing rule to the writer.
479    DigraphWriter& node(const std::string& caption, const Node& node) {
480      typedef _writer_bits::MapLookUpConverter<Node> Converter;
481      Converter converter(_node_index);
482      _writer_bits::ValueStorageBase* storage =
483        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
484      _attributes.push_back(std::make_pair(caption, storage));
485      return *this;
486    }
487
488    /// \brief Arc writing rule
489    ///
490    /// Add an arc writing rule to writer.
491    DigraphWriter& arc(const std::string& caption, const Arc& arc) {
492      typedef _writer_bits::MapLookUpConverter<Arc> Converter;
493      Converter converter(_arc_index);
494      _writer_bits::ValueStorageBase* storage =
495        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
496      _attributes.push_back(std::make_pair(caption, storage));
497      return *this;
498    }
499
500    /// \name Select section by name
501    /// @{
502
503    /// \brief Set \c \@nodes section to be read
504    ///
505    /// Set \c \@nodes section to be read
506    DigraphWriter& nodes(const std::string& caption) {
507      _nodes_caption = caption;
508      return *this;
509    }
510
511    /// \brief Set \c \@arcs section to be read
512    ///
513    /// Set \c \@arcs section to be read
514    DigraphWriter& arcs(const std::string& caption) {
515      _arcs_caption = caption;
516      return *this;
517    }
518
519    /// \brief Set \c \@attributes section to be read
520    ///
521    /// Set \c \@attributes section to be read
522    DigraphWriter& attributes(const std::string& caption) {
523      _attributes_caption = caption;
524      return *this;
525    }
526
527    /// \name Skipping section
528    /// @{
529
530    /// \brief Skip writing the node set
531    ///
532    /// The \c \@nodes section will be not written to the stream.
533    DigraphWriter& skipNodes() {
534      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
535      return *this;
536    }
537
538    /// \brief Skip writing arc set
539    ///
540    /// The \c \@arcs section will be not written to the stream.
541    DigraphWriter& skipArcs() {
542      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
543      return *this;
544    }
545
546    /// @}
547
548  private:
549
550    void writeNodes() {
551      _writer_bits::MapStorageBase<Node>* label = 0;
552      for (typename NodeMaps::iterator it = _node_maps.begin();
553           it != _node_maps.end(); ++it) {
554        if (it->first == "label") {
555          label = it->second;
556          break;
557        }
558      }
559
560      *_os << "@nodes";
561      if (!_nodes_caption.empty()) {
562        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
563      }
564      *_os << std::endl;
565
566      if (label == 0) {
567        *_os << "label" << '\t';
568      }
569      for (typename NodeMaps::iterator it = _node_maps.begin();
570           it != _node_maps.end(); ++it) {
571        _writer_bits::writeToken(*_os, it->first) << '\t';
572      }
573      *_os << std::endl;
574
575      std::vector<Node> nodes;
576      for (NodeIt n(_digraph); n != INVALID; ++n) {
577        nodes.push_back(n);
578      }
579     
580      if (label == 0) {
581        IdMap<Digraph, Node> id_map(_digraph);
582        _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
583        std::sort(nodes.begin(), nodes.end(), id_less);
584      } else {
585        label->sort(nodes);
586      }
587
588      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
589        Node n = nodes[i];
590        if (label == 0) {
591          std::ostringstream os;
592          os << _digraph.id(n);
593          _writer_bits::writeToken(*_os, os.str());
594          *_os << '\t';
595          _node_index.insert(std::make_pair(n, os.str()));
596        }
597        for (typename NodeMaps::iterator it = _node_maps.begin();
598             it != _node_maps.end(); ++it) {
599          std::string value = it->second->get(n);
600          _writer_bits::writeToken(*_os, value);
601          if (it->first == "label") {
602            _node_index.insert(std::make_pair(n, value));
603          }
604          *_os << '\t';
605        }
606        *_os << std::endl;
607      }
608    }
609
610    void writeArcs() {
611      _writer_bits::MapStorageBase<Arc>* label = 0;
612      for (typename ArcMaps::iterator it = _arc_maps.begin();
613           it != _arc_maps.end(); ++it) {
614        if (it->first == "label") {
615          label = it->second;
616          break;
617        }
618      }
619
620      *_os << "@arcs";
621      if (!_arcs_caption.empty()) {
622        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
623      }
624      *_os << std::endl;
625
626      *_os << '\t' << '\t';
627      if (label == 0) {
628        *_os << "label" << '\t';
629      }
630      for (typename ArcMaps::iterator it = _arc_maps.begin();
631           it != _arc_maps.end(); ++it) {
632        _writer_bits::writeToken(*_os, it->first) << '\t';
633      }
634      *_os << std::endl;
635
636      std::vector<Arc> arcs;
637      for (ArcIt n(_digraph); n != INVALID; ++n) {
638        arcs.push_back(n);
639      }
640     
641      if (label == 0) {
642        IdMap<Digraph, Arc> id_map(_digraph);
643        _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
644        std::sort(arcs.begin(), arcs.end(), id_less);
645      } else {
646        label->sort(arcs);
647      }
648
649      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
650        Arc a = arcs[i];
651        _writer_bits::writeToken(*_os, _node_index.
652                                 find(_digraph.source(a))->second);
653        *_os << '\t';
654        _writer_bits::writeToken(*_os, _node_index.
655                                 find(_digraph.target(a))->second);
656        *_os << '\t';
657        if (label == 0) {
658          std::ostringstream os;
659          os << _digraph.id(a);
660          _writer_bits::writeToken(*_os, os.str());
661          *_os << '\t';
662          _arc_index.insert(std::make_pair(a, os.str()));
663        }
664        for (typename ArcMaps::iterator it = _arc_maps.begin();
665             it != _arc_maps.end(); ++it) {
666          std::string value = it->second->get(a);
667          _writer_bits::writeToken(*_os, value);
668          if (it->first == "label") {
669            _arc_index.insert(std::make_pair(a, value));
670          }
671          *_os << '\t';
672        }
673        *_os << std::endl;
674      }
675    }
676
677    void writeAttributes() {
678      if (_attributes.empty()) return;
679      *_os << "@attributes";
680      if (!_attributes_caption.empty()) {
681        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
682      }
683      *_os << std::endl;
684      for (typename Attributes::iterator it = _attributes.begin();
685           it != _attributes.end(); ++it) {
686        _writer_bits::writeToken(*_os, it->first) << ' ';
687        _writer_bits::writeToken(*_os, it->second->get());
688        *_os << std::endl;
689      }
690    }
691   
692  public:
693   
694    /// \name Execution of the writer   
695    /// @{
696
697    /// \brief Start the batch processing
698    ///
699    /// This function starts the batch processing
700    void run() {
701      if (!_skip_nodes) {
702        writeNodes();
703      }
704      if (!_skip_arcs) {     
705        writeArcs();
706      }
707      writeAttributes();
708    }
709
710    /// \brief Gives back the stream of the writer
711    ///
712    /// Gives back the stream of the writer
713    std::ostream& ostream() {
714      return *_os;
715    }
716
717    /// @}
718  };
719
720  /// \relates DigraphWriter
721  template <typename Digraph>
722  DigraphWriter<Digraph> digraphWriter(std::ostream& os, Digraph& digraph) {
723    DigraphWriter<Digraph> tmp(os, digraph);
724    return tmp;
725  }
726
727  /// \relates DigraphWriter
728  template <typename Digraph>
729  DigraphWriter<Digraph> digraphWriter(const std::string& fn,
730                                       Digraph& digraph) {
731    DigraphWriter<Digraph> tmp(fn, digraph);
732    return tmp;
733  }
734
735  /// \relates DigraphWriter
736  template <typename Digraph>
737  DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
738    DigraphWriter<Digraph> tmp(fn, digraph);
739    return tmp;
740  }
741}
742
743#endif
Note: See TracBrowser for help on using the repository browser.