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