COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_writer.h @ 156:e561aa7675de

Last change on this file since 156:e561aa7675de was 156:e561aa7675de, checked in by Alpar Juttner <alpar@…>, 11 years ago

More flexible header names in .lgf + largely improved doc

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