lemon/lgf_writer.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 14 Jul 2008 15:23:11 +0100
changeset 280 e7f8647ce760
parent 240 bea328c5a8d3
child 290 f6899946c1ac
child 293 47fbc814aa31
permissions -rw-r--r--
Remove todo-s and convert them to trac tickets
     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-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup lemon_io
    20 ///\file
    21 ///\brief \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/assert.h>
    37 #include <lemon/core.h>
    38 #include <lemon/maps.h>
    39 
    40 #include <lemon/concept_check.h>
    41 #include <lemon/concepts/maps.h>
    42 
    43 namespace lemon {
    44 
    45   namespace _writer_bits {
    46 
    47     template <typename Value>
    48     struct DefaultConverter {
    49       std::string operator()(const Value& value) {
    50         std::ostringstream os;
    51         os << value;
    52         return os.str();
    53       }
    54     };
    55 
    56     template <typename T>
    57     bool operator<(const T&, const T&) {
    58       throw DataFormatError("Label map is not comparable");
    59     }
    60 
    61     template <typename _Map>
    62     class MapLess {
    63     public:
    64       typedef _Map Map;
    65       typedef typename Map::Key Item;
    66 
    67     private:
    68       const Map& _map;
    69 
    70     public:
    71       MapLess(const Map& map) : _map(map) {}
    72 
    73       bool operator()(const Item& left, const Item& right) {
    74         return _map[left] < _map[right];
    75       }
    76     };
    77 
    78     template <typename _Graph, bool _dir, typename _Map>
    79     class GraphArcMapLess {
    80     public:
    81       typedef _Map Map;
    82       typedef _Graph Graph;
    83       typedef typename Graph::Edge Item;
    84 
    85     private:
    86       const Graph& _graph;
    87       const Map& _map;
    88 
    89     public:
    90       GraphArcMapLess(const Graph& graph, const Map& map)
    91         : _graph(graph), _map(map) {}
    92 
    93       bool operator()(const Item& left, const Item& right) {
    94         return _map[_graph.direct(left, _dir)] <
    95           _map[_graph.direct(right, _dir)];
    96       }
    97     };
    98 
    99     template <typename _Item>
   100     class MapStorageBase {
   101     public:
   102       typedef _Item Item;
   103 
   104     public:
   105       MapStorageBase() {}
   106       virtual ~MapStorageBase() {}
   107 
   108       virtual std::string get(const Item& item) = 0;
   109       virtual void sort(std::vector<Item>&) = 0;
   110     };
   111 
   112     template <typename _Item, typename _Map,
   113               typename _Converter = DefaultConverter<typename _Map::Value> >
   114     class MapStorage : public MapStorageBase<_Item> {
   115     public:
   116       typedef _Map Map;
   117       typedef _Converter Converter;
   118       typedef _Item Item;
   119 
   120     private:
   121       const Map& _map;
   122       Converter _converter;
   123 
   124     public:
   125       MapStorage(const Map& map, const Converter& converter = Converter())
   126         : _map(map), _converter(converter) {}
   127       virtual ~MapStorage() {}
   128 
   129       virtual std::string get(const Item& item) {
   130         return _converter(_map[item]);
   131       }
   132       virtual void sort(std::vector<Item>& items) {
   133         MapLess<Map> less(_map);
   134         std::sort(items.begin(), items.end(), less);
   135       }
   136     };
   137 
   138     template <typename _Graph, bool _dir, typename _Map,
   139               typename _Converter = DefaultConverter<typename _Map::Value> >
   140     class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
   141     public:
   142       typedef _Map Map;
   143       typedef _Converter Converter;
   144       typedef _Graph Graph;
   145       typedef typename Graph::Edge Item;
   146       static const bool dir = _dir;
   147 
   148     private:
   149       const Graph& _graph;
   150       const Map& _map;
   151       Converter _converter;
   152 
   153     public:
   154       GraphArcMapStorage(const Graph& graph, const Map& map,
   155                          const Converter& converter = Converter())
   156         : _graph(graph), _map(map), _converter(converter) {}
   157       virtual ~GraphArcMapStorage() {}
   158 
   159       virtual std::string get(const Item& item) {
   160         return _converter(_map[_graph.direct(item, dir)]);
   161       }
   162       virtual void sort(std::vector<Item>& items) {
   163         GraphArcMapLess<Graph, dir, Map> less(_graph, _map);
   164         std::sort(items.begin(), items.end(), less);
   165       }
   166     };
   167 
   168     class ValueStorageBase {
   169     public:
   170       ValueStorageBase() {}
   171       virtual ~ValueStorageBase() {}
   172 
   173       virtual std::string get() = 0;
   174     };
   175 
   176     template <typename _Value, typename _Converter = DefaultConverter<_Value> >
   177     class ValueStorage : public ValueStorageBase {
   178     public:
   179       typedef _Value Value;
   180       typedef _Converter Converter;
   181 
   182     private:
   183       const Value& _value;
   184       Converter _converter;
   185 
   186     public:
   187       ValueStorage(const Value& value, const Converter& converter = Converter())
   188         : _value(value), _converter(converter) {}
   189 
   190       virtual std::string get() {
   191         return _converter(_value);
   192       }
   193     };
   194 
   195     template <typename Value>
   196     struct MapLookUpConverter {
   197       const std::map<Value, std::string>& _map;
   198 
   199       MapLookUpConverter(const std::map<Value, std::string>& map)
   200         : _map(map) {}
   201 
   202       std::string operator()(const Value& str) {
   203         typename std::map<Value, std::string>::const_iterator it =
   204           _map.find(str);
   205         if (it == _map.end()) {
   206           throw DataFormatError("Item not found");
   207         }
   208         return it->second;
   209       }
   210     };
   211 
   212     template <typename Graph>
   213     struct GraphArcLookUpConverter {
   214       const Graph& _graph;
   215       const std::map<typename Graph::Edge, std::string>& _map;
   216 
   217       GraphArcLookUpConverter(const Graph& graph,
   218                               const std::map<typename Graph::Edge,
   219                                              std::string>& map)
   220         : _graph(graph), _map(map) {}
   221 
   222       std::string operator()(const typename Graph::Arc& val) {
   223         typename std::map<typename Graph::Edge, std::string>
   224           ::const_iterator it = _map.find(val);
   225         if (it == _map.end()) {
   226           throw DataFormatError("Item not found");
   227         }
   228         return (_graph.direction(val) ? '+' : '-') + it->second;
   229       }
   230     };
   231 
   232     inline bool isWhiteSpace(char c) {
   233       return c == ' ' || c == '\t' || c == '\v' ||
   234         c == '\n' || c == '\r' || c == '\f';
   235     }
   236 
   237     inline bool isEscaped(char c) {
   238       return c == '\\' || c == '\"' || c == '\'' ||
   239         c == '\a' || c == '\b';
   240     }
   241 
   242     inline static void writeEscape(std::ostream& os, char c) {
   243       switch (c) {
   244       case '\\':
   245         os << "\\\\";
   246         return;
   247       case '\"':
   248         os << "\\\"";
   249         return;
   250       case '\a':
   251         os << "\\a";
   252         return;
   253       case '\b':
   254         os << "\\b";
   255         return;
   256       case '\f':
   257         os << "\\f";
   258         return;
   259       case '\r':
   260         os << "\\r";
   261         return;
   262       case '\n':
   263         os << "\\n";
   264         return;
   265       case '\t':
   266         os << "\\t";
   267         return;
   268       case '\v':
   269         os << "\\v";
   270         return;
   271       default:
   272         if (c < 0x20) {
   273           std::ios::fmtflags flags = os.flags();
   274           os << '\\' << std::oct << static_cast<int>(c);
   275           os.flags(flags);
   276         } else {
   277           os << c;
   278         }
   279         return;
   280       }
   281     }
   282 
   283     inline bool requireEscape(const std::string& str) {
   284       if (str.empty() || str[0] == '@') return true;
   285       std::istringstream is(str);
   286       char c;
   287       while (is.get(c)) {
   288         if (isWhiteSpace(c) || isEscaped(c)) {
   289           return true;
   290         }
   291       }
   292       return false;
   293     }
   294 
   295     inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
   296 
   297       if (requireEscape(str)) {
   298         os << '\"';
   299         for (std::string::const_iterator it = str.begin();
   300              it != str.end(); ++it) {
   301           writeEscape(os, *it);
   302         }
   303         os << '\"';
   304       } else {
   305         os << str;
   306       }
   307       return os;
   308     }
   309 
   310     class Section {
   311     public:
   312       virtual ~Section() {}
   313       virtual void process(std::ostream& os) = 0;
   314     };
   315 
   316     template <typename Functor>
   317     class LineSection : public Section {
   318     private:
   319 
   320       Functor _functor;
   321 
   322     public:
   323 
   324       LineSection(const Functor& functor) : _functor(functor) {}
   325       virtual ~LineSection() {}
   326 
   327       virtual void process(std::ostream& os) {
   328         std::string line;
   329         while (!(line = _functor()).empty()) os << line << std::endl;
   330       }
   331     };
   332 
   333     template <typename Functor>
   334     class StreamSection : public Section {
   335     private:
   336 
   337       Functor _functor;
   338 
   339     public:
   340 
   341       StreamSection(const Functor& functor) : _functor(functor) {}
   342       virtual ~StreamSection() {}
   343 
   344       virtual void process(std::ostream& os) {
   345         _functor(os);
   346       }
   347     };
   348 
   349   }
   350 
   351   template <typename Digraph>
   352   class DigraphWriter;
   353 
   354   template <typename Digraph>
   355   DigraphWriter<Digraph> digraphWriter(std::ostream& os,
   356                                        const Digraph& digraph);
   357 
   358   template <typename Digraph>
   359   DigraphWriter<Digraph> digraphWriter(const std::string& fn,
   360                                        const Digraph& digraph);
   361 
   362   template <typename Digraph>
   363   DigraphWriter<Digraph> digraphWriter(const char *fn,
   364                                        const Digraph& digraph);
   365 
   366   /// \ingroup lemon_io
   367   ///
   368   /// \brief \ref lgf-format "LGF" writer for directed graphs
   369   ///
   370   /// This utility writes an \ref lgf-format "LGF" file.
   371   ///
   372   /// The writing method does a batch processing. The user creates a
   373   /// writer object, then various writing rules can be added to the
   374   /// writer, and eventually the writing is executed with the \c run()
   375   /// member function. A map writing rule can be added to the writer
   376   /// with the \c nodeMap() or \c arcMap() members. An optional
   377   /// converter parameter can also be added as a standard functor
   378   /// converting from the value type of the map to \c std::string. If it
   379   /// is set, it will determine how the value type of the map is written to
   380   /// the output stream. If the functor is not set, then a default
   381   /// conversion will be used. The \c attribute(), \c node() and \c
   382   /// arc() functions are used to add attribute writing rules.
   383   ///
   384   ///\code
   385   /// DigraphWriter<Digraph>(std::cout, digraph).
   386   ///   nodeMap("coordinates", coord_map).
   387   ///   nodeMap("size", size).
   388   ///   nodeMap("title", title).
   389   ///   arcMap("capacity", cap_map).
   390   ///   node("source", src).
   391   ///   node("target", trg).
   392   ///   attribute("caption", caption).
   393   ///   run();
   394   ///\endcode
   395   ///
   396   ///
   397   /// By default, the writer does not write additional captions to the
   398   /// sections, but they can be give as an optional parameter of
   399   /// the \c nodes(), \c arcs() or \c
   400   /// attributes() functions.
   401   ///
   402   /// The \c skipNodes() and \c skipArcs() functions forbid the
   403   /// writing of the sections. If two arc sections should be written
   404   /// to the output, it can be done in two passes, the first pass
   405   /// writes the node section and the first arc section, then the
   406   /// second pass skips the node section and writes just the arc
   407   /// section to the stream. The output stream can be retrieved with
   408   /// the \c ostream() function, hence the second pass can append its
   409   /// output to the output of the first pass.
   410   template <typename _Digraph>
   411   class DigraphWriter {
   412   public:
   413 
   414     typedef _Digraph Digraph;
   415     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   416 
   417   private:
   418 
   419 
   420     std::ostream* _os;
   421     bool local_os;
   422 
   423     const Digraph& _digraph;
   424 
   425     std::string _nodes_caption;
   426     std::string _arcs_caption;
   427     std::string _attributes_caption;
   428 
   429     typedef std::map<Node, std::string> NodeIndex;
   430     NodeIndex _node_index;
   431     typedef std::map<Arc, std::string> ArcIndex;
   432     ArcIndex _arc_index;
   433 
   434     typedef std::vector<std::pair<std::string,
   435       _writer_bits::MapStorageBase<Node>* > > NodeMaps;
   436     NodeMaps _node_maps;
   437 
   438     typedef std::vector<std::pair<std::string,
   439       _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
   440     ArcMaps _arc_maps;
   441 
   442     typedef std::vector<std::pair<std::string,
   443       _writer_bits::ValueStorageBase*> > Attributes;
   444     Attributes _attributes;
   445 
   446     bool _skip_nodes;
   447     bool _skip_arcs;
   448 
   449   public:
   450 
   451     /// \brief Constructor
   452     ///
   453     /// Construct a directed graph writer, which writes to the given
   454     /// output stream.
   455     DigraphWriter(std::ostream& is, const Digraph& digraph)
   456       : _os(&is), local_os(false), _digraph(digraph),
   457         _skip_nodes(false), _skip_arcs(false) {}
   458 
   459     /// \brief Constructor
   460     ///
   461     /// Construct a directed graph writer, which writes to the given
   462     /// output file.
   463     DigraphWriter(const std::string& fn, const Digraph& digraph)
   464       : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
   465         _skip_nodes(false), _skip_arcs(false) {}
   466 
   467     /// \brief Constructor
   468     ///
   469     /// Construct a directed graph writer, which writes to the given
   470     /// output file.
   471     DigraphWriter(const char* fn, const Digraph& digraph)
   472       : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
   473         _skip_nodes(false), _skip_arcs(false) {}
   474 
   475     /// \brief Destructor
   476     ~DigraphWriter() {
   477       for (typename NodeMaps::iterator it = _node_maps.begin();
   478            it != _node_maps.end(); ++it) {
   479         delete it->second;
   480       }
   481 
   482       for (typename ArcMaps::iterator it = _arc_maps.begin();
   483            it != _arc_maps.end(); ++it) {
   484         delete it->second;
   485       }
   486 
   487       for (typename Attributes::iterator it = _attributes.begin();
   488            it != _attributes.end(); ++it) {
   489         delete it->second;
   490       }
   491 
   492       if (local_os) {
   493         delete _os;
   494       }
   495     }
   496 
   497   private:
   498 
   499     friend DigraphWriter<Digraph> digraphWriter<>(std::ostream& os,
   500                                                   const Digraph& digraph);
   501     friend DigraphWriter<Digraph> digraphWriter<>(const std::string& fn,
   502                                                   const Digraph& digraph);
   503     friend DigraphWriter<Digraph> digraphWriter<>(const char *fn,
   504                                                   const Digraph& digraph);
   505 
   506     DigraphWriter(DigraphWriter& other)
   507       : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
   508         _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
   509 
   510       other._os = 0;
   511       other.local_os = false;
   512 
   513       _node_index.swap(other._node_index);
   514       _arc_index.swap(other._arc_index);
   515 
   516       _node_maps.swap(other._node_maps);
   517       _arc_maps.swap(other._arc_maps);
   518       _attributes.swap(other._attributes);
   519 
   520       _nodes_caption = other._nodes_caption;
   521       _arcs_caption = other._arcs_caption;
   522       _attributes_caption = other._attributes_caption;
   523     }
   524 
   525     DigraphWriter& operator=(const DigraphWriter&);
   526 
   527   public:
   528 
   529     /// \name Writing rules
   530     /// @{
   531 
   532     /// \brief Node map writing rule
   533     ///
   534     /// Add a node map writing rule to the writer.
   535     template <typename Map>
   536     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
   537       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   538       _writer_bits::MapStorageBase<Node>* storage =
   539         new _writer_bits::MapStorage<Node, Map>(map);
   540       _node_maps.push_back(std::make_pair(caption, storage));
   541       return *this;
   542     }
   543 
   544     /// \brief Node map writing rule
   545     ///
   546     /// Add a node map writing rule with specialized converter to the
   547     /// writer.
   548     template <typename Map, typename Converter>
   549     DigraphWriter& nodeMap(const std::string& caption, const Map& map,
   550                            const Converter& converter = Converter()) {
   551       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   552       _writer_bits::MapStorageBase<Node>* storage =
   553         new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
   554       _node_maps.push_back(std::make_pair(caption, storage));
   555       return *this;
   556     }
   557 
   558     /// \brief Arc map writing rule
   559     ///
   560     /// Add an arc map writing rule to the writer.
   561     template <typename Map>
   562     DigraphWriter& arcMap(const std::string& caption, const Map& map) {
   563       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   564       _writer_bits::MapStorageBase<Arc>* storage =
   565         new _writer_bits::MapStorage<Arc, Map>(map);
   566       _arc_maps.push_back(std::make_pair(caption, storage));
   567       return *this;
   568     }
   569 
   570     /// \brief Arc map writing rule
   571     ///
   572     /// Add an arc map writing rule with specialized converter to the
   573     /// writer.
   574     template <typename Map, typename Converter>
   575     DigraphWriter& arcMap(const std::string& caption, const Map& map,
   576                           const Converter& converter = Converter()) {
   577       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   578       _writer_bits::MapStorageBase<Arc>* storage =
   579         new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
   580       _arc_maps.push_back(std::make_pair(caption, storage));
   581       return *this;
   582     }
   583 
   584     /// \brief Attribute writing rule
   585     ///
   586     /// Add an attribute writing rule to the writer.
   587     template <typename Value>
   588     DigraphWriter& attribute(const std::string& caption, const Value& value) {
   589       _writer_bits::ValueStorageBase* storage =
   590         new _writer_bits::ValueStorage<Value>(value);
   591       _attributes.push_back(std::make_pair(caption, storage));
   592       return *this;
   593     }
   594 
   595     /// \brief Attribute writing rule
   596     ///
   597     /// Add an attribute writing rule with specialized converter to the
   598     /// writer.
   599     template <typename Value, typename Converter>
   600     DigraphWriter& attribute(const std::string& caption, const Value& value,
   601                              const Converter& converter = Converter()) {
   602       _writer_bits::ValueStorageBase* storage =
   603         new _writer_bits::ValueStorage<Value, Converter>(value, converter);
   604       _attributes.push_back(std::make_pair(caption, storage));
   605       return *this;
   606     }
   607 
   608     /// \brief Node writing rule
   609     ///
   610     /// Add a node writing rule to the writer.
   611     DigraphWriter& node(const std::string& caption, const Node& node) {
   612       typedef _writer_bits::MapLookUpConverter<Node> Converter;
   613       Converter converter(_node_index);
   614       _writer_bits::ValueStorageBase* storage =
   615         new _writer_bits::ValueStorage<Node, Converter>(node, converter);
   616       _attributes.push_back(std::make_pair(caption, storage));
   617       return *this;
   618     }
   619 
   620     /// \brief Arc writing rule
   621     ///
   622     /// Add an arc writing rule to writer.
   623     DigraphWriter& arc(const std::string& caption, const Arc& arc) {
   624       typedef _writer_bits::MapLookUpConverter<Arc> Converter;
   625       Converter converter(_arc_index);
   626       _writer_bits::ValueStorageBase* storage =
   627         new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
   628       _attributes.push_back(std::make_pair(caption, storage));
   629       return *this;
   630     }
   631 
   632     /// \name Section captions
   633     /// @{
   634 
   635     /// \brief Add an additional caption to the \c \@nodes section
   636     ///
   637     /// Add an additional caption to the \c \@nodes section.
   638     DigraphWriter& nodes(const std::string& caption) {
   639       _nodes_caption = caption;
   640       return *this;
   641     }
   642 
   643     /// \brief Add an additional caption to the \c \@arcs section
   644     ///
   645     /// Add an additional caption to the \c \@arcs section.
   646     DigraphWriter& arcs(const std::string& caption) {
   647       _arcs_caption = caption;
   648       return *this;
   649     }
   650 
   651     /// \brief Add an additional caption to the \c \@attributes section
   652     ///
   653     /// Add an additional caption to the \c \@attributes section.
   654     DigraphWriter& attributes(const std::string& caption) {
   655       _attributes_caption = caption;
   656       return *this;
   657     }
   658 
   659     /// \name Skipping section
   660     /// @{
   661 
   662     /// \brief Skip writing the node set
   663     ///
   664     /// The \c \@nodes section will not be written to the stream.
   665     DigraphWriter& skipNodes() {
   666       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
   667       _skip_nodes = true;
   668       return *this;
   669     }
   670 
   671     /// \brief Skip writing arc set
   672     ///
   673     /// The \c \@arcs section will not be written to the stream.
   674     DigraphWriter& skipArcs() {
   675       LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
   676       _skip_arcs = true;
   677       return *this;
   678     }
   679 
   680     /// @}
   681 
   682   private:
   683 
   684     void writeNodes() {
   685       _writer_bits::MapStorageBase<Node>* label = 0;
   686       for (typename NodeMaps::iterator it = _node_maps.begin();
   687            it != _node_maps.end(); ++it) {
   688         if (it->first == "label") {
   689           label = it->second;
   690           break;
   691         }
   692       }
   693 
   694       *_os << "@nodes";
   695       if (!_nodes_caption.empty()) {
   696         _writer_bits::writeToken(*_os << ' ', _nodes_caption);
   697       }
   698       *_os << std::endl;
   699 
   700       if (label == 0) {
   701         *_os << "label" << '\t';
   702       }
   703       for (typename NodeMaps::iterator it = _node_maps.begin();
   704            it != _node_maps.end(); ++it) {
   705         _writer_bits::writeToken(*_os, it->first) << '\t';
   706       }
   707       *_os << std::endl;
   708 
   709       std::vector<Node> nodes;
   710       for (NodeIt n(_digraph); n != INVALID; ++n) {
   711         nodes.push_back(n);
   712       }
   713 
   714       if (label == 0) {
   715         IdMap<Digraph, Node> id_map(_digraph);
   716         _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
   717         std::sort(nodes.begin(), nodes.end(), id_less);
   718       } else {
   719         label->sort(nodes);
   720       }
   721 
   722       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
   723         Node n = nodes[i];
   724         if (label == 0) {
   725           std::ostringstream os;
   726           os << _digraph.id(n);
   727           _writer_bits::writeToken(*_os, os.str());
   728           *_os << '\t';
   729           _node_index.insert(std::make_pair(n, os.str()));
   730         }
   731         for (typename NodeMaps::iterator it = _node_maps.begin();
   732              it != _node_maps.end(); ++it) {
   733           std::string value = it->second->get(n);
   734           _writer_bits::writeToken(*_os, value);
   735           if (it->first == "label") {
   736             _node_index.insert(std::make_pair(n, value));
   737           }
   738           *_os << '\t';
   739         }
   740         *_os << std::endl;
   741       }
   742     }
   743 
   744     void createNodeIndex() {
   745       _writer_bits::MapStorageBase<Node>* label = 0;
   746       for (typename NodeMaps::iterator it = _node_maps.begin();
   747            it != _node_maps.end(); ++it) {
   748         if (it->first == "label") {
   749           label = it->second;
   750           break;
   751         }
   752       }
   753 
   754       if (label == 0) {
   755         for (NodeIt n(_digraph); n != INVALID; ++n) {
   756           std::ostringstream os;
   757           os << _digraph.id(n);
   758           _node_index.insert(std::make_pair(n, os.str()));
   759         }
   760       } else {
   761         for (NodeIt n(_digraph); n != INVALID; ++n) {
   762           std::string value = label->get(n);
   763           _node_index.insert(std::make_pair(n, value));
   764         }
   765       }
   766     }
   767 
   768     void writeArcs() {
   769       _writer_bits::MapStorageBase<Arc>* label = 0;
   770       for (typename ArcMaps::iterator it = _arc_maps.begin();
   771            it != _arc_maps.end(); ++it) {
   772         if (it->first == "label") {
   773           label = it->second;
   774           break;
   775         }
   776       }
   777 
   778       *_os << "@arcs";
   779       if (!_arcs_caption.empty()) {
   780         _writer_bits::writeToken(*_os << ' ', _arcs_caption);
   781       }
   782       *_os << std::endl;
   783 
   784       *_os << '\t' << '\t';
   785       if (label == 0) {
   786         *_os << "label" << '\t';
   787       }
   788       for (typename ArcMaps::iterator it = _arc_maps.begin();
   789            it != _arc_maps.end(); ++it) {
   790         _writer_bits::writeToken(*_os, it->first) << '\t';
   791       }
   792       *_os << std::endl;
   793 
   794       std::vector<Arc> arcs;
   795       for (ArcIt n(_digraph); n != INVALID; ++n) {
   796         arcs.push_back(n);
   797       }
   798 
   799       if (label == 0) {
   800         IdMap<Digraph, Arc> id_map(_digraph);
   801         _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
   802         std::sort(arcs.begin(), arcs.end(), id_less);
   803       } else {
   804         label->sort(arcs);
   805       }
   806 
   807       for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
   808         Arc a = arcs[i];
   809         _writer_bits::writeToken(*_os, _node_index.
   810                                  find(_digraph.source(a))->second);
   811         *_os << '\t';
   812         _writer_bits::writeToken(*_os, _node_index.
   813                                  find(_digraph.target(a))->second);
   814         *_os << '\t';
   815         if (label == 0) {
   816           std::ostringstream os;
   817           os << _digraph.id(a);
   818           _writer_bits::writeToken(*_os, os.str());
   819           *_os << '\t';
   820           _arc_index.insert(std::make_pair(a, os.str()));
   821         }
   822         for (typename ArcMaps::iterator it = _arc_maps.begin();
   823              it != _arc_maps.end(); ++it) {
   824           std::string value = it->second->get(a);
   825           _writer_bits::writeToken(*_os, value);
   826           if (it->first == "label") {
   827             _arc_index.insert(std::make_pair(a, value));
   828           }
   829           *_os << '\t';
   830         }
   831         *_os << std::endl;
   832       }
   833     }
   834 
   835     void createArcIndex() {
   836       _writer_bits::MapStorageBase<Arc>* label = 0;
   837       for (typename ArcMaps::iterator it = _arc_maps.begin();
   838            it != _arc_maps.end(); ++it) {
   839         if (it->first == "label") {
   840           label = it->second;
   841           break;
   842         }
   843       }
   844 
   845       if (label == 0) {
   846         for (ArcIt a(_digraph); a != INVALID; ++a) {
   847           std::ostringstream os;
   848           os << _digraph.id(a);
   849           _arc_index.insert(std::make_pair(a, os.str()));
   850         }
   851       } else {
   852         for (ArcIt a(_digraph); a != INVALID; ++a) {
   853           std::string value = label->get(a);
   854           _arc_index.insert(std::make_pair(a, value));
   855         }
   856       }
   857     }
   858 
   859     void writeAttributes() {
   860       if (_attributes.empty()) return;
   861       *_os << "@attributes";
   862       if (!_attributes_caption.empty()) {
   863         _writer_bits::writeToken(*_os << ' ', _attributes_caption);
   864       }
   865       *_os << std::endl;
   866       for (typename Attributes::iterator it = _attributes.begin();
   867            it != _attributes.end(); ++it) {
   868         _writer_bits::writeToken(*_os, it->first) << ' ';
   869         _writer_bits::writeToken(*_os, it->second->get());
   870         *_os << std::endl;
   871       }
   872     }
   873 
   874   public:
   875 
   876     /// \name Execution of the writer
   877     /// @{
   878 
   879     /// \brief Start the batch processing
   880     ///
   881     /// This function starts the batch processing.
   882     void run() {
   883       if (!_skip_nodes) {
   884         writeNodes();
   885       } else {
   886         createNodeIndex();
   887       }
   888       if (!_skip_arcs) {
   889         writeArcs();
   890       } else {
   891         createArcIndex();
   892       }
   893       writeAttributes();
   894     }
   895 
   896     /// \brief Give back the stream of the writer
   897     ///
   898     /// Give back the stream of the writer.
   899     std::ostream& ostream() {
   900       return *_os;
   901     }
   902 
   903     /// @}
   904   };
   905 
   906   /// \brief Return a \ref DigraphWriter class
   907   ///
   908   /// This function just returns a \ref DigraphWriter class.
   909   /// \relates DigraphWriter
   910   template <typename Digraph>
   911   DigraphWriter<Digraph> digraphWriter(std::ostream& os,
   912                                        const Digraph& digraph) {
   913     DigraphWriter<Digraph> tmp(os, digraph);
   914     return tmp;
   915   }
   916 
   917   /// \brief Return a \ref DigraphWriter class
   918   ///
   919   /// This function just returns a \ref DigraphWriter class.
   920   /// \relates DigraphWriter
   921   template <typename Digraph>
   922   DigraphWriter<Digraph> digraphWriter(const std::string& fn,
   923                                        const Digraph& digraph) {
   924     DigraphWriter<Digraph> tmp(fn, digraph);
   925     return tmp;
   926   }
   927 
   928   /// \brief Return a \ref DigraphWriter class
   929   ///
   930   /// This function just returns a \ref DigraphWriter class.
   931   /// \relates DigraphWriter
   932   template <typename Digraph>
   933   DigraphWriter<Digraph> digraphWriter(const char* fn,
   934                                        const Digraph& digraph) {
   935     DigraphWriter<Digraph> tmp(fn, digraph);
   936     return tmp;
   937   }
   938 
   939   template <typename Graph>
   940   class GraphWriter;
   941 
   942   template <typename Graph>
   943   GraphWriter<Graph> graphWriter(std::ostream& os, const Graph& graph);
   944 
   945   template <typename Graph>
   946   GraphWriter<Graph> graphWriter(const std::string& fn, const Graph& graph);
   947 
   948   template <typename Graph>
   949   GraphWriter<Graph> graphWriter(const char *fn, const Graph& graph);
   950 
   951   /// \ingroup lemon_io
   952   ///
   953   /// \brief \ref lgf-format "LGF" writer for directed graphs
   954   ///
   955   /// This utility writes an \ref lgf-format "LGF" file.
   956   ///
   957   /// It can be used almost the same way as \c DigraphWriter.
   958   /// The only difference is that this class can handle edges and
   959   /// edge maps as well as arcs and arc maps.
   960   ///
   961   /// The arc maps are written into the file as two columns, the
   962   /// caption of the columns are the name of the map prefixed with \c
   963   /// '+' and \c '-'. The arcs are written into the \c \@attributes
   964   /// section as a \c '+' or a \c '-' prefix (depends on the direction
   965   /// of the arc) and the label of corresponding edge.
   966   template <typename _Graph>
   967   class GraphWriter {
   968   public:
   969 
   970     typedef _Graph Graph;
   971     TEMPLATE_GRAPH_TYPEDEFS(Graph);
   972 
   973   private:
   974 
   975 
   976     std::ostream* _os;
   977     bool local_os;
   978 
   979     const Graph& _graph;
   980 
   981     std::string _nodes_caption;
   982     std::string _edges_caption;
   983     std::string _attributes_caption;
   984 
   985     typedef std::map<Node, std::string> NodeIndex;
   986     NodeIndex _node_index;
   987     typedef std::map<Edge, std::string> EdgeIndex;
   988     EdgeIndex _edge_index;
   989 
   990     typedef std::vector<std::pair<std::string,
   991       _writer_bits::MapStorageBase<Node>* > > NodeMaps;
   992     NodeMaps _node_maps;
   993 
   994     typedef std::vector<std::pair<std::string,
   995       _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
   996     EdgeMaps _edge_maps;
   997 
   998     typedef std::vector<std::pair<std::string,
   999       _writer_bits::ValueStorageBase*> > Attributes;
  1000     Attributes _attributes;
  1001 
  1002     bool _skip_nodes;
  1003     bool _skip_edges;
  1004 
  1005   public:
  1006 
  1007     /// \brief Constructor
  1008     ///
  1009     /// Construct a directed graph writer, which writes to the given
  1010     /// output stream.
  1011     GraphWriter(std::ostream& is, const Graph& graph)
  1012       : _os(&is), local_os(false), _graph(graph),
  1013         _skip_nodes(false), _skip_edges(false) {}
  1014 
  1015     /// \brief Constructor
  1016     ///
  1017     /// Construct a directed graph writer, which writes to the given
  1018     /// output file.
  1019     GraphWriter(const std::string& fn, const Graph& graph)
  1020       : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
  1021         _skip_nodes(false), _skip_edges(false) {}
  1022 
  1023     /// \brief Constructor
  1024     ///
  1025     /// Construct a directed graph writer, which writes to the given
  1026     /// output file.
  1027     GraphWriter(const char* fn, const Graph& graph)
  1028       : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
  1029         _skip_nodes(false), _skip_edges(false) {}
  1030 
  1031     /// \brief Destructor
  1032     ~GraphWriter() {
  1033       for (typename NodeMaps::iterator it = _node_maps.begin();
  1034            it != _node_maps.end(); ++it) {
  1035         delete it->second;
  1036       }
  1037 
  1038       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1039            it != _edge_maps.end(); ++it) {
  1040         delete it->second;
  1041       }
  1042 
  1043       for (typename Attributes::iterator it = _attributes.begin();
  1044            it != _attributes.end(); ++it) {
  1045         delete it->second;
  1046       }
  1047 
  1048       if (local_os) {
  1049         delete _os;
  1050       }
  1051     }
  1052 
  1053   private:
  1054 
  1055     friend GraphWriter<Graph> graphWriter<>(std::ostream& os,
  1056                                             const Graph& graph);
  1057     friend GraphWriter<Graph> graphWriter<>(const std::string& fn,
  1058                                             const Graph& graph);
  1059     friend GraphWriter<Graph> graphWriter<>(const char *fn,
  1060                                             const Graph& graph);
  1061 
  1062     GraphWriter(GraphWriter& other)
  1063       : _os(other._os), local_os(other.local_os), _graph(other._graph),
  1064         _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1065 
  1066       other._os = 0;
  1067       other.local_os = false;
  1068 
  1069       _node_index.swap(other._node_index);
  1070       _edge_index.swap(other._edge_index);
  1071 
  1072       _node_maps.swap(other._node_maps);
  1073       _edge_maps.swap(other._edge_maps);
  1074       _attributes.swap(other._attributes);
  1075 
  1076       _nodes_caption = other._nodes_caption;
  1077       _edges_caption = other._edges_caption;
  1078       _attributes_caption = other._attributes_caption;
  1079     }
  1080 
  1081     GraphWriter& operator=(const GraphWriter&);
  1082 
  1083   public:
  1084 
  1085     /// \name Writing rules
  1086     /// @{
  1087 
  1088     /// \brief Node map writing rule
  1089     ///
  1090     /// Add a node map writing rule to the writer.
  1091     template <typename Map>
  1092     GraphWriter& nodeMap(const std::string& caption, const Map& map) {
  1093       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1094       _writer_bits::MapStorageBase<Node>* storage =
  1095         new _writer_bits::MapStorage<Node, Map>(map);
  1096       _node_maps.push_back(std::make_pair(caption, storage));
  1097       return *this;
  1098     }
  1099 
  1100     /// \brief Node map writing rule
  1101     ///
  1102     /// Add a node map writing rule with specialized converter to the
  1103     /// writer.
  1104     template <typename Map, typename Converter>
  1105     GraphWriter& nodeMap(const std::string& caption, const Map& map,
  1106                            const Converter& converter = Converter()) {
  1107       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1108       _writer_bits::MapStorageBase<Node>* storage =
  1109         new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
  1110       _node_maps.push_back(std::make_pair(caption, storage));
  1111       return *this;
  1112     }
  1113 
  1114     /// \brief Edge map writing rule
  1115     ///
  1116     /// Add an edge map writing rule to the writer.
  1117     template <typename Map>
  1118     GraphWriter& edgeMap(const std::string& caption, const Map& map) {
  1119       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1120       _writer_bits::MapStorageBase<Edge>* storage =
  1121         new _writer_bits::MapStorage<Edge, Map>(map);
  1122       _edge_maps.push_back(std::make_pair(caption, storage));
  1123       return *this;
  1124     }
  1125 
  1126     /// \brief Edge map writing rule
  1127     ///
  1128     /// Add an edge map writing rule with specialized converter to the
  1129     /// writer.
  1130     template <typename Map, typename Converter>
  1131     GraphWriter& edgeMap(const std::string& caption, const Map& map,
  1132                           const Converter& converter = Converter()) {
  1133       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1134       _writer_bits::MapStorageBase<Edge>* storage =
  1135         new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1136       _edge_maps.push_back(std::make_pair(caption, storage));
  1137       return *this;
  1138     }
  1139 
  1140     /// \brief Arc map writing rule
  1141     ///
  1142     /// Add an arc map writing rule to the writer.
  1143     template <typename Map>
  1144     GraphWriter& arcMap(const std::string& caption, const Map& map) {
  1145       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1146       _writer_bits::MapStorageBase<Edge>* forward_storage =
  1147         new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1148       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1149       _writer_bits::MapStorageBase<Edge>* backward_storage =
  1150         new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1151       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1152       return *this;
  1153     }
  1154 
  1155     /// \brief Arc map writing rule
  1156     ///
  1157     /// Add an arc map writing rule with specialized converter to the
  1158     /// writer.
  1159     template <typename Map, typename Converter>
  1160     GraphWriter& arcMap(const std::string& caption, const Map& map,
  1161                           const Converter& converter = Converter()) {
  1162       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1163       _writer_bits::MapStorageBase<Edge>* forward_storage =
  1164         new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1165         (_graph, map, converter);
  1166       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1167       _writer_bits::MapStorageBase<Edge>* backward_storage =
  1168         new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1169         (_graph, map, converter);
  1170       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1171       return *this;
  1172     }
  1173 
  1174     /// \brief Attribute writing rule
  1175     ///
  1176     /// Add an attribute writing rule to the writer.
  1177     template <typename Value>
  1178     GraphWriter& attribute(const std::string& caption, const Value& value) {
  1179       _writer_bits::ValueStorageBase* storage =
  1180         new _writer_bits::ValueStorage<Value>(value);
  1181       _attributes.push_back(std::make_pair(caption, storage));
  1182       return *this;
  1183     }
  1184 
  1185     /// \brief Attribute writing rule
  1186     ///
  1187     /// Add an attribute writing rule with specialized converter to the
  1188     /// writer.
  1189     template <typename Value, typename Converter>
  1190     GraphWriter& attribute(const std::string& caption, const Value& value,
  1191                              const Converter& converter = Converter()) {
  1192       _writer_bits::ValueStorageBase* storage =
  1193         new _writer_bits::ValueStorage<Value, Converter>(value, converter);
  1194       _attributes.push_back(std::make_pair(caption, storage));
  1195       return *this;
  1196     }
  1197 
  1198     /// \brief Node writing rule
  1199     ///
  1200     /// Add a node writing rule to the writer.
  1201     GraphWriter& node(const std::string& caption, const Node& node) {
  1202       typedef _writer_bits::MapLookUpConverter<Node> Converter;
  1203       Converter converter(_node_index);
  1204       _writer_bits::ValueStorageBase* storage =
  1205         new _writer_bits::ValueStorage<Node, Converter>(node, converter);
  1206       _attributes.push_back(std::make_pair(caption, storage));
  1207       return *this;
  1208     }
  1209 
  1210     /// \brief Edge writing rule
  1211     ///
  1212     /// Add an edge writing rule to writer.
  1213     GraphWriter& edge(const std::string& caption, const Edge& edge) {
  1214       typedef _writer_bits::MapLookUpConverter<Edge> Converter;
  1215       Converter converter(_edge_index);
  1216       _writer_bits::ValueStorageBase* storage =
  1217         new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
  1218       _attributes.push_back(std::make_pair(caption, storage));
  1219       return *this;
  1220     }
  1221 
  1222     /// \brief Arc writing rule
  1223     ///
  1224     /// Add an arc writing rule to writer.
  1225     GraphWriter& arc(const std::string& caption, const Arc& arc) {
  1226       typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
  1227       Converter converter(_graph, _edge_index);
  1228       _writer_bits::ValueStorageBase* storage =
  1229         new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
  1230       _attributes.push_back(std::make_pair(caption, storage));
  1231       return *this;
  1232     }
  1233 
  1234     /// \name Section captions
  1235     /// @{
  1236 
  1237     /// \brief Add an additional caption to the \c \@nodes section
  1238     ///
  1239     /// Add an additional caption to the \c \@nodes section.
  1240     GraphWriter& nodes(const std::string& caption) {
  1241       _nodes_caption = caption;
  1242       return *this;
  1243     }
  1244 
  1245     /// \brief Add an additional caption to the \c \@arcs section
  1246     ///
  1247     /// Add an additional caption to the \c \@arcs section.
  1248     GraphWriter& edges(const std::string& caption) {
  1249       _edges_caption = caption;
  1250       return *this;
  1251     }
  1252 
  1253     /// \brief Add an additional caption to the \c \@attributes section
  1254     ///
  1255     /// Add an additional caption to the \c \@attributes section.
  1256     GraphWriter& attributes(const std::string& caption) {
  1257       _attributes_caption = caption;
  1258       return *this;
  1259     }
  1260 
  1261     /// \name Skipping section
  1262     /// @{
  1263 
  1264     /// \brief Skip writing the node set
  1265     ///
  1266     /// The \c \@nodes section will not be written to the stream.
  1267     GraphWriter& skipNodes() {
  1268       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
  1269       _skip_nodes = true;
  1270       return *this;
  1271     }
  1272 
  1273     /// \brief Skip writing edge set
  1274     ///
  1275     /// The \c \@edges section will not be written to the stream.
  1276     GraphWriter& skipEdges() {
  1277       LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
  1278       _skip_edges = true;
  1279       return *this;
  1280     }
  1281 
  1282     /// @}
  1283 
  1284   private:
  1285 
  1286     void writeNodes() {
  1287       _writer_bits::MapStorageBase<Node>* label = 0;
  1288       for (typename NodeMaps::iterator it = _node_maps.begin();
  1289            it != _node_maps.end(); ++it) {
  1290         if (it->first == "label") {
  1291           label = it->second;
  1292           break;
  1293         }
  1294       }
  1295 
  1296       *_os << "@nodes";
  1297       if (!_nodes_caption.empty()) {
  1298         _writer_bits::writeToken(*_os << ' ', _nodes_caption);
  1299       }
  1300       *_os << std::endl;
  1301 
  1302       if (label == 0) {
  1303         *_os << "label" << '\t';
  1304       }
  1305       for (typename NodeMaps::iterator it = _node_maps.begin();
  1306            it != _node_maps.end(); ++it) {
  1307         _writer_bits::writeToken(*_os, it->first) << '\t';
  1308       }
  1309       *_os << std::endl;
  1310 
  1311       std::vector<Node> nodes;
  1312       for (NodeIt n(_graph); n != INVALID; ++n) {
  1313         nodes.push_back(n);
  1314       }
  1315 
  1316       if (label == 0) {
  1317         IdMap<Graph, Node> id_map(_graph);
  1318         _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
  1319         std::sort(nodes.begin(), nodes.end(), id_less);
  1320       } else {
  1321         label->sort(nodes);
  1322       }
  1323 
  1324       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
  1325         Node n = nodes[i];
  1326         if (label == 0) {
  1327           std::ostringstream os;
  1328           os << _graph.id(n);
  1329           _writer_bits::writeToken(*_os, os.str());
  1330           *_os << '\t';
  1331           _node_index.insert(std::make_pair(n, os.str()));
  1332         }
  1333         for (typename NodeMaps::iterator it = _node_maps.begin();
  1334              it != _node_maps.end(); ++it) {
  1335           std::string value = it->second->get(n);
  1336           _writer_bits::writeToken(*_os, value);
  1337           if (it->first == "label") {
  1338             _node_index.insert(std::make_pair(n, value));
  1339           }
  1340           *_os << '\t';
  1341         }
  1342         *_os << std::endl;
  1343       }
  1344     }
  1345 
  1346     void createNodeIndex() {
  1347       _writer_bits::MapStorageBase<Node>* label = 0;
  1348       for (typename NodeMaps::iterator it = _node_maps.begin();
  1349            it != _node_maps.end(); ++it) {
  1350         if (it->first == "label") {
  1351           label = it->second;
  1352           break;
  1353         }
  1354       }
  1355 
  1356       if (label == 0) {
  1357         for (NodeIt n(_graph); n != INVALID; ++n) {
  1358           std::ostringstream os;
  1359           os << _graph.id(n);
  1360           _node_index.insert(std::make_pair(n, os.str()));
  1361         }
  1362       } else {
  1363         for (NodeIt n(_graph); n != INVALID; ++n) {
  1364           std::string value = label->get(n);
  1365           _node_index.insert(std::make_pair(n, value));
  1366         }
  1367       }
  1368     }
  1369 
  1370     void writeEdges() {
  1371       _writer_bits::MapStorageBase<Edge>* label = 0;
  1372       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1373            it != _edge_maps.end(); ++it) {
  1374         if (it->first == "label") {
  1375           label = it->second;
  1376           break;
  1377         }
  1378       }
  1379 
  1380       *_os << "@edges";
  1381       if (!_edges_caption.empty()) {
  1382         _writer_bits::writeToken(*_os << ' ', _edges_caption);
  1383       }
  1384       *_os << std::endl;
  1385 
  1386       *_os << '\t' << '\t';
  1387       if (label == 0) {
  1388         *_os << "label" << '\t';
  1389       }
  1390       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1391            it != _edge_maps.end(); ++it) {
  1392         _writer_bits::writeToken(*_os, it->first) << '\t';
  1393       }
  1394       *_os << std::endl;
  1395 
  1396       std::vector<Edge> edges;
  1397       for (EdgeIt n(_graph); n != INVALID; ++n) {
  1398         edges.push_back(n);
  1399       }
  1400 
  1401       if (label == 0) {
  1402         IdMap<Graph, Edge> id_map(_graph);
  1403         _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
  1404         std::sort(edges.begin(), edges.end(), id_less);
  1405       } else {
  1406         label->sort(edges);
  1407       }
  1408 
  1409       for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
  1410         Edge e = edges[i];
  1411         _writer_bits::writeToken(*_os, _node_index.
  1412                                  find(_graph.u(e))->second);
  1413         *_os << '\t';
  1414         _writer_bits::writeToken(*_os, _node_index.
  1415                                  find(_graph.v(e))->second);
  1416         *_os << '\t';
  1417         if (label == 0) {
  1418           std::ostringstream os;
  1419           os << _graph.id(e);
  1420           _writer_bits::writeToken(*_os, os.str());
  1421           *_os << '\t';
  1422           _edge_index.insert(std::make_pair(e, os.str()));
  1423         }
  1424         for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1425              it != _edge_maps.end(); ++it) {
  1426           std::string value = it->second->get(e);
  1427           _writer_bits::writeToken(*_os, value);
  1428           if (it->first == "label") {
  1429             _edge_index.insert(std::make_pair(e, value));
  1430           }
  1431           *_os << '\t';
  1432         }
  1433         *_os << std::endl;
  1434       }
  1435     }
  1436 
  1437     void createEdgeIndex() {
  1438       _writer_bits::MapStorageBase<Edge>* label = 0;
  1439       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1440            it != _edge_maps.end(); ++it) {
  1441         if (it->first == "label") {
  1442           label = it->second;
  1443           break;
  1444         }
  1445       }
  1446 
  1447       if (label == 0) {
  1448         for (EdgeIt e(_graph); e != INVALID; ++e) {
  1449           std::ostringstream os;
  1450           os << _graph.id(e);
  1451           _edge_index.insert(std::make_pair(e, os.str()));
  1452         }
  1453       } else {
  1454         for (EdgeIt e(_graph); e != INVALID; ++e) {
  1455           std::string value = label->get(e);
  1456           _edge_index.insert(std::make_pair(e, value));
  1457         }
  1458       }
  1459     }
  1460 
  1461     void writeAttributes() {
  1462       if (_attributes.empty()) return;
  1463       *_os << "@attributes";
  1464       if (!_attributes_caption.empty()) {
  1465         _writer_bits::writeToken(*_os << ' ', _attributes_caption);
  1466       }
  1467       *_os << std::endl;
  1468       for (typename Attributes::iterator it = _attributes.begin();
  1469            it != _attributes.end(); ++it) {
  1470         _writer_bits::writeToken(*_os, it->first) << ' ';
  1471         _writer_bits::writeToken(*_os, it->second->get());
  1472         *_os << std::endl;
  1473       }
  1474     }
  1475 
  1476   public:
  1477 
  1478     /// \name Execution of the writer
  1479     /// @{
  1480 
  1481     /// \brief Start the batch processing
  1482     ///
  1483     /// This function starts the batch processing.
  1484     void run() {
  1485       if (!_skip_nodes) {
  1486         writeNodes();
  1487       } else {
  1488         createNodeIndex();
  1489       }
  1490       if (!_skip_edges) {
  1491         writeEdges();
  1492       } else {
  1493         createEdgeIndex();
  1494       }
  1495       writeAttributes();
  1496     }
  1497 
  1498     /// \brief Give back the stream of the writer
  1499     ///
  1500     /// Give back the stream of the writer
  1501     std::ostream& ostream() {
  1502       return *_os;
  1503     }
  1504 
  1505     /// @}
  1506   };
  1507 
  1508   /// \brief Return a \ref GraphWriter class
  1509   ///
  1510   /// This function just returns a \ref GraphWriter class.
  1511   /// \relates GraphWriter
  1512   template <typename Graph>
  1513   GraphWriter<Graph> graphWriter(std::ostream& os, const Graph& graph) {
  1514     GraphWriter<Graph> tmp(os, graph);
  1515     return tmp;
  1516   }
  1517 
  1518   /// \brief Return a \ref GraphWriter class
  1519   ///
  1520   /// This function just returns a \ref GraphWriter class.
  1521   /// \relates GraphWriter
  1522   template <typename Graph>
  1523   GraphWriter<Graph> graphWriter(const std::string& fn, const Graph& graph) {
  1524     GraphWriter<Graph> tmp(fn, graph);
  1525     return tmp;
  1526   }
  1527 
  1528   /// \brief Return a \ref GraphWriter class
  1529   ///
  1530   /// This function just returns a \ref GraphWriter class.
  1531   /// \relates GraphWriter
  1532   template <typename Graph>
  1533   GraphWriter<Graph> graphWriter(const char* fn, const Graph& graph) {
  1534     GraphWriter<Graph> tmp(fn, graph);
  1535     return tmp;
  1536   }
  1537 
  1538   class SectionWriter;
  1539 
  1540   SectionWriter sectionWriter(std::istream& is);
  1541   SectionWriter sectionWriter(const std::string& fn);
  1542   SectionWriter sectionWriter(const char* fn);
  1543 
  1544   /// \ingroup lemon_io
  1545   ///
  1546   /// \brief Section writer class
  1547   ///
  1548   /// In the \ref lgf-format "LGF" file extra sections can be placed,
  1549   /// which contain any data in arbitrary format. Such sections can be
  1550   /// written with this class. A writing rule can be added to the
  1551   /// class with two different functions. With the \c sectionLines()
  1552   /// function a generator can write the section line-by-line, while
  1553   /// with the \c sectionStream() member the section can be written to
  1554   /// an output stream.
  1555   class SectionWriter {
  1556   private:
  1557 
  1558     std::ostream* _os;
  1559     bool local_os;
  1560 
  1561     typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
  1562     Sections;
  1563 
  1564     Sections _sections;
  1565 
  1566   public:
  1567 
  1568     /// \brief Constructor
  1569     ///
  1570     /// Construct a section writer, which writes to the given output
  1571     /// stream.
  1572     SectionWriter(std::ostream& os)
  1573       : _os(&os), local_os(false) {}
  1574 
  1575     /// \brief Constructor
  1576     ///
  1577     /// Construct a section writer, which writes into the given file.
  1578     SectionWriter(const std::string& fn)
  1579       : _os(new std::ofstream(fn.c_str())), local_os(true) {}
  1580 
  1581     /// \brief Constructor
  1582     ///
  1583     /// Construct a section writer, which writes into the given file.
  1584     SectionWriter(const char* fn)
  1585       : _os(new std::ofstream(fn)), local_os(true) {}
  1586 
  1587     /// \brief Destructor
  1588     ~SectionWriter() {
  1589       for (Sections::iterator it = _sections.begin();
  1590            it != _sections.end(); ++it) {
  1591         delete it->second;
  1592       }
  1593 
  1594       if (local_os) {
  1595         delete _os;
  1596       }
  1597 
  1598     }
  1599 
  1600   private:
  1601 
  1602     friend SectionWriter sectionWriter(std::ostream& os);
  1603     friend SectionWriter sectionWriter(const std::string& fn);
  1604     friend SectionWriter sectionWriter(const char* fn);
  1605 
  1606     SectionWriter(SectionWriter& other)
  1607       : _os(other._os), local_os(other.local_os) {
  1608 
  1609       other._os = 0;
  1610       other.local_os = false;
  1611 
  1612       _sections.swap(other._sections);
  1613     }
  1614 
  1615     SectionWriter& operator=(const SectionWriter&);
  1616 
  1617   public:
  1618 
  1619     /// \name Section writers
  1620     /// @{
  1621 
  1622     /// \brief Add a section writer with line oriented writing
  1623     ///
  1624     /// The first parameter is the type descriptor of the section, the
  1625     /// second is a generator with std::string values. At the writing
  1626     /// process, the returned \c std::string will be written into the
  1627     /// output file until it is an empty string.
  1628     ///
  1629     /// For example, an integer vector is written into a section.
  1630     ///\code
  1631     ///  @numbers
  1632     ///  12 45 23 78
  1633     ///  4 28 38 28
  1634     ///  23 6 16
  1635     ///\endcode
  1636     ///
  1637     /// The generator is implemented as a struct.
  1638     ///\code
  1639     ///  struct NumberSection {
  1640     ///    std::vector<int>::const_iterator _it, _end;
  1641     ///    NumberSection(const std::vector<int>& data)
  1642     ///      : _it(data.begin()), _end(data.end()) {}
  1643     ///    std::string operator()() {
  1644     ///      int rem_in_line = 4;
  1645     ///      std::ostringstream ls;
  1646     ///      while (rem_in_line > 0 && _it != _end) {
  1647     ///        ls << *(_it++) << ' ';
  1648     ///        --rem_in_line;
  1649     ///      }
  1650     ///      return ls.str();
  1651     ///    }
  1652     ///  };
  1653     ///
  1654     ///  // ...
  1655     ///
  1656     ///  writer.sectionLines("numbers", NumberSection(vec));
  1657     ///\endcode
  1658     template <typename Functor>
  1659     SectionWriter& sectionLines(const std::string& type, Functor functor) {
  1660       LEMON_ASSERT(!type.empty(), "Type is empty.");
  1661       _sections.push_back(std::make_pair(type,
  1662         new _writer_bits::LineSection<Functor>(functor)));
  1663       return *this;
  1664     }
  1665 
  1666 
  1667     /// \brief Add a section writer with stream oriented writing
  1668     ///
  1669     /// The first parameter is the type of the section, the second is
  1670     /// a functor, which takes a \c std::ostream& parameter. The
  1671     /// functor writes the section to the output stream.
  1672     /// \warning The last line must be closed with end-line character.
  1673     template <typename Functor>
  1674     SectionWriter& sectionStream(const std::string& type, Functor functor) {
  1675       LEMON_ASSERT(!type.empty(), "Type is empty.");
  1676       _sections.push_back(std::make_pair(type,
  1677          new _writer_bits::StreamSection<Functor>(functor)));
  1678       return *this;
  1679     }
  1680 
  1681     /// @}
  1682 
  1683   public:
  1684 
  1685 
  1686     /// \name Execution of the writer
  1687     /// @{
  1688 
  1689     /// \brief Start the batch processing
  1690     ///
  1691     /// This function starts the batch processing.
  1692     void run() {
  1693 
  1694       LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");
  1695 
  1696       for (Sections::iterator it = _sections.begin();
  1697            it != _sections.end(); ++it) {
  1698         (*_os) << '@' << it->first << std::endl;
  1699         it->second->process(*_os);
  1700       }
  1701     }
  1702 
  1703     /// \brief Give back the stream of the writer
  1704     ///
  1705     /// Returns the stream of the writer
  1706     std::ostream& ostream() {
  1707       return *_os;
  1708     }
  1709 
  1710     /// @}
  1711 
  1712   };
  1713 
  1714   /// \brief Return a \ref SectionWriter class
  1715   ///
  1716   /// This function just returns a \ref SectionWriter class.
  1717   /// \relates SectionWriter
  1718   inline SectionWriter sectionWriter(std::ostream& os) {
  1719     SectionWriter tmp(os);
  1720     return tmp;
  1721   }
  1722 
  1723   /// \brief Return a \ref SectionWriter class
  1724   ///
  1725   /// This function just returns a \ref SectionWriter class.
  1726   /// \relates SectionWriter
  1727   inline SectionWriter sectionWriter(const std::string& fn) {
  1728     SectionWriter tmp(fn);
  1729     return tmp;
  1730   }
  1731 
  1732   /// \brief Return a \ref SectionWriter class
  1733   ///
  1734   /// This function just returns a \ref SectionWriter class.
  1735   /// \relates SectionWriter
  1736   inline SectionWriter sectionWriter(const char* fn) {
  1737     SectionWriter tmp(fn);
  1738     return tmp;
  1739   }
  1740 }
  1741 
  1742 #endif