COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_writer.h @ 1198:4936be66d2f5

Last change on this file since 1198:4936be66d2f5 was 1198:4936be66d2f5, checked in by Balazs Dezso <deba@…>, 7 years ago

Changes in BpGraph? lgf reader and writer (#69)

File size: 82.1 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-2010
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 DigraphWriter class
948  ///
949  /// This function just returns a \ref DigraphWriter class.
950  ///
951  /// With this function a digraph can be write to a file or output
952  /// stream in \ref lgf-format "LGF" format with several maps and
953  /// attributes. For example, with the following code a network flow
954  /// problem can be written to the standard output, i.e. a digraph
955  /// with a \e capacity map on the arcs and \e source and \e target
956  /// nodes:
957  ///
958  ///\code
959  ///ListDigraph digraph;
960  ///ListDigraph::ArcMap<int> cap(digraph);
961  ///ListDigraph::Node src, trg;
962  ///  // Setting the capacity map and source and target nodes
963  ///digraphWriter(digraph, std::cout).
964  ///  arcMap("capacity", cap).
965  ///  node("source", src).
966  ///  node("target", trg).
967  ///  run();
968  ///\endcode
969  ///
970  /// For a complete documentation, please see the \ref DigraphWriter
971  /// class documentation.
972  /// \warning Don't forget to put the \ref DigraphWriter::run() "run()"
973  /// to the end of the parameter list.
974  /// \relates DigraphWriter
975  /// \sa digraphWriter(const TDGR& digraph, const std::string& fn)
976  /// \sa digraphWriter(const TDGR& digraph, const char* fn)
977  template <typename TDGR>
978  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, std::ostream& os) {
979    DigraphWriter<TDGR> tmp(digraph, os);
980    return tmp;
981  }
982
983  /// \brief Return a \ref DigraphWriter class
984  ///
985  /// This function just returns a \ref DigraphWriter class.
986  /// \relates DigraphWriter
987  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
988  template <typename TDGR>
989  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph,
990                                    const std::string& fn) {
991    DigraphWriter<TDGR> tmp(digraph, fn);
992    return tmp;
993  }
994
995  /// \brief Return a \ref DigraphWriter class
996  ///
997  /// This function just returns a \ref DigraphWriter class.
998  /// \relates DigraphWriter
999  /// \sa digraphWriter(const TDGR& digraph, std::ostream& os)
1000  template <typename TDGR>
1001  DigraphWriter<TDGR> digraphWriter(const TDGR& digraph, const char* fn) {
1002    DigraphWriter<TDGR> tmp(digraph, fn);
1003    return tmp;
1004  }
1005
1006  template <typename GR>
1007  class GraphWriter;
1008
1009  template <typename TGR>
1010  GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os = std::cout);
1011  template <typename TGR>
1012  GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn);
1013  template <typename TGR>
1014  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn);
1015
1016  /// \ingroup lemon_io
1017  ///
1018  /// \brief \ref lgf-format "LGF" writer for undirected graphs
1019  ///
1020  /// This utility writes an \ref lgf-format "LGF" file.
1021  ///
1022  /// It can be used almost the same way as \c DigraphWriter.
1023  /// The only difference is that this class can handle edges and
1024  /// edge maps as well as arcs and arc maps.
1025  ///
1026  /// The arc maps are written into the file as two columns, the
1027  /// caption of the columns are the name of the map prefixed with \c
1028  /// '+' and \c '-'. The arcs are written into the \c \@attributes
1029  /// section as a \c '+' or a \c '-' prefix (depends on the direction
1030  /// of the arc) and the label of corresponding edge.
1031  template <typename GR>
1032  class GraphWriter {
1033  public:
1034
1035    typedef GR Graph;
1036    TEMPLATE_GRAPH_TYPEDEFS(GR);
1037
1038  private:
1039
1040
1041    std::ostream* _os;
1042    bool local_os;
1043
1044    const GR& _graph;
1045
1046    std::string _nodes_caption;
1047    std::string _edges_caption;
1048    std::string _attributes_caption;
1049
1050    typedef std::map<Node, std::string> NodeIndex;
1051    NodeIndex _node_index;
1052    typedef std::map<Edge, std::string> EdgeIndex;
1053    EdgeIndex _edge_index;
1054
1055    typedef std::vector<std::pair<std::string,
1056      _writer_bits::MapStorageBase<Node>* > > NodeMaps;
1057    NodeMaps _node_maps;
1058
1059    typedef std::vector<std::pair<std::string,
1060      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
1061    EdgeMaps _edge_maps;
1062
1063    typedef std::vector<std::pair<std::string,
1064      _writer_bits::ValueStorageBase*> > Attributes;
1065    Attributes _attributes;
1066
1067    bool _skip_nodes;
1068    bool _skip_edges;
1069
1070  public:
1071
1072    /// \brief Constructor
1073    ///
1074    /// Construct an undirected graph writer, which writes to the
1075    /// given output stream.
1076    GraphWriter(const GR& graph, std::ostream& os = std::cout)
1077      : _os(&os), local_os(false), _graph(graph),
1078        _skip_nodes(false), _skip_edges(false) {}
1079
1080    /// \brief Constructor
1081    ///
1082    /// Construct a undirected graph writer, which writes to the given
1083    /// output file.
1084    GraphWriter(const GR& graph, const std::string& fn)
1085      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
1086        _skip_nodes(false), _skip_edges(false) {
1087      if (!(*_os)) {
1088        delete _os;
1089        throw IoError("Cannot write file", fn);
1090      }
1091    }
1092
1093    /// \brief Constructor
1094    ///
1095    /// Construct a undirected graph writer, which writes to the given
1096    /// output file.
1097    GraphWriter(const GR& graph, const char* fn)
1098      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
1099        _skip_nodes(false), _skip_edges(false) {
1100      if (!(*_os)) {
1101        delete _os;
1102        throw IoError("Cannot write file", fn);
1103      }
1104    }
1105
1106    /// \brief Destructor
1107    ~GraphWriter() {
1108      for (typename NodeMaps::iterator it = _node_maps.begin();
1109           it != _node_maps.end(); ++it) {
1110        delete it->second;
1111      }
1112
1113      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1114           it != _edge_maps.end(); ++it) {
1115        delete it->second;
1116      }
1117
1118      for (typename Attributes::iterator it = _attributes.begin();
1119           it != _attributes.end(); ++it) {
1120        delete it->second;
1121      }
1122
1123      if (local_os) {
1124        delete _os;
1125      }
1126    }
1127
1128  private:
1129
1130    template <typename TGR>
1131    friend GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os);
1132    template <typename TGR>
1133    friend GraphWriter<TGR> graphWriter(const TGR& graph,
1134                                        const std::string& fn);
1135    template <typename TGR>
1136    friend GraphWriter<TGR> graphWriter(const TGR& graph, const char *fn);
1137
1138    GraphWriter(GraphWriter& other)
1139      : _os(other._os), local_os(other.local_os), _graph(other._graph),
1140        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1141
1142      other._os = 0;
1143      other.local_os = false;
1144
1145      _node_index.swap(other._node_index);
1146      _edge_index.swap(other._edge_index);
1147
1148      _node_maps.swap(other._node_maps);
1149      _edge_maps.swap(other._edge_maps);
1150      _attributes.swap(other._attributes);
1151
1152      _nodes_caption = other._nodes_caption;
1153      _edges_caption = other._edges_caption;
1154      _attributes_caption = other._attributes_caption;
1155    }
1156
1157    GraphWriter& operator=(const GraphWriter&);
1158
1159  public:
1160
1161    /// \name Writing Rules
1162    /// @{
1163
1164    /// \brief Node map writing rule
1165    ///
1166    /// Add a node map writing rule to the writer.
1167    template <typename Map>
1168    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
1169      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1170      _writer_bits::MapStorageBase<Node>* storage =
1171        new _writer_bits::MapStorage<Node, Map>(map);
1172      _node_maps.push_back(std::make_pair(caption, storage));
1173      return *this;
1174    }
1175
1176    /// \brief Node map writing rule
1177    ///
1178    /// Add a node map writing rule with specialized converter to the
1179    /// writer.
1180    template <typename Map, typename Converter>
1181    GraphWriter& nodeMap(const std::string& caption, const Map& map,
1182                           const Converter& converter = Converter()) {
1183      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1184      _writer_bits::MapStorageBase<Node>* storage =
1185        new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
1186      _node_maps.push_back(std::make_pair(caption, storage));
1187      return *this;
1188    }
1189
1190    /// \brief Edge map writing rule
1191    ///
1192    /// Add an edge map writing rule to the writer.
1193    template <typename Map>
1194    GraphWriter& edgeMap(const std::string& caption, const Map& map) {
1195      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1196      _writer_bits::MapStorageBase<Edge>* storage =
1197        new _writer_bits::MapStorage<Edge, Map>(map);
1198      _edge_maps.push_back(std::make_pair(caption, storage));
1199      return *this;
1200    }
1201
1202    /// \brief Edge map writing rule
1203    ///
1204    /// Add an edge map writing rule with specialized converter to the
1205    /// writer.
1206    template <typename Map, typename Converter>
1207    GraphWriter& edgeMap(const std::string& caption, const Map& map,
1208                          const Converter& converter = Converter()) {
1209      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1210      _writer_bits::MapStorageBase<Edge>* storage =
1211        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
1212      _edge_maps.push_back(std::make_pair(caption, storage));
1213      return *this;
1214    }
1215
1216    /// \brief Arc map writing rule
1217    ///
1218    /// Add an arc map writing rule to the writer.
1219    template <typename Map>
1220    GraphWriter& arcMap(const std::string& caption, const Map& map) {
1221      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1222      _writer_bits::MapStorageBase<Edge>* forward_storage =
1223        new _writer_bits::GraphArcMapStorage<GR, true, Map>(_graph, map);
1224      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1225      _writer_bits::MapStorageBase<Edge>* backward_storage =
1226        new _writer_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
1227      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1228      return *this;
1229    }
1230
1231    /// \brief Arc map writing rule
1232    ///
1233    /// Add an arc map writing rule with specialized converter to the
1234    /// writer.
1235    template <typename Map, typename Converter>
1236    GraphWriter& arcMap(const std::string& caption, const Map& map,
1237                          const Converter& converter = Converter()) {
1238      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1239      _writer_bits::MapStorageBase<Edge>* forward_storage =
1240        new _writer_bits::GraphArcMapStorage<GR, true, Map, Converter>
1241        (_graph, map, converter);
1242      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1243      _writer_bits::MapStorageBase<Edge>* backward_storage =
1244        new _writer_bits::GraphArcMapStorage<GR, false, Map, Converter>
1245        (_graph, map, converter);
1246      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1247      return *this;
1248    }
1249
1250    /// \brief Attribute writing rule
1251    ///
1252    /// Add an attribute writing rule to the writer.
1253    template <typename Value>
1254    GraphWriter& attribute(const std::string& caption, const Value& value) {
1255      _writer_bits::ValueStorageBase* storage =
1256        new _writer_bits::ValueStorage<Value>(value);
1257      _attributes.push_back(std::make_pair(caption, storage));
1258      return *this;
1259    }
1260
1261    /// \brief Attribute writing rule
1262    ///
1263    /// Add an attribute writing rule with specialized converter to the
1264    /// writer.
1265    template <typename Value, typename Converter>
1266    GraphWriter& attribute(const std::string& caption, const Value& value,
1267                             const Converter& converter = Converter()) {
1268      _writer_bits::ValueStorageBase* storage =
1269        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1270      _attributes.push_back(std::make_pair(caption, storage));
1271      return *this;
1272    }
1273
1274    /// \brief Node writing rule
1275    ///
1276    /// Add a node writing rule to the writer.
1277    GraphWriter& node(const std::string& caption, const Node& node) {
1278      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1279      Converter converter(_node_index);
1280      _writer_bits::ValueStorageBase* storage =
1281        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1282      _attributes.push_back(std::make_pair(caption, storage));
1283      return *this;
1284    }
1285
1286    /// \brief Edge writing rule
1287    ///
1288    /// Add an edge writing rule to writer.
1289    GraphWriter& edge(const std::string& caption, const Edge& edge) {
1290      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
1291      Converter converter(_edge_index);
1292      _writer_bits::ValueStorageBase* storage =
1293        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
1294      _attributes.push_back(std::make_pair(caption, storage));
1295      return *this;
1296    }
1297
1298    /// \brief Arc writing rule
1299    ///
1300    /// Add an arc writing rule to writer.
1301    GraphWriter& arc(const std::string& caption, const Arc& arc) {
1302      typedef _writer_bits::GraphArcLookUpConverter<GR> Converter;
1303      Converter converter(_graph, _edge_index);
1304      _writer_bits::ValueStorageBase* storage =
1305        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
1306      _attributes.push_back(std::make_pair(caption, storage));
1307      return *this;
1308    }
1309
1310    /// \name Section Captions
1311    /// @{
1312
1313    /// \brief Add an additional caption to the \c \@nodes section
1314    ///
1315    /// Add an additional caption to the \c \@nodes section.
1316    GraphWriter& nodes(const std::string& caption) {
1317      _nodes_caption = caption;
1318      return *this;
1319    }
1320
1321    /// \brief Add an additional caption to the \c \@edges section
1322    ///
1323    /// Add an additional caption to the \c \@edges section.
1324    GraphWriter& edges(const std::string& caption) {
1325      _edges_caption = caption;
1326      return *this;
1327    }
1328
1329    /// \brief Add an additional caption to the \c \@attributes section
1330    ///
1331    /// Add an additional caption to the \c \@attributes section.
1332    GraphWriter& attributes(const std::string& caption) {
1333      _attributes_caption = caption;
1334      return *this;
1335    }
1336
1337    /// \name Skipping Section
1338    /// @{
1339
1340    /// \brief Skip writing the node set
1341    ///
1342    /// The \c \@nodes section will not be written to the stream.
1343    GraphWriter& skipNodes() {
1344      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
1345      _skip_nodes = true;
1346      return *this;
1347    }
1348
1349    /// \brief Skip writing edge set
1350    ///
1351    /// The \c \@edges section will not be written to the stream.
1352    GraphWriter& skipEdges() {
1353      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
1354      _skip_edges = true;
1355      return *this;
1356    }
1357
1358    /// @}
1359
1360  private:
1361
1362    void writeNodes() {
1363      _writer_bits::MapStorageBase<Node>* label = 0;
1364      for (typename NodeMaps::iterator it = _node_maps.begin();
1365           it != _node_maps.end(); ++it) {
1366        if (it->first == "label") {
1367          label = it->second;
1368          break;
1369        }
1370      }
1371
1372      *_os << "@nodes";
1373      if (!_nodes_caption.empty()) {
1374        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
1375      }
1376      *_os << std::endl;
1377
1378      if (label == 0) {
1379        *_os << "label" << '\t';
1380      }
1381      for (typename NodeMaps::iterator it = _node_maps.begin();
1382           it != _node_maps.end(); ++it) {
1383        _writer_bits::writeToken(*_os, it->first) << '\t';
1384      }
1385      *_os << std::endl;
1386
1387      std::vector<Node> nodes;
1388      for (NodeIt n(_graph); n != INVALID; ++n) {
1389        nodes.push_back(n);
1390      }
1391
1392      if (label == 0) {
1393        IdMap<GR, Node> id_map(_graph);
1394        _writer_bits::MapLess<IdMap<GR, Node> > id_less(id_map);
1395        std::sort(nodes.begin(), nodes.end(), id_less);
1396      } else {
1397        label->sort(nodes);
1398      }
1399
1400      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
1401        Node n = nodes[i];
1402        if (label == 0) {
1403          std::ostringstream os;
1404          os << _graph.id(n);
1405          _writer_bits::writeToken(*_os, os.str());
1406          *_os << '\t';
1407          _node_index.insert(std::make_pair(n, os.str()));
1408        }
1409        for (typename NodeMaps::iterator it = _node_maps.begin();
1410             it != _node_maps.end(); ++it) {
1411          std::string value = it->second->get(n);
1412          _writer_bits::writeToken(*_os, value);
1413          if (it->first == "label") {
1414            _node_index.insert(std::make_pair(n, value));
1415          }
1416          *_os << '\t';
1417        }
1418        *_os << std::endl;
1419      }
1420    }
1421
1422    void createNodeIndex() {
1423      _writer_bits::MapStorageBase<Node>* label = 0;
1424      for (typename NodeMaps::iterator it = _node_maps.begin();
1425           it != _node_maps.end(); ++it) {
1426        if (it->first == "label") {
1427          label = it->second;
1428          break;
1429        }
1430      }
1431
1432      if (label == 0) {
1433        for (NodeIt n(_graph); n != INVALID; ++n) {
1434          std::ostringstream os;
1435          os << _graph.id(n);
1436          _node_index.insert(std::make_pair(n, os.str()));
1437        }
1438      } else {
1439        for (NodeIt n(_graph); n != INVALID; ++n) {
1440          std::string value = label->get(n);
1441          _node_index.insert(std::make_pair(n, value));
1442        }
1443      }
1444    }
1445
1446    void writeEdges() {
1447      _writer_bits::MapStorageBase<Edge>* label = 0;
1448      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1449           it != _edge_maps.end(); ++it) {
1450        if (it->first == "label") {
1451          label = it->second;
1452          break;
1453        }
1454      }
1455
1456      *_os << "@edges";
1457      if (!_edges_caption.empty()) {
1458        _writer_bits::writeToken(*_os << ' ', _edges_caption);
1459      }
1460      *_os << std::endl;
1461
1462      *_os << '\t' << '\t';
1463      if (label == 0) {
1464        *_os << "label" << '\t';
1465      }
1466      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1467           it != _edge_maps.end(); ++it) {
1468        _writer_bits::writeToken(*_os, it->first) << '\t';
1469      }
1470      *_os << std::endl;
1471
1472      std::vector<Edge> edges;
1473      for (EdgeIt n(_graph); n != INVALID; ++n) {
1474        edges.push_back(n);
1475      }
1476
1477      if (label == 0) {
1478        IdMap<GR, Edge> id_map(_graph);
1479        _writer_bits::MapLess<IdMap<GR, Edge> > id_less(id_map);
1480        std::sort(edges.begin(), edges.end(), id_less);
1481      } else {
1482        label->sort(edges);
1483      }
1484
1485      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
1486        Edge e = edges[i];
1487        _writer_bits::writeToken(*_os, _node_index.
1488                                 find(_graph.u(e))->second);
1489        *_os << '\t';
1490        _writer_bits::writeToken(*_os, _node_index.
1491                                 find(_graph.v(e))->second);
1492        *_os << '\t';
1493        if (label == 0) {
1494          std::ostringstream os;
1495          os << _graph.id(e);
1496          _writer_bits::writeToken(*_os, os.str());
1497          *_os << '\t';
1498          _edge_index.insert(std::make_pair(e, os.str()));
1499        }
1500        for (typename EdgeMaps::iterator it = _edge_maps.begin();
1501             it != _edge_maps.end(); ++it) {
1502          std::string value = it->second->get(e);
1503          _writer_bits::writeToken(*_os, value);
1504          if (it->first == "label") {
1505            _edge_index.insert(std::make_pair(e, value));
1506          }
1507          *_os << '\t';
1508        }
1509        *_os << std::endl;
1510      }
1511    }
1512
1513    void createEdgeIndex() {
1514      _writer_bits::MapStorageBase<Edge>* label = 0;
1515      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1516           it != _edge_maps.end(); ++it) {
1517        if (it->first == "label") {
1518          label = it->second;
1519          break;
1520        }
1521      }
1522
1523      if (label == 0) {
1524        for (EdgeIt e(_graph); e != INVALID; ++e) {
1525          std::ostringstream os;
1526          os << _graph.id(e);
1527          _edge_index.insert(std::make_pair(e, os.str()));
1528        }
1529      } else {
1530        for (EdgeIt e(_graph); e != INVALID; ++e) {
1531          std::string value = label->get(e);
1532          _edge_index.insert(std::make_pair(e, value));
1533        }
1534      }
1535    }
1536
1537    void writeAttributes() {
1538      if (_attributes.empty()) return;
1539      *_os << "@attributes";
1540      if (!_attributes_caption.empty()) {
1541        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
1542      }
1543      *_os << std::endl;
1544      for (typename Attributes::iterator it = _attributes.begin();
1545           it != _attributes.end(); ++it) {
1546        _writer_bits::writeToken(*_os, it->first) << ' ';
1547        _writer_bits::writeToken(*_os, it->second->get());
1548        *_os << std::endl;
1549      }
1550    }
1551
1552  public:
1553
1554    /// \name Execution of the Writer
1555    /// @{
1556
1557    /// \brief Start the batch processing
1558    ///
1559    /// This function starts the batch processing.
1560    void run() {
1561      if (!_skip_nodes) {
1562        writeNodes();
1563      } else {
1564        createNodeIndex();
1565      }
1566      if (!_skip_edges) {
1567        writeEdges();
1568      } else {
1569        createEdgeIndex();
1570      }
1571      writeAttributes();
1572    }
1573
1574    /// \brief Give back the stream of the writer
1575    ///
1576    /// Give back the stream of the writer
1577    std::ostream& ostream() {
1578      return *_os;
1579    }
1580
1581    /// @}
1582  };
1583
1584  /// \ingroup lemon_io
1585  ///
1586  /// \brief Return a \ref GraphWriter class
1587  ///
1588  /// This function just returns a \ref GraphWriter class.
1589  ///
1590  /// With this function a graph can be write to a file or output
1591  /// stream in \ref lgf-format "LGF" format with several maps and
1592  /// attributes. For example, with the following code a weighted
1593  /// matching problem can be written to the standard output, i.e. a
1594  /// graph with a \e weight map on the edges:
1595  ///
1596  ///\code
1597  ///ListGraph graph;
1598  ///ListGraph::EdgeMap<int> weight(graph);
1599  ///  // Setting the weight map
1600  ///graphWriter(graph, std::cout).
1601  ///  edgeMap("weight", weight).
1602  ///  run();
1603  ///\endcode
1604  ///
1605  /// For a complete documentation, please see the \ref GraphWriter
1606  /// class documentation.
1607  /// \warning Don't forget to put the \ref GraphWriter::run() "run()"
1608  /// to the end of the parameter list.
1609  /// \relates GraphWriter
1610  /// \sa graphWriter(const TGR& graph, const std::string& fn)
1611  /// \sa graphWriter(const TGR& graph, const char* fn)
1612  template <typename TGR>
1613  GraphWriter<TGR> graphWriter(const TGR& graph, std::ostream& os) {
1614    GraphWriter<TGR> tmp(graph, os);
1615    return tmp;
1616  }
1617
1618  /// \brief Return a \ref GraphWriter class
1619  ///
1620  /// This function just returns a \ref GraphWriter class.
1621  /// \relates GraphWriter
1622  /// \sa graphWriter(const TGR& graph, std::ostream& os)
1623  template <typename TGR>
1624  GraphWriter<TGR> graphWriter(const TGR& graph, const std::string& fn) {
1625    GraphWriter<TGR> tmp(graph, fn);
1626    return tmp;
1627  }
1628
1629  /// \brief Return a \ref GraphWriter class
1630  ///
1631  /// This function just returns a \ref GraphWriter class.
1632  /// \relates GraphWriter
1633  /// \sa graphWriter(const TGR& graph, std::ostream& os)
1634  template <typename TGR>
1635  GraphWriter<TGR> graphWriter(const TGR& graph, const char* fn) {
1636    GraphWriter<TGR> tmp(graph, fn);
1637    return tmp;
1638  }
1639
1640  template <typename BGR>
1641  class BpGraphWriter;
1642
1643  template <typename TBGR>
1644  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
1645                                    std::ostream& os = std::cout);
1646  template <typename TBGR>
1647  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn);
1648  template <typename TBGR>
1649  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn);
1650
1651  /// \ingroup lemon_io
1652  ///
1653  /// \brief \ref lgf-format "LGF" writer for undirected bipartite graphs
1654  ///
1655  /// This utility writes an \ref lgf-format "LGF" file.
1656  ///
1657  /// It can be used almost the same way as \c GraphWriter, but it
1658  /// reads the red and blue nodes from separate sections, and these
1659  /// sections can contain different set of maps.
1660  ///
1661  /// The red and blue node maps are written to the corresponding
1662  /// sections. The node maps are written to both of these sections
1663  /// with the same map name.
1664  template <typename BGR>
1665  class BpGraphWriter {
1666  public:
1667
1668    typedef BGR BpGraph;
1669    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
1670
1671  private:
1672
1673
1674    std::ostream* _os;
1675    bool local_os;
1676
1677    const BGR& _graph;
1678
1679    std::string _nodes_caption;
1680    std::string _edges_caption;
1681    std::string _attributes_caption;
1682
1683    typedef std::map<Node, std::string> RedNodeIndex;
1684    RedNodeIndex _red_node_index;
1685    typedef std::map<Node, std::string> BlueNodeIndex;
1686    BlueNodeIndex _blue_node_index;
1687    typedef std::map<Edge, std::string> EdgeIndex;
1688    EdgeIndex _edge_index;
1689
1690    typedef std::vector<std::pair<std::string,
1691      _writer_bits::MapStorageBase<RedNode>* > > RedNodeMaps;
1692    RedNodeMaps _red_node_maps;
1693    typedef std::vector<std::pair<std::string,
1694      _writer_bits::MapStorageBase<BlueNode>* > > BlueNodeMaps;
1695    BlueNodeMaps _blue_node_maps;
1696
1697    typedef std::vector<std::pair<std::string,
1698      _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
1699    EdgeMaps _edge_maps;
1700
1701    typedef std::vector<std::pair<std::string,
1702      _writer_bits::ValueStorageBase*> > Attributes;
1703    Attributes _attributes;
1704
1705    bool _skip_nodes;
1706    bool _skip_edges;
1707
1708  public:
1709
1710    /// \brief Constructor
1711    ///
1712    /// Construct a bipartite graph writer, which writes to the given
1713    /// output stream.
1714    BpGraphWriter(const BGR& graph, std::ostream& os = std::cout)
1715      : _os(&os), local_os(false), _graph(graph),
1716        _skip_nodes(false), _skip_edges(false) {}
1717
1718    /// \brief Constructor
1719    ///
1720    /// Construct a bipartite graph writer, which writes to the given
1721    /// output file.
1722    BpGraphWriter(const BGR& graph, const std::string& fn)
1723      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
1724        _skip_nodes(false), _skip_edges(false) {
1725      if (!(*_os)) {
1726        delete _os;
1727        throw IoError("Cannot write file", fn);
1728      }
1729    }
1730
1731    /// \brief Constructor
1732    ///
1733    /// Construct a bipartite graph writer, which writes to the given
1734    /// output file.
1735    BpGraphWriter(const BGR& graph, const char* fn)
1736      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
1737        _skip_nodes(false), _skip_edges(false) {
1738      if (!(*_os)) {
1739        delete _os;
1740        throw IoError("Cannot write file", fn);
1741      }
1742    }
1743
1744    /// \brief Destructor
1745    ~BpGraphWriter() {
1746      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
1747           it != _red_node_maps.end(); ++it) {
1748        delete it->second;
1749      }
1750
1751      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
1752           it != _blue_node_maps.end(); ++it) {
1753        delete it->second;
1754      }
1755
1756      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1757           it != _edge_maps.end(); ++it) {
1758        delete it->second;
1759      }
1760
1761      for (typename Attributes::iterator it = _attributes.begin();
1762           it != _attributes.end(); ++it) {
1763        delete it->second;
1764      }
1765
1766      if (local_os) {
1767        delete _os;
1768      }
1769    }
1770
1771  private:
1772
1773    template <typename TBGR>
1774    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
1775                                             std::ostream& os);
1776    template <typename TBGR>
1777    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph,
1778                                             const std::string& fn);
1779    template <typename TBGR>
1780    friend BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char *fn);
1781
1782    BpGraphWriter(BpGraphWriter& other)
1783      : _os(other._os), local_os(other.local_os), _graph(other._graph),
1784        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1785
1786      other._os = 0;
1787      other.local_os = false;
1788
1789      _red_node_index.swap(other._red_node_index);
1790      _blue_node_index.swap(other._blue_node_index);
1791      _edge_index.swap(other._edge_index);
1792
1793      _red_node_maps.swap(other._red_node_maps);
1794      _blue_node_maps.swap(other._blue_node_maps);
1795      _edge_maps.swap(other._edge_maps);
1796      _attributes.swap(other._attributes);
1797
1798      _nodes_caption = other._nodes_caption;
1799      _edges_caption = other._edges_caption;
1800      _attributes_caption = other._attributes_caption;
1801    }
1802
1803    BpGraphWriter& operator=(const BpGraphWriter&);
1804
1805  public:
1806
1807    /// \name Writing Rules
1808    /// @{
1809
1810    /// \brief Node map writing rule
1811    ///
1812    /// Add a node map writing rule to the writer.
1813    template <typename Map>
1814    BpGraphWriter& nodeMap(const std::string& caption, const Map& map) {
1815      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1816      _writer_bits::MapStorageBase<RedNode>* red_storage =
1817        new _writer_bits::MapStorage<RedNode, Map>(map);
1818      _red_node_maps.push_back(std::make_pair(caption, red_storage));
1819      _writer_bits::MapStorageBase<BlueNode>* blue_storage =
1820        new _writer_bits::MapStorage<BlueNode, Map>(map);
1821      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
1822      return *this;
1823    }
1824
1825    /// \brief Node map writing rule
1826    ///
1827    /// Add a node map writing rule with specialized converter to the
1828    /// writer.
1829    template <typename Map, typename Converter>
1830    BpGraphWriter& nodeMap(const std::string& caption, const Map& map,
1831                           const Converter& converter = Converter()) {
1832      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1833      _writer_bits::MapStorageBase<RedNode>* red_storage =
1834        new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter);
1835      _red_node_maps.push_back(std::make_pair(caption, red_storage));
1836      _writer_bits::MapStorageBase<BlueNode>* blue_storage =
1837        new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
1838      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
1839      return *this;
1840    }
1841
1842    /// \brief Red node map writing rule
1843    ///
1844    /// Add a red node map writing rule to the writer.
1845    template <typename Map>
1846    BpGraphWriter& redNodeMap(const std::string& caption, const Map& map) {
1847      checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>();
1848      _writer_bits::MapStorageBase<RedNode>* storage =
1849        new _writer_bits::MapStorage<RedNode, Map>(map);
1850      _red_node_maps.push_back(std::make_pair(caption, storage));
1851      return *this;
1852    }
1853
1854    /// \brief Red node map writing rule
1855    ///
1856    /// Add a red node map writing rule with specialized converter to the
1857    /// writer.
1858    template <typename Map, typename Converter>
1859    BpGraphWriter& redNodeMap(const std::string& caption, const Map& map,
1860                              const Converter& converter = Converter()) {
1861      checkConcept<concepts::ReadMap<RedNode, typename Map::Value>, Map>();
1862      _writer_bits::MapStorageBase<RedNode>* storage =
1863        new _writer_bits::MapStorage<RedNode, Map, Converter>(map, converter);
1864      _red_node_maps.push_back(std::make_pair(caption, storage));
1865      return *this;
1866    }
1867
1868    /// \brief Blue node map writing rule
1869    ///
1870    /// Add a blue node map writing rule to the writer.
1871    template <typename Map>
1872    BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map) {
1873      checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>();
1874      _writer_bits::MapStorageBase<BlueNode>* storage =
1875        new _writer_bits::MapStorage<BlueNode, Map>(map);
1876      _blue_node_maps.push_back(std::make_pair(caption, storage));
1877      return *this;
1878    }
1879
1880    /// \brief Blue node map writing rule
1881    ///
1882    /// Add a blue node map writing rule with specialized converter to the
1883    /// writer.
1884    template <typename Map, typename Converter>
1885    BpGraphWriter& blueNodeMap(const std::string& caption, const Map& map,
1886                               const Converter& converter = Converter()) {
1887      checkConcept<concepts::ReadMap<BlueNode, typename Map::Value>, Map>();
1888      _writer_bits::MapStorageBase<BlueNode>* storage =
1889        new _writer_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
1890      _blue_node_maps.push_back(std::make_pair(caption, storage));
1891      return *this;
1892    }
1893
1894    /// \brief Edge map writing rule
1895    ///
1896    /// Add an edge map writing rule to the writer.
1897    template <typename Map>
1898    BpGraphWriter& edgeMap(const std::string& caption, const Map& map) {
1899      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1900      _writer_bits::MapStorageBase<Edge>* storage =
1901        new _writer_bits::MapStorage<Edge, Map>(map);
1902      _edge_maps.push_back(std::make_pair(caption, storage));
1903      return *this;
1904    }
1905
1906    /// \brief Edge map writing rule
1907    ///
1908    /// Add an edge map writing rule with specialized converter to the
1909    /// writer.
1910    template <typename Map, typename Converter>
1911    BpGraphWriter& edgeMap(const std::string& caption, const Map& map,
1912                          const Converter& converter = Converter()) {
1913      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1914      _writer_bits::MapStorageBase<Edge>* storage =
1915        new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
1916      _edge_maps.push_back(std::make_pair(caption, storage));
1917      return *this;
1918    }
1919
1920    /// \brief Arc map writing rule
1921    ///
1922    /// Add an arc map writing rule to the writer.
1923    template <typename Map>
1924    BpGraphWriter& arcMap(const std::string& caption, const Map& map) {
1925      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1926      _writer_bits::MapStorageBase<Edge>* forward_storage =
1927        new _writer_bits::GraphArcMapStorage<BGR, true, Map>(_graph, map);
1928      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1929      _writer_bits::MapStorageBase<Edge>* backward_storage =
1930        new _writer_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
1931      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1932      return *this;
1933    }
1934
1935    /// \brief Arc map writing rule
1936    ///
1937    /// Add an arc map writing rule with specialized converter to the
1938    /// writer.
1939    template <typename Map, typename Converter>
1940    BpGraphWriter& arcMap(const std::string& caption, const Map& map,
1941                          const Converter& converter = Converter()) {
1942      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1943      _writer_bits::MapStorageBase<Edge>* forward_storage =
1944        new _writer_bits::GraphArcMapStorage<BGR, true, Map, Converter>
1945        (_graph, map, converter);
1946      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1947      _writer_bits::MapStorageBase<Edge>* backward_storage =
1948        new _writer_bits::GraphArcMapStorage<BGR, false, Map, Converter>
1949        (_graph, map, converter);
1950      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1951      return *this;
1952    }
1953
1954    /// \brief Attribute writing rule
1955    ///
1956    /// Add an attribute writing rule to the writer.
1957    template <typename Value>
1958    BpGraphWriter& attribute(const std::string& caption, const Value& value) {
1959      _writer_bits::ValueStorageBase* storage =
1960        new _writer_bits::ValueStorage<Value>(value);
1961      _attributes.push_back(std::make_pair(caption, storage));
1962      return *this;
1963    }
1964
1965    /// \brief Attribute writing rule
1966    ///
1967    /// Add an attribute writing rule with specialized converter to the
1968    /// writer.
1969    template <typename Value, typename Converter>
1970    BpGraphWriter& attribute(const std::string& caption, const Value& value,
1971                             const Converter& converter = Converter()) {
1972      _writer_bits::ValueStorageBase* storage =
1973        new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1974      _attributes.push_back(std::make_pair(caption, storage));
1975      return *this;
1976    }
1977
1978    /// \brief Node writing rule
1979    ///
1980    /// Add a node writing rule to the writer.
1981    BpGraphWriter& node(const std::string& caption, const Node& node) {
1982      typedef _writer_bits::DoubleMapLookUpConverter<
1983        Node, RedNodeIndex, BlueNodeIndex> Converter;
1984      Converter converter(_red_node_index, _blue_node_index);
1985      _writer_bits::ValueStorageBase* storage =
1986        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1987      _attributes.push_back(std::make_pair(caption, storage));
1988      return *this;
1989    }
1990
1991    /// \brief Red node writing rule
1992    ///
1993    /// Add a red node writing rule to the writer.
1994    BpGraphWriter& redNode(const std::string& caption, const RedNode& node) {
1995      typedef _writer_bits::MapLookUpConverter<Node> Converter;
1996      Converter converter(_red_node_index);
1997      _writer_bits::ValueStorageBase* storage =
1998        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1999      _attributes.push_back(std::make_pair(caption, storage));
2000      return *this;
2001    }
2002
2003    /// \brief Blue node writing rule
2004    ///
2005    /// Add a blue node writing rule to the writer.
2006    BpGraphWriter& blueNode(const std::string& caption, const BlueNode& node) {
2007      typedef _writer_bits::MapLookUpConverter<Node> Converter;
2008      Converter converter(_blue_node_index);
2009      _writer_bits::ValueStorageBase* storage =
2010        new _writer_bits::ValueStorage<Node, Converter>(node, converter);
2011      _attributes.push_back(std::make_pair(caption, storage));
2012      return *this;
2013    }
2014
2015    /// \brief Edge writing rule
2016    ///
2017    /// Add an edge writing rule to writer.
2018    BpGraphWriter& edge(const std::string& caption, const Edge& edge) {
2019      typedef _writer_bits::MapLookUpConverter<Edge> Converter;
2020      Converter converter(_edge_index);
2021      _writer_bits::ValueStorageBase* storage =
2022        new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
2023      _attributes.push_back(std::make_pair(caption, storage));
2024      return *this;
2025    }
2026
2027    /// \brief Arc writing rule
2028    ///
2029    /// Add an arc writing rule to writer.
2030    BpGraphWriter& arc(const std::string& caption, const Arc& arc) {
2031      typedef _writer_bits::GraphArcLookUpConverter<BGR> Converter;
2032      Converter converter(_graph, _edge_index);
2033      _writer_bits::ValueStorageBase* storage =
2034        new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
2035      _attributes.push_back(std::make_pair(caption, storage));
2036      return *this;
2037    }
2038
2039    /// \name Section Captions
2040    /// @{
2041
2042    /// \brief Add an additional caption to the \c \@red_nodes and
2043    /// \c \@blue_nodes section
2044    ///
2045    /// Add an additional caption to the \c \@red_nodes and \c
2046    /// \@blue_nodes section.
2047    BpGraphWriter& nodes(const std::string& caption) {
2048      _nodes_caption = caption;
2049      return *this;
2050    }
2051
2052    /// \brief Add an additional caption to the \c \@edges section
2053    ///
2054    /// Add an additional caption to the \c \@edges section.
2055    BpGraphWriter& edges(const std::string& caption) {
2056      _edges_caption = caption;
2057      return *this;
2058    }
2059
2060    /// \brief Add an additional caption to the \c \@attributes section
2061    ///
2062    /// Add an additional caption to the \c \@attributes section.
2063    BpGraphWriter& attributes(const std::string& caption) {
2064      _attributes_caption = caption;
2065      return *this;
2066    }
2067
2068    /// \name Skipping Section
2069    /// @{
2070
2071    /// \brief Skip writing the node set
2072    ///
2073    /// The \c \@red_nodes and \c \@blue_nodes section will not be
2074    /// written to the stream.
2075    BpGraphWriter& skipNodes() {
2076      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
2077      _skip_nodes = true;
2078      return *this;
2079    }
2080
2081    /// \brief Skip writing edge set
2082    ///
2083    /// The \c \@edges section will not be written to the stream.
2084    BpGraphWriter& skipEdges() {
2085      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
2086      _skip_edges = true;
2087      return *this;
2088    }
2089
2090    /// @}
2091
2092  private:
2093
2094    void writeRedNodes() {
2095      _writer_bits::MapStorageBase<RedNode>* label = 0;
2096      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2097           it != _red_node_maps.end(); ++it) {
2098        if (it->first == "label") {
2099          label = it->second;
2100          break;
2101        }
2102      }
2103
2104      *_os << "@red_nodes";
2105      if (!_nodes_caption.empty()) {
2106        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
2107      }
2108      *_os << std::endl;
2109
2110      if (label == 0) {
2111        *_os << "label" << '\t';
2112      }
2113      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2114           it != _red_node_maps.end(); ++it) {
2115        _writer_bits::writeToken(*_os, it->first) << '\t';
2116      }
2117      *_os << std::endl;
2118
2119      std::vector<RedNode> nodes;
2120      for (RedNodeIt n(_graph); n != INVALID; ++n) {
2121        nodes.push_back(n);
2122      }
2123
2124      if (label == 0) {
2125        IdMap<BGR, Node> id_map(_graph);
2126        _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map);
2127        std::sort(nodes.begin(), nodes.end(), id_less);
2128      } else {
2129        label->sort(nodes);
2130      }
2131
2132      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
2133        RedNode n = nodes[i];
2134        if (label == 0) {
2135          std::ostringstream os;
2136          os << _graph.id(static_cast<Node>(n));
2137          _writer_bits::writeToken(*_os, os.str());
2138          *_os << '\t';
2139          _red_node_index.insert(std::make_pair(n, os.str()));
2140        }
2141        for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2142             it != _red_node_maps.end(); ++it) {
2143          std::string value = it->second->get(n);
2144          _writer_bits::writeToken(*_os, value);
2145          if (it->first == "label") {
2146            _red_node_index.insert(std::make_pair(n, value));
2147          }
2148          *_os << '\t';
2149        }
2150        *_os << std::endl;
2151      }
2152    }
2153
2154    void writeBlueNodes() {
2155      _writer_bits::MapStorageBase<BlueNode>* label = 0;
2156      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2157           it != _blue_node_maps.end(); ++it) {
2158        if (it->first == "label") {
2159          label = it->second;
2160          break;
2161        }
2162      }
2163
2164      *_os << "@blue_nodes";
2165      if (!_nodes_caption.empty()) {
2166        _writer_bits::writeToken(*_os << ' ', _nodes_caption);
2167      }
2168      *_os << std::endl;
2169
2170      if (label == 0) {
2171        *_os << "label" << '\t';
2172      }
2173      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2174           it != _blue_node_maps.end(); ++it) {
2175        _writer_bits::writeToken(*_os, it->first) << '\t';
2176      }
2177      *_os << std::endl;
2178
2179      std::vector<BlueNode> nodes;
2180      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2181        nodes.push_back(n);
2182      }
2183
2184      if (label == 0) {
2185        IdMap<BGR, Node> id_map(_graph);
2186        _writer_bits::MapLess<IdMap<BGR, Node> > id_less(id_map);
2187        std::sort(nodes.begin(), nodes.end(), id_less);
2188      } else {
2189        label->sort(nodes);
2190      }
2191
2192      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
2193        BlueNode n = nodes[i];
2194        if (label == 0) {
2195          std::ostringstream os;
2196          os << _graph.id(static_cast<Node>(n));
2197          _writer_bits::writeToken(*_os, os.str());
2198          *_os << '\t';
2199          _blue_node_index.insert(std::make_pair(n, os.str()));
2200        }
2201        for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2202             it != _blue_node_maps.end(); ++it) {
2203          std::string value = it->second->get(n);
2204          _writer_bits::writeToken(*_os, value);
2205          if (it->first == "label") {
2206            _blue_node_index.insert(std::make_pair(n, value));
2207          }
2208          *_os << '\t';
2209        }
2210        *_os << std::endl;
2211      }
2212    }
2213
2214    void createRedNodeIndex() {
2215      _writer_bits::MapStorageBase<RedNode>* label = 0;
2216      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2217           it != _red_node_maps.end(); ++it) {
2218        if (it->first == "label") {
2219          label = it->second;
2220          break;
2221        }
2222      }
2223
2224      if (label == 0) {
2225        for (RedNodeIt n(_graph); n != INVALID; ++n) {
2226          std::ostringstream os;
2227          os << _graph.id(n);
2228          _red_node_index.insert(std::make_pair(n, os.str()));
2229        }
2230      } else {
2231        for (RedNodeIt n(_graph); n != INVALID; ++n) {
2232          std::string value = label->get(n);
2233          _red_node_index.insert(std::make_pair(n, value));
2234        }
2235      }
2236    }
2237
2238    void createBlueNodeIndex() {
2239      _writer_bits::MapStorageBase<BlueNode>* label = 0;
2240      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2241           it != _blue_node_maps.end(); ++it) {
2242        if (it->first == "label") {
2243          label = it->second;
2244          break;
2245        }
2246      }
2247
2248      if (label == 0) {
2249        for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2250          std::ostringstream os;
2251          os << _graph.id(n);
2252          _blue_node_index.insert(std::make_pair(n, os.str()));
2253        }
2254      } else {
2255        for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2256          std::string value = label->get(n);
2257          _blue_node_index.insert(std::make_pair(n, value));
2258        }
2259      }
2260    }
2261
2262    void writeEdges() {
2263      _writer_bits::MapStorageBase<Edge>* label = 0;
2264      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2265           it != _edge_maps.end(); ++it) {
2266        if (it->first == "label") {
2267          label = it->second;
2268          break;
2269        }
2270      }
2271
2272      *_os << "@edges";
2273      if (!_edges_caption.empty()) {
2274        _writer_bits::writeToken(*_os << ' ', _edges_caption);
2275      }
2276      *_os << std::endl;
2277
2278      *_os << '\t' << '\t';
2279      if (label == 0) {
2280        *_os << "label" << '\t';
2281      }
2282      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2283           it != _edge_maps.end(); ++it) {
2284        _writer_bits::writeToken(*_os, it->first) << '\t';
2285      }
2286      *_os << std::endl;
2287
2288      std::vector<Edge> edges;
2289      for (EdgeIt n(_graph); n != INVALID; ++n) {
2290        edges.push_back(n);
2291      }
2292
2293      if (label == 0) {
2294        IdMap<BGR, Edge> id_map(_graph);
2295        _writer_bits::MapLess<IdMap<BGR, Edge> > id_less(id_map);
2296        std::sort(edges.begin(), edges.end(), id_less);
2297      } else {
2298        label->sort(edges);
2299      }
2300
2301      for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
2302        Edge e = edges[i];
2303        _writer_bits::writeToken(*_os, _red_node_index.
2304                                 find(_graph.redNode(e))->second);
2305        *_os << '\t';
2306        _writer_bits::writeToken(*_os, _blue_node_index.
2307                                 find(_graph.blueNode(e))->second);
2308        *_os << '\t';
2309        if (label == 0) {
2310          std::ostringstream os;
2311          os << _graph.id(e);
2312          _writer_bits::writeToken(*_os, os.str());
2313          *_os << '\t';
2314          _edge_index.insert(std::make_pair(e, os.str()));
2315        }
2316        for (typename EdgeMaps::iterator it = _edge_maps.begin();
2317             it != _edge_maps.end(); ++it) {
2318          std::string value = it->second->get(e);
2319          _writer_bits::writeToken(*_os, value);
2320          if (it->first == "label") {
2321            _edge_index.insert(std::make_pair(e, value));
2322          }
2323          *_os << '\t';
2324        }
2325        *_os << std::endl;
2326      }
2327    }
2328
2329    void createEdgeIndex() {
2330      _writer_bits::MapStorageBase<Edge>* label = 0;
2331      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2332           it != _edge_maps.end(); ++it) {
2333        if (it->first == "label") {
2334          label = it->second;
2335          break;
2336        }
2337      }
2338
2339      if (label == 0) {
2340        for (EdgeIt e(_graph); e != INVALID; ++e) {
2341          std::ostringstream os;
2342          os << _graph.id(e);
2343          _edge_index.insert(std::make_pair(e, os.str()));
2344        }
2345      } else {
2346        for (EdgeIt e(_graph); e != INVALID; ++e) {
2347          std::string value = label->get(e);
2348          _edge_index.insert(std::make_pair(e, value));
2349        }
2350      }
2351    }
2352
2353    void writeAttributes() {
2354      if (_attributes.empty()) return;
2355      *_os << "@attributes";
2356      if (!_attributes_caption.empty()) {
2357        _writer_bits::writeToken(*_os << ' ', _attributes_caption);
2358      }
2359      *_os << std::endl;
2360      for (typename Attributes::iterator it = _attributes.begin();
2361           it != _attributes.end(); ++it) {
2362        _writer_bits::writeToken(*_os, it->first) << ' ';
2363        _writer_bits::writeToken(*_os, it->second->get());
2364        *_os << std::endl;
2365      }
2366    }
2367
2368  public:
2369
2370    /// \name Execution of the Writer
2371    /// @{
2372
2373    /// \brief Start the batch processing
2374    ///
2375    /// This function starts the batch processing.
2376    void run() {
2377      if (!_skip_nodes) {
2378        writeRedNodes();
2379        writeBlueNodes();
2380      } else {
2381        createRedNodeIndex();
2382        createBlueNodeIndex();
2383      }
2384      if (!_skip_edges) {
2385        writeEdges();
2386      } else {
2387        createEdgeIndex();
2388      }
2389      writeAttributes();
2390    }
2391
2392    /// \brief Give back the stream of the writer
2393    ///
2394    /// Give back the stream of the writer
2395    std::ostream& ostream() {
2396      return *_os;
2397    }
2398
2399    /// @}
2400  };
2401
2402  /// \ingroup lemon_io
2403  ///
2404  /// \brief Return a \ref BpGraphWriter class
2405  ///
2406  /// This function just returns a \ref BpGraphWriter class.
2407  ///
2408  /// With this function a bipartite graph can be write to a file or output
2409  /// stream in \ref lgf-format "LGF" format with several maps and
2410  /// attributes. For example, with the following code a bipartite
2411  /// weighted matching problem can be written to the standard output,
2412  /// i.e. a graph with a \e weight map on the edges:
2413  ///
2414  ///\code
2415  ///ListBpGraph graph;
2416  ///ListBpGraph::EdgeMap<int> weight(graph);
2417  ///  // Setting the weight map
2418  ///bpGraphWriter(graph, std::cout).
2419  ///  edgeMap("weight", weight).
2420  ///  run();
2421  ///\endcode
2422  ///
2423  /// For a complete documentation, please see the \ref BpGraphWriter
2424  /// class documentation.
2425  /// \warning Don't forget to put the \ref BpGraphWriter::run() "run()"
2426  /// to the end of the parameter list.
2427  /// \relates BpGraphWriter
2428  /// \sa bpGraphWriter(const TBGR& graph, const std::string& fn)
2429  /// \sa bpGraphWriter(const TBGR& graph, const char* fn)
2430  template <typename TBGR>
2431  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, std::ostream& os) {
2432    BpGraphWriter<TBGR> tmp(graph, os);
2433    return tmp;
2434  }
2435
2436  /// \brief Return a \ref BpGraphWriter class
2437  ///
2438  /// This function just returns a \ref BpGraphWriter class.
2439  /// \relates BpGraphWriter
2440  /// \sa graphWriter(const TBGR& graph, std::ostream& os)
2441  template <typename TBGR>
2442  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const std::string& fn) {
2443    BpGraphWriter<TBGR> tmp(graph, fn);
2444    return tmp;
2445  }
2446
2447  /// \brief Return a \ref BpGraphWriter class
2448  ///
2449  /// This function just returns a \ref BpGraphWriter class.
2450  /// \relates BpGraphWriter
2451  /// \sa graphWriter(const TBGR& graph, std::ostream& os)
2452  template <typename TBGR>
2453  BpGraphWriter<TBGR> bpGraphWriter(const TBGR& graph, const char* fn) {
2454    BpGraphWriter<TBGR> tmp(graph, fn);
2455    return tmp;
2456  }
2457
2458  class SectionWriter;
2459
2460  SectionWriter sectionWriter(std::istream& is);
2461  SectionWriter sectionWriter(const std::string& fn);
2462  SectionWriter sectionWriter(const char* fn);
2463
2464  /// \ingroup lemon_io
2465  ///
2466  /// \brief Section writer class
2467  ///
2468  /// In the \ref lgf-format "LGF" file extra sections can be placed,
2469  /// which contain any data in arbitrary format. Such sections can be
2470  /// written with this class. A writing rule can be added to the
2471  /// class with two different functions. With the \c sectionLines()
2472  /// function a generator can write the section line-by-line, while
2473  /// with the \c sectionStream() member the section can be written to
2474  /// an output stream.
2475  class SectionWriter {
2476  private:
2477
2478    std::ostream* _os;
2479    bool local_os;
2480
2481    typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
2482    Sections;
2483
2484    Sections _sections;
2485
2486  public:
2487
2488    /// \brief Constructor
2489    ///
2490    /// Construct a section writer, which writes to the given output
2491    /// stream.
2492    SectionWriter(std::ostream& os)
2493      : _os(&os), local_os(false) {}
2494
2495    /// \brief Constructor
2496    ///
2497    /// Construct a section writer, which writes into the given file.
2498    SectionWriter(const std::string& fn)
2499      : _os(new std::ofstream(fn.c_str())), local_os(true) {
2500      if (!(*_os)) {
2501        delete _os;
2502        throw IoError("Cannot write file", fn);
2503      }
2504    }
2505
2506    /// \brief Constructor
2507    ///
2508    /// Construct a section writer, which writes into the given file.
2509    SectionWriter(const char* fn)
2510      : _os(new std::ofstream(fn)), local_os(true) {
2511      if (!(*_os)) {
2512        delete _os;
2513        throw IoError("Cannot write file", fn);
2514      }
2515    }
2516
2517    /// \brief Destructor
2518    ~SectionWriter() {
2519      for (Sections::iterator it = _sections.begin();
2520           it != _sections.end(); ++it) {
2521        delete it->second;
2522      }
2523
2524      if (local_os) {
2525        delete _os;
2526      }
2527
2528    }
2529
2530  private:
2531
2532    friend SectionWriter sectionWriter(std::ostream& os);
2533    friend SectionWriter sectionWriter(const std::string& fn);
2534    friend SectionWriter sectionWriter(const char* fn);
2535
2536    SectionWriter(SectionWriter& other)
2537      : _os(other._os), local_os(other.local_os) {
2538
2539      other._os = 0;
2540      other.local_os = false;
2541
2542      _sections.swap(other._sections);
2543    }
2544
2545    SectionWriter& operator=(const SectionWriter&);
2546
2547  public:
2548
2549    /// \name Section Writers
2550    /// @{
2551
2552    /// \brief Add a section writer with line oriented writing
2553    ///
2554    /// The first parameter is the type descriptor of the section, the
2555    /// second is a generator with std::string values. At the writing
2556    /// process, the returned \c std::string will be written into the
2557    /// output file until it is an empty string.
2558    ///
2559    /// For example, an integer vector is written into a section.
2560    ///\code
2561    ///  @numbers
2562    ///  12 45 23 78
2563    ///  4 28 38 28
2564    ///  23 6 16
2565    ///\endcode
2566    ///
2567    /// The generator is implemented as a struct.
2568    ///\code
2569    ///  struct NumberSection {
2570    ///    std::vector<int>::const_iterator _it, _end;
2571    ///    NumberSection(const std::vector<int>& data)
2572    ///      : _it(data.begin()), _end(data.end()) {}
2573    ///    std::string operator()() {
2574    ///      int rem_in_line = 4;
2575    ///      std::ostringstream ls;
2576    ///      while (rem_in_line > 0 && _it != _end) {
2577    ///        ls << *(_it++) << ' ';
2578    ///        --rem_in_line;
2579    ///      }
2580    ///      return ls.str();
2581    ///    }
2582    ///  };
2583    ///
2584    ///  // ...
2585    ///
2586    ///  writer.sectionLines("numbers", NumberSection(vec));
2587    ///\endcode
2588    template <typename Functor>
2589    SectionWriter& sectionLines(const std::string& type, Functor functor) {
2590      LEMON_ASSERT(!type.empty(), "Type is empty.");
2591      _sections.push_back(std::make_pair(type,
2592        new _writer_bits::LineSection<Functor>(functor)));
2593      return *this;
2594    }
2595
2596
2597    /// \brief Add a section writer with stream oriented writing
2598    ///
2599    /// The first parameter is the type of the section, the second is
2600    /// a functor, which takes a \c std::ostream& parameter. The
2601    /// functor writes the section to the output stream.
2602    /// \warning The last line must be closed with end-line character.
2603    template <typename Functor>
2604    SectionWriter& sectionStream(const std::string& type, Functor functor) {
2605      LEMON_ASSERT(!type.empty(), "Type is empty.");
2606      _sections.push_back(std::make_pair(type,
2607         new _writer_bits::StreamSection<Functor>(functor)));
2608      return *this;
2609    }
2610
2611    /// @}
2612
2613  public:
2614
2615
2616    /// \name Execution of the Writer
2617    /// @{
2618
2619    /// \brief Start the batch processing
2620    ///
2621    /// This function starts the batch processing.
2622    void run() {
2623
2624      LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");
2625
2626      for (Sections::iterator it = _sections.begin();
2627           it != _sections.end(); ++it) {
2628        (*_os) << '@' << it->first << std::endl;
2629        it->second->process(*_os);
2630      }
2631    }
2632
2633    /// \brief Give back the stream of the writer
2634    ///
2635    /// Returns the stream of the writer
2636    std::ostream& ostream() {
2637      return *_os;
2638    }
2639
2640    /// @}
2641
2642  };
2643
2644  /// \ingroup lemon_io
2645  ///
2646  /// \brief Return a \ref SectionWriter class
2647  ///
2648  /// This function just returns a \ref SectionWriter class.
2649  ///
2650  /// Please see SectionWriter documentation about the custom section
2651  /// output.
2652  ///
2653  /// \relates SectionWriter
2654  /// \sa sectionWriter(const std::string& fn)
2655  /// \sa sectionWriter(const char *fn)
2656  inline SectionWriter sectionWriter(std::ostream& os) {
2657    SectionWriter tmp(os);
2658    return tmp;
2659  }
2660
2661  /// \brief Return a \ref SectionWriter class
2662  ///
2663  /// This function just returns a \ref SectionWriter class.
2664  /// \relates SectionWriter
2665  /// \sa sectionWriter(std::ostream& os)
2666  inline SectionWriter sectionWriter(const std::string& fn) {
2667    SectionWriter tmp(fn);
2668    return tmp;
2669  }
2670
2671  /// \brief Return a \ref SectionWriter class
2672  ///
2673  /// This function just returns a \ref SectionWriter class.
2674  /// \relates SectionWriter
2675  /// \sa sectionWriter(std::ostream& os)
2676  inline SectionWriter sectionWriter(const char* fn) {
2677    SectionWriter tmp(fn);
2678    return tmp;
2679  }
2680}
2681
2682#endif
Note: See TracBrowser for help on using the repository browser.