lemon/lgf_writer.h
author Alpar Juttner <alpar@cs.elte.hu>
Wed, 08 Oct 2008 13:16:04 +0100
changeset 302 1871777f62b7
parent 294 cbe3ec2d59d2
child 303 a3a69f5bba62
permissions -rw-r--r--
Merge
     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 FormatError("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 FormatError("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 FormatError("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(const Digraph& digraph,
   356                                        std::ostream& os = std::cout);
   357 
   358   template <typename Digraph>
   359   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
   360                                        const std::string& fn);
   361 
   362   template <typename Digraph>
   363   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
   364                                        const char *fn);
   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>(digraph, std::cout).
   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(const Digraph& digraph, std::ostream& os = std::cout)
   456       : _os(&os), 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 Digraph& digraph, const std::string& fn)
   464       : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
   465         _skip_nodes(false), _skip_arcs(false) {
   466       if (!(*_os)) {
   467         delete _os;
   468         throw IoError("Cannot write file", fn);
   469       }
   470     }
   471 
   472     /// \brief Constructor
   473     ///
   474     /// Construct a directed graph writer, which writes to the given
   475     /// output file.
   476     DigraphWriter(const Digraph& digraph, const char* fn)
   477       : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
   478         _skip_nodes(false), _skip_arcs(false) {
   479       if (!(*_os)) {
   480         delete _os;
   481         throw IoError("Cannot write file", fn);
   482       }
   483     }
   484 
   485     /// \brief Destructor
   486     ~DigraphWriter() {
   487       for (typename NodeMaps::iterator it = _node_maps.begin();
   488            it != _node_maps.end(); ++it) {
   489         delete it->second;
   490       }
   491 
   492       for (typename ArcMaps::iterator it = _arc_maps.begin();
   493            it != _arc_maps.end(); ++it) {
   494         delete it->second;
   495       }
   496 
   497       for (typename Attributes::iterator it = _attributes.begin();
   498            it != _attributes.end(); ++it) {
   499         delete it->second;
   500       }
   501 
   502       if (local_os) {
   503         delete _os;
   504       }
   505     }
   506 
   507   private:
   508 
   509     friend DigraphWriter<Digraph> digraphWriter<>(const Digraph& digraph,
   510                                                   std::ostream& os);
   511     friend DigraphWriter<Digraph> digraphWriter<>(const Digraph& digraph,
   512                                                   const std::string& fn);
   513     friend DigraphWriter<Digraph> digraphWriter<>(const Digraph& digraph,
   514                                                   const char *fn);
   515 
   516     DigraphWriter(DigraphWriter& other)
   517       : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
   518         _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
   519 
   520       other._os = 0;
   521       other.local_os = false;
   522 
   523       _node_index.swap(other._node_index);
   524       _arc_index.swap(other._arc_index);
   525 
   526       _node_maps.swap(other._node_maps);
   527       _arc_maps.swap(other._arc_maps);
   528       _attributes.swap(other._attributes);
   529 
   530       _nodes_caption = other._nodes_caption;
   531       _arcs_caption = other._arcs_caption;
   532       _attributes_caption = other._attributes_caption;
   533     }
   534 
   535     DigraphWriter& operator=(const DigraphWriter&);
   536 
   537   public:
   538 
   539     /// \name Writing rules
   540     /// @{
   541 
   542     /// \brief Node map writing rule
   543     ///
   544     /// Add a node map writing rule to the writer.
   545     template <typename Map>
   546     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
   547       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   548       _writer_bits::MapStorageBase<Node>* storage =
   549         new _writer_bits::MapStorage<Node, Map>(map);
   550       _node_maps.push_back(std::make_pair(caption, storage));
   551       return *this;
   552     }
   553 
   554     /// \brief Node map writing rule
   555     ///
   556     /// Add a node map writing rule with specialized converter to the
   557     /// writer.
   558     template <typename Map, typename Converter>
   559     DigraphWriter& nodeMap(const std::string& caption, const Map& map,
   560                            const Converter& converter = Converter()) {
   561       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   562       _writer_bits::MapStorageBase<Node>* storage =
   563         new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
   564       _node_maps.push_back(std::make_pair(caption, storage));
   565       return *this;
   566     }
   567 
   568     /// \brief Arc map writing rule
   569     ///
   570     /// Add an arc map writing rule to the writer.
   571     template <typename Map>
   572     DigraphWriter& arcMap(const std::string& caption, const Map& map) {
   573       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   574       _writer_bits::MapStorageBase<Arc>* storage =
   575         new _writer_bits::MapStorage<Arc, Map>(map);
   576       _arc_maps.push_back(std::make_pair(caption, storage));
   577       return *this;
   578     }
   579 
   580     /// \brief Arc map writing rule
   581     ///
   582     /// Add an arc map writing rule with specialized converter to the
   583     /// writer.
   584     template <typename Map, typename Converter>
   585     DigraphWriter& arcMap(const std::string& caption, const Map& map,
   586                           const Converter& converter = Converter()) {
   587       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   588       _writer_bits::MapStorageBase<Arc>* storage =
   589         new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
   590       _arc_maps.push_back(std::make_pair(caption, storage));
   591       return *this;
   592     }
   593 
   594     /// \brief Attribute writing rule
   595     ///
   596     /// Add an attribute writing rule to the writer.
   597     template <typename Value>
   598     DigraphWriter& attribute(const std::string& caption, const Value& value) {
   599       _writer_bits::ValueStorageBase* storage =
   600         new _writer_bits::ValueStorage<Value>(value);
   601       _attributes.push_back(std::make_pair(caption, storage));
   602       return *this;
   603     }
   604 
   605     /// \brief Attribute writing rule
   606     ///
   607     /// Add an attribute writing rule with specialized converter to the
   608     /// writer.
   609     template <typename Value, typename Converter>
   610     DigraphWriter& attribute(const std::string& caption, const Value& value,
   611                              const Converter& converter = Converter()) {
   612       _writer_bits::ValueStorageBase* storage =
   613         new _writer_bits::ValueStorage<Value, Converter>(value, converter);
   614       _attributes.push_back(std::make_pair(caption, storage));
   615       return *this;
   616     }
   617 
   618     /// \brief Node writing rule
   619     ///
   620     /// Add a node writing rule to the writer.
   621     DigraphWriter& node(const std::string& caption, const Node& node) {
   622       typedef _writer_bits::MapLookUpConverter<Node> Converter;
   623       Converter converter(_node_index);
   624       _writer_bits::ValueStorageBase* storage =
   625         new _writer_bits::ValueStorage<Node, Converter>(node, converter);
   626       _attributes.push_back(std::make_pair(caption, storage));
   627       return *this;
   628     }
   629 
   630     /// \brief Arc writing rule
   631     ///
   632     /// Add an arc writing rule to writer.
   633     DigraphWriter& arc(const std::string& caption, const Arc& arc) {
   634       typedef _writer_bits::MapLookUpConverter<Arc> Converter;
   635       Converter converter(_arc_index);
   636       _writer_bits::ValueStorageBase* storage =
   637         new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
   638       _attributes.push_back(std::make_pair(caption, storage));
   639       return *this;
   640     }
   641 
   642     /// \name Section captions
   643     /// @{
   644 
   645     /// \brief Add an additional caption to the \c \@nodes section
   646     ///
   647     /// Add an additional caption to the \c \@nodes section.
   648     DigraphWriter& nodes(const std::string& caption) {
   649       _nodes_caption = caption;
   650       return *this;
   651     }
   652 
   653     /// \brief Add an additional caption to the \c \@arcs section
   654     ///
   655     /// Add an additional caption to the \c \@arcs section.
   656     DigraphWriter& arcs(const std::string& caption) {
   657       _arcs_caption = caption;
   658       return *this;
   659     }
   660 
   661     /// \brief Add an additional caption to the \c \@attributes section
   662     ///
   663     /// Add an additional caption to the \c \@attributes section.
   664     DigraphWriter& attributes(const std::string& caption) {
   665       _attributes_caption = caption;
   666       return *this;
   667     }
   668 
   669     /// \name Skipping section
   670     /// @{
   671 
   672     /// \brief Skip writing the node set
   673     ///
   674     /// The \c \@nodes section will not be written to the stream.
   675     DigraphWriter& skipNodes() {
   676       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
   677       _skip_nodes = true;
   678       return *this;
   679     }
   680 
   681     /// \brief Skip writing arc set
   682     ///
   683     /// The \c \@arcs section will not be written to the stream.
   684     DigraphWriter& skipArcs() {
   685       LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
   686       _skip_arcs = true;
   687       return *this;
   688     }
   689 
   690     /// @}
   691 
   692   private:
   693 
   694     void writeNodes() {
   695       _writer_bits::MapStorageBase<Node>* label = 0;
   696       for (typename NodeMaps::iterator it = _node_maps.begin();
   697            it != _node_maps.end(); ++it) {
   698         if (it->first == "label") {
   699           label = it->second;
   700           break;
   701         }
   702       }
   703 
   704       *_os << "@nodes";
   705       if (!_nodes_caption.empty()) {
   706         _writer_bits::writeToken(*_os << ' ', _nodes_caption);
   707       }
   708       *_os << std::endl;
   709 
   710       if (label == 0) {
   711         *_os << "label" << '\t';
   712       }
   713       for (typename NodeMaps::iterator it = _node_maps.begin();
   714            it != _node_maps.end(); ++it) {
   715         _writer_bits::writeToken(*_os, it->first) << '\t';
   716       }
   717       *_os << std::endl;
   718 
   719       std::vector<Node> nodes;
   720       for (NodeIt n(_digraph); n != INVALID; ++n) {
   721         nodes.push_back(n);
   722       }
   723 
   724       if (label == 0) {
   725         IdMap<Digraph, Node> id_map(_digraph);
   726         _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
   727         std::sort(nodes.begin(), nodes.end(), id_less);
   728       } else {
   729         label->sort(nodes);
   730       }
   731 
   732       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
   733         Node n = nodes[i];
   734         if (label == 0) {
   735           std::ostringstream os;
   736           os << _digraph.id(n);
   737           _writer_bits::writeToken(*_os, os.str());
   738           *_os << '\t';
   739           _node_index.insert(std::make_pair(n, os.str()));
   740         }
   741         for (typename NodeMaps::iterator it = _node_maps.begin();
   742              it != _node_maps.end(); ++it) {
   743           std::string value = it->second->get(n);
   744           _writer_bits::writeToken(*_os, value);
   745           if (it->first == "label") {
   746             _node_index.insert(std::make_pair(n, value));
   747           }
   748           *_os << '\t';
   749         }
   750         *_os << std::endl;
   751       }
   752     }
   753 
   754     void createNodeIndex() {
   755       _writer_bits::MapStorageBase<Node>* label = 0;
   756       for (typename NodeMaps::iterator it = _node_maps.begin();
   757            it != _node_maps.end(); ++it) {
   758         if (it->first == "label") {
   759           label = it->second;
   760           break;
   761         }
   762       }
   763 
   764       if (label == 0) {
   765         for (NodeIt n(_digraph); n != INVALID; ++n) {
   766           std::ostringstream os;
   767           os << _digraph.id(n);
   768           _node_index.insert(std::make_pair(n, os.str()));
   769         }
   770       } else {
   771         for (NodeIt n(_digraph); n != INVALID; ++n) {
   772           std::string value = label->get(n);
   773           _node_index.insert(std::make_pair(n, value));
   774         }
   775       }
   776     }
   777 
   778     void writeArcs() {
   779       _writer_bits::MapStorageBase<Arc>* label = 0;
   780       for (typename ArcMaps::iterator it = _arc_maps.begin();
   781            it != _arc_maps.end(); ++it) {
   782         if (it->first == "label") {
   783           label = it->second;
   784           break;
   785         }
   786       }
   787 
   788       *_os << "@arcs";
   789       if (!_arcs_caption.empty()) {
   790         _writer_bits::writeToken(*_os << ' ', _arcs_caption);
   791       }
   792       *_os << std::endl;
   793 
   794       *_os << '\t' << '\t';
   795       if (label == 0) {
   796         *_os << "label" << '\t';
   797       }
   798       for (typename ArcMaps::iterator it = _arc_maps.begin();
   799            it != _arc_maps.end(); ++it) {
   800         _writer_bits::writeToken(*_os, it->first) << '\t';
   801       }
   802       *_os << std::endl;
   803 
   804       std::vector<Arc> arcs;
   805       for (ArcIt n(_digraph); n != INVALID; ++n) {
   806         arcs.push_back(n);
   807       }
   808 
   809       if (label == 0) {
   810         IdMap<Digraph, Arc> id_map(_digraph);
   811         _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
   812         std::sort(arcs.begin(), arcs.end(), id_less);
   813       } else {
   814         label->sort(arcs);
   815       }
   816 
   817       for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
   818         Arc a = arcs[i];
   819         _writer_bits::writeToken(*_os, _node_index.
   820                                  find(_digraph.source(a))->second);
   821         *_os << '\t';
   822         _writer_bits::writeToken(*_os, _node_index.
   823                                  find(_digraph.target(a))->second);
   824         *_os << '\t';
   825         if (label == 0) {
   826           std::ostringstream os;
   827           os << _digraph.id(a);
   828           _writer_bits::writeToken(*_os, os.str());
   829           *_os << '\t';
   830           _arc_index.insert(std::make_pair(a, os.str()));
   831         }
   832         for (typename ArcMaps::iterator it = _arc_maps.begin();
   833              it != _arc_maps.end(); ++it) {
   834           std::string value = it->second->get(a);
   835           _writer_bits::writeToken(*_os, value);
   836           if (it->first == "label") {
   837             _arc_index.insert(std::make_pair(a, value));
   838           }
   839           *_os << '\t';
   840         }
   841         *_os << std::endl;
   842       }
   843     }
   844 
   845     void createArcIndex() {
   846       _writer_bits::MapStorageBase<Arc>* label = 0;
   847       for (typename ArcMaps::iterator it = _arc_maps.begin();
   848            it != _arc_maps.end(); ++it) {
   849         if (it->first == "label") {
   850           label = it->second;
   851           break;
   852         }
   853       }
   854 
   855       if (label == 0) {
   856         for (ArcIt a(_digraph); a != INVALID; ++a) {
   857           std::ostringstream os;
   858           os << _digraph.id(a);
   859           _arc_index.insert(std::make_pair(a, os.str()));
   860         }
   861       } else {
   862         for (ArcIt a(_digraph); a != INVALID; ++a) {
   863           std::string value = label->get(a);
   864           _arc_index.insert(std::make_pair(a, value));
   865         }
   866       }
   867     }
   868 
   869     void writeAttributes() {
   870       if (_attributes.empty()) return;
   871       *_os << "@attributes";
   872       if (!_attributes_caption.empty()) {
   873         _writer_bits::writeToken(*_os << ' ', _attributes_caption);
   874       }
   875       *_os << std::endl;
   876       for (typename Attributes::iterator it = _attributes.begin();
   877            it != _attributes.end(); ++it) {
   878         _writer_bits::writeToken(*_os, it->first) << ' ';
   879         _writer_bits::writeToken(*_os, it->second->get());
   880         *_os << std::endl;
   881       }
   882     }
   883 
   884   public:
   885 
   886     /// \name Execution of the writer
   887     /// @{
   888 
   889     /// \brief Start the batch processing
   890     ///
   891     /// This function starts the batch processing.
   892     void run() {
   893       if (!_skip_nodes) {
   894         writeNodes();
   895       } else {
   896         createNodeIndex();
   897       }
   898       if (!_skip_arcs) {
   899         writeArcs();
   900       } else {
   901         createArcIndex();
   902       }
   903       writeAttributes();
   904     }
   905 
   906     /// \brief Give back the stream of the writer
   907     ///
   908     /// Give back the stream of the writer.
   909     std::ostream& ostream() {
   910       return *_os;
   911     }
   912 
   913     /// @}
   914   };
   915 
   916   /// \brief Return a \ref DigraphWriter class
   917   ///
   918   /// This function just returns a \ref DigraphWriter class.
   919   /// \relates DigraphWriter
   920   template <typename Digraph>
   921   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
   922                                        std::ostream& os = std::cout) {
   923     DigraphWriter<Digraph> tmp(digraph, os);
   924     return tmp;
   925   }
   926 
   927   /// \brief Return a \ref DigraphWriter class
   928   ///
   929   /// This function just returns a \ref DigraphWriter class.
   930   /// \relates DigraphWriter
   931   template <typename Digraph>
   932   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
   933                                        const std::string& fn) {
   934     DigraphWriter<Digraph> tmp(digraph, fn);
   935     return tmp;
   936   }
   937 
   938   /// \brief Return a \ref DigraphWriter class
   939   ///
   940   /// This function just returns a \ref DigraphWriter class.
   941   /// \relates DigraphWriter
   942   template <typename Digraph>
   943   DigraphWriter<Digraph> digraphWriter(const Digraph& digraph,
   944                                        const char* fn) {
   945     DigraphWriter<Digraph> tmp(digraph, fn);
   946     return tmp;
   947   }
   948 
   949   template <typename Graph>
   950   class GraphWriter;
   951 
   952   template <typename Graph>
   953   GraphWriter<Graph> graphWriter(const Graph& graph,
   954                                  std::ostream& os = std::cout);
   955 
   956   template <typename Graph>
   957   GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn);
   958 
   959   template <typename Graph>
   960   GraphWriter<Graph> graphWriter(const Graph& graph, const char *fn);
   961 
   962   /// \ingroup lemon_io
   963   ///
   964   /// \brief \ref lgf-format "LGF" writer for directed graphs
   965   ///
   966   /// This utility writes an \ref lgf-format "LGF" file.
   967   ///
   968   /// It can be used almost the same way as \c DigraphWriter.
   969   /// The only difference is that this class can handle edges and
   970   /// edge maps as well as arcs and arc maps.
   971   ///
   972   /// The arc maps are written into the file as two columns, the
   973   /// caption of the columns are the name of the map prefixed with \c
   974   /// '+' and \c '-'. The arcs are written into the \c \@attributes
   975   /// section as a \c '+' or a \c '-' prefix (depends on the direction
   976   /// of the arc) and the label of corresponding edge.
   977   template <typename _Graph>
   978   class GraphWriter {
   979   public:
   980 
   981     typedef _Graph Graph;
   982     TEMPLATE_GRAPH_TYPEDEFS(Graph);
   983 
   984   private:
   985 
   986 
   987     std::ostream* _os;
   988     bool local_os;
   989 
   990     const Graph& _graph;
   991 
   992     std::string _nodes_caption;
   993     std::string _edges_caption;
   994     std::string _attributes_caption;
   995 
   996     typedef std::map<Node, std::string> NodeIndex;
   997     NodeIndex _node_index;
   998     typedef std::map<Edge, std::string> EdgeIndex;
   999     EdgeIndex _edge_index;
  1000 
  1001     typedef std::vector<std::pair<std::string,
  1002       _writer_bits::MapStorageBase<Node>* > > NodeMaps;
  1003     NodeMaps _node_maps;
  1004 
  1005     typedef std::vector<std::pair<std::string,
  1006       _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
  1007     EdgeMaps _edge_maps;
  1008 
  1009     typedef std::vector<std::pair<std::string,
  1010       _writer_bits::ValueStorageBase*> > Attributes;
  1011     Attributes _attributes;
  1012 
  1013     bool _skip_nodes;
  1014     bool _skip_edges;
  1015 
  1016   public:
  1017 
  1018     /// \brief Constructor
  1019     ///
  1020     /// Construct a directed graph writer, which writes to the given
  1021     /// output stream.
  1022     GraphWriter(const Graph& graph, std::ostream& os = std::cout)
  1023       : _os(&os), local_os(false), _graph(graph),
  1024         _skip_nodes(false), _skip_edges(false) {}
  1025 
  1026     /// \brief Constructor
  1027     ///
  1028     /// Construct a directed graph writer, which writes to the given
  1029     /// output file.
  1030     GraphWriter(const Graph& graph, const std::string& fn)
  1031       : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
  1032         _skip_nodes(false), _skip_edges(false) {
  1033       if (!(*_os)) {
  1034         delete _os;
  1035         throw IoError("Cannot write file", fn);
  1036       }
  1037     }
  1038 
  1039     /// \brief Constructor
  1040     ///
  1041     /// Construct a directed graph writer, which writes to the given
  1042     /// output file.
  1043     GraphWriter(const Graph& graph, const char* fn)
  1044       : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
  1045         _skip_nodes(false), _skip_edges(false) {
  1046       if (!(*_os)) {
  1047         delete _os;
  1048         throw IoError("Cannot write file", fn);
  1049       }
  1050     }
  1051 
  1052     /// \brief Destructor
  1053     ~GraphWriter() {
  1054       for (typename NodeMaps::iterator it = _node_maps.begin();
  1055            it != _node_maps.end(); ++it) {
  1056         delete it->second;
  1057       }
  1058 
  1059       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1060            it != _edge_maps.end(); ++it) {
  1061         delete it->second;
  1062       }
  1063 
  1064       for (typename Attributes::iterator it = _attributes.begin();
  1065            it != _attributes.end(); ++it) {
  1066         delete it->second;
  1067       }
  1068 
  1069       if (local_os) {
  1070         delete _os;
  1071       }
  1072     }
  1073 
  1074   private:
  1075 
  1076     friend GraphWriter<Graph> graphWriter<>(const Graph& graph,
  1077                                             std::ostream& os);
  1078     friend GraphWriter<Graph> graphWriter<>(const Graph& graph,
  1079                                             const std::string& fn);
  1080     friend GraphWriter<Graph> graphWriter<>(const Graph& graph,
  1081                                             const char *fn);
  1082 
  1083     GraphWriter(GraphWriter& other)
  1084       : _os(other._os), local_os(other.local_os), _graph(other._graph),
  1085         _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1086 
  1087       other._os = 0;
  1088       other.local_os = false;
  1089 
  1090       _node_index.swap(other._node_index);
  1091       _edge_index.swap(other._edge_index);
  1092 
  1093       _node_maps.swap(other._node_maps);
  1094       _edge_maps.swap(other._edge_maps);
  1095       _attributes.swap(other._attributes);
  1096 
  1097       _nodes_caption = other._nodes_caption;
  1098       _edges_caption = other._edges_caption;
  1099       _attributes_caption = other._attributes_caption;
  1100     }
  1101 
  1102     GraphWriter& operator=(const GraphWriter&);
  1103 
  1104   public:
  1105 
  1106     /// \name Writing rules
  1107     /// @{
  1108 
  1109     /// \brief Node map writing rule
  1110     ///
  1111     /// Add a node map writing rule to the writer.
  1112     template <typename Map>
  1113     GraphWriter& nodeMap(const std::string& caption, const Map& map) {
  1114       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1115       _writer_bits::MapStorageBase<Node>* storage =
  1116         new _writer_bits::MapStorage<Node, Map>(map);
  1117       _node_maps.push_back(std::make_pair(caption, storage));
  1118       return *this;
  1119     }
  1120 
  1121     /// \brief Node map writing rule
  1122     ///
  1123     /// Add a node map writing rule with specialized converter to the
  1124     /// writer.
  1125     template <typename Map, typename Converter>
  1126     GraphWriter& nodeMap(const std::string& caption, const Map& map,
  1127                            const Converter& converter = Converter()) {
  1128       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1129       _writer_bits::MapStorageBase<Node>* storage =
  1130         new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
  1131       _node_maps.push_back(std::make_pair(caption, storage));
  1132       return *this;
  1133     }
  1134 
  1135     /// \brief Edge map writing rule
  1136     ///
  1137     /// Add an edge map writing rule to the writer.
  1138     template <typename Map>
  1139     GraphWriter& edgeMap(const std::string& caption, const Map& map) {
  1140       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1141       _writer_bits::MapStorageBase<Edge>* storage =
  1142         new _writer_bits::MapStorage<Edge, Map>(map);
  1143       _edge_maps.push_back(std::make_pair(caption, storage));
  1144       return *this;
  1145     }
  1146 
  1147     /// \brief Edge map writing rule
  1148     ///
  1149     /// Add an edge map writing rule with specialized converter to the
  1150     /// writer.
  1151     template <typename Map, typename Converter>
  1152     GraphWriter& edgeMap(const std::string& caption, const Map& map,
  1153                           const Converter& converter = Converter()) {
  1154       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1155       _writer_bits::MapStorageBase<Edge>* storage =
  1156         new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1157       _edge_maps.push_back(std::make_pair(caption, storage));
  1158       return *this;
  1159     }
  1160 
  1161     /// \brief Arc map writing rule
  1162     ///
  1163     /// Add an arc map writing rule to the writer.
  1164     template <typename Map>
  1165     GraphWriter& arcMap(const std::string& caption, const Map& map) {
  1166       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1167       _writer_bits::MapStorageBase<Edge>* forward_storage =
  1168         new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1169       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1170       _writer_bits::MapStorageBase<Edge>* backward_storage =
  1171         new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1172       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1173       return *this;
  1174     }
  1175 
  1176     /// \brief Arc map writing rule
  1177     ///
  1178     /// Add an arc map writing rule with specialized converter to the
  1179     /// writer.
  1180     template <typename Map, typename Converter>
  1181     GraphWriter& arcMap(const std::string& caption, const Map& map,
  1182                           const Converter& converter = Converter()) {
  1183       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1184       _writer_bits::MapStorageBase<Edge>* forward_storage =
  1185         new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1186         (_graph, map, converter);
  1187       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1188       _writer_bits::MapStorageBase<Edge>* backward_storage =
  1189         new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1190         (_graph, map, converter);
  1191       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1192       return *this;
  1193     }
  1194 
  1195     /// \brief Attribute writing rule
  1196     ///
  1197     /// Add an attribute writing rule to the writer.
  1198     template <typename Value>
  1199     GraphWriter& attribute(const std::string& caption, const Value& value) {
  1200       _writer_bits::ValueStorageBase* storage =
  1201         new _writer_bits::ValueStorage<Value>(value);
  1202       _attributes.push_back(std::make_pair(caption, storage));
  1203       return *this;
  1204     }
  1205 
  1206     /// \brief Attribute writing rule
  1207     ///
  1208     /// Add an attribute writing rule with specialized converter to the
  1209     /// writer.
  1210     template <typename Value, typename Converter>
  1211     GraphWriter& attribute(const std::string& caption, const Value& value,
  1212                              const Converter& converter = Converter()) {
  1213       _writer_bits::ValueStorageBase* storage =
  1214         new _writer_bits::ValueStorage<Value, Converter>(value, converter);
  1215       _attributes.push_back(std::make_pair(caption, storage));
  1216       return *this;
  1217     }
  1218 
  1219     /// \brief Node writing rule
  1220     ///
  1221     /// Add a node writing rule to the writer.
  1222     GraphWriter& node(const std::string& caption, const Node& node) {
  1223       typedef _writer_bits::MapLookUpConverter<Node> Converter;
  1224       Converter converter(_node_index);
  1225       _writer_bits::ValueStorageBase* storage =
  1226         new _writer_bits::ValueStorage<Node, Converter>(node, converter);
  1227       _attributes.push_back(std::make_pair(caption, storage));
  1228       return *this;
  1229     }
  1230 
  1231     /// \brief Edge writing rule
  1232     ///
  1233     /// Add an edge writing rule to writer.
  1234     GraphWriter& edge(const std::string& caption, const Edge& edge) {
  1235       typedef _writer_bits::MapLookUpConverter<Edge> Converter;
  1236       Converter converter(_edge_index);
  1237       _writer_bits::ValueStorageBase* storage =
  1238         new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
  1239       _attributes.push_back(std::make_pair(caption, storage));
  1240       return *this;
  1241     }
  1242 
  1243     /// \brief Arc writing rule
  1244     ///
  1245     /// Add an arc writing rule to writer.
  1246     GraphWriter& arc(const std::string& caption, const Arc& arc) {
  1247       typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
  1248       Converter converter(_graph, _edge_index);
  1249       _writer_bits::ValueStorageBase* storage =
  1250         new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
  1251       _attributes.push_back(std::make_pair(caption, storage));
  1252       return *this;
  1253     }
  1254 
  1255     /// \name Section captions
  1256     /// @{
  1257 
  1258     /// \brief Add an additional caption to the \c \@nodes section
  1259     ///
  1260     /// Add an additional caption to the \c \@nodes section.
  1261     GraphWriter& nodes(const std::string& caption) {
  1262       _nodes_caption = caption;
  1263       return *this;
  1264     }
  1265 
  1266     /// \brief Add an additional caption to the \c \@arcs section
  1267     ///
  1268     /// Add an additional caption to the \c \@arcs section.
  1269     GraphWriter& edges(const std::string& caption) {
  1270       _edges_caption = caption;
  1271       return *this;
  1272     }
  1273 
  1274     /// \brief Add an additional caption to the \c \@attributes section
  1275     ///
  1276     /// Add an additional caption to the \c \@attributes section.
  1277     GraphWriter& attributes(const std::string& caption) {
  1278       _attributes_caption = caption;
  1279       return *this;
  1280     }
  1281 
  1282     /// \name Skipping section
  1283     /// @{
  1284 
  1285     /// \brief Skip writing the node set
  1286     ///
  1287     /// The \c \@nodes section will not be written to the stream.
  1288     GraphWriter& skipNodes() {
  1289       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
  1290       _skip_nodes = true;
  1291       return *this;
  1292     }
  1293 
  1294     /// \brief Skip writing edge set
  1295     ///
  1296     /// The \c \@edges section will not be written to the stream.
  1297     GraphWriter& skipEdges() {
  1298       LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
  1299       _skip_edges = true;
  1300       return *this;
  1301     }
  1302 
  1303     /// @}
  1304 
  1305   private:
  1306 
  1307     void writeNodes() {
  1308       _writer_bits::MapStorageBase<Node>* label = 0;
  1309       for (typename NodeMaps::iterator it = _node_maps.begin();
  1310            it != _node_maps.end(); ++it) {
  1311         if (it->first == "label") {
  1312           label = it->second;
  1313           break;
  1314         }
  1315       }
  1316 
  1317       *_os << "@nodes";
  1318       if (!_nodes_caption.empty()) {
  1319         _writer_bits::writeToken(*_os << ' ', _nodes_caption);
  1320       }
  1321       *_os << std::endl;
  1322 
  1323       if (label == 0) {
  1324         *_os << "label" << '\t';
  1325       }
  1326       for (typename NodeMaps::iterator it = _node_maps.begin();
  1327            it != _node_maps.end(); ++it) {
  1328         _writer_bits::writeToken(*_os, it->first) << '\t';
  1329       }
  1330       *_os << std::endl;
  1331 
  1332       std::vector<Node> nodes;
  1333       for (NodeIt n(_graph); n != INVALID; ++n) {
  1334         nodes.push_back(n);
  1335       }
  1336 
  1337       if (label == 0) {
  1338         IdMap<Graph, Node> id_map(_graph);
  1339         _writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
  1340         std::sort(nodes.begin(), nodes.end(), id_less);
  1341       } else {
  1342         label->sort(nodes);
  1343       }
  1344 
  1345       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
  1346         Node n = nodes[i];
  1347         if (label == 0) {
  1348           std::ostringstream os;
  1349           os << _graph.id(n);
  1350           _writer_bits::writeToken(*_os, os.str());
  1351           *_os << '\t';
  1352           _node_index.insert(std::make_pair(n, os.str()));
  1353         }
  1354         for (typename NodeMaps::iterator it = _node_maps.begin();
  1355              it != _node_maps.end(); ++it) {
  1356           std::string value = it->second->get(n);
  1357           _writer_bits::writeToken(*_os, value);
  1358           if (it->first == "label") {
  1359             _node_index.insert(std::make_pair(n, value));
  1360           }
  1361           *_os << '\t';
  1362         }
  1363         *_os << std::endl;
  1364       }
  1365     }
  1366 
  1367     void createNodeIndex() {
  1368       _writer_bits::MapStorageBase<Node>* label = 0;
  1369       for (typename NodeMaps::iterator it = _node_maps.begin();
  1370            it != _node_maps.end(); ++it) {
  1371         if (it->first == "label") {
  1372           label = it->second;
  1373           break;
  1374         }
  1375       }
  1376 
  1377       if (label == 0) {
  1378         for (NodeIt n(_graph); n != INVALID; ++n) {
  1379           std::ostringstream os;
  1380           os << _graph.id(n);
  1381           _node_index.insert(std::make_pair(n, os.str()));
  1382         }
  1383       } else {
  1384         for (NodeIt n(_graph); n != INVALID; ++n) {
  1385           std::string value = label->get(n);
  1386           _node_index.insert(std::make_pair(n, value));
  1387         }
  1388       }
  1389     }
  1390 
  1391     void writeEdges() {
  1392       _writer_bits::MapStorageBase<Edge>* label = 0;
  1393       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1394            it != _edge_maps.end(); ++it) {
  1395         if (it->first == "label") {
  1396           label = it->second;
  1397           break;
  1398         }
  1399       }
  1400 
  1401       *_os << "@edges";
  1402       if (!_edges_caption.empty()) {
  1403         _writer_bits::writeToken(*_os << ' ', _edges_caption);
  1404       }
  1405       *_os << std::endl;
  1406 
  1407       *_os << '\t' << '\t';
  1408       if (label == 0) {
  1409         *_os << "label" << '\t';
  1410       }
  1411       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1412            it != _edge_maps.end(); ++it) {
  1413         _writer_bits::writeToken(*_os, it->first) << '\t';
  1414       }
  1415       *_os << std::endl;
  1416 
  1417       std::vector<Edge> edges;
  1418       for (EdgeIt n(_graph); n != INVALID; ++n) {
  1419         edges.push_back(n);
  1420       }
  1421 
  1422       if (label == 0) {
  1423         IdMap<Graph, Edge> id_map(_graph);
  1424         _writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
  1425         std::sort(edges.begin(), edges.end(), id_less);
  1426       } else {
  1427         label->sort(edges);
  1428       }
  1429 
  1430       for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
  1431         Edge e = edges[i];
  1432         _writer_bits::writeToken(*_os, _node_index.
  1433                                  find(_graph.u(e))->second);
  1434         *_os << '\t';
  1435         _writer_bits::writeToken(*_os, _node_index.
  1436                                  find(_graph.v(e))->second);
  1437         *_os << '\t';
  1438         if (label == 0) {
  1439           std::ostringstream os;
  1440           os << _graph.id(e);
  1441           _writer_bits::writeToken(*_os, os.str());
  1442           *_os << '\t';
  1443           _edge_index.insert(std::make_pair(e, os.str()));
  1444         }
  1445         for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1446              it != _edge_maps.end(); ++it) {
  1447           std::string value = it->second->get(e);
  1448           _writer_bits::writeToken(*_os, value);
  1449           if (it->first == "label") {
  1450             _edge_index.insert(std::make_pair(e, value));
  1451           }
  1452           *_os << '\t';
  1453         }
  1454         *_os << std::endl;
  1455       }
  1456     }
  1457 
  1458     void createEdgeIndex() {
  1459       _writer_bits::MapStorageBase<Edge>* label = 0;
  1460       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1461            it != _edge_maps.end(); ++it) {
  1462         if (it->first == "label") {
  1463           label = it->second;
  1464           break;
  1465         }
  1466       }
  1467 
  1468       if (label == 0) {
  1469         for (EdgeIt e(_graph); e != INVALID; ++e) {
  1470           std::ostringstream os;
  1471           os << _graph.id(e);
  1472           _edge_index.insert(std::make_pair(e, os.str()));
  1473         }
  1474       } else {
  1475         for (EdgeIt e(_graph); e != INVALID; ++e) {
  1476           std::string value = label->get(e);
  1477           _edge_index.insert(std::make_pair(e, value));
  1478         }
  1479       }
  1480     }
  1481 
  1482     void writeAttributes() {
  1483       if (_attributes.empty()) return;
  1484       *_os << "@attributes";
  1485       if (!_attributes_caption.empty()) {
  1486         _writer_bits::writeToken(*_os << ' ', _attributes_caption);
  1487       }
  1488       *_os << std::endl;
  1489       for (typename Attributes::iterator it = _attributes.begin();
  1490            it != _attributes.end(); ++it) {
  1491         _writer_bits::writeToken(*_os, it->first) << ' ';
  1492         _writer_bits::writeToken(*_os, it->second->get());
  1493         *_os << std::endl;
  1494       }
  1495     }
  1496 
  1497   public:
  1498 
  1499     /// \name Execution of the writer
  1500     /// @{
  1501 
  1502     /// \brief Start the batch processing
  1503     ///
  1504     /// This function starts the batch processing.
  1505     void run() {
  1506       if (!_skip_nodes) {
  1507         writeNodes();
  1508       } else {
  1509         createNodeIndex();
  1510       }
  1511       if (!_skip_edges) {
  1512         writeEdges();
  1513       } else {
  1514         createEdgeIndex();
  1515       }
  1516       writeAttributes();
  1517     }
  1518 
  1519     /// \brief Give back the stream of the writer
  1520     ///
  1521     /// Give back the stream of the writer
  1522     std::ostream& ostream() {
  1523       return *_os;
  1524     }
  1525 
  1526     /// @}
  1527   };
  1528 
  1529   /// \brief Return a \ref GraphWriter class
  1530   ///
  1531   /// This function just returns a \ref GraphWriter class.
  1532   /// \relates GraphWriter
  1533   template <typename Graph>
  1534   GraphWriter<Graph> graphWriter(const Graph& graph,
  1535                                  std::ostream& os = std::cout) {
  1536     GraphWriter<Graph> tmp(graph, os);
  1537     return tmp;
  1538   }
  1539 
  1540   /// \brief Return a \ref GraphWriter class
  1541   ///
  1542   /// This function just returns a \ref GraphWriter class.
  1543   /// \relates GraphWriter
  1544   template <typename Graph>
  1545   GraphWriter<Graph> graphWriter(const Graph& graph, const std::string& fn) {
  1546     GraphWriter<Graph> tmp(graph, fn);
  1547     return tmp;
  1548   }
  1549 
  1550   /// \brief Return a \ref GraphWriter class
  1551   ///
  1552   /// This function just returns a \ref GraphWriter class.
  1553   /// \relates GraphWriter
  1554   template <typename Graph>
  1555   GraphWriter<Graph> graphWriter(const Graph& graph, const char* fn) {
  1556     GraphWriter<Graph> tmp(graph, fn);
  1557     return tmp;
  1558   }
  1559 
  1560   class SectionWriter;
  1561 
  1562   SectionWriter sectionWriter(std::istream& is);
  1563   SectionWriter sectionWriter(const std::string& fn);
  1564   SectionWriter sectionWriter(const char* fn);
  1565 
  1566   /// \ingroup lemon_io
  1567   ///
  1568   /// \brief Section writer class
  1569   ///
  1570   /// In the \ref lgf-format "LGF" file extra sections can be placed,
  1571   /// which contain any data in arbitrary format. Such sections can be
  1572   /// written with this class. A writing rule can be added to the
  1573   /// class with two different functions. With the \c sectionLines()
  1574   /// function a generator can write the section line-by-line, while
  1575   /// with the \c sectionStream() member the section can be written to
  1576   /// an output stream.
  1577   class SectionWriter {
  1578   private:
  1579 
  1580     std::ostream* _os;
  1581     bool local_os;
  1582 
  1583     typedef std::vector<std::pair<std::string, _writer_bits::Section*> >
  1584     Sections;
  1585 
  1586     Sections _sections;
  1587 
  1588   public:
  1589 
  1590     /// \brief Constructor
  1591     ///
  1592     /// Construct a section writer, which writes to the given output
  1593     /// stream.
  1594     SectionWriter(std::ostream& os)
  1595       : _os(&os), local_os(false) {}
  1596 
  1597     /// \brief Constructor
  1598     ///
  1599     /// Construct a section writer, which writes into the given file.
  1600     SectionWriter(const std::string& fn)
  1601       : _os(new std::ofstream(fn.c_str())), local_os(true) {
  1602       if (!(*_os)) {
  1603         delete _os;
  1604         throw IoError("Cannot write file", fn);
  1605       }
  1606     }
  1607 
  1608     /// \brief Constructor
  1609     ///
  1610     /// Construct a section writer, which writes into the given file.
  1611     SectionWriter(const char* fn)
  1612       : _os(new std::ofstream(fn)), local_os(true) {
  1613       if (!(*_os)) {
  1614         delete _os;
  1615         throw IoError("Cannot write file", fn);
  1616       }
  1617     }
  1618 
  1619     /// \brief Destructor
  1620     ~SectionWriter() {
  1621       for (Sections::iterator it = _sections.begin();
  1622            it != _sections.end(); ++it) {
  1623         delete it->second;
  1624       }
  1625 
  1626       if (local_os) {
  1627         delete _os;
  1628       }
  1629 
  1630     }
  1631 
  1632   private:
  1633 
  1634     friend SectionWriter sectionWriter(std::ostream& os);
  1635     friend SectionWriter sectionWriter(const std::string& fn);
  1636     friend SectionWriter sectionWriter(const char* fn);
  1637 
  1638     SectionWriter(SectionWriter& other)
  1639       : _os(other._os), local_os(other.local_os) {
  1640 
  1641       other._os = 0;
  1642       other.local_os = false;
  1643 
  1644       _sections.swap(other._sections);
  1645     }
  1646 
  1647     SectionWriter& operator=(const SectionWriter&);
  1648 
  1649   public:
  1650 
  1651     /// \name Section writers
  1652     /// @{
  1653 
  1654     /// \brief Add a section writer with line oriented writing
  1655     ///
  1656     /// The first parameter is the type descriptor of the section, the
  1657     /// second is a generator with std::string values. At the writing
  1658     /// process, the returned \c std::string will be written into the
  1659     /// output file until it is an empty string.
  1660     ///
  1661     /// For example, an integer vector is written into a section.
  1662     ///\code
  1663     ///  @numbers
  1664     ///  12 45 23 78
  1665     ///  4 28 38 28
  1666     ///  23 6 16
  1667     ///\endcode
  1668     ///
  1669     /// The generator is implemented as a struct.
  1670     ///\code
  1671     ///  struct NumberSection {
  1672     ///    std::vector<int>::const_iterator _it, _end;
  1673     ///    NumberSection(const std::vector<int>& data)
  1674     ///      : _it(data.begin()), _end(data.end()) {}
  1675     ///    std::string operator()() {
  1676     ///      int rem_in_line = 4;
  1677     ///      std::ostringstream ls;
  1678     ///      while (rem_in_line > 0 && _it != _end) {
  1679     ///        ls << *(_it++) << ' ';
  1680     ///        --rem_in_line;
  1681     ///      }
  1682     ///      return ls.str();
  1683     ///    }
  1684     ///  };
  1685     ///
  1686     ///  // ...
  1687     ///
  1688     ///  writer.sectionLines("numbers", NumberSection(vec));
  1689     ///\endcode
  1690     template <typename Functor>
  1691     SectionWriter& sectionLines(const std::string& type, Functor functor) {
  1692       LEMON_ASSERT(!type.empty(), "Type is empty.");
  1693       _sections.push_back(std::make_pair(type,
  1694         new _writer_bits::LineSection<Functor>(functor)));
  1695       return *this;
  1696     }
  1697 
  1698 
  1699     /// \brief Add a section writer with stream oriented writing
  1700     ///
  1701     /// The first parameter is the type of the section, the second is
  1702     /// a functor, which takes a \c std::ostream& parameter. The
  1703     /// functor writes the section to the output stream.
  1704     /// \warning The last line must be closed with end-line character.
  1705     template <typename Functor>
  1706     SectionWriter& sectionStream(const std::string& type, Functor functor) {
  1707       LEMON_ASSERT(!type.empty(), "Type is empty.");
  1708       _sections.push_back(std::make_pair(type,
  1709          new _writer_bits::StreamSection<Functor>(functor)));
  1710       return *this;
  1711     }
  1712 
  1713     /// @}
  1714 
  1715   public:
  1716 
  1717 
  1718     /// \name Execution of the writer
  1719     /// @{
  1720 
  1721     /// \brief Start the batch processing
  1722     ///
  1723     /// This function starts the batch processing.
  1724     void run() {
  1725 
  1726       LEMON_ASSERT(_os != 0, "This writer is assigned to an other writer");
  1727 
  1728       for (Sections::iterator it = _sections.begin();
  1729            it != _sections.end(); ++it) {
  1730         (*_os) << '@' << it->first << std::endl;
  1731         it->second->process(*_os);
  1732       }
  1733     }
  1734 
  1735     /// \brief Give back the stream of the writer
  1736     ///
  1737     /// Returns the stream of the writer
  1738     std::ostream& ostream() {
  1739       return *_os;
  1740     }
  1741 
  1742     /// @}
  1743 
  1744   };
  1745 
  1746   /// \brief Return a \ref SectionWriter class
  1747   ///
  1748   /// This function just returns a \ref SectionWriter class.
  1749   /// \relates SectionWriter
  1750   inline SectionWriter sectionWriter(std::ostream& os) {
  1751     SectionWriter tmp(os);
  1752     return tmp;
  1753   }
  1754 
  1755   /// \brief Return a \ref SectionWriter class
  1756   ///
  1757   /// This function just returns a \ref SectionWriter class.
  1758   /// \relates SectionWriter
  1759   inline SectionWriter sectionWriter(const std::string& fn) {
  1760     SectionWriter tmp(fn);
  1761     return tmp;
  1762   }
  1763 
  1764   /// \brief Return a \ref SectionWriter class
  1765   ///
  1766   /// This function just returns a \ref SectionWriter class.
  1767   /// \relates SectionWriter
  1768   inline SectionWriter sectionWriter(const char* fn) {
  1769     SectionWriter tmp(fn);
  1770     return tmp;
  1771   }
  1772 }
  1773 
  1774 #endif