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