lemon/lgf_writer.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 03 Jul 2008 12:40:04 +0200
changeset 188 70694e6bdcac
parent 165 b4c336c27a03
child 190 1e6af6f0843c
permissions -rw-r--r--
New skip*() functions in (Dig|G)raphReader
     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   /// \ingroup lemon_io
   309   ///  
   310   /// \brief LGF writer for directed graphs
   311   ///
   312   /// This utility writes an \ref lgf-format "LGF" file.
   313   ///
   314   /// The writing method does a batch processing. The user creates a
   315   /// writer object, then various writing rules can be added to the
   316   /// writer, and eventually the writing is executed with the \c run()
   317   /// member function. A map writing rule can be added to the writer
   318   /// with the \c nodeMap() or \c arcMap() members. An optional
   319   /// converter parameter can also be added as a standard functor
   320   /// converting from the value type of the map to std::string. If it
   321   /// is set, it will determine how the map's value type is written to
   322   /// the output stream. If the functor is not set, then a default
   323   /// conversion will be used. The \c attribute(), \c node() and \c
   324   /// arc() functions are used to add attribute writing rules.
   325   ///
   326   ///\code
   327   ///     DigraphWriter<Digraph>(std::cout, digraph).
   328   ///       nodeMap("coordinates", coord_map).
   329   ///       nodeMap("size", size).
   330   ///       nodeMap("title", title).
   331   ///       arcMap("capacity", cap_map).
   332   ///       node("source", src).
   333   ///       node("target", trg).
   334   ///       attribute("caption", caption).
   335   ///       run();
   336   ///\endcode
   337   ///
   338   ///
   339   /// By default, the writer does not write additional captions to the
   340   /// sections, but they can be give as an optional parameter of
   341   /// the \c nodes(), \c arcs() or \c
   342   /// attributes() functions.
   343   ///
   344   /// The \c skipNodes() and \c skipArcs() functions forbid the
   345   /// writing of the sections. If two arc sections should be written
   346   /// to the output, it can be done in two passes, the first pass
   347   /// writes the node section and the first arc section, then the
   348   /// second pass skips the node section and writes just the arc
   349   /// section to the stream. The output stream can be retrieved with
   350   /// the \c ostream() function, hence the second pass can append its
   351   /// output to the output of the first pass.
   352   template <typename _Digraph>
   353   class DigraphWriter {
   354   public:
   355 
   356     typedef _Digraph Digraph;
   357     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   358     
   359   private:
   360 
   361 
   362     std::ostream* _os;
   363     bool local_os;
   364 
   365     Digraph& _digraph;
   366 
   367     std::string _nodes_caption;
   368     std::string _arcs_caption;
   369     std::string _attributes_caption;
   370     
   371     typedef std::map<Node, std::string> NodeIndex;
   372     NodeIndex _node_index;
   373     typedef std::map<Arc, std::string> ArcIndex;
   374     ArcIndex _arc_index;
   375 
   376     typedef std::vector<std::pair<std::string, 
   377       _writer_bits::MapStorageBase<Node>* > > NodeMaps;    
   378     NodeMaps _node_maps; 
   379 
   380     typedef std::vector<std::pair<std::string, 
   381       _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
   382     ArcMaps _arc_maps;
   383 
   384     typedef std::vector<std::pair<std::string, 
   385       _writer_bits::ValueStorageBase*> > Attributes;
   386     Attributes _attributes;
   387 
   388     bool _skip_nodes;
   389     bool _skip_arcs;
   390 
   391   public:
   392 
   393     /// \brief Constructor
   394     ///
   395     /// Construct a directed graph writer, which writes to the given
   396     /// output stream.
   397     DigraphWriter(std::ostream& is, Digraph& digraph) 
   398       : _os(&is), local_os(false), _digraph(digraph),
   399 	_skip_nodes(false), _skip_arcs(false) {}
   400 
   401     /// \brief Constructor
   402     ///
   403     /// Construct a directed graph writer, which writes to the given
   404     /// output file.
   405     DigraphWriter(const std::string& fn, Digraph& digraph) 
   406       : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
   407 	_skip_nodes(false), _skip_arcs(false) {}
   408 
   409     /// \brief Constructor
   410     ///
   411     /// Construct a directed graph writer, which writes to the given
   412     /// output file.
   413     DigraphWriter(const char* fn, Digraph& digraph) 
   414       : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
   415 	_skip_nodes(false), _skip_arcs(false) {}
   416 
   417     /// \brief Copy constructor
   418     ///
   419     /// The copy constructor transfers all data from the other writer,
   420     /// therefore the copied writer will not be usable more. 
   421     DigraphWriter(DigraphWriter& other) 
   422       : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
   423 	_skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
   424 
   425       other._os = 0;
   426       other.local_os = false;
   427 
   428       _node_index.swap(other._node_index);
   429       _arc_index.swap(other._arc_index);
   430 
   431       _node_maps.swap(other._node_maps);
   432       _arc_maps.swap(other._arc_maps);
   433       _attributes.swap(other._attributes);
   434 
   435       _nodes_caption = other._nodes_caption;
   436       _arcs_caption = other._arcs_caption;
   437       _attributes_caption = other._attributes_caption;
   438     }
   439 
   440     /// \brief Destructor
   441     ~DigraphWriter() {
   442       for (typename NodeMaps::iterator it = _node_maps.begin(); 
   443 	   it != _node_maps.end(); ++it) {
   444 	delete it->second;
   445       }
   446 
   447       for (typename ArcMaps::iterator it = _arc_maps.begin(); 
   448 	   it != _arc_maps.end(); ++it) {
   449 	delete it->second;
   450       }
   451 
   452       for (typename Attributes::iterator it = _attributes.begin(); 
   453 	   it != _attributes.end(); ++it) {
   454 	delete it->second;
   455       }
   456 
   457       if (local_os) {
   458 	delete _os;
   459       }
   460     }
   461 
   462   private:
   463     
   464     DigraphWriter& operator=(const DigraphWriter&);
   465 
   466   public:
   467 
   468     /// \name Writing rules
   469     /// @{
   470     
   471     /// \brief Node map reading rule
   472     ///
   473     /// Add a node map reading rule to the writer.
   474     template <typename Map>
   475     DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
   476       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   477       _writer_bits::MapStorageBase<Node>* storage = 
   478 	new _writer_bits::MapStorage<Node, Map>(map);
   479       _node_maps.push_back(std::make_pair(caption, storage));
   480       return *this;
   481     }
   482 
   483     /// \brief Node map writing rule
   484     ///
   485     /// Add a node map writing rule with specialized converter to the
   486     /// writer.
   487     template <typename Map, typename Converter>
   488     DigraphWriter& nodeMap(const std::string& caption, const Map& map, 
   489 			   const Converter& converter = Converter()) {
   490       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   491       _writer_bits::MapStorageBase<Node>* storage = 
   492 	new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
   493       _node_maps.push_back(std::make_pair(caption, storage));
   494       return *this;
   495     }
   496 
   497     /// \brief Arc map writing rule
   498     ///
   499     /// Add an arc map writing rule to the writer.
   500     template <typename Map>
   501     DigraphWriter& arcMap(const std::string& caption, const Map& map) {
   502       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   503       _writer_bits::MapStorageBase<Arc>* storage = 
   504 	new _writer_bits::MapStorage<Arc, Map>(map);
   505       _arc_maps.push_back(std::make_pair(caption, storage));
   506       return *this;
   507     }
   508 
   509     /// \brief Arc map writing rule
   510     ///
   511     /// Add an arc map writing rule with specialized converter to the
   512     /// writer.
   513     template <typename Map, typename Converter>
   514     DigraphWriter& arcMap(const std::string& caption, const Map& map, 
   515 			  const Converter& converter = Converter()) {
   516       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   517       _writer_bits::MapStorageBase<Arc>* storage = 
   518 	new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
   519       _arc_maps.push_back(std::make_pair(caption, storage));
   520       return *this;
   521     }
   522 
   523     /// \brief Attribute writing rule
   524     ///
   525     /// Add an attribute writing rule to the writer.
   526     template <typename Value>
   527     DigraphWriter& attribute(const std::string& caption, const Value& value) {
   528       _writer_bits::ValueStorageBase* storage = 
   529 	new _writer_bits::ValueStorage<Value>(value);
   530       _attributes.push_back(std::make_pair(caption, storage));
   531       return *this;
   532     }
   533 
   534     /// \brief Attribute writing rule
   535     ///
   536     /// Add an attribute writing rule with specialized converter to the
   537     /// writer.
   538     template <typename Value, typename Converter>
   539     DigraphWriter& attribute(const std::string& caption, const Value& value, 
   540 			     const Converter& converter = Converter()) {
   541       _writer_bits::ValueStorageBase* storage = 
   542 	new _writer_bits::ValueStorage<Value, Converter>(value, converter);
   543       _attributes.push_back(std::make_pair(caption, storage));
   544       return *this;
   545     }
   546 
   547     /// \brief Node writing rule
   548     ///
   549     /// Add a node writing rule to the writer.
   550     DigraphWriter& node(const std::string& caption, const Node& node) {
   551       typedef _writer_bits::MapLookUpConverter<Node> Converter;
   552       Converter converter(_node_index);
   553       _writer_bits::ValueStorageBase* storage = 
   554 	new _writer_bits::ValueStorage<Node, Converter>(node, converter);
   555       _attributes.push_back(std::make_pair(caption, storage));
   556       return *this;
   557     }
   558 
   559     /// \brief Arc writing rule
   560     ///
   561     /// Add an arc writing rule to writer.
   562     DigraphWriter& arc(const std::string& caption, const Arc& arc) {
   563       typedef _writer_bits::MapLookUpConverter<Arc> Converter;
   564       Converter converter(_arc_index);
   565       _writer_bits::ValueStorageBase* storage = 
   566 	new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
   567       _attributes.push_back(std::make_pair(caption, storage));
   568       return *this;
   569     }
   570 
   571     /// \name Select section by name
   572     /// @{
   573 
   574     /// \brief Set \c \@nodes section to be read
   575     ///
   576     /// Set \c \@nodes section to be read
   577     DigraphWriter& nodes(const std::string& caption) {
   578       _nodes_caption = caption;
   579       return *this;
   580     }
   581 
   582     /// \brief Set \c \@arcs section to be read
   583     ///
   584     /// Set \c \@arcs section to be read
   585     DigraphWriter& arcs(const std::string& caption) {
   586       _arcs_caption = caption;
   587       return *this;
   588     }
   589 
   590     /// \brief Set \c \@attributes section to be read
   591     ///
   592     /// Set \c \@attributes section to be read
   593     DigraphWriter& attributes(const std::string& caption) {
   594       _attributes_caption = caption;
   595       return *this;
   596     }
   597 
   598     /// \name Skipping section
   599     /// @{
   600 
   601     /// \brief Skip writing the node set
   602     ///
   603     /// The \c \@nodes section will be not written to the stream.
   604     DigraphWriter& skipNodes() {
   605       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
   606       _skip_nodes = true;
   607       return *this;
   608     }
   609 
   610     /// \brief Skip writing arc set
   611     ///
   612     /// The \c \@arcs section will be not written to the stream.
   613     DigraphWriter& skipArcs() {
   614       LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
   615       _skip_arcs = true;
   616       return *this;
   617     }
   618 
   619     /// @}
   620 
   621   private:
   622 
   623     void writeNodes() {
   624       _writer_bits::MapStorageBase<Node>* label = 0;
   625       for (typename NodeMaps::iterator it = _node_maps.begin();
   626 	   it != _node_maps.end(); ++it) {
   627         if (it->first == "label") {
   628 	  label = it->second;
   629 	  break;
   630 	}
   631       }
   632 
   633       *_os << "@nodes";
   634       if (!_nodes_caption.empty()) {
   635 	_writer_bits::writeToken(*_os << ' ', _nodes_caption);
   636       }
   637       *_os << std::endl;
   638 
   639       if (label == 0) {
   640 	*_os << "label" << '\t';
   641       }
   642       for (typename NodeMaps::iterator it = _node_maps.begin();
   643 	   it != _node_maps.end(); ++it) {
   644 	_writer_bits::writeToken(*_os, it->first) << '\t';
   645       }
   646       *_os << std::endl;
   647 
   648       std::vector<Node> nodes;
   649       for (NodeIt n(_digraph); n != INVALID; ++n) {
   650 	nodes.push_back(n);
   651       }
   652       
   653       if (label == 0) {
   654 	IdMap<Digraph, Node> id_map(_digraph);
   655 	_writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
   656 	std::sort(nodes.begin(), nodes.end(), id_less);
   657       } else {
   658 	label->sort(nodes);
   659       }
   660 
   661       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
   662 	Node n = nodes[i];
   663 	if (label == 0) {
   664 	  std::ostringstream os;
   665 	  os << _digraph.id(n);
   666 	  _writer_bits::writeToken(*_os, os.str());
   667 	  *_os << '\t';
   668 	  _node_index.insert(std::make_pair(n, os.str()));
   669 	}
   670 	for (typename NodeMaps::iterator it = _node_maps.begin();
   671 	     it != _node_maps.end(); ++it) {
   672 	  std::string value = it->second->get(n);
   673 	  _writer_bits::writeToken(*_os, value);
   674 	  if (it->first == "label") {
   675 	    _node_index.insert(std::make_pair(n, value));
   676 	  }
   677 	  *_os << '\t';
   678 	}
   679 	*_os << std::endl;
   680       }
   681     }
   682 
   683     void createNodeIndex() {
   684       _writer_bits::MapStorageBase<Node>* label = 0;
   685       for (typename NodeMaps::iterator it = _node_maps.begin();
   686 	   it != _node_maps.end(); ++it) {
   687         if (it->first == "label") {
   688 	  label = it->second;
   689 	  break;
   690 	}
   691       }
   692 
   693       if (label == 0) {
   694 	for (NodeIt n(_digraph); n != INVALID; ++n) {
   695 	  std::ostringstream os;
   696 	  os << _digraph.id(n);
   697 	  _node_index.insert(std::make_pair(n, os.str()));	  
   698 	}	
   699       } else {
   700 	for (NodeIt n(_digraph); n != INVALID; ++n) {
   701 	  std::string value = label->get(n);	  
   702 	  _node_index.insert(std::make_pair(n, value));
   703 	}
   704       }
   705     }
   706 
   707     void writeArcs() {
   708       _writer_bits::MapStorageBase<Arc>* label = 0;
   709       for (typename ArcMaps::iterator it = _arc_maps.begin();
   710 	   it != _arc_maps.end(); ++it) {
   711         if (it->first == "label") {
   712 	  label = it->second;
   713 	  break;
   714 	}
   715       }
   716 
   717       *_os << "@arcs";
   718       if (!_arcs_caption.empty()) {
   719 	_writer_bits::writeToken(*_os << ' ', _arcs_caption);
   720       }
   721       *_os << std::endl;
   722 
   723       *_os << '\t' << '\t';
   724       if (label == 0) {
   725 	*_os << "label" << '\t';
   726       }
   727       for (typename ArcMaps::iterator it = _arc_maps.begin();
   728 	   it != _arc_maps.end(); ++it) {
   729 	_writer_bits::writeToken(*_os, it->first) << '\t';
   730       }
   731       *_os << std::endl;
   732 
   733       std::vector<Arc> arcs;
   734       for (ArcIt n(_digraph); n != INVALID; ++n) {
   735 	arcs.push_back(n);
   736       }
   737       
   738       if (label == 0) {
   739 	IdMap<Digraph, Arc> id_map(_digraph);
   740 	_writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
   741 	std::sort(arcs.begin(), arcs.end(), id_less);
   742       } else {
   743 	label->sort(arcs);
   744       }
   745 
   746       for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
   747 	Arc a = arcs[i];
   748 	_writer_bits::writeToken(*_os, _node_index.
   749 				 find(_digraph.source(a))->second);
   750 	*_os << '\t';
   751 	_writer_bits::writeToken(*_os, _node_index.
   752 				 find(_digraph.target(a))->second);
   753 	*_os << '\t';
   754 	if (label == 0) {
   755 	  std::ostringstream os;
   756 	  os << _digraph.id(a);
   757 	  _writer_bits::writeToken(*_os, os.str());
   758 	  *_os << '\t';
   759 	  _arc_index.insert(std::make_pair(a, os.str()));
   760 	}
   761 	for (typename ArcMaps::iterator it = _arc_maps.begin();
   762 	     it != _arc_maps.end(); ++it) {
   763 	  std::string value = it->second->get(a);
   764 	  _writer_bits::writeToken(*_os, value);
   765 	  if (it->first == "label") {
   766 	    _arc_index.insert(std::make_pair(a, value));
   767 	  }
   768 	  *_os << '\t';
   769 	}
   770 	*_os << std::endl;
   771       }
   772     }
   773 
   774     void createArcIndex() {
   775       _writer_bits::MapStorageBase<Arc>* label = 0;
   776       for (typename ArcMaps::iterator it = _arc_maps.begin();
   777 	   it != _arc_maps.end(); ++it) {
   778         if (it->first == "label") {
   779 	  label = it->second;
   780 	  break;
   781 	}
   782       }
   783 
   784       if (label == 0) {
   785 	for (ArcIt a(_digraph); a != INVALID; ++a) {
   786 	  std::ostringstream os;
   787 	  os << _digraph.id(a);
   788 	  _arc_index.insert(std::make_pair(a, os.str()));	  
   789 	}	
   790       } else {
   791 	for (ArcIt a(_digraph); a != INVALID; ++a) {
   792 	  std::string value = label->get(a);	  
   793 	  _arc_index.insert(std::make_pair(a, value));
   794 	}
   795       }
   796     }
   797 
   798     void writeAttributes() {
   799       if (_attributes.empty()) return;
   800       *_os << "@attributes";
   801       if (!_attributes_caption.empty()) {
   802 	_writer_bits::writeToken(*_os << ' ', _attributes_caption);
   803       }
   804       *_os << std::endl;
   805       for (typename Attributes::iterator it = _attributes.begin();
   806 	   it != _attributes.end(); ++it) {
   807 	_writer_bits::writeToken(*_os, it->first) << ' ';
   808 	_writer_bits::writeToken(*_os, it->second->get());
   809 	*_os << std::endl;
   810       }
   811     }
   812     
   813   public:
   814     
   815     /// \name Execution of the writer    
   816     /// @{
   817 
   818     /// \brief Start the batch processing
   819     ///
   820     /// This function starts the batch processing
   821     void run() {
   822       if (!_skip_nodes) {
   823 	writeNodes();
   824       } else {
   825 	createNodeIndex();
   826       }
   827       if (!_skip_arcs) {      
   828 	writeArcs();
   829       } else {
   830 	createArcIndex();
   831       }
   832       writeAttributes();
   833     }
   834 
   835     /// \brief Gives back the stream of the writer
   836     ///
   837     /// Gives back the stream of the writer
   838     std::ostream& ostream() {
   839       return *_os;
   840     }
   841 
   842     /// @}
   843   };
   844 
   845   /// \relates DigraphWriter
   846   template <typename Digraph>
   847   DigraphWriter<Digraph> digraphWriter(std::ostream& os, Digraph& digraph) {
   848     DigraphWriter<Digraph> tmp(os, digraph);
   849     return tmp;
   850   }
   851 
   852   /// \relates DigraphWriter
   853   template <typename Digraph>
   854   DigraphWriter<Digraph> digraphWriter(const std::string& fn, 
   855 				       Digraph& digraph) {
   856     DigraphWriter<Digraph> tmp(fn, digraph);
   857     return tmp;
   858   }
   859 
   860   /// \relates DigraphWriter
   861   template <typename Digraph>
   862   DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
   863     DigraphWriter<Digraph> tmp(fn, digraph);
   864     return tmp;
   865   }
   866 
   867   /// \ingroup lemon_io
   868   ///  
   869   /// \brief LGF writer for directed graphs
   870   ///
   871   /// This utility writes an \ref lgf-format "LGF" file.
   872   template <typename _Graph>
   873   class GraphWriter {
   874   public:
   875 
   876     typedef _Graph Graph;
   877     TEMPLATE_GRAPH_TYPEDEFS(Graph);
   878     
   879   private:
   880 
   881 
   882     std::ostream* _os;
   883     bool local_os;
   884 
   885     Graph& _graph;
   886 
   887     std::string _nodes_caption;
   888     std::string _edges_caption;
   889     std::string _attributes_caption;
   890     
   891     typedef std::map<Node, std::string> NodeIndex;
   892     NodeIndex _node_index;
   893     typedef std::map<Edge, std::string> EdgeIndex;
   894     EdgeIndex _edge_index;
   895 
   896     typedef std::vector<std::pair<std::string, 
   897       _writer_bits::MapStorageBase<Node>* > > NodeMaps;    
   898     NodeMaps _node_maps; 
   899 
   900     typedef std::vector<std::pair<std::string, 
   901       _writer_bits::MapStorageBase<Edge>* > >EdgeMaps;
   902     EdgeMaps _edge_maps;
   903 
   904     typedef std::vector<std::pair<std::string, 
   905       _writer_bits::ValueStorageBase*> > Attributes;
   906     Attributes _attributes;
   907 
   908     bool _skip_nodes;
   909     bool _skip_edges;
   910 
   911   public:
   912 
   913     /// \brief Constructor
   914     ///
   915     /// Construct a directed graph writer, which writes to the given
   916     /// output stream.
   917     GraphWriter(std::ostream& is, Graph& graph) 
   918       : _os(&is), local_os(false), _graph(graph),
   919 	_skip_nodes(false), _skip_edges(false) {}
   920 
   921     /// \brief Constructor
   922     ///
   923     /// Construct a directed graph writer, which writes to the given
   924     /// output file.
   925     GraphWriter(const std::string& fn, Graph& graph) 
   926       : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),
   927 	_skip_nodes(false), _skip_edges(false) {}
   928 
   929     /// \brief Constructor
   930     ///
   931     /// Construct a directed graph writer, which writes to the given
   932     /// output file.
   933     GraphWriter(const char* fn, Graph& graph) 
   934       : _os(new std::ofstream(fn)), local_os(true), _graph(graph),
   935 	_skip_nodes(false), _skip_edges(false) {}
   936 
   937     /// \brief Copy constructor
   938     ///
   939     /// The copy constructor transfers all data from the other writer,
   940     /// therefore the copied writer will not be usable more. 
   941     GraphWriter(GraphWriter& other) 
   942       : _os(other._os), local_os(other.local_os), _graph(other._graph),
   943 	_skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
   944 
   945       other._os = 0;
   946       other.local_os = false;
   947 
   948       _node_index.swap(other._node_index);
   949       _edge_index.swap(other._edge_index);
   950 
   951       _node_maps.swap(other._node_maps);
   952       _edge_maps.swap(other._edge_maps);
   953       _attributes.swap(other._attributes);
   954 
   955       _nodes_caption = other._nodes_caption;
   956       _edges_caption = other._edges_caption;
   957       _attributes_caption = other._attributes_caption;
   958     }
   959 
   960     /// \brief Destructor
   961     ~GraphWriter() {
   962       for (typename NodeMaps::iterator it = _node_maps.begin(); 
   963 	   it != _node_maps.end(); ++it) {
   964 	delete it->second;
   965       }
   966 
   967       for (typename EdgeMaps::iterator it = _edge_maps.begin(); 
   968 	   it != _edge_maps.end(); ++it) {
   969 	delete it->second;
   970       }
   971 
   972       for (typename Attributes::iterator it = _attributes.begin(); 
   973 	   it != _attributes.end(); ++it) {
   974 	delete it->second;
   975       }
   976 
   977       if (local_os) {
   978 	delete _os;
   979       }
   980     }
   981 
   982   private:
   983     
   984     GraphWriter& operator=(const GraphWriter&);
   985 
   986   public:
   987 
   988     /// \name Writing rules
   989     /// @{
   990     
   991     /// \brief Node map reading rule
   992     ///
   993     /// Add a node map reading rule to the writer.
   994     template <typename Map>
   995     GraphWriter& nodeMap(const std::string& caption, const Map& map) {
   996       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   997       _writer_bits::MapStorageBase<Node>* storage = 
   998 	new _writer_bits::MapStorage<Node, Map>(map);
   999       _node_maps.push_back(std::make_pair(caption, storage));
  1000       return *this;
  1001     }
  1002 
  1003     /// \brief Node map writing rule
  1004     ///
  1005     /// Add a node map writing rule with specialized converter to the
  1006     /// writer.
  1007     template <typename Map, typename Converter>
  1008     GraphWriter& nodeMap(const std::string& caption, const Map& map, 
  1009 			   const Converter& converter = Converter()) {
  1010       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1011       _writer_bits::MapStorageBase<Node>* storage = 
  1012 	new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
  1013       _node_maps.push_back(std::make_pair(caption, storage));
  1014       return *this;
  1015     }
  1016 
  1017     /// \brief Edge map writing rule
  1018     ///
  1019     /// Add an edge map writing rule to the writer.
  1020     template <typename Map>
  1021     GraphWriter& edgeMap(const std::string& caption, const Map& map) {
  1022       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1023       _writer_bits::MapStorageBase<Edge>* storage = 
  1024 	new _writer_bits::MapStorage<Edge, Map>(map);
  1025       _edge_maps.push_back(std::make_pair(caption, storage));
  1026       return *this;
  1027     }
  1028 
  1029     /// \brief Edge map writing rule
  1030     ///
  1031     /// Add an edge map writing rule with specialized converter to the
  1032     /// writer.
  1033     template <typename Map, typename Converter>
  1034     GraphWriter& edgeMap(const std::string& caption, const Map& map, 
  1035 			  const Converter& converter = Converter()) {
  1036       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1037       _writer_bits::MapStorageBase<Edge>* storage = 
  1038 	new _writer_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1039       _edge_maps.push_back(std::make_pair(caption, storage));
  1040       return *this;
  1041     }
  1042 
  1043     /// \brief Arc map writing rule
  1044     ///
  1045     /// Add an arc map writing rule to the writer.
  1046     template <typename Map>
  1047     GraphWriter& arcMap(const std::string& caption, const Map& map) {
  1048       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1049       _writer_bits::MapStorageBase<Edge>* forward_storage = 
  1050 	new _writer_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1051       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1052       _writer_bits::MapStorageBase<Edge>* backward_storage = 
  1053 	new _writer_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1054       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1055       return *this;
  1056     }
  1057 
  1058     /// \brief Arc map writing rule
  1059     ///
  1060     /// Add an arc map writing rule with specialized converter to the
  1061     /// writer.
  1062     template <typename Map, typename Converter>
  1063     GraphWriter& arcMap(const std::string& caption, const Map& map, 
  1064 			  const Converter& converter = Converter()) {
  1065       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
  1066       _writer_bits::MapStorageBase<Edge>* forward_storage = 
  1067 	new _writer_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1068 	(_graph, map, converter);
  1069       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1070       _writer_bits::MapStorageBase<Edge>* backward_storage = 
  1071 	new _writer_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1072 	(_graph, map, converter);
  1073       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1074       return *this;
  1075     }
  1076 
  1077     /// \brief Attribute writing rule
  1078     ///
  1079     /// Add an attribute writing rule to the writer.
  1080     template <typename Value>
  1081     GraphWriter& attribute(const std::string& caption, const Value& value) {
  1082       _writer_bits::ValueStorageBase* storage = 
  1083 	new _writer_bits::ValueStorage<Value>(value);
  1084       _attributes.push_back(std::make_pair(caption, storage));
  1085       return *this;
  1086     }
  1087 
  1088     /// \brief Attribute writing rule
  1089     ///
  1090     /// Add an attribute writing rule with specialized converter to the
  1091     /// writer.
  1092     template <typename Value, typename Converter>
  1093     GraphWriter& attribute(const std::string& caption, const Value& value, 
  1094 			     const Converter& converter = Converter()) {
  1095       _writer_bits::ValueStorageBase* storage = 
  1096 	new _writer_bits::ValueStorage<Value, Converter>(value, converter);
  1097       _attributes.push_back(std::make_pair(caption, storage));
  1098       return *this;
  1099     }
  1100 
  1101     /// \brief Node writing rule
  1102     ///
  1103     /// Add a node writing rule to the writer.
  1104     GraphWriter& node(const std::string& caption, const Node& node) {
  1105       typedef _writer_bits::MapLookUpConverter<Node> Converter;
  1106       Converter converter(_node_index);
  1107       _writer_bits::ValueStorageBase* storage = 
  1108 	new _writer_bits::ValueStorage<Node, Converter>(node, converter);
  1109       _attributes.push_back(std::make_pair(caption, storage));
  1110       return *this;
  1111     }
  1112 
  1113     /// \brief Edge writing rule
  1114     ///
  1115     /// Add an edge writing rule to writer.
  1116     GraphWriter& edge(const std::string& caption, const Edge& edge) {
  1117       typedef _writer_bits::MapLookUpConverter<Edge> Converter;
  1118       Converter converter(_edge_index);
  1119       _writer_bits::ValueStorageBase* storage = 
  1120 	new _writer_bits::ValueStorage<Edge, Converter>(edge, converter);
  1121       _attributes.push_back(std::make_pair(caption, storage));
  1122       return *this;
  1123     }
  1124 
  1125     /// \brief Arc writing rule
  1126     ///
  1127     /// Add an arc writing rule to writer.
  1128     GraphWriter& arc(const std::string& caption, const Arc& arc) {
  1129       typedef _writer_bits::GraphArcLookUpConverter<Graph> Converter;
  1130       Converter converter(_graph, _edge_index);
  1131       _writer_bits::ValueStorageBase* storage = 
  1132 	new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
  1133       _attributes.push_back(std::make_pair(caption, storage));
  1134       return *this;
  1135     }
  1136 
  1137     /// \name Select section by name
  1138     /// @{
  1139 
  1140     /// \brief Set \c \@nodes section to be read
  1141     ///
  1142     /// Set \c \@nodes section to be read
  1143     GraphWriter& nodes(const std::string& caption) {
  1144       _nodes_caption = caption;
  1145       return *this;
  1146     }
  1147 
  1148     /// \brief Set \c \@edges section to be read
  1149     ///
  1150     /// Set \c \@edges section to be read
  1151     GraphWriter& edges(const std::string& caption) {
  1152       _edges_caption = caption;
  1153       return *this;
  1154     }
  1155 
  1156     /// \brief Set \c \@attributes section to be read
  1157     ///
  1158     /// Set \c \@attributes section to be read
  1159     GraphWriter& attributes(const std::string& caption) {
  1160       _attributes_caption = caption;
  1161       return *this;
  1162     }
  1163 
  1164     /// \name Skipping section
  1165     /// @{
  1166 
  1167     /// \brief Skip writing the node set
  1168     ///
  1169     /// The \c \@nodes section will be not written to the stream.
  1170     GraphWriter& skipNodes() {
  1171       LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
  1172       _skip_nodes = true;
  1173       return *this;
  1174     }
  1175 
  1176     /// \brief Skip writing edge set
  1177     ///
  1178     /// The \c \@edges section will be not written to the stream.
  1179     GraphWriter& skipEdges() {
  1180       LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
  1181       _skip_edges = true;
  1182       return *this;
  1183     }
  1184 
  1185     /// @}
  1186 
  1187   private:
  1188 
  1189     void writeNodes() {
  1190       _writer_bits::MapStorageBase<Node>* label = 0;
  1191       for (typename NodeMaps::iterator it = _node_maps.begin();
  1192 	   it != _node_maps.end(); ++it) {
  1193         if (it->first == "label") {
  1194 	  label = it->second;
  1195 	  break;
  1196 	}
  1197       }
  1198 
  1199       *_os << "@nodes";
  1200       if (!_nodes_caption.empty()) {
  1201 	_writer_bits::writeToken(*_os << ' ', _nodes_caption);
  1202       }
  1203       *_os << std::endl;
  1204 
  1205       if (label == 0) {
  1206 	*_os << "label" << '\t';
  1207       }
  1208       for (typename NodeMaps::iterator it = _node_maps.begin();
  1209 	   it != _node_maps.end(); ++it) {
  1210 	_writer_bits::writeToken(*_os, it->first) << '\t';
  1211       }
  1212       *_os << std::endl;
  1213 
  1214       std::vector<Node> nodes;
  1215       for (NodeIt n(_graph); n != INVALID; ++n) {
  1216 	nodes.push_back(n);
  1217       }
  1218       
  1219       if (label == 0) {
  1220 	IdMap<Graph, Node> id_map(_graph);
  1221 	_writer_bits::MapLess<IdMap<Graph, Node> > id_less(id_map);
  1222 	std::sort(nodes.begin(), nodes.end(), id_less);
  1223       } else {
  1224 	label->sort(nodes);
  1225       }
  1226 
  1227       for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
  1228 	Node n = nodes[i];
  1229 	if (label == 0) {
  1230 	  std::ostringstream os;
  1231 	  os << _graph.id(n);
  1232 	  _writer_bits::writeToken(*_os, os.str());
  1233 	  *_os << '\t';
  1234 	  _node_index.insert(std::make_pair(n, os.str()));
  1235 	}
  1236 	for (typename NodeMaps::iterator it = _node_maps.begin();
  1237 	     it != _node_maps.end(); ++it) {
  1238 	  std::string value = it->second->get(n);
  1239 	  _writer_bits::writeToken(*_os, value);
  1240 	  if (it->first == "label") {
  1241 	    _node_index.insert(std::make_pair(n, value));
  1242 	  }
  1243 	  *_os << '\t';
  1244 	}
  1245 	*_os << std::endl;
  1246       }
  1247     }
  1248 
  1249     void createNodeIndex() {
  1250       _writer_bits::MapStorageBase<Node>* label = 0;
  1251       for (typename NodeMaps::iterator it = _node_maps.begin();
  1252 	   it != _node_maps.end(); ++it) {
  1253         if (it->first == "label") {
  1254 	  label = it->second;
  1255 	  break;
  1256 	}
  1257       }
  1258 
  1259       if (label == 0) {
  1260 	for (NodeIt n(_graph); n != INVALID; ++n) {
  1261 	  std::ostringstream os;
  1262 	  os << _graph.id(n);
  1263 	  _node_index.insert(std::make_pair(n, os.str()));	  
  1264 	}	
  1265       } else {
  1266 	for (NodeIt n(_graph); n != INVALID; ++n) {
  1267 	  std::string value = label->get(n);	  
  1268 	  _node_index.insert(std::make_pair(n, value));
  1269 	}
  1270       }
  1271     }
  1272 
  1273     void writeEdges() {
  1274       _writer_bits::MapStorageBase<Edge>* label = 0;
  1275       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1276 	   it != _edge_maps.end(); ++it) {
  1277         if (it->first == "label") {
  1278 	  label = it->second;
  1279 	  break;
  1280 	}
  1281       }
  1282 
  1283       *_os << "@edges";
  1284       if (!_edges_caption.empty()) {
  1285 	_writer_bits::writeToken(*_os << ' ', _edges_caption);
  1286       }
  1287       *_os << std::endl;
  1288 
  1289       *_os << '\t' << '\t';
  1290       if (label == 0) {
  1291 	*_os << "label" << '\t';
  1292       }
  1293       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1294 	   it != _edge_maps.end(); ++it) {
  1295 	_writer_bits::writeToken(*_os, it->first) << '\t';
  1296       }
  1297       *_os << std::endl;
  1298 
  1299       std::vector<Edge> edges;
  1300       for (EdgeIt n(_graph); n != INVALID; ++n) {
  1301 	edges.push_back(n);
  1302       }
  1303       
  1304       if (label == 0) {
  1305 	IdMap<Graph, Edge> id_map(_graph);
  1306 	_writer_bits::MapLess<IdMap<Graph, Edge> > id_less(id_map);
  1307 	std::sort(edges.begin(), edges.end(), id_less);
  1308       } else {
  1309 	label->sort(edges);
  1310       }
  1311 
  1312       for (int i = 0; i < static_cast<int>(edges.size()); ++i) {
  1313 	Edge e = edges[i];
  1314 	_writer_bits::writeToken(*_os, _node_index.
  1315 				 find(_graph.u(e))->second);
  1316 	*_os << '\t';
  1317 	_writer_bits::writeToken(*_os, _node_index.
  1318 				 find(_graph.v(e))->second);
  1319 	*_os << '\t';
  1320 	if (label == 0) {
  1321 	  std::ostringstream os;
  1322 	  os << _graph.id(e);
  1323 	  _writer_bits::writeToken(*_os, os.str());
  1324 	  *_os << '\t';
  1325 	  _edge_index.insert(std::make_pair(e, os.str()));
  1326 	}
  1327 	for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1328 	     it != _edge_maps.end(); ++it) {
  1329 	  std::string value = it->second->get(e);
  1330 	  _writer_bits::writeToken(*_os, value);
  1331 	  if (it->first == "label") {
  1332 	    _edge_index.insert(std::make_pair(e, value));
  1333 	  }
  1334 	  *_os << '\t';
  1335 	}
  1336 	*_os << std::endl;
  1337       }
  1338     }
  1339 
  1340     void createEdgeIndex() {
  1341       _writer_bits::MapStorageBase<Edge>* label = 0;
  1342       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1343 	   it != _edge_maps.end(); ++it) {
  1344         if (it->first == "label") {
  1345 	  label = it->second;
  1346 	  break;
  1347 	}
  1348       }
  1349 
  1350       if (label == 0) {
  1351 	for (EdgeIt e(_graph); e != INVALID; ++e) {
  1352 	  std::ostringstream os;
  1353 	  os << _graph.id(e);
  1354 	  _edge_index.insert(std::make_pair(e, os.str()));	  
  1355 	}	
  1356       } else {
  1357 	for (EdgeIt e(_graph); e != INVALID; ++e) {
  1358 	  std::string value = label->get(e);	  
  1359 	  _edge_index.insert(std::make_pair(e, value));
  1360 	}
  1361       }
  1362     }
  1363 
  1364     void writeAttributes() {
  1365       if (_attributes.empty()) return;
  1366       *_os << "@attributes";
  1367       if (!_attributes_caption.empty()) {
  1368 	_writer_bits::writeToken(*_os << ' ', _attributes_caption);
  1369       }
  1370       *_os << std::endl;
  1371       for (typename Attributes::iterator it = _attributes.begin();
  1372 	   it != _attributes.end(); ++it) {
  1373 	_writer_bits::writeToken(*_os, it->first) << ' ';
  1374 	_writer_bits::writeToken(*_os, it->second->get());
  1375 	*_os << std::endl;
  1376       }
  1377     }
  1378     
  1379   public:
  1380     
  1381     /// \name Execution of the writer    
  1382     /// @{
  1383 
  1384     /// \brief Start the batch processing
  1385     ///
  1386     /// This function starts the batch processing
  1387     void run() {
  1388       if (!_skip_nodes) {
  1389 	writeNodes();
  1390       } else {
  1391 	createNodeIndex();
  1392       }
  1393       if (!_skip_edges) {      
  1394 	writeEdges();
  1395       } else {
  1396 	createEdgeIndex();
  1397       }
  1398       writeAttributes();
  1399     }
  1400 
  1401     /// \brief Gives back the stream of the writer
  1402     ///
  1403     /// Gives back the stream of the writer
  1404     std::ostream& ostream() {
  1405       return *_os;
  1406     }
  1407 
  1408     /// @}
  1409   };
  1410 
  1411   /// \relates GraphWriter
  1412   template <typename Graph>
  1413   GraphWriter<Graph> graphWriter(std::ostream& os, Graph& graph) {
  1414     GraphWriter<Graph> tmp(os, graph);
  1415     return tmp;
  1416   }
  1417 
  1418   /// \relates GraphWriter
  1419   template <typename Graph>
  1420   GraphWriter<Graph> graphWriter(const std::string& fn, Graph& graph) {
  1421     GraphWriter<Graph> tmp(fn, graph);
  1422     return tmp;
  1423   }
  1424 
  1425   /// \relates GraphWriter
  1426   template <typename Graph>
  1427   GraphWriter<Graph> graphWriter(const char* fn, Graph& graph) {
  1428     GraphWriter<Graph> tmp(fn, graph);
  1429     return tmp;
  1430   }
  1431 }
  1432 
  1433 #endif