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