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