COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_writer.h @ 1270:dceba191c00d

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

Apply unify-sources.sh to the source tree

File size: 82.3 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
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 \ref lgf-format "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/core.h>
37#include <lemon/maps.h>
38
39#include <lemon/concept_check.h>
40#include <lemon/concepts/maps.h>
41
42namespace lemon {
43
44  namespace _writer_bits {
45
46    template <typename Value>
47    struct DefaultConverter {
48      std::string operator()(const Value& value) {
49        std::ostringstream os;
50        os << value;
51        return os.str();
52      }
53    };
54
55    template <typename T>
56    bool operator<(const T&, const T&) {
57      throw FormatError("Label map is not comparable");
58    }
59
60    template <typename _Map>
61    class MapLess {
62    public:
63      typedef _Map Map;
64      typedef typename Map::Key Item;
65
66    private:
67      const Map& _map;
68
69    public:
70      MapLess(const Map& map) : _map(map) {}
71
72      bool operator()(const Item& left, const Item& right) {
73        return _map[left] < _map[right];
74      }
75    };
76
77    template <typename _Graph, bool _dir, typename _Map>
78    class GraphArcMapLess {
79    public:
80      typedef _Map Map;
81      typedef _Graph Graph;
82      typedef typename Graph::Edge Item;
83
84    private:
85      const Graph& _graph;
86      const Map& _map;
87
88    public:
89      GraphArcMapLess(const Graph& graph, const Map& map)
90        : _graph(graph), _map(map) {}
91
92      bool operator()(const Item& left, const Item& right) {
93        return _map[_graph.direct(left, _dir)] <
94          _map[_graph.direct(right, _dir)];
95      }
96    };
97
98    template <typename _Item>
99    class MapStorageBase {
100    public:
101      typedef _Item Item;
102
103    public:
104      MapStorageBase() {}
105      virtual ~MapStorageBase() {}
106
107      virtual std::string get(const Item& item) = 0;
108      virtual void sort(std::vector<Item>&) = 0;
109    };
110
111    template <typename _Item, typename _Map,
112              typename _Converter = DefaultConverter<typename _Map::Value> >
113    class MapStorage : public MapStorageBase<_Item> {
114    public:
115      typedef _Map Map;
116      typedef _Converter Converter;
117      typedef _Item Item;
118
119    private:
120      const Map& _map;
121      Converter _converter;
122
123    public:
124      MapStorage(const Map& map, const Converter& converter = Converter())
125        : _map(map), _converter(converter) {}
126      virtual ~MapStorage() {}
127
128      virtual std::string get(const Item& item) {
129        return _converter(_map[item]);
130      }
131      virtual void sort(std::vector<Item>& items) {
132        MapLess<Map> less(_map);
133        std::sort(items.begin(), items.end(), less);
134      }
135    };
136
137    template <typename _Graph, bool _dir, typename _Map,
138              typename _Converter = DefaultConverter<typename _Map::Value> >
139    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
140    public:
141      typedef _Map Map;
142      typedef _Converter Converter;
143      typedef _Graph Graph;
144      typedef typename Graph::Edge Item;
145      static const bool dir = _dir;
146
147    private:
148      const Graph& _graph;
149      const Map& _map;
150      Converter _converter;
151
152    public:
153      GraphArcMapStorage(const Graph& graph, const Map& map,
154                         const Converter& converter = Converter())
155        : _graph(graph), _map(map), _converter(converter) {}
156      virtual ~GraphArcMapStorage() {}
157
158      virtual std::string get(const Item& item) {
159        return _converter(_map[_graph.direct(item, dir)]);
160      }
161      virtual void sort(std::vector<Item>& items) {
162        GraphArcMapLess<Graph, dir, Map> less(_graph, _map);
163        std::sort(items.begin(), items.end(), less);
164      }
165    };
166
167    class ValueStorageBase {
168    public:
169      ValueStorageBase() {}
170      virtual ~ValueStorageBase() {}
171
172      virtual std::string get() = 0;
173    };
174
175    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
176    class ValueStorage : public ValueStorageBase {
177    public:
178      typedef _Value Value;
179      typedef _Converter Converter;
180
181    private:
182      const Value& _value;
183      Converter _converter;
184
185    public:
186      ValueStorage(const Value& value, const Converter& converter = Converter())
187        : _value(value), _converter(converter) {}
188
189      virtual std::string get() {
190        return _converter(_value);
191      }
192    };
193
194    template <typename Value,
195              typename Map = std::map<Value, std::string> >
196    struct MapLookUpConverter {
197      const Map& _map;
198
199      MapLookUpConverter(const Map& map)
200        : _map(map) {}
201
202      std::string operator()(const Value& value) {
203        typename Map::const_iterator it = _map.find(value);
204        if (it == _map.end()) {
205          throw FormatError("Item not found");
206        }
207        return it->second;
208      }
209    };
210
211    template <typename Value,
212              typename Map1 = std::map<Value, std::string>,
213              typename Map2 = std::map<Value, std::string> >
214    struct DoubleMapLookUpConverter {
215      const Map1& _map1;
216      const Map2& _map2;
217
218      DoubleMapLookUpConverter(const Map1& map1, const Map2& map2)
219        : _map1(map1), _map2(map2) {}
220
221      std::string operator()(const Value& value) {
222        typename Map1::const_iterator it1 = _map1.find(value);
223        typename Map1::const_iterator it2 = _map2.find(value);
224        if (it1 == _map1.end()) {
225          if (it2 == _map2.end()) {
226            throw FormatError("Item not found");
227          } else {
228            return it2->second;
229          }
230        } else {
231          if (it2 == _map2.end()) {
232            return it1->second;
233          } else {
234            throw FormatError("Item is ambigous");
235          }
236        }
237      }
238    };
239
240    template <typename Graph>
241    struct GraphArcLookUpConverter {
242      const Graph& _graph;
243      const std::map<typename Graph::Edge, std::string>& _map;
244
245      GraphArcLookUpConverter(const Graph& graph,
246                              const std::map<typename Graph::Edge,
247                                             std::string>& map)
248        : _graph(graph), _map(map) {}
249
250      std::string operator()(const typename Graph::Arc& val) {
251        typename std::map<typename Graph::Edge, std::string>
252          ::const_iterator it = _map.find(val);
253        if (it == _map.end()) {
254          throw FormatError("Item not found");
255        }
256        return (_graph.direction(val) ? '+' : '-') + it->second;
257      }
258    };
259
260    inline bool isWhiteSpace(char c) {
261      return c == ' ' || c == '\t' || c == '\v' ||
262        c == '\n' || c == '\r' || c == '\f';
263    }
264
265    inline bool isEscaped(char c) {
266      return c == '\\' || c == '\"' || c == '\'' ||
267        c == '\a' || c == '\b';
268    }
269
270    inline static void writeEscape(std::ostream& os, char c) {
271      switch (c) {
272      case '\\':
273        os << "\\\\";
274        return;
275      case '\"':
276        os << "\\\"";
277        return;
278      case '\a':
279        os << "\\a";
280        return;
281      case '\b':
282        os << "\\b";
283        return;
284      case '\f':
285        os << "\\f";
286        return;
287      case '\r':
288        os << "\\r";
289        return;
290      case '\n':
291        os << "\\n";
292        return;
293      case '\t':
294        os << "\\t";
295        return;
296      case '\v':
297        os << "\\v";
298        return;
299      default:
300        if (c < 0x20) {
301          std::ios::fmtflags flags = os.flags();
302          os << '\\' << std::oct << static_cast<int>(c);
303          os.flags(flags);
304        } else {
305          os << c;
306        }
307        return;
308      }
309    }
310
311    inline bool requireEscape(const std::string& str) {
312      if (str.empty() || str[0] == '@') return true;
313      std::istringstream is(str);
314      char c;
315      while (is.get(c)) {
316        if (isWhiteSpace(c) || isEscaped(c)) {
317          return true;
318        }
319      }
320      return false;
321    }
322
323    inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
324
325      if (requireEscape(str)) {
326        os << '\"';
327        for (std::string::const_iterator it = str.begin();
328             it != str.end(); ++it) {
329          writeEscape(os, *it);
330        }
331        os << '\"';
332      } else {
333        os << str;
334      }
335      return os;
336    }
337
338    class Section {
339    public:
340      virtual ~Section() {}
341      virtual void process(std::ostream& os) = 0;
342    };
343
344    template <typename Functor>
345    class LineSection : public Section {
346    private:
347
348      Functor _functor;
349
350    public:
351
352      LineSection(const Functor& functor) : _functor(functor) {}
353      virtual ~LineSection() {}
354
355      virtual void process(std::ostream& os) {
356        std::string line;
357        while (!(line = _functor()).empty()) os << line << std::endl;
358      }
359    };
360
361    template <typename Functor>
362    class StreamSection : public Section {
363    private:
364
365      Functor _functor;
366
367    public:
368
369      StreamSection(const Functor& functor) : _functor(functor) {}
370      virtual ~StreamSection() {}
371
372      virtual void process(std::ostream& os) {
373        _functor(os);
374      }
375    };
376
377  }
378
379  template <typename DGR>
380  class DigraphWriter;
381
382  template <typename TDGR>
383  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
384                                   std::ostream& os = std::cout);
385  template <typename TDGR>
386  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const std::string& fn);
387
388  template <typename TDGR>
389  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn);
390
391
392  /// \ingroup lemon_io
393  ///
394  /// \brief \ref lgf-format "LGF" writer for directed graphs
395  ///
396  /// This utility writes an \ref lgf-format "LGF" file.
397  ///
398  /// The writing method does a batch processing. The user creates a
399  /// writer object, then various writing rules can be added to the
400  /// writer, and eventually the writing is executed with the \c run()
401  /// member function. A map writing rule can be added to the writer
402  /// with the \c nodeMap() or \c arcMap() members. An optional
403  /// converter parameter can also be added as a standard functor
404  /// converting from the value type of the map to \c std::string. If it
405  /// is set, it will determine how the value type of the map is written to
406  /// the output stream. If the functor is not set, then a default
407  /// conversion will be used. The \c attribute(), \c node() and \c
408  /// arc() functions are used to add attribute writing rules.
409  ///
410  ///\code
411  /// DigraphWriter<DGR>(digraph, std::cout).
412  ///   nodeMap("coordinates", coord_map).
413  ///   nodeMap("size", size).
414  ///   nodeMap("title", title).
415  ///   arcMap("capacity", cap_map).
416  ///   node("source", src).
417  ///   node("target", trg).
418  ///   attribute("caption", caption).
419  ///   run();
420  ///\endcode
421  ///
422  ///
423  /// By default, the writer does not write additional captions to the
424  /// sections, but they can be give as an optional parameter of
425  /// the \c nodes(), \c arcs() or \c
426  /// attributes() functions.
427  ///
428  /// The \c skipNodes() and \c skipArcs() functions forbid the
429  /// writing of the sections. If two arc sections should be written
430  /// to the output, it can be done in two passes, the first pass
431  /// writes the node section and the first arc section, then the
432  /// second pass skips the node section and writes just the arc
433  /// section to the stream. The output stream can be retrieved with
434  /// the \c ostream() function, hence the second pass can append its
435  /// output to the output of the first pass.
436  template <typename DGR>
437  class DigraphWriter {
438  public:
439
440    typedef DGR Digraph;
441    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
442
443  private:
444
445
446    std::ostream* _os;
447    bool local_os;
448
449    const DGR& _digraph;
450
451    std::string _nodes_caption;
452    std::string _arcs_caption;
453    std::string _attributes_caption;
454
455    typedef std::map<Node, std::string> NodeIndex;
456    NodeIndex _node_index;
457    typedef std::map<Arc, std::string> ArcIndex;
458    ArcIndex _arc_index;
459
460    typedef std::vector<std::pair<std::string,
461      _writer_bits::MapStorageBase<Node>* > > NodeMaps;
462    NodeMaps _node_maps;
463
464    typedef std::vector<std::pair<std::string,
465      _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
466    ArcMaps _arc_maps;
467
468    typedef std::vector<std::pair<std::string,
469      _writer_bits::ValueStorageBase*> > Attributes;
470    Attributes _attributes;
471
472    bool _skip_nodes;
473    bool _skip_arcs;
474
475  public:
476
477    /// \brief Constructor
478    ///
479    /// Construct a directed graph writer, which writes to the given
480    /// output stream.
481    DigraphWriter(const DGR& digraph, std::ostream& os = std::cout)
482      : _os(&os), local_os(false), _digraph(digraph),
483        _skip_nodes(false), _skip_arcs(false) {}
484
485    /// \brief Constructor
486    ///
487    /// Construct a directed graph writer, which writes to the given
488    /// output file.
489    DigraphWriter(const DGR& digraph, const std::string& fn)
490      : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
491        _skip_nodes(false), _skip_arcs(false) {
492      if (!(*_os)) {
493        delete _os;
494        throw IoError("Cannot write file", fn);
495      }
496    }
497
498    /// \brief Constructor
499    ///
500    /// Construct a directed graph writer, which writes to the given
501    /// output file.
502    DigraphWriter(const DGR& digraph, const char* fn)
503      : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
504        _skip_nodes(false), _skip_arcs(false) {
505      if (!(*_os)) {
506        delete _os;
507        throw IoError("Cannot write file", fn);
508      }
509    }
510
511    /// \brief Destructor
512    ~DigraphWriter() {
513      for (typename NodeMaps::iterator it = _node_maps.begin();
514           it != _node_maps.end(); ++it) {
515        delete it->second;
516      }
517
518      for (typename ArcMaps::iterator it = _arc_maps.begin();
519           it != _arc_maps.end(); ++it) {
520        delete it->second;
521      }
522
523      for (typename Attributes::iterator it = _attributes.begin();
524           it != _attributes.end(); ++it) {
525        delete it->second;
526      }
527
528      if (local_os) {
529        delete _os;
530      }
531    }
532
533  private:
534
535    template <typename TDGR>
536    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
537                                             std::ostream& os);
538    template <typename TDGR>
539    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
540                                             const std::string& fn);
541    template <typename TDGR>
542    friend DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
543                                             const char *fn);
544
545    DigraphWriter(DigraphWriter& other)
546      : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
547        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
548
549      other._os = 0;
550      other.local_os = false;
551
552      _node_index.swap(other._node_index);
553      _arc_index.swap(other._arc_index);
554
555      _node_maps.swap(other._node_maps);
556      _arc_maps.swap(other._arc_maps);
557      _attributes.swap(other._attributes);
558
559      _nodes_caption = other._nodes_caption;
560      _arcs_caption = other._arcs_caption;
561      _attributes_caption = other._attributes_caption;
562    }
563
564    DigraphWriter& operator=(const DigraphWriter&);
565
566  public:
567
568    /// \name Writing Rules
569    /// @{
570
571    /// \brief Node map writing rule
572    ///
573    /// Add a node map writing rule to the writer.
574    template <typename Map>
575    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
576      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
577      _writer_bits::MapStorageBase<Node>* storage =
578        new _writer_bits::MapStorage<Node, Map>(map);
579      _node_maps.push_back(std::make_pair(caption, storage));
580      return *this;
581    }
582
583    /// \brief Node map writing rule
584    ///
585    /// Add a node map writing rule with specialized converter to the
586    /// writer.
587    template <typename Map, typename Converter>
588    DigraphWriter& nodeMap(const std::string& caption, const Map& map,
589                           const Converter& converter = Converter()) {
590      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
591      _writer_bits::MapStorageBase<Node>* storage =
592        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
593      _node_maps.push_back(std::make_pair(caption, storage));
594      return *this;
595    }
596
597    /// \brief Arc map writing rule
598    ///
599    /// Add an arc map writing rule to the writer.
600    template <typename Map>
601    DigraphWriter& arcMap(const std::string& caption, const Map& map) {
602      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
603      _writer_bits::MapStorageBase<Arc>* storage =
604        new _writer_bits::MapStorage<Arc, Map>(map);
605      _arc_maps.push_back(std::make_pair(caption, storage));
606      return *this;
607    }
608
609    /// \brief Arc map writing rule
610    ///
611    /// Add an arc map writing rule with specialized converter to the
612    /// writer.
613    template <typename Map, typename Converter>
614    DigraphWriter& arcMap(const std::string& caption, const Map& map,
615                          const Converter& converter = Converter()) {
616      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
617      _writer_bits::MapStorageBase<Arc>* storage =
618        new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
619      _arc_maps.push_back(std::make_pair(caption, storage));
620      return *this;
621    }
622
623    /// \brief Attribute writing rule
624    ///
625    /// Add an attribute writing rule to the writer.
626    template <typename Value>
627    DigraphWriter& attribute(const std::string& caption, const Value& value) {
628      _writer_bits::ValueStorageBase* storage =
629        new _writer_bits::ValueStorage<Value>(value);
630      _attributes.push_back(std::make_pair(caption, storage));
631      return *this;
632    }
633
634    /// \brief Attribute writing rule
635    ///
636    /// Add an attribute writing rule with specialized converter to the
637    /// writer.
638    template <typename Value, typename Converter>
639    DigraphWriter& attribute(const std::string& caption, const Value& value,
640                             const Converter& converter = Converter()) {
641      _writer_bits::ValueStorageBase* storage =
642        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
643      _attributes.push_back(std::make_pair(caption, storage));
644      return *this;
645    }
646
647    /// \brief Node writing rule
648    ///
649    /// Add a node writing rule to the writer.
650    DigraphWriter& node(const std::string& caption, const Node& node) {
651      typedef _writer_bits::MapLookUpConverter<Node> Converter;
652      Converter converter(_node_index);
653      _writer_bits::ValueStorageBase* storage =
654        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
655      _attributes.push_back(std::make_pair(caption, storage));
656      return *this;
657    }
658
659    /// \brief Arc writing rule
660    ///
661    /// Add an arc writing rule to writer.
662    DigraphWriter& arc(const std::string& caption, const Arc& arc) {
663      typedef _writer_bits::MapLookUpConverter<Arc> Converter;
664      Converter converter(_arc_index);
665      _writer_bits::ValueStorageBase* storage =
666        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
667      _attributes.push_back(std::make_pair(caption, storage));
668      return *this;
669    }
670
671    /// \name Section Captions
672    /// @{
673
674    /// \brief Add an additional caption to the \c \@nodes section
675    ///
676    /// Add an additional caption to the \c \@nodes section.
677    DigraphWriter& nodes(const std::string& caption) {
678      _nodes_caption = caption;
679      return *this;
680    }
681
682    /// \brief Add an additional caption to the \c \@arcs section
683    ///
684    /// Add an additional caption to the \c \@arcs section.
685    DigraphWriter& arcs(const std::string& caption) {
686      _arcs_caption = caption;
687      return *this;
688    }
689
690    /// \brief Add an additional caption to the \c \@attributes section
691    ///
692    /// Add an additional caption to the \c \@attributes section.
693    DigraphWriter& attributes(const std::string& caption) {
694      _attributes_caption = caption;
695      return *this;
696    }
697
698    /// \name Skipping Section
699    /// @{
700
701    /// \brief Skip writing the node set
702    ///
703    /// The \c \@nodes section will not be written to the stream.
704    DigraphWriter& skipNodes() {
705      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
706      _skip_nodes = true;
707      return *this;
708    }
709
710    /// \brief Skip writing arc set
711    ///
712    /// The \c \@arcs section will not be written to the stream.
713    DigraphWriter& skipArcs() {
714      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
715      _skip_arcs = true;
716      return *this;
717    }
718
719    /// @}
720
721  private:
722
723    void writeNodes() {
724      _writer_bits::MapStorageBase<Node>* label = 0;
725      for (typename NodeMaps::iterator it = _node_maps.begin();
726           it != _node_maps.end(); ++it) {
727        if (it->first == "label") {
728          label = it->second;
729          break;
730        }
731      }
732
733      *_os << "@nodes";
734      if (!_nodes_caption.empty()) {
735        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
736      }
737      *_os << std::endl;
738
739      if (label == 0) {
740        *_os << "label" << '\t';
741      }
742      for (typename NodeMaps::iterator it = _node_maps.begin();
743           it != _node_maps.end(); ++it) {
744        _writer_bits::writeToken(*_os, it->first) << '\t';
745      }
746      *_os << std::endl;
747
748      std::vector<Node> nodes;
749      for (NodeIt n(_digraph); n != INVALID; ++n) {
750        nodes.push_back(n);
751      }
752
753      if (label == 0) {
754        IdMap<DGR, Node> id_map(_digraph);
755        _writer_bits::MapLess<IdMap<DGR, Node> > id_less(id_map);
756        std::sort(nodes.begin(), nodes.end(), id_less);
757      } else {
758        label->sort(nodes);
759      }
760
761      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
762        Node n = nodes[i];
763        if (label == 0) {
764          std::ostringstream os;
765          os << _digraph.id(n);
766          _writer_bits::writeToken(*_os, os.str());
767          *_os << '\t';
768          _node_index.insert(std::make_pair(n, os.str()));
769        }
770        for (typename NodeMaps::iterator it = _node_maps.begin();
771             it != _node_maps.end(); ++it) {
772          std::string value = it->second->get(n);
773          _writer_bits::writeToken(*_os, value);
774          if (it->first == "label") {
775            _node_index.insert(std::make_pair(n, value));
776          }
777          *_os << '\t';
778        }
779        *_os << std::endl;
780      }
781    }
782
783    void createNodeIndex() {
784      _writer_bits::MapStorageBase<Node>* label = 0;
785      for (typename NodeMaps::iterator it = _node_maps.begin();
786           it != _node_maps.end(); ++it) {
787        if (it->first == "label") {
788          label = it->second;
789          break;
790        }
791      }
792
793      if (label == 0) {
794        for (NodeIt n(_digraph); n != INVALID; ++n) {
795          std::ostringstream os;
796          os << _digraph.id(n);
797          _node_index.insert(std::make_pair(n, os.str()));
798        }
799      } else {
800        for (NodeIt n(_digraph); n != INVALID; ++n) {
801          std::string value = label->get(n);
802          _node_index.insert(std::make_pair(n, value));
803        }
804      }
805    }
806
807    void writeArcs() {
808      _writer_bits::MapStorageBase<Arc>* label = 0;
809      for (typename ArcMaps::iterator it = _arc_maps.begin();
810           it != _arc_maps.end(); ++it) {
811        if (it->first == "label") {
812          label = it->second;
813          break;
814        }
815      }
816
817      *_os << "@arcs";
818      if (!_arcs_caption.empty()) {
819        _writer_bits::writeToken(*_os << ' ', _arcs_caption);
820      }
821      *_os << std::endl;
822
823      *_os << '\t' << '\t';
824      if (label == 0) {
825        *_os << "label" << '\t';
826      }
827      for (typename ArcMaps::iterator it = _arc_maps.begin();
828           it != _arc_maps.end(); ++it) {
829        _writer_bits::writeToken(*_os, it->first) << '\t';
830      }
831      *_os << std::endl;
832
833      std::vector<Arc> arcs;
834      for (ArcIt n(_digraph); n != INVALID; ++n) {
835        arcs.push_back(n);
836      }
837
838      if (label == 0) {
839        IdMap<DGR, Arc> id_map(_digraph);
840        _writer_bits::MapLess<IdMap<DGR, Arc> > id_less(id_map);
841        std::sort(arcs.begin(), arcs.end(), id_less);
842      } else {
843        label->sort(arcs);
844      }
845
846      for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
847        Arc a = arcs[i];
848        _writer_bits::writeToken(*_os, _node_index.
849                                 find(_digraph.source(a))->second);
850        *_os << '\t';
851        _writer_bits::writeToken(*_os, _node_index.
852                                 find(_digraph.target(a))->second);
853        *_os << '\t';
854        if (label == 0) {
855          std::ostringstream os;
856          os << _digraph.id(a);
857          _writer_bits::writeToken(*_os, os.str());
858          *_os << '\t';
859          _arc_index.insert(std::make_pair(a, os.str()));
860        }
861        for (typename ArcMaps::iterator it = _arc_maps.begin();
862             it != _arc_maps.end(); ++it) {
863          std::string value = it->second->get(a);
864          _writer_bits::writeToken(*_os, value);
865          if (it->first == "label") {
866            _arc_index.insert(std::make_pair(a, value));
867          }
868          *_os << '\t';
869        }
870        *_os << std::endl;
871      }
872    }
873
874    void createArcIndex() {
875      _writer_bits::MapStorageBase<Arc>* label = 0;
876      for (typename ArcMaps::iterator it = _arc_maps.begin();
877           it != _arc_maps.end(); ++it) {
878        if (it->first == "label") {
879          label = it->second;
880          break;
881        }
882      }
883
884      if (label == 0) {
885        for (ArcIt a(_digraph); a != INVALID; ++a) {
886          std::ostringstream os;
887          os << _digraph.id(a);
888          _arc_index.insert(std::make_pair(a, os.str()));
889        }
890      } else {
891        for (ArcIt a(_digraph); a != INVALID; ++a) {
892          std::string value = label->get(a);
893          _arc_index.insert(std::make_pair(a, value));
894        }
895      }
896    }
897
898    void writeAttributes() {
899      if (_attributes.empty()) return;
900      *_os << "@attributes";
901      if (!_attributes_caption.empty()) {
902        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
903      }
904      *_os << std::endl;
905      for (typename Attributes::iterator it = _attributes.begin();
906           it != _attributes.end(); ++it) {
907        _writer_bits::writeToken(*_os, it->first) << ' ';
908        _writer_bits::writeToken(*_os, it->second->get());
909        *_os << std::endl;
910      }
911    }
912
913  public:
914
915    /// \name Execution of the Writer
916    /// @{
917
918    /// \brief Start the batch processing
919    ///
920    /// This function starts the batch processing.
921    void run() {
922      if (!_skip_nodes) {
923        writeNodes();
924      } else {
925        createNodeIndex();
926      }
927      if (!_skip_arcs) {
928        writeArcs();
929      } else {
930        createArcIndex();
931      }
932      writeAttributes();
933    }
934
935    /// \brief Give back the stream of the writer
936    ///
937    /// Give back the stream of the writer.
938    std::ostream& ostream() {
939      return *_os;
940    }
941
942    /// @}
943  };
944
945  /// \ingroup lemon_io
946  ///
947  /// \brief Return a \ref lemon::DigraphWriter "DigraphWriter" class
948  ///
949  /// This function just returns a \ref lemon::DigraphWriter
950  /// "DigraphWriter" class.
951  ///
952  /// With this function a digraph can be write to a file or output
953  /// stream in \ref lgf-format "LGF" format with several maps and
954  /// attributes. For example, with the following code a network flow
955  /// problem can be written to the standard output, i.e. a digraph
956  /// with a \e capacity map on the arcs and \e source and \e target
957  /// nodes:
958  ///
959  ///\code
960  ///ListDigraph digraph;
961  ///ListDigraph::ArcMap<int> cap(digraph);
962  ///ListDigraph::Node src, trg;
963  ///  // Setting the capacity map and source and target nodes
964  ///digraphWriter(digraph, std::cout).
965  ///  arcMap("capacity", cap).
966  ///  node("source", src).
967  ///  node("target", trg).
968  ///  run();
969  ///\endcode
970  ///
971  /// For a complete documentation, please see the
972  /// \ref lemon::DigraphWriter "DigraphWriter"
973  /// class documentation.
974  /// \warning Don't forget to put the \ref lemon::DigraphWriter::run() "run()"
975  /// to the end of the parameter list.
976  /// \relates DigraphWriter
977  /// \sa digraphWriter(const TDGR& digraph, const std::string& fn)
978  /// \sa digraphWriter(const TDGR& digraph, const char* fn)
979  template <typename TDGR>
980  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, std::ostream& os) {
981    DigraphWriter<TDGR> tmp(digraph, os);
982    return tmp;
983  }
984
985  /// \brief Return a \ref DigraphWriter class
986  ///
987  /// This function just returns a \ref DigraphWriter class.
988  /// \relates DigraphWriter
989  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
990  template <typename TDGR>
991  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
992                                    const std::string& fn) {
993    DigraphWriter<TDGR> tmp(digraph, fn);
994    return tmp;
995  }
996
997  /// \brief Return a \ref DigraphWriter class
998  ///
999  /// This function just returns a \ref DigraphWriter class.
1000  /// \relates DigraphWriter
1001  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
1002  template <typename TDGR>
1003  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn) {
1004    DigraphWriter<TDGR> tmp(digraph, fn);
1005    return tmp;
1006  }
1007
1008  template <typename GR>
1009  class GraphWriter;
1010
1011  template <typename TGR>
1012  GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os = std::cout);
1013  template <typename TGR>
1014  GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn);
1015  template <typename TGR>
1016  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn);
1017
1018  /// \ingroup lemon_io
1019  ///
1020  /// \brief \ref lgf-format "LGF" writer for undirected graphs
1021  ///
1022  /// This utility writes an \ref lgf-format "LGF" file.
1023  ///
1024  /// It can be used almost the same way as \c DigraphWriter.
1025  /// The only difference is that this class can handle edges and
1026  /// edge maps as well as arcs and arc maps.
1027  ///
1028  /// The arc maps are written into the file as two columns, the
1029  /// caption of the columns are the name of the map prefixed with \c
1030  /// '+' and \c '-'. The arcs are written into the \c \@attributes
1031  /// section as a \c '+' or a \c '-' prefix (depends on the direction
1032  /// of the arc) and the label of corresponding edge.
1033  template <typename GR>
1034  class GraphWriter {
1035  public:
1036
1037    typedef GR Graph;
1038    TEMPLATE_GRAPH_TYPEDEFS(GR);
1039
1040  private:
1041
1042
1043    std::ostream* _os;
1044    bool local_os;
1045
1046    const GR& _graph;
1047
1048    std::string _nodes_caption;
1049    std::string _edges_caption;
1050    std::string _attributes_caption;
1051
1052    typedef std::map<Node, std::string> NodeIndex;
1053    NodeIndex _node_index;
1054    typedef std::map<Edge, std::string> EdgeIndex;
1055    EdgeIndex _edge_index;
1056
1057    typedef std::vector<std::pair<std::string,
1058      _writer_bits::MapStorageBase<Node>* > > NodeMaps;
1059    NodeMaps _node_maps;
1060
1061    typedef std::vector<std::pair<std::string,
1062      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
1063    EdgeMaps _edge_maps;
1064
1065    typedef std::vector<std::pair<std::string,
1066      _writer_bits::ValueStorageBase*> > Attributes;
1067    Attributes _attributes;
1068
1069    bool _skip_nodes;
1070    bool _skip_edges;
1071
1072  public:
1073
1074    /// \brief Constructor
1075    ///
1076    /// Construct an undirected graph writer, which writes to the
1077    /// given output stream.
1078    GraphWriter(const GR& graph, std::ostream& os = std::cout)
1079      : _os(&os), local_os(false), _graph(graph),
1080        _skip_nodes(false), _skip_edges(false) {}
1081
1082    /// \brief Constructor
1083    ///
1084    /// Construct a undirected graph writer, which writes to the given
1085    /// output file.
1086    GraphWriter(const GR& graph, const std::string& fn)
1087      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
1088        _skip_nodes(false), _skip_edges(false) {
1089      if (!(*_os)) {
1090        delete _os;
1091        throw IoError("Cannot write file", fn);
1092      }
1093    }
1094
1095    /// \brief Constructor
1096    ///
1097    /// Construct a undirected graph writer, which writes to the given
1098    /// output file.
1099    GraphWriter(const GR& graph, const char* fn)
1100      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
1101        _skip_nodes(false), _skip_edges(false) {
1102      if (!(*_os)) {
1103        delete _os;
1104        throw IoError("Cannot write file", fn);
1105      }
1106    }
1107
1108    /// \brief Destructor
1109    ~GraphWriter() {
1110      for (typename NodeMaps::iterator it = _node_maps.begin();
1111           it != _node_maps.end(); ++it) {
1112        delete it->second;
1113      }
1114
1115      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1116           it != _edge_maps.end(); ++it) {
1117        delete it->second;
1118      }
1119
1120      for (typename Attributes::iterator it = _attributes.begin();
1121           it != _attributes.end(); ++it) {
1122        delete it->second;
1123      }
1124
1125      if (local_os) {
1126        delete _os;
1127      }
1128    }
1129
1130  private:
1131
1132    template <typename TGR>
1133    friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
1134    template <typename TGR>
1135    friend GraphWriter<TGR> graphWriter(const TGR& graph,
1136                                        const std::string& fn);
1137    template <typename TGR>
1138    friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn);
1139
1140    GraphWriter(GraphWriter& other)
1141      : _os(other._os), local_os(other.local_os), _graph(other._graph),
1142        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1143
1144      other._os = 0;
1145      other.local_os = false;
1146
1147      _node_index.swap(other._node_index);
1148      _edge_index.swap(other._edge_index);
1149
1150      _node_maps.swap(other._node_maps);
1151      _edge_maps.swap(other._edge_maps);
1152      _attributes.swap(other._attributes);
1153
1154      _nodes_caption = other._nodes_caption;
1155      _edges_caption = other._edges_caption;
1156      _attributes_caption = other._attributes_caption;
1157    }
1158
1159    GraphWriter& operator=(const GraphWriter&);
1160
1161  public:
1162
1163    /// \name Writing Rules
1164    /// @{
1165
1166    /// \brief Node map writing rule
1167    ///
1168    /// Add a node map writing rule to the writer.
1169    template <typename Map>
1170    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
1171      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1172      _writer_bits::MapStorageBase<Node>* storage =
1173        new _writer_bits::MapStorage<Node, Map>(map);
1174      _node_maps.push_back(std::make_pair(caption, storage));
1175      return *this;
1176    }
1177
1178    /// \brief Node map writing rule
1179    ///
1180    /// Add a node map writing rule with specialized converter to the
1181    /// writer.
1182    template <typename Map, typename Converter>
1183    GraphWriter& nodeMap(const std::string& caption, const Map& map,
1184                           const Converter& converter = Converter()) {
1185      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1186      _writer_bits::MapStorageBase<Node>* storage =
1187        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
1188      _node_maps.push_back(std::make_pair(caption, storage));
1189      return *this;
1190    }
1191
1192    /// \brief Edge map writing rule
1193    ///
1194    /// Add an edge map writing rule to the writer.
1195    template <typename Map>
1196    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
1197      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1198      _writer_bits::MapStorageBase<Edge>* storage =
1199        new _writer_bits::MapStorage<Edge, Map>(map);
1200      _edge_maps.push_back(std::make_pair(caption, storage));
1201      return *this;
1202    }
1203
1204    /// \brief Edge map writing rule
1205    ///
1206    /// Add an edge map writing rule with specialized converter to the
1207    /// writer.
1208    template <typename Map, typename Converter>
1209    GraphWriter& edgeMap(const std::string& caption, const Map& map,
1210                          const Converter& converter = Converter()) {
1211      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1212      _writer_bits::MapStorageBase<Edge>* storage =
1213        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
1214      _edge_maps.push_back(std::make_pair(caption, storage));
1215      return *this;
1216    }
1217
1218    /// \brief Arc map writing rule
1219    ///
1220    /// Add an arc map writing rule to the writer.
1221    template <typename Map>
1222    GraphWriter& arcMap(const std::string& caption, const Map& map) {
1223      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1224      _writer_bits::MapStorageBase<Edge>* forward_storage =
1225        new _writer_bits::GraphArcMapStorage<GR, true, Map>(_graph, map);
1226      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1227      _writer_bits::MapStorageBase<Edge>* backward_storage =
1228        new _writer_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
1229      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1230      return *this;
1231    }
1232
1233    /// \brief Arc map writing rule
1234    ///
1235    /// Add an arc map writing rule with specialized converter to the
1236    /// writer.
1237    template <typename Map, typename Converter>
1238    GraphWriter& arcMap(const std::string& caption, const Map& map,
1239                          const Converter& converter = Converter()) {
1240      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1241      _writer_bits::MapStorageBase<Edge>* forward_storage =
1242        new _writer_bits::GraphArcMapStorage<GR, true, Map, Converter>
1243        (_graph, map, converter);
1244      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1245      _writer_bits::MapStorageBase<Edge>* backward_storage =
1246        new _writer_bits::GraphArcMapStorage<GR, false, Map, Converter>
1247        (_graph, map, converter);
1248      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1249      return *this;
1250    }
1251
1252    /// \brief Attribute writing rule
1253    ///
1254    /// Add an attribute writing rule to the writer.
1255    template <typename Value>
1256    GraphWriter& attribute(const std::string& caption, const Value& value) {
1257      _writer_bits::ValueStorageBase* storage =
1258        new _writer_bits::ValueStorage<Value>(value);
1259      _attributes.push_back(std::make_pair(caption, storage));
1260      return *this;
1261    }
1262
1263    /// \brief Attribute writing rule
1264    ///
1265    /// Add an attribute writing rule with specialized converter to the
1266    /// writer.
1267    template <typename Value, typename Converter>
1268    GraphWriter& attribute(const std::string& caption, const Value& value,
1269                             const Converter& converter = Converter()) {
1270      _writer_bits::ValueStorageBase* storage =
1271        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1272      _attributes.push_back(std::make_pair(caption, storage));
1273      return *this;
1274    }
1275
1276    /// \brief Node writing rule
1277    ///
1278    /// Add a node writing rule to the writer.
1279    GraphWriter& node(const std::string& caption, const Node& node) {
1280      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1281      Converter converter(_node_index);
1282      _writer_bits::ValueStorageBase* storage =
1283        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1284      _attributes.push_back(std::make_pair(caption, storage));
1285      return *this;
1286    }
1287
1288    /// \brief Edge writing rule
1289    ///
1290    /// Add an edge writing rule to writer.
1291    GraphWriter& edge(const std::string& caption, const Edge& edge) {
1292      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
1293      Converter converter(_edge_index);
1294      _writer_bits::ValueStorageBase* storage =
1295        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
1296      _attributes.push_back(std::make_pair(caption, storage));
1297      return *this;
1298    }
1299
1300    /// \brief Arc writing rule
1301    ///
1302    /// Add an arc writing rule to writer.
1303    GraphWriter& arc(const std::string& caption, const Arc& arc) {
1304      typedef _writer_bits::GraphArcLookUpConverter<GR> Converter;
1305      Converter converter(_graph, _edge_index);
1306      _writer_bits::ValueStorageBase* storage =
1307        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
1308      _attributes.push_back(std::make_pair(caption, storage));
1309      return *this;
1310    }
1311
1312    /// \name Section Captions
1313    /// @{
1314
1315    /// \brief Add an additional caption to the \c \@nodes section
1316    ///
1317    /// Add an additional caption to the \c \@nodes section.
1318    GraphWriter& nodes(const std::string& caption) {
1319      _nodes_caption = caption;
1320      return *this;
1321    }
1322
1323    /// \brief Add an additional caption to the \c \@edges section
1324    ///
1325    /// Add an additional caption to the \c \@edges section.
1326    GraphWriter& edges(const std::string& caption) {
1327      _edges_caption = caption;
1328      return *this;
1329    }
1330
1331    /// \brief Add an additional caption to the \c \@attributes section
1332    ///
1333    /// Add an additional caption to the \c \@attributes section.
1334    GraphWriter& attributes(const std::string& caption) {
1335      _attributes_caption = caption;
1336      return *this;
1337    }
1338
1339    /// \name Skipping Section
1340    /// @{
1341
1342    /// \brief Skip writing the node set
1343    ///
1344    /// The \c \@nodes section will not be written to the stream.
1345    GraphWriter& skipNodes() {
1346      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
1347      _skip_nodes = true;
1348      return *this;
1349    }
1350
1351    /// \brief Skip writing edge set
1352    ///
1353    /// The \c \@edges section will not be written to the stream.
1354    GraphWriter& skipEdges() {
1355      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
1356      _skip_edges = true;
1357      return *this;
1358    }
1359
1360    /// @}
1361
1362  private:
1363
1364    void writeNodes() {
1365      _writer_bits::MapStorageBase<Node>* label = 0;
1366      for (typename NodeMaps::iterator it = _node_maps.begin();
1367           it != _node_maps.end(); ++it) {
1368        if (it->first == "label") {
1369          label = it->second;
1370          break;
1371        }
1372      }
1373
1374      *_os << "@nodes";
1375      if (!_nodes_caption.empty()) {
1376        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
1377      }
1378      *_os << std::endl;
1379
1380      if (label == 0) {
1381        *_os << "label" << '\t';
1382      }
1383      for (typename NodeMaps::iterator it = _node_maps.begin();
1384           it != _node_maps.end(); ++it) {
1385        _writer_bits::writeToken(*_os, it->first) << '\t';
1386      }
1387      *_os << std::endl;
1388
1389      std::vector<Node> nodes;
1390      for (NodeIt n(_graph); n != INVALID; ++n) {
1391        nodes.push_back(n);
1392      }
1393
1394      if (label == 0) {
1395        IdMap<GR, Node> id_map(_graph);
1396        _writer_bits::MapLess<IdMap<GR, Node> > id_less(id_map);
1397        std::sort(nodes.begin(), nodes.end(), id_less);
1398      } else {
1399        label->sort(nodes);
1400      }
1401
1402      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
1403        Node n = nodes[i];
1404        if (label == 0) {
1405          std::ostringstream os;
1406          os << _graph.id(n);
1407          _writer_bits::writeToken(*_os, os.str());
1408          *_os << '\t';
1409          _node_index.insert(std::make_pair(n, os.str()));
1410        }
1411        for (typename NodeMaps::iterator it = _node_maps.begin();
1412             it != _node_maps.end(); ++it) {
1413          std::string value = it->second->get(n);
1414          _writer_bits::writeToken(*_os, value);
1415          if (it->first == "label") {
1416            _node_index.insert(std::make_pair(n, value));
1417          }
1418          *_os << '\t';
1419        }
1420        *_os << std::endl;
1421      }
1422    }
1423
1424    void createNodeIndex() {
1425      _writer_bits::MapStorageBase<Node>* label = 0;
1426      for (typename NodeMaps::iterator it = _node_maps.begin();
1427           it != _node_maps.end(); ++it) {
1428        if (it->first == "label") {
1429          label = it->second;
1430          break;
1431        }
1432      }
1433
1434      if (label == 0) {
1435        for (NodeIt n(_graph); n != INVALID; ++n) {
1436          std::ostringstream os;
1437          os << _graph.id(n);
1438          _node_index.insert(std::make_pair(n, os.str()));
1439        }
1440      } else {
1441        for (NodeIt n(_graph); n != INVALID; ++n) {
1442          std::string value = label->get(n);
1443          _node_index.insert(std::make_pair(n, value));
1444        }
1445      }
1446    }
1447
1448    void writeEdges() {
1449      _writer_bits::MapStorageBase<Edge>* label = 0;
1450      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1451           it != _edge_maps.end(); ++it) {
1452        if (it->first == "label") {
1453          label = it->second;
1454          break;
1455        }
1456      }
1457
1458      *_os << "@edges";
1459      if (!_edges_caption.empty()) {
1460        _writer_bits::writeToken(*_os << ' ', _edges_caption);
1461      }
1462      *_os << std::endl;
1463
1464      *_os << '\t' << '\t';
1465      if (label == 0) {
1466        *_os << "label" << '\t';
1467      }
1468      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1469           it != _edge_maps.end(); ++it) {
1470        _writer_bits::writeToken(*_os, it->first) << '\t';
1471      }
1472      *_os << std::endl;
1473
1474      std::vector<Edge> edges;
1475      for (EdgeIt n(_graph); n != INVALID; ++n) {
1476        edges.push_back(n);
1477      }
1478
1479      if (label == 0) {
1480        IdMap<GR, Edge> id_map(_graph);
1481        _writer_bits::MapLess<IdMap<GR, Edge> > id_less(id_map);
1482        std::sort(edges.begin(), edges.end(), id_less);
1483      } else {
1484        label->sort(edges);
1485      }
1486
1487      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
1488        Edge e = edges[i];
1489        _writer_bits::writeToken(*_os, _node_index.
1490                                 find(_graph.u(e))->second);
1491        *_os << '\t';
1492        _writer_bits::writeToken(*_os, _node_index.
1493                                 find(_graph.v(e))->second);
1494        *_os << '\t';
1495        if (label == 0) {
1496          std::ostringstream os;
1497          os << _graph.id(e);
1498          _writer_bits::writeToken(*_os, os.str());
1499          *_os << '\t';
1500          _edge_index.insert(std::make_pair(e, os.str()));
1501        }
1502        for (typename EdgeMaps::iterator it = _edge_maps.begin();
1503             it != _edge_maps.end(); ++it) {
1504          std::string value = it->second->get(e);
1505          _writer_bits::writeToken(*_os, value);
1506          if (it->first == "label") {
1507            _edge_index.insert(std::make_pair(e, value));
1508          }
1509          *_os << '\t';
1510        }
1511        *_os << std::endl;
1512      }
1513    }
1514
1515    void createEdgeIndex() {
1516      _writer_bits::MapStorageBase<Edge>* label = 0;
1517      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1518           it != _edge_maps.end(); ++it) {
1519        if (it->first == "label") {
1520          label = it->second;
1521          break;
1522        }
1523      }
1524
1525      if (label == 0) {
1526        for (EdgeIt e(_graph); e != INVALID; ++e) {
1527          std::ostringstream os;
1528          os << _graph.id(e);
1529          _edge_index.insert(std::make_pair(e, os.str()));
1530        }
1531      } else {
1532        for (EdgeIt e(_graph); e != INVALID; ++e) {
1533          std::string value = label->get(e);
1534          _edge_index.insert(std::make_pair(e, value));
1535        }
1536      }
1537    }
1538
1539    void writeAttributes() {
1540      if (_attributes.empty()) return;
1541      *_os << "@attributes";
1542      if (!_attributes_caption.empty()) {
1543        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
1544      }
1545      *_os << std::endl;
1546      for (typename Attributes::iterator it = _attributes.begin();
1547           it != _attributes.end(); ++it) {
1548        _writer_bits::writeToken(*_os, it->first) << ' ';
1549        _writer_bits::writeToken(*_os, it->second->get());
1550        *_os << std::endl;
1551      }
1552    }
1553
1554  public:
1555
1556    /// \name Execution of the Writer
1557    /// @{
1558
1559    /// \brief Start the batch processing
1560    ///
1561    /// This function starts the batch processing.
1562    void run() {
1563      if (!_skip_nodes) {
1564        writeNodes();
1565      } else {
1566        createNodeIndex();
1567      }
1568      if (!_skip_edges) {
1569        writeEdges();
1570      } else {
1571        createEdgeIndex();
1572      }
1573      writeAttributes();
1574    }
1575
1576    /// \brief Give back the stream of the writer
1577    ///
1578    /// Give back the stream of the writer
1579    std::ostream& ostream() {
1580      return *_os;
1581    }
1582
1583    /// @}
1584  };
1585
1586  /// \ingroup lemon_io
1587  ///
1588  /// \brief Return a \ref lemon::GraphWriter "GraphWriter" class
1589  ///
1590  /// This function just returns a \ref lemon::GraphWriter "GraphWriter" class.
1591  ///
1592  /// With this function a graph can be write to a file or output
1593  /// stream in \ref lgf-format "LGF" format with several maps and
1594  /// attributes. For example, with the following code a weighted
1595  /// matching problem can be written to the standard output, i.e. a
1596  /// graph with a \e weight map on the edges:
1597  ///
1598  ///\code
1599  ///ListGraph graph;
1600  ///ListGraph::EdgeMap<int> weight(graph);
1601  ///  // Setting the weight map
1602  ///graphWriter(graph, std::cout).
1603  ///  edgeMap("weight", weight).
1604  ///  run();
1605  ///\endcode
1606  ///
1607  /// For a complete documentation, please see the
1608  /// \ref lemon::GraphWriter "GraphWriter"
1609  /// class documentation.
1610  /// \warning Don't forget to put the \ref lemon::GraphWriter::run() "run()"
1611  /// to the end of the parameter list.
1612  /// \relates GraphWriter
1613  /// \sa graphWriter(const TGR& graph, const std::string& fn)
1614  /// \sa graphWriter(const TGR& graph, const char* fn)
1615  template <typename TGR>
1616  GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os) {
1617    GraphWriter<TGR> tmp(graph, os);
1618    return tmp;
1619  }
1620
1621  /// \brief Return a \ref GraphWriter class
1622  ///
1623  /// This function just returns a \ref GraphWriter class.
1624  /// \relates GraphWriter
1625  /// \sa graphWriter(const TGR& graph, std::ostream& os)
1626  template <typename TGR>
1627  GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn) {
1628    GraphWriter<TGR> tmp(graph, fn);
1629    return tmp;
1630  }
1631
1632  /// \brief Return a \ref GraphWriter class
1633  ///
1634  /// This function just returns a \ref GraphWriter class.
1635  /// \relates GraphWriter
1636  /// \sa graphWriter(const TGR& graph, std::ostream& os)
1637  template <typename TGR>
1638  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
1639    GraphWriter<TGR> tmp(graph, fn);
1640    return tmp;
1641  }
1642
1643  template <typename BGR>
1644  class BpGraphWriter;
1645
1646  template <typename TBGR>
1647  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
1648                                    std::ostream& os = std::cout);
1649  template <typename TBGR>
1650  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn);
1651  template <typename TBGR>
1652  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn);
1653
1654  /// \ingroup lemon_io
1655  ///
1656  /// \brief \ref lgf-format "LGF" writer for undirected bipartite graphs
1657  ///
1658  /// This utility writes an \ref lgf-format "LGF" file.
1659  ///
1660  /// It can be used almost the same way as \c GraphWriter, but it
1661  /// reads the red and blue nodes from separate sections, and these
1662  /// sections can contain different set of maps.
1663  ///
1664  /// The red and blue node maps are written to the corresponding
1665  /// sections. The node maps are written to both of these sections
1666  /// with the same map name.
1667  template <typename BGR>
1668  class BpGraphWriter {
1669  public:
1670
1671    typedef BGR BpGraph;
1672    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
1673
1674  private:
1675
1676
1677    std::ostream* _os;
1678    bool local_os;
1679
1680    const BGR& _graph;
1681
1682    std::string _nodes_caption;
1683    std::string _edges_caption;
1684    std::string _attributes_caption;
1685
1686    typedef std::map<Node, std::string> RedNodeIndex;
1687    RedNodeIndex _red_node_index;
1688    typedef std::map<Node, std::string> BlueNodeIndex;
1689    BlueNodeIndex _blue_node_index;
1690    typedef std::map<Edge, std::string> EdgeIndex;
1691    EdgeIndex _edge_index;
1692
1693    typedef std::vector<std::pair<std::string,
1694      _writer_bits::MapStorageBase<RedNode>* > > RedNodeMaps;
1695    RedNodeMaps _red_node_maps;
1696    typedef std::vector<std::pair<std::string,
1697      _writer_bits::MapStorageBase<BlueNode>* > > BlueNodeMaps;
1698    BlueNodeMaps _blue_node_maps;
1699
1700    typedef std::vector<std::pair<std::string,
1701      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
1702    EdgeMaps _edge_maps;
1703
1704    typedef std::vector<std::pair<std::string,
1705      _writer_bits::ValueStorageBase*> > Attributes;
1706    Attributes _attributes;
1707
1708    bool _skip_nodes;
1709    bool _skip_edges;
1710
1711  public:
1712
1713    /// \brief Constructor
1714    ///
1715    /// Construct a bipartite graph writer, which writes to the given
1716    /// output stream.
1717    BpGraphWriter(const BGR& graph, std::ostream& os = std::cout)
1718      : _os(&os), local_os(false), _graph(graph),
1719        _skip_nodes(false), _skip_edges(false) {}
1720
1721    /// \brief Constructor
1722    ///
1723    /// Construct a bipartite graph writer, which writes to the given
1724    /// output file.
1725    BpGraphWriter(const BGR& graph, const std::string& fn)
1726      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
1727        _skip_nodes(false), _skip_edges(false) {
1728      if (!(*_os)) {
1729        delete _os;
1730        throw IoError("Cannot write file", fn);
1731      }
1732    }
1733
1734    /// \brief Constructor
1735    ///
1736    /// Construct a bipartite graph writer, which writes to the given
1737    /// output file.
1738    BpGraphWriter(const BGR& graph, const char* fn)
1739      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
1740        _skip_nodes(false), _skip_edges(false) {
1741      if (!(*_os)) {
1742        delete _os;
1743        throw IoError("Cannot write file", fn);
1744      }
1745    }
1746
1747    /// \brief Destructor
1748    ~BpGraphWriter() {
1749      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
1750           it != _red_node_maps.end(); ++it) {
1751        delete it->second;
1752      }
1753
1754      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
1755           it != _blue_node_maps.end(); ++it) {
1756        delete it->second;
1757      }
1758
1759      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1760           it != _edge_maps.end(); ++it) {
1761        delete it->second;
1762      }
1763
1764      for (typename Attributes::iterator it = _attributes.begin();
1765           it != _attributes.end(); ++it) {
1766        delete it->second;
1767      }
1768
1769      if (local_os) {
1770        delete _os;
1771      }
1772    }
1773
1774  private:
1775
1776    template <typename TBGR>
1777    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
1778                                             std::ostream& os);
1779    template <typename TBGR>
1780    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
1781                                             const std::string& fn);
1782    template <typename TBGR>
1783    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char *fn);
1784
1785    BpGraphWriter(BpGraphWriter& other)
1786      : _os(other._os), local_os(other.local_os), _graph(other._graph),
1787        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1788
1789      other._os = 0;
1790      other.local_os = false;
1791
1792      _red_node_index.swap(other._red_node_index);
1793      _blue_node_index.swap(other._blue_node_index);
1794      _edge_index.swap(other._edge_index);
1795
1796      _red_node_maps.swap(other._red_node_maps);
1797      _blue_node_maps.swap(other._blue_node_maps);
1798      _edge_maps.swap(other._edge_maps);
1799      _attributes.swap(other._attributes);
1800
1801      _nodes_caption = other._nodes_caption;
1802      _edges_caption = other._edges_caption;
1803      _attributes_caption = other._attributes_caption;
1804    }
1805
1806    BpGraphWriter& operator=(const BpGraphWriter&);
1807
1808  public:
1809
1810    /// \name Writing Rules
1811    /// @{
1812
1813    /// \brief Node map writing rule
1814    ///
1815    /// Add a node map writing rule to the writer.
1816    template <typename Map>
1817    BpGraphWriter& nodeMap(const std::string& caption, const Map& map) {
1818      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1819      _writer_bits::MapStorageBase<RedNode>* red_storage =
1820        new _writer_bits::MapStorage<RedNode, Map>(map);
1821      _red_node_maps.push_back(std::make_pair(caption, red_storage));
1822      _writer_bits::MapStorageBase<BlueNode>* blue_storage =
1823        new _writer_bits::MapStorage<BlueNode, Map>(map);
1824      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
1825      return *this;
1826    }
1827
1828    /// \brief Node map writing rule
1829    ///
1830    /// Add a node map writing rule with specialized converter to the
1831    /// writer.
1832    template <typename Map, typename Converter>
1833    BpGraphWriter& nodeMap(const std::string& caption, const Map& map,
1834                           const Converter& converter = Converter()) {
1835      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1836      _writer_bits::MapStorageBase<RedNode>* red_storage =
1837        new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter);
1838      _red_node_maps.push_back(std::make_pair(caption, red_storage));
1839      _writer_bits::MapStorageBase<BlueNode>* blue_storage =
1840        new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
1841      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
1842      return *this;
1843    }
1844
1845    /// \brief Red node map writing rule
1846    ///
1847    /// Add a red node map writing rule to the writer.
1848    template <typename Map>
1849    BpGraphWriter& redNodeMap(const std::string& caption, const Map& map) {
1850      checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>();
1851      _writer_bits::MapStorageBase<RedNode>* storage =
1852        new _writer_bits::MapStorage<RedNode, Map>(map);
1853      _red_node_maps.push_back(std::make_pair(caption, storage));
1854      return *this;
1855    }
1856
1857    /// \brief Red node map writing rule
1858    ///
1859    /// Add a red node map writing rule with specialized converter to the
1860    /// writer.
1861    template <typename Map, typename Converter>
1862    BpGraphWriter& redNodeMap(const std::string& caption, const Map& map,
1863                              const Converter& converter = Converter()) {
1864      checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>();
1865      _writer_bits::MapStorageBase<RedNode>* storage =
1866        new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter);
1867      _red_node_maps.push_back(std::make_pair(caption, storage));
1868      return *this;
1869    }
1870
1871    /// \brief Blue node map writing rule
1872    ///
1873    /// Add a blue node map writing rule to the writer.
1874    template <typename Map>
1875    BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map) {
1876      checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>();
1877      _writer_bits::MapStorageBase<BlueNode>* storage =
1878        new _writer_bits::MapStorage<BlueNode, Map>(map);
1879      _blue_node_maps.push_back(std::make_pair(caption, storage));
1880      return *this;
1881    }
1882
1883    /// \brief Blue node map writing rule
1884    ///
1885    /// Add a blue node map writing rule with specialized converter to the
1886    /// writer.
1887    template <typename Map, typename Converter>
1888    BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map,
1889                               const Converter& converter = Converter()) {
1890      checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>();
1891      _writer_bits::MapStorageBase<BlueNode>* storage =
1892        new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
1893      _blue_node_maps.push_back(std::make_pair(caption, storage));
1894      return *this;
1895    }
1896
1897    /// \brief Edge map writing rule
1898    ///
1899    /// Add an edge map writing rule to the writer.
1900    template <typename Map>
1901    BpGraphWriter& edgeMap(const std::string& caption, const Map& map) {
1902      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1903      _writer_bits::MapStorageBase<Edge>* storage =
1904        new _writer_bits::MapStorage<Edge, Map>(map);
1905      _edge_maps.push_back(std::make_pair(caption, storage));
1906      return *this;
1907    }
1908
1909    /// \brief Edge map writing rule
1910    ///
1911    /// Add an edge map writing rule with specialized converter to the
1912    /// writer.
1913    template <typename Map, typename Converter>
1914    BpGraphWriter& edgeMap(const std::string& caption, const Map& map,
1915                          const Converter& converter = Converter()) {
1916      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1917      _writer_bits::MapStorageBase<Edge>* storage =
1918        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
1919      _edge_maps.push_back(std::make_pair(caption, storage));
1920      return *this;
1921    }
1922
1923    /// \brief Arc map writing rule
1924    ///
1925    /// Add an arc map writing rule to the writer.
1926    template <typename Map>
1927    BpGraphWriter& arcMap(const std::string& caption, const Map& map) {
1928      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1929      _writer_bits::MapStorageBase<Edge>* forward_storage =
1930        new _writer_bits::GraphArcMapStorage<BGR, true, Map>(_graph, map);
1931      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1932      _writer_bits::MapStorageBase<Edge>* backward_storage =
1933        new _writer_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
1934      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1935      return *this;
1936    }
1937
1938    /// \brief Arc map writing rule
1939    ///
1940    /// Add an arc map writing rule with specialized converter to the
1941    /// writer.
1942    template <typename Map, typename Converter>
1943    BpGraphWriter& arcMap(const std::string& caption, const Map& map,
1944                          const Converter& converter = Converter()) {
1945      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1946      _writer_bits::MapStorageBase<Edge>* forward_storage =
1947        new _writer_bits::GraphArcMapStorage<BGR, true, Map, Converter>
1948        (_graph, map, converter);
1949      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1950      _writer_bits::MapStorageBase<Edge>* backward_storage =
1951        new _writer_bits::GraphArcMapStorage<BGR, false, Map, Converter>
1952        (_graph, map, converter);
1953      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1954      return *this;
1955    }
1956
1957    /// \brief Attribute writing rule
1958    ///
1959    /// Add an attribute writing rule to the writer.
1960    template <typename Value>
1961    BpGraphWriter& attribute(const std::string& caption, const Value& value) {
1962      _writer_bits::ValueStorageBase* storage =
1963        new _writer_bits::ValueStorage<Value>(value);
1964      _attributes.push_back(std::make_pair(caption, storage));
1965      return *this;
1966    }
1967
1968    /// \brief Attribute writing rule
1969    ///
1970    /// Add an attribute writing rule with specialized converter to the
1971    /// writer.
1972    template <typename Value, typename Converter>
1973    BpGraphWriter& attribute(const std::string& caption, const Value& value,
1974                             const Converter& converter = Converter()) {
1975      _writer_bits::ValueStorageBase* storage =
1976        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1977      _attributes.push_back(std::make_pair(caption, storage));
1978      return *this;
1979    }
1980
1981    /// \brief Node writing rule
1982    ///
1983    /// Add a node writing rule to the writer.
1984    BpGraphWriter& node(const std::string& caption, const Node& node) {
1985      typedef _writer_bits::DoubleMapLookUpConverter<
1986        Node, RedNodeIndex, BlueNodeIndex> Converter;
1987      Converter converter(_red_node_index, _blue_node_index);
1988      _writer_bits::ValueStorageBase* storage =
1989        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1990      _attributes.push_back(std::make_pair(caption, storage));
1991      return *this;
1992    }
1993
1994    /// \brief Red node writing rule
1995    ///
1996    /// Add a red node writing rule to the writer.
1997    BpGraphWriter& redNode(const std::string& caption, const RedNode& node) {
1998      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1999      Converter converter(_red_node_index);
2000      _writer_bits::ValueStorageBase* storage =
2001        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
2002      _attributes.push_back(std::make_pair(caption, storage));
2003      return *this;
2004    }
2005
2006    /// \brief Blue node writing rule
2007    ///
2008    /// Add a blue node writing rule to the writer.
2009    BpGraphWriter& blueNode(const std::string& caption, const BlueNode& node) {
2010      typedef _writer_bits::MapLookUpConverter<Node> Converter;
2011      Converter converter(_blue_node_index);
2012      _writer_bits::ValueStorageBase* storage =
2013        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
2014      _attributes.push_back(std::make_pair(caption, storage));
2015      return *this;
2016    }
2017
2018    /// \brief Edge writing rule
2019    ///
2020    /// Add an edge writing rule to writer.
2021    BpGraphWriter& edge(const std::string& caption, const Edge& edge) {
2022      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
2023      Converter converter(_edge_index);
2024      _writer_bits::ValueStorageBase* storage =
2025        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
2026      _attributes.push_back(std::make_pair(caption, storage));
2027      return *this;
2028    }
2029
2030    /// \brief Arc writing rule
2031    ///
2032    /// Add an arc writing rule to writer.
2033    BpGraphWriter& arc(const std::string& caption, const Arc& arc) {
2034      typedef _writer_bits::GraphArcLookUpConverter<BGR> Converter;
2035      Converter converter(_graph, _edge_index);
2036      _writer_bits::ValueStorageBase* storage =
2037        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
2038      _attributes.push_back(std::make_pair(caption, storage));
2039      return *this;
2040    }
2041
2042    /// \name Section Captions
2043    /// @{
2044
2045    /// \brief Add an additional caption to the \c \@red_nodes and
2046    /// \c \@blue_nodes section
2047    ///
2048    /// Add an additional caption to the \c \@red_nodes and \c
2049    /// \@blue_nodes section.
2050    BpGraphWriter& nodes(const std::string& caption) {
2051      _nodes_caption = caption;
2052      return *this;
2053    }
2054
2055    /// \brief Add an additional caption to the \c \@edges section
2056    ///
2057    /// Add an additional caption to the \c \@edges section.
2058    BpGraphWriter& edges(const std::string& caption) {
2059      _edges_caption = caption;
2060      return *this;
2061    }
2062
2063    /// \brief Add an additional caption to the \c \@attributes section
2064    ///
2065    /// Add an additional caption to the \c \@attributes section.
2066    BpGraphWriter& attributes(const std::string& caption) {
2067      _attributes_caption = caption;
2068      return *this;
2069    }
2070
2071    /// \name Skipping Section
2072    /// @{
2073
2074    /// \brief Skip writing the node set
2075    ///
2076    /// The \c \@red_nodes and \c \@blue_nodes section will not be
2077    /// written to the stream.
2078    BpGraphWriter& skipNodes() {
2079      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
2080      _skip_nodes = true;
2081      return *this;
2082    }
2083
2084    /// \brief Skip writing edge set
2085    ///
2086    /// The \c \@edges section will not be written to the stream.
2087    BpGraphWriter& skipEdges() {
2088      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
2089      _skip_edges = true;
2090      return *this;
2091    }
2092
2093    /// @}
2094
2095  private:
2096
2097    void writeRedNodes() {
2098      _writer_bits::MapStorageBase<RedNode>* label = 0;
2099      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2100           it != _red_node_maps.end(); ++it) {
2101        if (it->first == "label") {
2102          label = it->second;
2103          break;
2104        }
2105      }
2106
2107      *_os << "@red_nodes";
2108      if (!_nodes_caption.empty()) {
2109        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
2110      }
2111      *_os << std::endl;
2112
2113      if (label == 0) {
2114        *_os << "label" << '\t';
2115      }
2116      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2117           it != _red_node_maps.end(); ++it) {
2118        _writer_bits::writeToken(*_os, it->first) << '\t';
2119      }
2120      *_os << std::endl;
2121
2122      std::vector<RedNode> nodes;
2123      for (RedNodeIt n(_graph); n != INVALID; ++n) {
2124        nodes.push_back(n);
2125      }
2126
2127      if (label == 0) {
2128        IdMap<BGR, Node> id_map(_graph);
2129        _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map);
2130        std::sort(nodes.begin(), nodes.end(), id_less);
2131      } else {
2132        label->sort(nodes);
2133      }
2134
2135      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
2136        RedNode n = nodes[i];
2137        if (label == 0) {
2138          std::ostringstream os;
2139          os << _graph.id(static_cast<Node>(n));
2140          _writer_bits::writeToken(*_os, os.str());
2141          *_os << '\t';
2142          _red_node_index.insert(std::make_pair(n, os.str()));
2143        }
2144        for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2145             it != _red_node_maps.end(); ++it) {
2146          std::string value = it->second->get(n);
2147          _writer_bits::writeToken(*_os, value);
2148          if (it->first == "label") {
2149            _red_node_index.insert(std::make_pair(n, value));
2150          }
2151          *_os << '\t';
2152        }
2153        *_os << std::endl;
2154      }
2155    }
2156
2157    void writeBlueNodes() {
2158      _writer_bits::MapStorageBase<BlueNode>* label = 0;
2159      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2160           it != _blue_node_maps.end(); ++it) {
2161        if (it->first == "label") {
2162          label = it->second;
2163          break;
2164        }
2165      }
2166
2167      *_os << "@blue_nodes";
2168      if (!_nodes_caption.empty()) {
2169        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
2170      }
2171      *_os << std::endl;
2172
2173      if (label == 0) {
2174        *_os << "label" << '\t';
2175      }
2176      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2177           it != _blue_node_maps.end(); ++it) {
2178        _writer_bits::writeToken(*_os, it->first) << '\t';
2179      }
2180      *_os << std::endl;
2181
2182      std::vector<BlueNode> nodes;
2183      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2184        nodes.push_back(n);
2185      }
2186
2187      if (label == 0) {
2188        IdMap<BGR, Node> id_map(_graph);
2189        _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map);
2190        std::sort(nodes.begin(), nodes.end(), id_less);
2191      } else {
2192        label->sort(nodes);
2193      }
2194
2195      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
2196        BlueNode n = nodes[i];
2197        if (label == 0) {
2198          std::ostringstream os;
2199          os << _graph.id(static_cast<Node>(n));
2200          _writer_bits::writeToken(*_os, os.str());
2201          *_os << '\t';
2202          _blue_node_index.insert(std::make_pair(n, os.str()));
2203        }
2204        for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2205             it != _blue_node_maps.end(); ++it) {
2206          std::string value = it->second->get(n);
2207          _writer_bits::writeToken(*_os, value);
2208          if (it->first == "label") {
2209            _blue_node_index.insert(std::make_pair(n, value));
2210          }
2211          *_os << '\t';
2212        }
2213        *_os << std::endl;
2214      }
2215    }
2216
2217    void createRedNodeIndex() {
2218      _writer_bits::MapStorageBase<RedNode>* label = 0;
2219      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2220           it != _red_node_maps.end(); ++it) {
2221        if (it->first == "label") {
2222          label = it->second;
2223          break;
2224        }
2225      }
2226
2227      if (label == 0) {
2228        for (RedNodeIt n(_graph); n != INVALID; ++n) {
2229          std::ostringstream os;
2230          os << _graph.id(n);
2231          _red_node_index.insert(std::make_pair(n, os.str()));
2232        }
2233      } else {
2234        for (RedNodeIt n(_graph); n != INVALID; ++n) {
2235          std::string value = label->get(n);
2236          _red_node_index.insert(std::make_pair(n, value));
2237        }
2238      }
2239    }
2240
2241    void createBlueNodeIndex() {
2242      _writer_bits::MapStorageBase<BlueNode>* label = 0;
2243      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2244           it != _blue_node_maps.end(); ++it) {
2245        if (it->first == "label") {
2246          label = it->second;
2247          break;
2248        }
2249      }
2250
2251      if (label == 0) {
2252        for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2253          std::ostringstream os;
2254          os << _graph.id(n);
2255          _blue_node_index.insert(std::make_pair(n, os.str()));
2256        }
2257      } else {
2258        for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2259          std::string value = label->get(n);
2260          _blue_node_index.insert(std::make_pair(n, value));
2261        }
2262      }
2263    }
2264
2265    void writeEdges() {
2266      _writer_bits::MapStorageBase<Edge>* label = 0;
2267      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2268           it != _edge_maps.end(); ++it) {
2269        if (it->first == "label") {
2270          label = it->second;
2271          break;
2272        }
2273      }
2274
2275      *_os << "@edges";
2276      if (!_edges_caption.empty()) {
2277        _writer_bits::writeToken(*_os << ' ', _edges_caption);
2278      }
2279      *_os << std::endl;
2280
2281      *_os << '\t' << '\t';
2282      if (label == 0) {
2283        *_os << "label" << '\t';
2284      }
2285      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2286           it != _edge_maps.end(); ++it) {
2287        _writer_bits::writeToken(*_os, it->first) << '\t';
2288      }
2289      *_os << std::endl;
2290
2291      std::vector<Edge> edges;
2292      for (EdgeIt n(_graph); n != INVALID; ++n) {
2293        edges.push_back(n);
2294      }
2295
2296      if (label == 0) {
2297        IdMap<BGR, Edge> id_map(_graph);
2298        _writer_bits::MapLess<IdMap<BGR, Edge> > id_less(id_map);
2299        std::sort(edges.begin(), edges.end(), id_less);
2300      } else {
2301        label->sort(edges);
2302      }
2303
2304      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
2305        Edge e = edges[i];
2306        _writer_bits::writeToken(*_os, _red_node_index.
2307                                 find(_graph.redNode(e))->second);
2308        *_os << '\t';
2309        _writer_bits::writeToken(*_os, _blue_node_index.
2310                                 find(_graph.blueNode(e))->second);
2311        *_os << '\t';
2312        if (label == 0) {
2313          std::ostringstream os;
2314          os << _graph.id(e);
2315          _writer_bits::writeToken(*_os, os.str());
2316          *_os << '\t';
2317          _edge_index.insert(std::make_pair(e, os.str()));
2318        }
2319        for (typename EdgeMaps::iterator it = _edge_maps.begin();
2320             it != _edge_maps.end(); ++it) {
2321          std::string value = it->second->get(e);
2322          _writer_bits::writeToken(*_os, value);
2323          if (it->first == "label") {
2324            _edge_index.insert(std::make_pair(e, value));
2325          }
2326          *_os << '\t';
2327        }
2328        *_os << std::endl;
2329      }
2330    }
2331
2332    void createEdgeIndex() {
2333      _writer_bits::MapStorageBase<Edge>* label = 0;
2334      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2335           it != _edge_maps.end(); ++it) {
2336        if (it->first == "label") {
2337          label = it->second;
2338          break;
2339        }
2340      }
2341
2342      if (label == 0) {
2343        for (EdgeIt e(_graph); e != INVALID; ++e) {
2344          std::ostringstream os;
2345          os << _graph.id(e);
2346          _edge_index.insert(std::make_pair(e, os.str()));
2347        }
2348      } else {
2349        for (EdgeIt e(_graph); e != INVALID; ++e) {
2350          std::string value = label->get(e);
2351          _edge_index.insert(std::make_pair(e, value));
2352        }
2353      }
2354    }
2355
2356    void writeAttributes() {
2357      if (_attributes.empty()) return;
2358      *_os << "@attributes";
2359      if (!_attributes_caption.empty()) {
2360        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
2361      }
2362      *_os << std::endl;
2363      for (typename Attributes::iterator it = _attributes.begin();
2364           it != _attributes.end(); ++it) {
2365        _writer_bits::writeToken(*_os, it->first) << ' ';
2366        _writer_bits::writeToken(*_os, it->second->get());
2367        *_os << std::endl;
2368      }
2369    }
2370
2371  public:
2372
2373    /// \name Execution of the Writer
2374    /// @{
2375
2376    /// \brief Start the batch processing
2377    ///
2378    /// This function starts the batch processing.
2379    void run() {
2380      if (!_skip_nodes) {
2381        writeRedNodes();
2382        writeBlueNodes();
2383      } else {
2384        createRedNodeIndex();
2385        createBlueNodeIndex();
2386      }
2387      if (!_skip_edges) {
2388        writeEdges();
2389      } else {
2390        createEdgeIndex();
2391      }
2392      writeAttributes();
2393    }
2394
2395    /// \brief Give back the stream of the writer
2396    ///
2397    /// Give back the stream of the writer
2398    std::ostream& ostream() {
2399      return *_os;
2400    }
2401
2402    /// @}
2403  };
2404
2405  /// \ingroup lemon_io
2406  ///
2407  /// \brief Return a \ref lemon::BpGraphWriter "BpGraphWriter" class
2408  ///
2409  /// This function just returns a \ref lemon::BpGraphWriter
2410  /// "BpGraphWriter" class.
2411  ///
2412  /// With this function a bipartite graph can be write to a file or output
2413  /// stream in \ref lgf-format "LGF" format with several maps and
2414  /// attributes. For example, with the following code a bipartite
2415  /// weighted matching problem can be written to the standard output,
2416  /// i.e. a graph with a \e weight map on the edges:
2417  ///
2418  ///\code
2419  ///ListBpGraph graph;
2420  ///ListBpGraph::EdgeMap<int> weight(graph);
2421  ///  // Setting the weight map
2422  ///bpGraphWriter(graph, std::cout).
2423  ///  edgeMap("weight", weight).
2424  ///  run();
2425  ///\endcode
2426  ///
2427  /// For a complete documentation, please see the
2428  /// \ref lemon::BpGraphWriter "BpGraphWriter"
2429  /// class documentation.
2430  /// \warning Don't forget to put the \ref lemon::BpGraphWriter::run() "run()"
2431  /// to the end of the parameter list.
2432  /// \relates BpGraphWriter
2433  /// \sa bpGraphWriter(const TBGR& graph, const std::string& fn)
2434  /// \sa bpGraphWriter(const TBGR& graph, const char* fn)
2435  template <typename TBGR>
2436  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, std::ostream& os) {
2437    BpGraphWriter<TBGR> tmp(graph, os);
2438    return tmp;
2439  }
2440
2441  /// \brief Return a \ref BpGraphWriter class
2442  ///
2443  /// This function just returns a \ref BpGraphWriter class.
2444  /// \relates BpGraphWriter
2445  /// \sa graphWriter(const TBGR& graph, std::ostream& os)
2446  template <typename TBGR>
2447  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn) {
2448    BpGraphWriter<TBGR> tmp(graph, fn);
2449    return tmp;
2450  }
2451
2452  /// \brief Return a \ref BpGraphWriter class
2453  ///
2454  /// This function just returns a \ref BpGraphWriter class.
2455  /// \relates BpGraphWriter
2456  /// \sa graphWriter(const TBGR& graph, std::ostream& os)
2457  template <typename TBGR>
2458  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn) {
2459    BpGraphWriter<TBGR> tmp(graph, fn);
2460    return tmp;
2461  }
2462
2463  class SectionWriter;
2464
2465  SectionWriter sectionWriter(std::istream& is);
2466  SectionWriter sectionWriter(const std::string& fn);
2467  SectionWriter sectionWriter(const char* fn);
2468
2469  /// \ingroup lemon_io
2470  ///
2471  /// \brief Section writer class
2472  ///
2473  /// In the \ref lgf-format "LGF" file extra sections can be placed,
2474  /// which contain any data in arbitrary format. Such sections can be
2475  /// written with this class. A writing rule can be added to the
2476  /// class with two different functions. With the \c sectionLines()
2477  /// function a generator can write the section line-by-line, while
2478  /// with the \c sectionStream() member the section can be written to
2479  /// an output stream.
2480  class SectionWriter {
2481  private:
2482
2483    std::ostream* _os;
2484    bool local_os;
2485
2486    typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
2487    Sections;
2488
2489    Sections _sections;
2490
2491  public:
2492
2493    /// \brief Constructor
2494    ///
2495    /// Construct a section writer, which writes to the given output
2496    /// stream.
2497    SectionWriter(std::ostream& os)
2498      : _os(&os), local_os(false) {}
2499
2500    /// \brief Constructor
2501    ///
2502    /// Construct a section writer, which writes into the given file.
2503    SectionWriter(const std::string& fn)
2504      : _os(new std::ofstream(fn.c_str())), local_os(true) {
2505      if (!(*_os)) {
2506        delete _os;
2507        throw IoError("Cannot write file", fn);
2508      }
2509    }
2510
2511    /// \brief Constructor
2512    ///
2513    /// Construct a section writer, which writes into the given file.
2514    SectionWriter(const char* fn)
2515      : _os(new std::ofstream(fn)), local_os(true) {
2516      if (!(*_os)) {
2517        delete _os;
2518        throw IoError("Cannot write file", fn);
2519      }
2520    }
2521
2522    /// \brief Destructor
2523    ~SectionWriter() {
2524      for (Sections::iterator it = _sections.begin();
2525           it != _sections.end(); ++it) {
2526        delete it->second;
2527      }
2528
2529      if (local_os) {
2530        delete _os;
2531      }
2532
2533    }
2534
2535  private:
2536
2537    friend SectionWriter sectionWriter(std::ostream& os);
2538    friend SectionWriter sectionWriter(const std::string& fn);
2539    friend SectionWriter sectionWriter(const char* fn);
2540
2541    SectionWriter(SectionWriter& other)
2542      : _os(other._os), local_os(other.local_os) {
2543
2544      other._os = 0;
2545      other.local_os = false;
2546
2547      _sections.swap(other._sections);
2548    }
2549
2550    SectionWriter& operator=(const SectionWriter&);
2551
2552  public:
2553
2554    /// \name Section Writers
2555    /// @{
2556
2557    /// \brief Add a section writer with line oriented writing
2558    ///
2559    /// The first parameter is the type descriptor of the section, the
2560    /// second is a generator with std::string values. At the writing
2561    /// process, the returned \c std::string will be written into the
2562    /// output file until it is an empty string.
2563    ///
2564    /// For example, an integer vector is written into a section.
2565    ///\code
2566    ///  @numbers
2567    ///  12 45 23 78
2568    ///  4 28 38 28
2569    ///  23 6 16
2570    ///\endcode
2571    ///
2572    /// The generator is implemented as a struct.
2573    ///\code
2574    ///  struct NumberSection {
2575    ///    std::vector<int>::const_iterator _it, _end;
2576    ///    NumberSection(const std::vector<int>& data)
2577    ///      : _it(data.begin()), _end(data.end()) {}
2578    ///    std::string operator()() {
2579    ///      int rem_in_line = 4;
2580    ///      std::ostringstream ls;
2581    ///      while (rem_in_line > 0 && _it != _end) {
2582    ///        ls << *(_it++) << ' ';
2583    ///        --rem_in_line;
2584    ///      }
2585    ///      return ls.str();
2586    ///    }
2587    ///  };
2588    ///
2589    ///  // ...
2590    ///
2591    ///  writer.sectionLines("numbers", NumberSection(vec));
2592    ///\endcode
2593    template <typename Functor>
2594    SectionWriter& sectionLines(const std::string& type, Functor functor) {
2595      LEMON_ASSERT(!type.empty(), "Type is empty.");
2596      _sections.push_back(std::make_pair(type,
2597        new _writer_bits::LineSection<Functor>(functor)));
2598      return *this;
2599    }
2600
2601
2602    /// \brief Add a section writer with stream oriented writing
2603    ///
2604    /// The first parameter is the type of the section, the second is
2605    /// a functor, which takes a \c std::ostream& parameter. The
2606    /// functor writes the section to the output stream.
2607    /// \warning The last line must be closed with end-line character.
2608    template <typename Functor>
2609    SectionWriter& sectionStream(const std::string& type, Functor functor) {
2610      LEMON_ASSERT(!type.empty(), "Type is empty.");
2611      _sections.push_back(std::make_pair(type,
2612         new _writer_bits::StreamSection<Functor>(functor)));
2613      return *this;
2614    }
2615
2616    /// @}
2617
2618  public:
2619
2620
2621    /// \name Execution of the Writer
2622    /// @{
2623
2624    /// \brief Start the batch processing
2625    ///
2626    /// This function starts the batch processing.
2627    void run() {
2628
2629      LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");
2630
2631      for (Sections::iterator it = _sections.begin();
2632           it != _sections.end(); ++it) {
2633        (*_os) << '@' << it->first << std::endl;
2634        it->second->process(*_os);
2635      }
2636    }
2637
2638    /// \brief Give back the stream of the writer
2639    ///
2640    /// Returns the stream of the writer
2641    std::ostream& ostream() {
2642      return *_os;
2643    }
2644
2645    /// @}
2646
2647  };
2648
2649  /// \ingroup lemon_io
2650  ///
2651  /// \brief Return a \ref SectionWriter class
2652  ///
2653  /// This function just returns a \ref SectionWriter class.
2654  ///
2655  /// Please see SectionWriter documentation about the custom section
2656  /// output.
2657  ///
2658  /// \relates SectionWriter
2659  /// \sa sectionWriter(const std::string& fn)
2660  /// \sa sectionWriter(const char *fn)
2661  inline SectionWriter sectionWriter(std::ostream& os) {
2662    SectionWriter tmp(os);
2663    return tmp;
2664  }
2665
2666  /// \brief Return a \ref SectionWriter class
2667  ///
2668  /// This function just returns a \ref SectionWriter class.
2669  /// \relates SectionWriter
2670  /// \sa sectionWriter(std::ostream& os)
2671  inline SectionWriter sectionWriter(const std::string& fn) {
2672    SectionWriter tmp(fn);
2673    return tmp;
2674  }
2675
2676  /// \brief Return a \ref SectionWriter class
2677  ///
2678  /// This function just returns a \ref SectionWriter class.
2679  /// \relates SectionWriter
2680  /// \sa sectionWriter(std::ostream& os)
2681  inline SectionWriter sectionWriter(const char* fn) {
2682    SectionWriter tmp(fn);
2683    return tmp;
2684  }
2685}
2686
2687#endif
Note: See TracBrowser for help on using the repository browser.