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