lemon/lgf_reader.h
author Peter Kovacs <kpeter@inf.elte.hu>
Mon, 07 Jul 2008 18:03:46 +0200
changeset 195 aa45ff44fcf3
parent 190 1e6af6f0843c
child 197 5893bacaa720
permissions -rw-r--r--
Add lgf_writer.h to Makefile.am (ticket #112)
     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 \ref lgf-format "Lemon Graph Format" reader.
    22 
    23 
    24 #ifndef LEMON_LGF_READER_H
    25 #define LEMON_LGF_READER_H
    26 
    27 #include <iostream>
    28 #include <fstream>
    29 #include <sstream>
    30 
    31 #include <set>
    32 #include <map>
    33 
    34 #include <lemon/assert.h>
    35 #include <lemon/graph_utils.h>
    36 
    37 #include <lemon/lgf_writer.h>
    38 
    39 #include <lemon/concept_check.h>
    40 #include <lemon/concepts/maps.h>
    41 
    42 namespace lemon {
    43 
    44   namespace _reader_bits {
    45 
    46     template <typename Value>
    47     struct DefaultConverter {
    48       Value operator()(const std::string& str) {
    49 	std::istringstream is(str);
    50 	Value value;
    51 	is >> value;
    52 
    53 	char c;
    54 	if (is >> std::ws >> c) {
    55 	  throw DataFormatError("Remaining characters in token");
    56 	}
    57 	return value;
    58       }
    59     };
    60 
    61     template <>
    62     struct DefaultConverter<std::string> {
    63       std::string operator()(const std::string& str) {
    64 	return str;
    65       }
    66     };
    67 
    68     template <typename _Item>    
    69     class MapStorageBase {
    70     public:
    71       typedef _Item Item;
    72 
    73     public:
    74       MapStorageBase() {}
    75       virtual ~MapStorageBase() {}
    76 
    77       virtual void set(const Item& item, const std::string& value) = 0;
    78 
    79     };
    80 
    81     template <typename _Item, typename _Map, 
    82 	      typename _Converter = DefaultConverter<typename _Map::Value> >
    83     class MapStorage : public MapStorageBase<_Item> {
    84     public:
    85       typedef _Map Map;
    86       typedef _Converter Converter;
    87       typedef _Item Item;
    88       
    89     private:
    90       Map& _map;
    91       Converter _converter;
    92 
    93     public:
    94       MapStorage(Map& map, const Converter& converter = Converter()) 
    95 	: _map(map), _converter(converter) {}
    96       virtual ~MapStorage() {}
    97 
    98       virtual void set(const Item& item ,const std::string& value) {
    99 	_map.set(item, _converter(value));
   100       }
   101     };
   102 
   103     template <typename _Graph, bool _dir, typename _Map, 
   104 	      typename _Converter = DefaultConverter<typename _Map::Value> >
   105     class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
   106     public:
   107       typedef _Map Map;
   108       typedef _Converter Converter;
   109       typedef _Graph Graph;
   110       typedef typename Graph::Edge Item;
   111       static const bool dir = _dir;
   112       
   113     private:
   114       const Graph& _graph;
   115       Map& _map;
   116       Converter _converter;
   117 
   118     public:
   119       GraphArcMapStorage(const Graph& graph, Map& map, 
   120 			 const Converter& converter = Converter()) 
   121 	: _graph(graph), _map(map), _converter(converter) {}
   122       virtual ~GraphArcMapStorage() {}
   123 
   124       virtual void set(const Item& item ,const std::string& value) {
   125 	_map.set(_graph.direct(item, dir), _converter(value));
   126       }
   127     };
   128 
   129     class ValueStorageBase {
   130     public:
   131       ValueStorageBase() {}
   132       virtual ~ValueStorageBase() {}
   133 
   134       virtual void set(const std::string&) = 0;
   135     };
   136 
   137     template <typename _Value, typename _Converter = DefaultConverter<_Value> >
   138     class ValueStorage : public ValueStorageBase {
   139     public:
   140       typedef _Value Value;
   141       typedef _Converter Converter;
   142 
   143     private:
   144       Value& _value;
   145       Converter _converter;
   146 
   147     public:
   148       ValueStorage(Value& value, const Converter& converter = Converter())
   149  	: _value(value), _converter(converter) {}
   150 
   151       virtual void set(const std::string& value) {
   152 	_value = _converter(value);
   153       }
   154     };
   155 
   156     template <typename Value>
   157     struct MapLookUpConverter {
   158       const std::map<std::string, Value>& _map;
   159 
   160       MapLookUpConverter(const std::map<std::string, Value>& map)
   161         : _map(map) {}
   162 
   163       Value operator()(const std::string& str) {
   164         typename std::map<std::string, Value>::const_iterator it =
   165           _map.find(str);
   166         if (it == _map.end()) {
   167           std::ostringstream msg;
   168           msg << "Item not found: " << str;
   169           throw DataFormatError(msg.str().c_str());
   170         }
   171         return it->second;
   172       }
   173     };
   174 
   175     template <typename Graph>
   176     struct GraphArcLookUpConverter {
   177       const Graph& _graph;
   178       const std::map<std::string, typename Graph::Edge>& _map;
   179       
   180       GraphArcLookUpConverter(const Graph& graph, 
   181 			      const std::map<std::string,
   182 			                     typename Graph::Edge>& map) 
   183 	: _graph(graph), _map(map) {}
   184       
   185       typename Graph::Arc operator()(const std::string& str) {
   186 	if (str.empty() || (str[0] != '+' && str[0] != '-')) {
   187 	  throw DataFormatError("Item must start with '+' or '-'");
   188 	}
   189 	typename std::map<std::string, typename Graph::Edge>
   190 	  ::const_iterator it = _map.find(str.substr(1));
   191 	if (it == _map.end()) {
   192 	  throw DataFormatError("Item not found");
   193 	}
   194 	return _graph.direct(it->second, str[0] == '+');
   195       }
   196     };
   197 
   198     bool isWhiteSpace(char c) {
   199       return c == ' ' || c == '\t' || c == '\v' || 
   200         c == '\n' || c == '\r' || c == '\f'; 
   201     }
   202     
   203     bool isOct(char c) {
   204       return '0' <= c && c <='7'; 
   205     }
   206     
   207     int valueOct(char c) {
   208       LEMON_ASSERT(isOct(c), "The character is not octal.");
   209       return c - '0';
   210     }
   211 
   212     bool isHex(char c) {
   213       return ('0' <= c && c <= '9') || 
   214 	('a' <= c && c <= 'z') || 
   215 	('A' <= c && c <= 'Z'); 
   216     }
   217     
   218     int valueHex(char c) {
   219       LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
   220       if ('0' <= c && c <= '9') return c - '0';
   221       if ('a' <= c && c <= 'z') return c - 'a' + 10;
   222       return c - 'A' + 10;
   223     }
   224 
   225     bool isIdentifierFirstChar(char c) {
   226       return ('a' <= c && c <= 'z') ||
   227 	('A' <= c && c <= 'Z') || c == '_';
   228     }
   229 
   230     bool isIdentifierChar(char c) {
   231       return isIdentifierFirstChar(c) ||
   232 	('0' <= c && c <= '9');
   233     }
   234 
   235     char readEscape(std::istream& is) {
   236       char c;
   237       if (!is.get(c))
   238 	throw DataFormatError("Escape format error");
   239 
   240       switch (c) {
   241       case '\\':
   242 	return '\\';
   243       case '\"':
   244 	return '\"';
   245       case '\'':
   246 	return '\'';
   247       case '\?':
   248 	return '\?';
   249       case 'a':
   250 	return '\a';
   251       case 'b':
   252 	return '\b';
   253       case 'f':
   254 	return '\f';
   255       case 'n':
   256 	return '\n';
   257       case 'r':
   258 	return '\r';
   259       case 't':
   260 	return '\t';
   261       case 'v':
   262 	return '\v';
   263       case 'x':
   264 	{
   265 	  int code;
   266 	  if (!is.get(c) || !isHex(c)) 
   267 	    throw DataFormatError("Escape format error");
   268 	  else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
   269 	  else code = code * 16 + valueHex(c);
   270 	  return code;
   271 	}
   272       default:
   273 	{
   274 	  int code;
   275 	  if (!isOct(c)) 
   276 	    throw DataFormatError("Escape format error");
   277 	  else if (code = valueOct(c), !is.get(c) || !isOct(c)) 
   278 	    is.putback(c);
   279 	  else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 
   280 	    is.putback(c);
   281 	  else code = code * 8 + valueOct(c);
   282 	  return code;
   283 	}	      
   284       } 
   285     }
   286     
   287     std::istream& readToken(std::istream& is, std::string& str) {
   288       std::ostringstream os;
   289 
   290       char c;
   291       is >> std::ws;
   292       
   293       if (!is.get(c)) 
   294 	return is;
   295 
   296       if (c == '\"') {
   297 	while (is.get(c) && c != '\"') {
   298 	  if (c == '\\') 
   299 	    c = readEscape(is);
   300 	  os << c;
   301 	}
   302 	if (!is) 
   303 	  throw DataFormatError("Quoted format error");
   304       } else {
   305 	is.putback(c);
   306 	while (is.get(c) && !isWhiteSpace(c)) {
   307 	  if (c == '\\') 
   308 	    c = readEscape(is);
   309 	  os << c;
   310 	}
   311 	if (!is) {
   312 	  is.clear();
   313 	} else {
   314 	  is.putback(c);
   315 	}
   316       }
   317       str = os.str();
   318       return is;
   319     }
   320 
   321     class Section {
   322     public:
   323       virtual ~Section() {}
   324       virtual void process(std::istream& is, int& line_num) = 0;
   325     };
   326 
   327     template <typename Functor>
   328     class LineSection : public Section {
   329     private:
   330 
   331       Functor _functor;
   332 
   333     public:
   334       
   335       LineSection(const Functor& functor) : _functor(functor) {}
   336       virtual ~LineSection() {}
   337 
   338       virtual void process(std::istream& is, int& line_num) {
   339 	char c;
   340 	std::string line;
   341 	while (is.get(c) && c != '@') {
   342 	  if (c == '\n') {
   343 	    ++line_num;
   344 	  } else if (c == '#') {
   345 	    getline(is, line);
   346 	    ++line_num;
   347 	  } else if (!isWhiteSpace(c)) {
   348 	    is.putback(c);
   349 	    getline(is, line);
   350 	    _functor(line);
   351 	    ++line_num;
   352 	  }
   353 	}
   354 	if (is) is.putback(c);
   355 	else if (is.eof()) is.clear();
   356       }
   357     };
   358 
   359     template <typename Functor>
   360     class StreamSection : public Section {
   361     private:
   362 
   363       Functor _functor;
   364 
   365     public:
   366       
   367       StreamSection(const Functor& functor) : _functor(functor) {}
   368       virtual ~StreamSection() {} 
   369 
   370       virtual void process(std::istream& is, int& line_num) {
   371 	_functor(is, line_num);
   372 	char c;
   373 	std::string line;
   374 	while (is.get(c) && c != '@') {
   375 	  if (c == '\n') {
   376 	    ++line_num;
   377 	  } else if (!isWhiteSpace(c)) {
   378 	    getline(is, line);
   379 	    ++line_num;
   380 	  }
   381 	}
   382 	if (is) is.putback(c);
   383 	else if (is.eof()) is.clear();	
   384       }
   385     };
   386     
   387   }
   388 
   389   template <typename Digraph>
   390   class DigraphReader;
   391 
   392   template <typename Digraph>
   393   DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph);
   394 
   395   template <typename Digraph>
   396   DigraphReader<Digraph> digraphReader(const std::string& fn, Digraph& digraph);
   397 
   398   template <typename Digraph>
   399   DigraphReader<Digraph> digraphReader(const char *fn, Digraph& digraph);
   400 
   401   /// \ingroup lemon_io
   402   ///  
   403   /// \brief \ref lgf-format "LGF" reader for directed graphs
   404   ///
   405   /// This utility reads an \ref lgf-format "LGF" file.
   406   ///
   407   /// The reading method does a batch processing. The user creates a
   408   /// reader object, then various reading rules can be added to the
   409   /// reader, and eventually the reading is executed with the \c run()
   410   /// member function. A map reading rule can be added to the reader
   411   /// with the \c nodeMap() or \c arcMap() members. An optional
   412   /// converter parameter can also be added as a standard functor
   413   /// converting from \c std::string to the value type of the map. If it
   414   /// is set, it will determine how the tokens in the file should be
   415   /// converted to the value type of the map. If the functor is not set,
   416   /// then a default conversion will be used. One map can be read into
   417   /// multiple map objects at the same time. The \c attribute(), \c
   418   /// node() and \c arc() functions are used to add attribute reading
   419   /// rules.
   420   ///
   421   ///\code
   422   /// DigraphReader<Digraph>(std::cin, digraph).
   423   ///   nodeMap("coordinates", coord_map).
   424   ///   arcMap("capacity", cap_map).
   425   ///   node("source", src).
   426   ///   node("target", trg).
   427   ///   attribute("caption", caption).
   428   ///   run();
   429   ///\endcode
   430   ///
   431   /// By default the reader uses the first section in the file of the
   432   /// proper type. If a section has an optional name, then it can be
   433   /// selected for reading by giving an optional name parameter to the
   434   /// \c nodes(), \c arcs() or \c attributes() functions.
   435   ///
   436   /// The \c useNodes() and \c useArcs() functions are used to tell the reader
   437   /// that the nodes or arcs should not be constructed (added to the
   438   /// graph) during the reading, but instead the label map of the items
   439   /// are given as a parameter of these functions. An
   440   /// application of these functions is multipass reading, which is
   441   /// important if two \c \@arcs sections must be read from the
   442   /// file. In this case the first phase would read the node set and one
   443   /// of the arc sets, while the second phase would read the second arc
   444   /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
   445   /// The previously read label node map should be passed to the \c
   446   /// useNodes() functions. Another application of multipass reading when
   447   /// paths are given as a node map or an arc map. It is impossible to read this in
   448   /// a single pass, because the arcs are not constructed when the node
   449   /// maps are read.
   450   template <typename _Digraph>
   451   class DigraphReader {
   452   public:
   453 
   454     typedef _Digraph Digraph;
   455     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   456     
   457   private:
   458 
   459 
   460     std::istream* _is;
   461     bool local_is;
   462 
   463     Digraph& _digraph;
   464 
   465     std::string _nodes_caption;
   466     std::string _arcs_caption;
   467     std::string _attributes_caption;
   468 
   469     typedef std::map<std::string, Node> NodeIndex;
   470     NodeIndex _node_index;
   471     typedef std::map<std::string, Arc> ArcIndex;
   472     ArcIndex _arc_index;
   473     
   474     typedef std::vector<std::pair<std::string, 
   475       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
   476     NodeMaps _node_maps; 
   477 
   478     typedef std::vector<std::pair<std::string,
   479       _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
   480     ArcMaps _arc_maps;
   481 
   482     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
   483       Attributes;
   484     Attributes _attributes;
   485 
   486     bool _use_nodes;
   487     bool _use_arcs;
   488 
   489     bool _skip_nodes;
   490     bool _skip_arcs;
   491 
   492     int line_num;
   493     std::istringstream line;
   494 
   495   public:
   496 
   497     /// \brief Constructor
   498     ///
   499     /// Construct a directed graph reader, which reads from the given
   500     /// input stream.
   501     DigraphReader(std::istream& is, Digraph& digraph) 
   502       : _is(&is), local_is(false), _digraph(digraph),
   503 	_use_nodes(false), _use_arcs(false),
   504 	_skip_nodes(false), _skip_arcs(false) {}
   505 
   506     /// \brief Constructor
   507     ///
   508     /// Construct a directed graph reader, which reads from the given
   509     /// file.
   510     DigraphReader(const std::string& fn, Digraph& digraph) 
   511       : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
   512     	_use_nodes(false), _use_arcs(false),
   513 	_skip_nodes(false), _skip_arcs(false) {}
   514     
   515     /// \brief Constructor
   516     ///
   517     /// Construct a directed graph reader, which reads from the given
   518     /// file.
   519     DigraphReader(const char* fn, Digraph& digraph) 
   520       : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
   521     	_use_nodes(false), _use_arcs(false),
   522 	_skip_nodes(false), _skip_arcs(false) {}
   523 
   524     /// \brief Destructor
   525     ~DigraphReader() {
   526       for (typename NodeMaps::iterator it = _node_maps.begin(); 
   527 	   it != _node_maps.end(); ++it) {
   528 	delete it->second;
   529       }
   530 
   531       for (typename ArcMaps::iterator it = _arc_maps.begin(); 
   532 	   it != _arc_maps.end(); ++it) {
   533 	delete it->second;
   534       }
   535 
   536       for (typename Attributes::iterator it = _attributes.begin(); 
   537 	   it != _attributes.end(); ++it) {
   538 	delete it->second;
   539       }
   540 
   541       if (local_is) {
   542 	delete _is;
   543       }
   544 
   545     }
   546 
   547   private:
   548 
   549     friend DigraphReader<Digraph> digraphReader<>(std::istream& is, 
   550 						  Digraph& digraph);    
   551     friend DigraphReader<Digraph> digraphReader<>(const std::string& fn, 
   552 						  Digraph& digraph);   
   553     friend DigraphReader<Digraph> digraphReader<>(const char *fn, 
   554 						  Digraph& digraph);    
   555 
   556     DigraphReader(DigraphReader& other) 
   557       : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
   558 	_use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
   559 	_skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
   560 
   561       other._is = 0;
   562       other.local_is = false;
   563       
   564       _node_index.swap(other._node_index);
   565       _arc_index.swap(other._arc_index);
   566 
   567       _node_maps.swap(other._node_maps);
   568       _arc_maps.swap(other._arc_maps);
   569       _attributes.swap(other._attributes);
   570 
   571       _nodes_caption = other._nodes_caption;
   572       _arcs_caption = other._arcs_caption;
   573       _attributes_caption = other._attributes_caption;
   574 
   575     }
   576 
   577     DigraphReader& operator=(const DigraphReader&);
   578 
   579   public:
   580 
   581     /// \name Reading rules
   582     /// @{
   583     
   584     /// \brief Node map reading rule
   585     ///
   586     /// Add a node map reading rule to the reader.
   587     template <typename Map>
   588     DigraphReader& nodeMap(const std::string& caption, Map& map) {
   589       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
   590       _reader_bits::MapStorageBase<Node>* storage = 
   591 	new _reader_bits::MapStorage<Node, Map>(map);
   592       _node_maps.push_back(std::make_pair(caption, storage));
   593       return *this;
   594     }
   595 
   596     /// \brief Node map reading rule
   597     ///
   598     /// Add a node map reading rule with specialized converter to the
   599     /// reader.
   600     template <typename Map, typename Converter>
   601     DigraphReader& nodeMap(const std::string& caption, Map& map, 
   602 			   const Converter& converter = Converter()) {
   603       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
   604       _reader_bits::MapStorageBase<Node>* storage = 
   605 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
   606       _node_maps.push_back(std::make_pair(caption, storage));
   607       return *this;
   608     }
   609 
   610     /// \brief Arc map reading rule
   611     ///
   612     /// Add an arc map reading rule to the reader.
   613     template <typename Map>
   614     DigraphReader& arcMap(const std::string& caption, Map& map) {
   615       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
   616       _reader_bits::MapStorageBase<Arc>* storage = 
   617 	new _reader_bits::MapStorage<Arc, Map>(map);
   618       _arc_maps.push_back(std::make_pair(caption, storage));
   619       return *this;
   620     }
   621 
   622     /// \brief Arc map reading rule
   623     ///
   624     /// Add an arc map reading rule with specialized converter to the
   625     /// reader.
   626     template <typename Map, typename Converter>
   627     DigraphReader& arcMap(const std::string& caption, Map& map, 
   628 			  const Converter& converter = Converter()) {
   629       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
   630       _reader_bits::MapStorageBase<Arc>* storage = 
   631 	new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
   632       _arc_maps.push_back(std::make_pair(caption, storage));
   633       return *this;
   634     }
   635 
   636     /// \brief Attribute reading rule
   637     ///
   638     /// Add an attribute reading rule to the reader.
   639     template <typename Value>
   640     DigraphReader& attribute(const std::string& caption, Value& value) {
   641       _reader_bits::ValueStorageBase* storage = 
   642 	new _reader_bits::ValueStorage<Value>(value);
   643       _attributes.insert(std::make_pair(caption, storage));
   644       return *this;
   645     }
   646 
   647     /// \brief Attribute reading rule
   648     ///
   649     /// Add an attribute reading rule with specialized converter to the
   650     /// reader.
   651     template <typename Value, typename Converter>
   652     DigraphReader& attribute(const std::string& caption, Value& value, 
   653 			     const Converter& converter = Converter()) {
   654       _reader_bits::ValueStorageBase* storage = 
   655 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
   656       _attributes.insert(std::make_pair(caption, storage));
   657       return *this;
   658     }
   659 
   660     /// \brief Node reading rule
   661     ///
   662     /// Add a node reading rule to reader.
   663     DigraphReader& node(const std::string& caption, Node& node) {
   664       typedef _reader_bits::MapLookUpConverter<Node> Converter;
   665       Converter converter(_node_index);
   666       _reader_bits::ValueStorageBase* storage = 
   667 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
   668       _attributes.insert(std::make_pair(caption, storage));
   669       return *this;
   670     }
   671 
   672     /// \brief Arc reading rule
   673     ///
   674     /// Add an arc reading rule to reader.
   675     DigraphReader& arc(const std::string& caption, Arc& arc) {
   676       typedef _reader_bits::MapLookUpConverter<Arc> Converter;
   677       Converter converter(_arc_index);
   678       _reader_bits::ValueStorageBase* storage = 
   679 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
   680       _attributes.insert(std::make_pair(caption, storage));
   681       return *this;
   682     }
   683 
   684     /// @}
   685 
   686     /// \name Select section by name
   687     /// @{
   688 
   689     /// \brief Set \c \@nodes section to be read
   690     ///
   691     /// Set \c \@nodes section to be read
   692     DigraphReader& nodes(const std::string& caption) {
   693       _nodes_caption = caption;
   694       return *this;
   695     }
   696 
   697     /// \brief Set \c \@arcs section to be read
   698     ///
   699     /// Set \c \@arcs section to be read
   700     DigraphReader& arcs(const std::string& caption) {
   701       _arcs_caption = caption;
   702       return *this;
   703     }
   704 
   705     /// \brief Set \c \@attributes section to be read
   706     ///
   707     /// Set \c \@attributes section to be read
   708     DigraphReader& attributes(const std::string& caption) {
   709       _attributes_caption = caption;
   710       return *this;
   711     }
   712 
   713     /// @}
   714 
   715     /// \name Using previously constructed node or arc set
   716     /// @{
   717 
   718     /// \brief Use previously constructed node set
   719     ///
   720     /// Use previously constructed node set, and specify the node
   721     /// label map.
   722     template <typename Map>
   723     DigraphReader& useNodes(const Map& map) {
   724       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   725       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
   726       _use_nodes = true;
   727       _writer_bits::DefaultConverter<typename Map::Value> converter;
   728       for (NodeIt n(_digraph); n != INVALID; ++n) {
   729 	_node_index.insert(std::make_pair(converter(map[n]), n));
   730       }
   731       return *this;
   732     }
   733 
   734     /// \brief Use previously constructed node set
   735     ///
   736     /// Use previously constructed node set, and specify the node
   737     /// label map and a functor which converts the label map values to
   738     /// \c std::string.
   739     template <typename Map, typename Converter>
   740     DigraphReader& useNodes(const Map& map, 
   741 			    const Converter& converter = Converter()) {
   742       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   743       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
   744       _use_nodes = true;
   745       for (NodeIt n(_digraph); n != INVALID; ++n) {
   746 	_node_index.insert(std::make_pair(converter(map[n]), n));
   747       }
   748       return *this;
   749     }
   750 
   751     /// \brief Use previously constructed arc set
   752     ///
   753     /// Use previously constructed arc set, and specify the arc
   754     /// label map.
   755     template <typename Map>
   756     DigraphReader& useArcs(const Map& map) {
   757       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   758       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
   759       _use_arcs = true;
   760       _writer_bits::DefaultConverter<typename Map::Value> converter;
   761       for (ArcIt a(_digraph); a != INVALID; ++a) {
   762 	_arc_index.insert(std::make_pair(converter(map[a]), a));
   763       }
   764       return *this;
   765     }
   766 
   767     /// \brief Use previously constructed arc set
   768     ///
   769     /// Use previously constructed arc set, and specify the arc
   770     /// label map and a functor which converts the label map values to
   771     /// \c std::string.
   772     template <typename Map, typename Converter>
   773     DigraphReader& useArcs(const Map& map, 
   774 			   const Converter& converter = Converter()) {
   775       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   776       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member"); 
   777       _use_arcs = true;
   778       for (ArcIt a(_digraph); a != INVALID; ++a) {
   779 	_arc_index.insert(std::make_pair(converter(map[a]), a));
   780       }
   781       return *this;
   782     }
   783 
   784     /// \brief Skips the reading of node section
   785     ///
   786     /// Omit the reading of the node section. This implies that each node
   787     /// map reading rule will be abandoned, and the nodes of the graph
   788     /// will not be constructed, which usually cause that the arc set
   789     /// could not be read due to lack of node name resolving.
   790     /// Therefore \c skipArcs() function should also be used, or
   791     /// \c useNodes() should be used to specify the label of the nodes.
   792     DigraphReader& skipNodes() {
   793       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
   794       _skip_nodes = true;
   795       return *this;
   796     }
   797 
   798     /// \brief Skips the reading of arc section
   799     ///
   800     /// Omit the reading of the arc section. This implies that each arc
   801     /// map reading rule will be abandoned, and the arcs of the graph
   802     /// will not be constructed.
   803     DigraphReader& skipArcs() {
   804       LEMON_ASSERT(!_skip_arcs, "Skip arcs already set"); 
   805       _skip_arcs = true;
   806       return *this;
   807     }
   808 
   809     /// @}
   810 
   811   private:
   812 
   813     bool readLine() {
   814       std::string str;
   815       while(++line_num, std::getline(*_is, str)) {
   816 	line.clear(); line.str(str);
   817 	char c;
   818 	if (line >> std::ws >> c && c != '#') {
   819 	  line.putback(c);
   820 	  return true;
   821 	}
   822       }
   823       return false;
   824     }
   825 
   826     bool readSuccess() {
   827       return static_cast<bool>(*_is);
   828     }
   829     
   830     void skipSection() {
   831       char c;
   832       while (readSuccess() && line >> c && c != '@') {
   833 	readLine();
   834       }
   835       line.putback(c);
   836     }
   837 
   838     void readNodes() {
   839 
   840       std::vector<int> map_index(_node_maps.size());
   841       int map_num, label_index;
   842 
   843       char c;
   844       if (!readLine() || !(line >> c) || c == '@') {
   845 	if (readSuccess() && line) line.putback(c);
   846 	if (!_node_maps.empty()) 
   847 	  throw DataFormatError("Cannot find map names");
   848 	return;
   849       }
   850       line.putback(c);
   851 
   852       {
   853 	std::map<std::string, int> maps;
   854 	
   855 	std::string map;
   856 	int index = 0;
   857 	while (_reader_bits::readToken(line, map)) {
   858 	  if (maps.find(map) != maps.end()) {
   859 	    std::ostringstream msg;
   860 	    msg << "Multiple occurence of node map: " << map;
   861 	    throw DataFormatError(msg.str().c_str());
   862 	  }
   863 	  maps.insert(std::make_pair(map, index));
   864 	  ++index;
   865 	}
   866 	
   867 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   868 	  std::map<std::string, int>::iterator jt = 
   869 	    maps.find(_node_maps[i].first);
   870 	  if (jt == maps.end()) {
   871 	    std::ostringstream msg;
   872 	    msg << "Map not found in file: " << _node_maps[i].first;
   873 	    throw DataFormatError(msg.str().c_str());
   874 	  }
   875 	  map_index[i] = jt->second;
   876 	}
   877 
   878 	{
   879 	  std::map<std::string, int>::iterator jt = maps.find("label");
   880 	  if (jt != maps.end()) {
   881 	    label_index = jt->second;
   882 	  } else {
   883 	    label_index = -1;
   884 	  }
   885 	}
   886 	map_num = maps.size();
   887       }
   888 
   889       while (readLine() && line >> c && c != '@') {
   890 	line.putback(c);
   891 
   892 	std::vector<std::string> tokens(map_num);
   893 	for (int i = 0; i < map_num; ++i) {
   894 	  if (!_reader_bits::readToken(line, tokens[i])) {
   895 	    std::ostringstream msg;
   896 	    msg << "Column not found (" << i + 1 << ")";
   897 	    throw DataFormatError(msg.str().c_str());
   898 	  }
   899 	}
   900 	if (line >> std::ws >> c)
   901 	  throw DataFormatError("Extra character on the end of line");
   902 	
   903 	Node n;
   904 	if (!_use_nodes) {
   905 	  n = _digraph.addNode();
   906 	  if (label_index != -1)
   907 	    _node_index.insert(std::make_pair(tokens[label_index], n));
   908 	} else {
   909 	  if (label_index == -1) 
   910 	    throw DataFormatError("Label map not found in file");
   911 	  typename std::map<std::string, Node>::iterator it =
   912 	    _node_index.find(tokens[label_index]);
   913 	  if (it == _node_index.end()) {
   914 	    std::ostringstream msg;
   915 	    msg << "Node with label not found: " << tokens[label_index];
   916 	    throw DataFormatError(msg.str().c_str());	    
   917 	  }
   918 	  n = it->second;
   919 	}
   920 
   921 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   922 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
   923 	}
   924 
   925       }
   926       if (readSuccess()) {
   927 	line.putback(c);
   928       }
   929     }
   930 
   931     void readArcs() {
   932 
   933       std::vector<int> map_index(_arc_maps.size());
   934       int map_num, label_index;
   935 
   936       char c;
   937       if (!readLine() || !(line >> c) || c == '@') {
   938 	if (readSuccess() && line) line.putback(c);
   939 	if (!_arc_maps.empty()) 
   940 	  throw DataFormatError("Cannot find map names");
   941 	return;
   942       }
   943       line.putback(c);
   944       
   945       {
   946 	std::map<std::string, int> maps;
   947 	
   948 	std::string map;
   949 	int index = 0;
   950 	while (_reader_bits::readToken(line, map)) {
   951 	  if (maps.find(map) != maps.end()) {
   952 	    std::ostringstream msg;
   953 	    msg << "Multiple occurence of arc map: " << map;
   954 	    throw DataFormatError(msg.str().c_str());
   955 	  }
   956 	  maps.insert(std::make_pair(map, index));
   957 	  ++index;
   958 	}
   959 	
   960 	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
   961 	  std::map<std::string, int>::iterator jt = 
   962 	    maps.find(_arc_maps[i].first);
   963 	  if (jt == maps.end()) {
   964 	    std::ostringstream msg;
   965 	    msg << "Map not found in file: " << _arc_maps[i].first;
   966 	    throw DataFormatError(msg.str().c_str());
   967 	  }
   968 	  map_index[i] = jt->second;
   969 	}
   970 
   971 	{
   972 	  std::map<std::string, int>::iterator jt = maps.find("label");
   973 	  if (jt != maps.end()) {
   974 	    label_index = jt->second;
   975 	  } else {
   976 	    label_index = -1;
   977 	  }
   978 	}
   979 	map_num = maps.size();
   980       }
   981 
   982       while (readLine() && line >> c && c != '@') {
   983 	line.putback(c);
   984 
   985 	std::string source_token;
   986 	std::string target_token;
   987 
   988 	if (!_reader_bits::readToken(line, source_token))
   989 	  throw DataFormatError("Source not found");
   990 
   991 	if (!_reader_bits::readToken(line, target_token))
   992 	  throw DataFormatError("Target not found");
   993 	
   994 	std::vector<std::string> tokens(map_num);
   995 	for (int i = 0; i < map_num; ++i) {
   996 	  if (!_reader_bits::readToken(line, tokens[i])) {
   997 	    std::ostringstream msg;
   998 	    msg << "Column not found (" << i + 1 << ")";
   999 	    throw DataFormatError(msg.str().c_str());
  1000 	  }
  1001 	}
  1002 	if (line >> std::ws >> c)
  1003 	  throw DataFormatError("Extra character on the end of line");
  1004 	
  1005 	Arc a;
  1006 	if (!_use_arcs) {
  1007 
  1008           typename NodeIndex::iterator it;
  1009  
  1010           it = _node_index.find(source_token);
  1011           if (it == _node_index.end()) {
  1012             std::ostringstream msg;
  1013             msg << "Item not found: " << source_token;
  1014             throw DataFormatError(msg.str().c_str());
  1015           }
  1016           Node source = it->second;
  1017 
  1018           it = _node_index.find(target_token);
  1019           if (it == _node_index.end()) {       
  1020             std::ostringstream msg;            
  1021             msg << "Item not found: " << target_token;
  1022             throw DataFormatError(msg.str().c_str());
  1023           }                                          
  1024           Node target = it->second;                            
  1025 
  1026 	  a = _digraph.addArc(source, target);
  1027 	  if (label_index != -1) 
  1028 	    _arc_index.insert(std::make_pair(tokens[label_index], a));
  1029 	} else {
  1030 	  if (label_index == -1) 
  1031 	    throw DataFormatError("Label map not found in file");
  1032 	  typename std::map<std::string, Arc>::iterator it =
  1033 	    _arc_index.find(tokens[label_index]);
  1034 	  if (it == _arc_index.end()) {
  1035 	    std::ostringstream msg;
  1036 	    msg << "Arc with label not found: " << tokens[label_index];
  1037 	    throw DataFormatError(msg.str().c_str());	    
  1038 	  }
  1039 	  a = it->second;
  1040 	}
  1041 
  1042 	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
  1043 	  _arc_maps[i].second->set(a, tokens[map_index[i]]);
  1044 	}
  1045 
  1046       }
  1047       if (readSuccess()) {
  1048 	line.putback(c);
  1049       }
  1050     }
  1051 
  1052     void readAttributes() {
  1053 
  1054       std::set<std::string> read_attr;
  1055 
  1056       char c;
  1057       while (readLine() && line >> c && c != '@') {
  1058 	line.putback(c);
  1059 	
  1060 	std::string attr, token;
  1061 	if (!_reader_bits::readToken(line, attr))
  1062 	  throw DataFormatError("Attribute name not found");
  1063 	if (!_reader_bits::readToken(line, token))
  1064 	  throw DataFormatError("Attribute value not found");
  1065 	if (line >> c)
  1066 	  throw DataFormatError("Extra character on the end of line");	  
  1067 
  1068 	{
  1069 	  std::set<std::string>::iterator it = read_attr.find(attr);
  1070 	  if (it != read_attr.end()) {
  1071 	    std::ostringstream msg;
  1072 	    msg << "Multiple occurence of attribute " << attr;
  1073 	    throw DataFormatError(msg.str().c_str());
  1074 	  }
  1075 	  read_attr.insert(attr);
  1076 	}
  1077 	
  1078 	{
  1079 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
  1080 	  while (it != _attributes.end() && it->first == attr) {
  1081 	    it->second->set(token);
  1082 	    ++it;
  1083 	  }
  1084 	}
  1085 
  1086       }
  1087       if (readSuccess()) {
  1088 	line.putback(c);
  1089       }
  1090       for (typename Attributes::iterator it = _attributes.begin();
  1091 	   it != _attributes.end(); ++it) {
  1092 	if (read_attr.find(it->first) == read_attr.end()) {
  1093 	  std::ostringstream msg;
  1094 	  msg << "Attribute not found in file: " << it->first;
  1095 	  throw DataFormatError(msg.str().c_str());
  1096 	}	
  1097       }
  1098     }
  1099 
  1100   public:
  1101 
  1102     /// \name Execution of the reader    
  1103     /// @{
  1104 
  1105     /// \brief Start the batch processing
  1106     ///
  1107     /// This function starts the batch processing
  1108     void run() {
  1109       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1110       if (!*_is) {
  1111 	throw DataFormatError("Cannot find file");
  1112       }
  1113       
  1114       bool nodes_done = _skip_nodes;
  1115       bool arcs_done = _skip_arcs;
  1116       bool attributes_done = false;
  1117 
  1118       line_num = 0;      
  1119       readLine();
  1120       skipSection();
  1121 
  1122       while (readSuccess()) {
  1123 	try {
  1124 	  char c;
  1125 	  std::string section, caption;
  1126 	  line >> c;
  1127 	  _reader_bits::readToken(line, section);
  1128 	  _reader_bits::readToken(line, caption);
  1129 
  1130 	  if (line >> c) 
  1131 	    throw DataFormatError("Extra character on the end of line");
  1132 
  1133 	  if (section == "nodes" && !nodes_done) {
  1134 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
  1135 	      readNodes();
  1136 	      nodes_done = true;
  1137 	    }
  1138 	  } else if ((section == "arcs" || section == "edges") && 
  1139 		     !arcs_done) {
  1140 	    if (_arcs_caption.empty() || _arcs_caption == caption) {
  1141 	      readArcs();
  1142 	      arcs_done = true;
  1143 	    }
  1144 	  } else if (section == "attributes" && !attributes_done) {
  1145 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
  1146 	      readAttributes();
  1147 	      attributes_done = true;
  1148 	    }
  1149 	  } else {
  1150 	    readLine();
  1151 	    skipSection();
  1152 	  }
  1153 	} catch (DataFormatError& error) {
  1154 	  error.line(line_num);
  1155 	  throw;
  1156 	}	
  1157       }
  1158 
  1159       if (!nodes_done) {
  1160 	throw DataFormatError("Section @nodes not found");
  1161       }
  1162 
  1163       if (!arcs_done) {
  1164 	throw DataFormatError("Section @arcs not found");
  1165       }
  1166 
  1167       if (!attributes_done && !_attributes.empty()) {
  1168 	throw DataFormatError("Section @attributes not found");
  1169       }
  1170 
  1171     }
  1172 
  1173     /// @}
  1174     
  1175   };
  1176 
  1177   /// \brief Return a \ref DigraphReader class
  1178   /// 
  1179   /// This function just returns a \ref DigraphReader class.
  1180   /// \relates DigraphReader
  1181   template <typename Digraph>
  1182   DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
  1183     DigraphReader<Digraph> tmp(is, digraph);
  1184     return tmp;
  1185   }
  1186 
  1187   /// \brief Return a \ref DigraphReader class
  1188   /// 
  1189   /// This function just returns a \ref DigraphReader class.
  1190   /// \relates DigraphReader
  1191   template <typename Digraph>
  1192   DigraphReader<Digraph> digraphReader(const std::string& fn, 
  1193 				       Digraph& digraph) {
  1194     DigraphReader<Digraph> tmp(fn, digraph);
  1195     return tmp;
  1196   }
  1197 
  1198   /// \brief Return a \ref DigraphReader class
  1199   /// 
  1200   /// This function just returns a \ref DigraphReader class.
  1201   /// \relates DigraphReader
  1202   template <typename Digraph>
  1203   DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
  1204     DigraphReader<Digraph> tmp(fn, digraph);
  1205     return tmp;
  1206   }
  1207 
  1208   template <typename Graph>
  1209   class GraphReader;
  1210 
  1211   template <typename Graph>
  1212   GraphReader<Graph> graphReader(std::istream& is, Graph& graph);    
  1213 
  1214   template <typename Graph>
  1215   GraphReader<Graph> graphReader(const std::string& fn, Graph& graph);   
  1216 
  1217   template <typename Graph>
  1218   GraphReader<Graph> graphReader(const char *fn, Graph& graph);    
  1219 
  1220   /// \ingroup lemon_io
  1221   ///  
  1222   /// \brief \ref lgf-format "LGF" reader for undirected graphs
  1223   ///
  1224   /// This utility reads an \ref lgf-format "LGF" file.
  1225   ///
  1226   /// It can be used almost the same way as \c DigraphReader.
  1227   /// The only difference is that this class can handle edges and
  1228   /// edge maps as well as arcs and arc maps.
  1229   template <typename _Graph>
  1230   class GraphReader {
  1231   public:
  1232 
  1233     typedef _Graph Graph;
  1234     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  1235     
  1236   private:
  1237 
  1238     std::istream* _is;
  1239     bool local_is;
  1240 
  1241     Graph& _graph;
  1242 
  1243     std::string _nodes_caption;
  1244     std::string _edges_caption;
  1245     std::string _attributes_caption;
  1246 
  1247     typedef std::map<std::string, Node> NodeIndex;
  1248     NodeIndex _node_index;
  1249     typedef std::map<std::string, Edge> EdgeIndex;
  1250     EdgeIndex _edge_index;
  1251     
  1252     typedef std::vector<std::pair<std::string, 
  1253       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
  1254     NodeMaps _node_maps; 
  1255 
  1256     typedef std::vector<std::pair<std::string,
  1257       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  1258     EdgeMaps _edge_maps;
  1259 
  1260     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
  1261       Attributes;
  1262     Attributes _attributes;
  1263 
  1264     bool _use_nodes;
  1265     bool _use_edges;
  1266 
  1267     bool _skip_nodes;
  1268     bool _skip_edges;
  1269 
  1270     int line_num;
  1271     std::istringstream line;
  1272 
  1273   public:
  1274 
  1275     /// \brief Constructor
  1276     ///
  1277     /// Construct an undirected graph reader, which reads from the given
  1278     /// input stream.
  1279     GraphReader(std::istream& is, Graph& graph) 
  1280       : _is(&is), local_is(false), _graph(graph),
  1281 	_use_nodes(false), _use_edges(false),
  1282 	_skip_nodes(false), _skip_edges(false) {}
  1283 
  1284     /// \brief Constructor
  1285     ///
  1286     /// Construct an undirected graph reader, which reads from the given
  1287     /// file.
  1288     GraphReader(const std::string& fn, Graph& graph) 
  1289       : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
  1290     	_use_nodes(false), _use_edges(false),
  1291 	_skip_nodes(false), _skip_edges(false) {}
  1292     
  1293     /// \brief Constructor
  1294     ///
  1295     /// Construct an undirected graph reader, which reads from the given
  1296     /// file.
  1297     GraphReader(const char* fn, Graph& graph) 
  1298       : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
  1299     	_use_nodes(false), _use_edges(false),
  1300 	_skip_nodes(false), _skip_edges(false) {}
  1301 
  1302     /// \brief Destructor
  1303     ~GraphReader() {
  1304       for (typename NodeMaps::iterator it = _node_maps.begin(); 
  1305 	   it != _node_maps.end(); ++it) {
  1306 	delete it->second;
  1307       }
  1308 
  1309       for (typename EdgeMaps::iterator it = _edge_maps.begin(); 
  1310 	   it != _edge_maps.end(); ++it) {
  1311 	delete it->second;
  1312       }
  1313 
  1314       for (typename Attributes::iterator it = _attributes.begin(); 
  1315 	   it != _attributes.end(); ++it) {
  1316 	delete it->second;
  1317       }
  1318 
  1319       if (local_is) {
  1320 	delete _is;
  1321       }
  1322 
  1323     }
  1324 
  1325   private:
  1326     friend GraphReader<Graph> graphReader<>(std::istream& is, Graph& graph);    
  1327     friend GraphReader<Graph> graphReader<>(const std::string& fn, 
  1328 					    Graph& graph);   
  1329     friend GraphReader<Graph> graphReader<>(const char *fn, Graph& graph);    
  1330 
  1331     GraphReader(GraphReader& other) 
  1332       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  1333 	_use_nodes(other._use_nodes), _use_edges(other._use_edges),
  1334 	_skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1335 
  1336       other._is = 0;
  1337       other.local_is = false;
  1338       
  1339       _node_index.swap(other._node_index);
  1340       _edge_index.swap(other._edge_index);
  1341 
  1342       _node_maps.swap(other._node_maps);
  1343       _edge_maps.swap(other._edge_maps);
  1344       _attributes.swap(other._attributes);
  1345 
  1346       _nodes_caption = other._nodes_caption;
  1347       _edges_caption = other._edges_caption;
  1348       _attributes_caption = other._attributes_caption;
  1349 
  1350     }
  1351 
  1352     GraphReader& operator=(const GraphReader&);
  1353 
  1354   public:
  1355 
  1356     /// \name Reading rules
  1357     /// @{
  1358     
  1359     /// \brief Node map reading rule
  1360     ///
  1361     /// Add a node map reading rule to the reader.
  1362     template <typename Map>
  1363     GraphReader& nodeMap(const std::string& caption, Map& map) {
  1364       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1365       _reader_bits::MapStorageBase<Node>* storage = 
  1366 	new _reader_bits::MapStorage<Node, Map>(map);
  1367       _node_maps.push_back(std::make_pair(caption, storage));
  1368       return *this;
  1369     }
  1370 
  1371     /// \brief Node map reading rule
  1372     ///
  1373     /// Add a node map reading rule with specialized converter to the
  1374     /// reader.
  1375     template <typename Map, typename Converter>
  1376     GraphReader& nodeMap(const std::string& caption, Map& map, 
  1377 			   const Converter& converter = Converter()) {
  1378       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1379       _reader_bits::MapStorageBase<Node>* storage = 
  1380 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  1381       _node_maps.push_back(std::make_pair(caption, storage));
  1382       return *this;
  1383     }
  1384 
  1385     /// \brief Edge map reading rule
  1386     ///
  1387     /// Add an edge map reading rule to the reader.
  1388     template <typename Map>
  1389     GraphReader& edgeMap(const std::string& caption, Map& map) {
  1390       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1391       _reader_bits::MapStorageBase<Edge>* storage = 
  1392 	new _reader_bits::MapStorage<Edge, Map>(map);
  1393       _edge_maps.push_back(std::make_pair(caption, storage));
  1394       return *this;
  1395     }
  1396 
  1397     /// \brief Edge map reading rule
  1398     ///
  1399     /// Add an edge map reading rule with specialized converter to the
  1400     /// reader.
  1401     template <typename Map, typename Converter>
  1402     GraphReader& edgeMap(const std::string& caption, Map& map, 
  1403 			  const Converter& converter = Converter()) {
  1404       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1405       _reader_bits::MapStorageBase<Edge>* storage = 
  1406 	new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1407       _edge_maps.push_back(std::make_pair(caption, storage));
  1408       return *this;
  1409     }
  1410 
  1411     /// \brief Arc map reading rule
  1412     ///
  1413     /// Add an arc map reading rule to the reader.
  1414     template <typename Map>
  1415     GraphReader& arcMap(const std::string& caption, Map& map) {
  1416       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1417       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1418 	new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1419       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1420       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1421 	new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1422       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1423       return *this;
  1424     }
  1425 
  1426     /// \brief Arc map reading rule
  1427     ///
  1428     /// Add an arc map reading rule with specialized converter to the
  1429     /// reader.
  1430     template <typename Map, typename Converter>
  1431     GraphReader& arcMap(const std::string& caption, Map& map, 
  1432 			  const Converter& converter = Converter()) {
  1433       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1434       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1435 	new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1436 	(_graph, map, converter);
  1437       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1438       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1439 	new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1440 	(_graph, map, converter);
  1441       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1442       return *this;
  1443     }
  1444 
  1445     /// \brief Attribute reading rule
  1446     ///
  1447     /// Add an attribute reading rule to the reader.
  1448     template <typename Value>
  1449     GraphReader& attribute(const std::string& caption, Value& value) {
  1450       _reader_bits::ValueStorageBase* storage = 
  1451 	new _reader_bits::ValueStorage<Value>(value);
  1452       _attributes.insert(std::make_pair(caption, storage));
  1453       return *this;
  1454     }
  1455 
  1456     /// \brief Attribute reading rule
  1457     ///
  1458     /// Add an attribute reading rule with specialized converter to the
  1459     /// reader.
  1460     template <typename Value, typename Converter>
  1461     GraphReader& attribute(const std::string& caption, Value& value, 
  1462 			     const Converter& converter = Converter()) {
  1463       _reader_bits::ValueStorageBase* storage = 
  1464 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  1465       _attributes.insert(std::make_pair(caption, storage));
  1466       return *this;
  1467     }
  1468 
  1469     /// \brief Node reading rule
  1470     ///
  1471     /// Add a node reading rule to reader.
  1472     GraphReader& node(const std::string& caption, Node& node) {
  1473       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  1474       Converter converter(_node_index);
  1475       _reader_bits::ValueStorageBase* storage = 
  1476 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  1477       _attributes.insert(std::make_pair(caption, storage));
  1478       return *this;
  1479     }
  1480 
  1481     /// \brief Edge reading rule
  1482     ///
  1483     /// Add an edge reading rule to reader.
  1484     GraphReader& edge(const std::string& caption, Edge& edge) {
  1485       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  1486       Converter converter(_edge_index);
  1487       _reader_bits::ValueStorageBase* storage = 
  1488 	new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  1489       _attributes.insert(std::make_pair(caption, storage));
  1490       return *this;
  1491     }
  1492 
  1493     /// \brief Arc reading rule
  1494     ///
  1495     /// Add an arc reading rule to reader.
  1496     GraphReader& arc(const std::string& caption, Arc& arc) {
  1497       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
  1498       Converter converter(_graph, _edge_index);
  1499       _reader_bits::ValueStorageBase* storage = 
  1500 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  1501       _attributes.insert(std::make_pair(caption, storage));
  1502       return *this;
  1503     }
  1504 
  1505     /// @}
  1506 
  1507     /// \name Select section by name
  1508     /// @{
  1509 
  1510     /// \brief Set \c \@nodes section to be read
  1511     ///
  1512     /// Set \c \@nodes section to be read.
  1513     GraphReader& nodes(const std::string& caption) {
  1514       _nodes_caption = caption;
  1515       return *this;
  1516     }
  1517 
  1518     /// \brief Set \c \@edges section to be read
  1519     ///
  1520     /// Set \c \@edges section to be read.
  1521     GraphReader& edges(const std::string& caption) {
  1522       _edges_caption = caption;
  1523       return *this;
  1524     }
  1525 
  1526     /// \brief Set \c \@attributes section to be read
  1527     ///
  1528     /// Set \c \@attributes section to be read.
  1529     GraphReader& attributes(const std::string& caption) {
  1530       _attributes_caption = caption;
  1531       return *this;
  1532     }
  1533 
  1534     /// @}
  1535 
  1536     /// \name Using previously constructed node or edge set
  1537     /// @{
  1538 
  1539     /// \brief Use previously constructed node set
  1540     ///
  1541     /// Use previously constructed node set, and specify the node
  1542     /// label map.
  1543     template <typename Map>
  1544     GraphReader& useNodes(const Map& map) {
  1545       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1546       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1547       _use_nodes = true;
  1548       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1549       for (NodeIt n(_graph); n != INVALID; ++n) {
  1550 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1551       }
  1552       return *this;
  1553     }
  1554 
  1555     /// \brief Use previously constructed node set
  1556     ///
  1557     /// Use previously constructed node set, and specify the node
  1558     /// label map and a functor which converts the label map values to
  1559     /// \c std::string.
  1560     template <typename Map, typename Converter>
  1561     GraphReader& useNodes(const Map& map, 
  1562 			    const Converter& converter = Converter()) {
  1563       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1564       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1565       _use_nodes = true;
  1566       for (NodeIt n(_graph); n != INVALID; ++n) {
  1567 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1568       }
  1569       return *this;
  1570     }
  1571 
  1572     /// \brief Use previously constructed edge set
  1573     ///
  1574     /// Use previously constructed edge set, and specify the edge
  1575     /// label map.
  1576     template <typename Map>
  1577     GraphReader& useEdges(const Map& map) {
  1578       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1579       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1580       _use_edges = true;
  1581       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1582       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1583 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1584       }
  1585       return *this;
  1586     }
  1587 
  1588     /// \brief Use previously constructed edge set
  1589     ///
  1590     /// Use previously constructed edge set, and specify the edge
  1591     /// label map and a functor which converts the label map values to
  1592     /// \c std::string.
  1593     template <typename Map, typename Converter>
  1594     GraphReader& useEdges(const Map& map, 
  1595 			    const Converter& converter = Converter()) {
  1596       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1597       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 
  1598       _use_edges = true;
  1599       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1600 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1601       }
  1602       return *this;
  1603     }
  1604 
  1605     /// \brief Skip the reading of node section
  1606     ///
  1607     /// Omit the reading of the node section. This implies that each node
  1608     /// map reading rule will be abandoned, and the nodes of the graph
  1609     /// will not be constructed, which usually cause that the edge set
  1610     /// could not be read due to lack of node name
  1611     /// could not be read due to lack of node name resolving.
  1612     /// Therefore \c skipEdges() function should also be used, or
  1613     /// \c useNodes() should be used to specify the label of the nodes.
  1614     GraphReader& skipNodes() {
  1615       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
  1616       _skip_nodes = true;
  1617       return *this;
  1618     }
  1619 
  1620     /// \brief Skip the reading of edge section
  1621     ///
  1622     /// Omit the reading of the edge section. This implies that each edge
  1623     /// map reading rule will be abandoned, and the edges of the graph
  1624     /// will not be constructed.
  1625     GraphReader& skipEdges() {
  1626       LEMON_ASSERT(!_skip_edges, "Skip edges already set"); 
  1627       _skip_edges = true;
  1628       return *this;
  1629     }
  1630 
  1631     /// @}
  1632 
  1633   private:
  1634 
  1635     bool readLine() {
  1636       std::string str;
  1637       while(++line_num, std::getline(*_is, str)) {
  1638 	line.clear(); line.str(str);
  1639 	char c;
  1640 	if (line >> std::ws >> c && c != '#') {
  1641 	  line.putback(c);
  1642 	  return true;
  1643 	}
  1644       }
  1645       return false;
  1646     }
  1647 
  1648     bool readSuccess() {
  1649       return static_cast<bool>(*_is);
  1650     }
  1651     
  1652     void skipSection() {
  1653       char c;
  1654       while (readSuccess() && line >> c && c != '@') {
  1655 	readLine();
  1656       }
  1657       line.putback(c);
  1658     }
  1659 
  1660     void readNodes() {
  1661 
  1662       std::vector<int> map_index(_node_maps.size());
  1663       int map_num, label_index;
  1664 
  1665       char c;
  1666       if (!readLine() || !(line >> c) || c == '@') {
  1667 	if (readSuccess() && line) line.putback(c);
  1668 	if (!_node_maps.empty()) 
  1669 	  throw DataFormatError("Cannot find map names");
  1670 	return;
  1671       }
  1672       line.putback(c);
  1673       
  1674       {
  1675 	std::map<std::string, int> maps;
  1676 	
  1677 	std::string map;
  1678 	int index = 0;
  1679 	while (_reader_bits::readToken(line, map)) {
  1680 	  if (maps.find(map) != maps.end()) {
  1681 	    std::ostringstream msg;
  1682 	    msg << "Multiple occurence of node map: " << map;
  1683 	    throw DataFormatError(msg.str().c_str());
  1684 	  }
  1685 	  maps.insert(std::make_pair(map, index));
  1686 	  ++index;
  1687 	}
  1688 	
  1689 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1690 	  std::map<std::string, int>::iterator jt = 
  1691 	    maps.find(_node_maps[i].first);
  1692 	  if (jt == maps.end()) {
  1693 	    std::ostringstream msg;
  1694 	    msg << "Map not found in file: " << _node_maps[i].first;
  1695 	    throw DataFormatError(msg.str().c_str());
  1696 	  }
  1697 	  map_index[i] = jt->second;
  1698 	}
  1699 
  1700 	{
  1701 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1702 	  if (jt != maps.end()) {
  1703 	    label_index = jt->second;
  1704 	  } else {
  1705 	    label_index = -1;
  1706 	  }
  1707 	}
  1708 	map_num = maps.size();
  1709       }
  1710 
  1711       while (readLine() && line >> c && c != '@') {
  1712 	line.putback(c);
  1713 
  1714 	std::vector<std::string> tokens(map_num);
  1715 	for (int i = 0; i < map_num; ++i) {
  1716 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1717 	    std::ostringstream msg;
  1718 	    msg << "Column not found (" << i + 1 << ")";
  1719 	    throw DataFormatError(msg.str().c_str());
  1720 	  }
  1721 	}
  1722 	if (line >> std::ws >> c)
  1723 	  throw DataFormatError("Extra character on the end of line");
  1724 	
  1725 	Node n;
  1726 	if (!_use_nodes) {
  1727 	  n = _graph.addNode();
  1728 	  if (label_index != -1) 
  1729 	    _node_index.insert(std::make_pair(tokens[label_index], n));
  1730 	} else {
  1731 	  if (label_index == -1) 
  1732 	    throw DataFormatError("Label map not found in file");
  1733 	  typename std::map<std::string, Node>::iterator it =
  1734 	    _node_index.find(tokens[label_index]);
  1735 	  if (it == _node_index.end()) {
  1736 	    std::ostringstream msg;
  1737 	    msg << "Node with label not found: " << tokens[label_index];
  1738 	    throw DataFormatError(msg.str().c_str());	    
  1739 	  }
  1740 	  n = it->second;
  1741 	}
  1742 
  1743 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1744 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
  1745 	}
  1746 
  1747       }
  1748       if (readSuccess()) {
  1749 	line.putback(c);
  1750       }
  1751     }
  1752 
  1753     void readEdges() {
  1754 
  1755       std::vector<int> map_index(_edge_maps.size());
  1756       int map_num, label_index;
  1757 
  1758       char c;
  1759       if (!readLine() || !(line >> c) || c == '@') {
  1760 	if (readSuccess() && line) line.putback(c);
  1761 	if (!_edge_maps.empty()) 
  1762 	  throw DataFormatError("Cannot find map names");
  1763 	return;
  1764       }
  1765       line.putback(c);
  1766       
  1767       {
  1768 	std::map<std::string, int> maps;
  1769 	
  1770 	std::string map;
  1771 	int index = 0;
  1772 	while (_reader_bits::readToken(line, map)) {
  1773 	  if (maps.find(map) != maps.end()) {
  1774 	    std::ostringstream msg;
  1775 	    msg << "Multiple occurence of edge map: " << map;
  1776 	    throw DataFormatError(msg.str().c_str());
  1777 	  }
  1778 	  maps.insert(std::make_pair(map, index));
  1779 	  ++index;
  1780 	}
  1781 	
  1782 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1783 	  std::map<std::string, int>::iterator jt = 
  1784 	    maps.find(_edge_maps[i].first);
  1785 	  if (jt == maps.end()) {
  1786 	    std::ostringstream msg;
  1787 	    msg << "Map not found in file: " << _edge_maps[i].first;
  1788 	    throw DataFormatError(msg.str().c_str());
  1789 	  }
  1790 	  map_index[i] = jt->second;
  1791 	}
  1792 
  1793 	{
  1794 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1795 	  if (jt != maps.end()) {
  1796 	    label_index = jt->second;
  1797 	  } else {
  1798 	    label_index = -1;
  1799 	  }
  1800 	}
  1801 	map_num = maps.size();
  1802       }
  1803 
  1804       while (readLine() && line >> c && c != '@') {
  1805 	line.putback(c);
  1806 
  1807 	std::string source_token;
  1808 	std::string target_token;
  1809 
  1810 	if (!_reader_bits::readToken(line, source_token))
  1811 	  throw DataFormatError("Node u not found");
  1812 
  1813 	if (!_reader_bits::readToken(line, target_token))
  1814 	  throw DataFormatError("Node v not found");
  1815 	
  1816 	std::vector<std::string> tokens(map_num);
  1817 	for (int i = 0; i < map_num; ++i) {
  1818 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1819 	    std::ostringstream msg;
  1820 	    msg << "Column not found (" << i + 1 << ")";
  1821 	    throw DataFormatError(msg.str().c_str());
  1822 	  }
  1823 	}
  1824 	if (line >> std::ws >> c)
  1825 	  throw DataFormatError("Extra character on the end of line");
  1826 	
  1827 	Edge e;
  1828 	if (!_use_edges) {
  1829 
  1830           typename NodeIndex::iterator it;
  1831  
  1832           it = _node_index.find(source_token);
  1833           if (it == _node_index.end()) {
  1834             std::ostringstream msg;
  1835             msg << "Item not found: " << source_token;
  1836             throw DataFormatError(msg.str().c_str());
  1837           }
  1838           Node source = it->second;
  1839 
  1840           it = _node_index.find(target_token);
  1841           if (it == _node_index.end()) {       
  1842             std::ostringstream msg;            
  1843             msg << "Item not found: " << target_token;
  1844             throw DataFormatError(msg.str().c_str());
  1845           }                                          
  1846           Node target = it->second;                            
  1847 
  1848 	  e = _graph.addEdge(source, target);
  1849 	  if (label_index != -1) 
  1850 	    _edge_index.insert(std::make_pair(tokens[label_index], e));
  1851 	} else {
  1852 	  if (label_index == -1) 
  1853 	    throw DataFormatError("Label map not found in file");
  1854 	  typename std::map<std::string, Edge>::iterator it =
  1855 	    _edge_index.find(tokens[label_index]);
  1856 	  if (it == _edge_index.end()) {
  1857 	    std::ostringstream msg;
  1858 	    msg << "Edge with label not found: " << tokens[label_index];
  1859 	    throw DataFormatError(msg.str().c_str());	    
  1860 	  }
  1861 	  e = it->second;
  1862 	}
  1863 
  1864 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1865 	  _edge_maps[i].second->set(e, tokens[map_index[i]]);
  1866 	}
  1867 
  1868       }
  1869       if (readSuccess()) {
  1870 	line.putback(c);
  1871       }
  1872     }
  1873 
  1874     void readAttributes() {
  1875 
  1876       std::set<std::string> read_attr;
  1877 
  1878       char c;
  1879       while (readLine() && line >> c && c != '@') {
  1880 	line.putback(c);
  1881 	
  1882 	std::string attr, token;
  1883 	if (!_reader_bits::readToken(line, attr))
  1884 	  throw DataFormatError("Attribute name not found");
  1885 	if (!_reader_bits::readToken(line, token))
  1886 	  throw DataFormatError("Attribute value not found");
  1887 	if (line >> c)
  1888 	  throw DataFormatError("Extra character on the end of line");	  
  1889 
  1890 	{
  1891 	  std::set<std::string>::iterator it = read_attr.find(attr);
  1892 	  if (it != read_attr.end()) {
  1893 	    std::ostringstream msg;
  1894 	    msg << "Multiple occurence of attribute " << attr;
  1895 	    throw DataFormatError(msg.str().c_str());
  1896 	  }
  1897 	  read_attr.insert(attr);
  1898 	}
  1899 	
  1900 	{
  1901 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
  1902 	  while (it != _attributes.end() && it->first == attr) {
  1903 	    it->second->set(token);
  1904 	    ++it;
  1905 	  }
  1906 	}
  1907 
  1908       }
  1909       if (readSuccess()) {
  1910 	line.putback(c);
  1911       }
  1912       for (typename Attributes::iterator it = _attributes.begin();
  1913 	   it != _attributes.end(); ++it) {
  1914 	if (read_attr.find(it->first) == read_attr.end()) {
  1915 	  std::ostringstream msg;
  1916 	  msg << "Attribute not found in file: " << it->first;
  1917 	  throw DataFormatError(msg.str().c_str());
  1918 	}	
  1919       }
  1920     }
  1921 
  1922   public:
  1923 
  1924     /// \name Execution of the reader    
  1925     /// @{
  1926 
  1927     /// \brief Start the batch processing
  1928     ///
  1929     /// This function starts the batch processing
  1930     void run() {
  1931       
  1932       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1933       
  1934       bool nodes_done = _skip_nodes;
  1935       bool edges_done = _skip_edges;
  1936       bool attributes_done = false;
  1937 
  1938       line_num = 0;      
  1939       readLine();
  1940       skipSection();
  1941 
  1942       while (readSuccess()) {
  1943 	try {
  1944 	  char c;
  1945 	  std::string section, caption;
  1946 	  line >> c;
  1947 	  _reader_bits::readToken(line, section);
  1948 	  _reader_bits::readToken(line, caption);
  1949 
  1950 	  if (line >> c) 
  1951 	    throw DataFormatError("Extra character on the end of line");
  1952 
  1953 	  if (section == "nodes" && !nodes_done) {
  1954 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
  1955 	      readNodes();
  1956 	      nodes_done = true;
  1957 	    }
  1958 	  } else if ((section == "edges" || section == "arcs") && 
  1959 		     !edges_done) {
  1960 	    if (_edges_caption.empty() || _edges_caption == caption) {
  1961 	      readEdges();
  1962 	      edges_done = true;
  1963 	    }
  1964 	  } else if (section == "attributes" && !attributes_done) {
  1965 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
  1966 	      readAttributes();
  1967 	      attributes_done = true;
  1968 	    }
  1969 	  } else {
  1970 	    readLine();
  1971 	    skipSection();
  1972 	  }
  1973 	} catch (DataFormatError& error) {
  1974 	  error.line(line_num);
  1975 	  throw;
  1976 	}	
  1977       }
  1978 
  1979       if (!nodes_done) {
  1980 	throw DataFormatError("Section @nodes not found");
  1981       }
  1982 
  1983       if (!edges_done) {
  1984 	throw DataFormatError("Section @edges not found");
  1985       }
  1986 
  1987       if (!attributes_done && !_attributes.empty()) {
  1988 	throw DataFormatError("Section @attributes not found");
  1989       }
  1990 
  1991     }
  1992 
  1993     /// @}
  1994     
  1995   };
  1996 
  1997   /// \brief Return a \ref GraphReader class
  1998   /// 
  1999   /// This function just returns a \ref GraphReader class.
  2000   /// \relates GraphReader
  2001   template <typename Graph>
  2002   GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
  2003     GraphReader<Graph> tmp(is, graph);
  2004     return tmp;
  2005   }
  2006 
  2007   /// \brief Return a \ref GraphReader class
  2008   /// 
  2009   /// This function just returns a \ref GraphReader class.
  2010   /// \relates GraphReader
  2011   template <typename Graph>
  2012   GraphReader<Graph> graphReader(const std::string& fn, 
  2013 				       Graph& graph) {
  2014     GraphReader<Graph> tmp(fn, graph);
  2015     return tmp;
  2016   }
  2017 
  2018   /// \brief Return a \ref GraphReader class
  2019   /// 
  2020   /// This function just returns a \ref GraphReader class.
  2021   /// \relates GraphReader
  2022   template <typename Graph>
  2023   GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
  2024     GraphReader<Graph> tmp(fn, graph);
  2025     return tmp;
  2026   }
  2027 
  2028   class SectionReader;
  2029 
  2030   SectionReader sectionReader(std::istream& is);
  2031   SectionReader sectionReader(const std::string& fn);
  2032   SectionReader sectionReader(const char* fn);
  2033   
  2034   /// \ingroup lemon_io
  2035   ///
  2036   /// \brief Section reader class
  2037   ///
  2038   /// In the \ref lgf-format "LGF" file extra sections can be placed, 
  2039   /// which contain any data in arbitrary format. Such sections can be
  2040   /// read with this class. A reading rule can be added to the class 
  2041   /// with two different functions. With the \c sectionLines() function a
  2042   /// functor can process the section line-by-line, while with the \c
  2043   /// sectionStream() member the section can be read from an input
  2044   /// stream.
  2045   class SectionReader {
  2046   private:
  2047     
  2048     std::istream* _is;
  2049     bool local_is;
  2050 
  2051     typedef std::map<std::string, _reader_bits::Section*> Sections;
  2052     Sections _sections;
  2053 
  2054     int line_num;
  2055     std::istringstream line;
  2056 
  2057   public:
  2058 
  2059     /// \brief Constructor
  2060     ///
  2061     /// Construct a section reader, which reads from the given input
  2062     /// stream.
  2063     SectionReader(std::istream& is) 
  2064       : _is(&is), local_is(false) {}
  2065 
  2066     /// \brief Constructor
  2067     ///
  2068     /// Construct a section reader, which reads from the given file.
  2069     SectionReader(const std::string& fn) 
  2070       : _is(new std::ifstream(fn.c_str())), local_is(true) {}
  2071     
  2072     /// \brief Constructor
  2073     ///
  2074     /// Construct a section reader, which reads from the given file.
  2075     SectionReader(const char* fn) 
  2076       : _is(new std::ifstream(fn)), local_is(true) {}
  2077 
  2078     /// \brief Destructor
  2079     ~SectionReader() {
  2080       for (Sections::iterator it = _sections.begin(); 
  2081 	   it != _sections.end(); ++it) {
  2082 	delete it->second;
  2083       }
  2084 
  2085       if (local_is) {
  2086 	delete _is;
  2087       }
  2088 
  2089     }
  2090 
  2091   private:
  2092 
  2093     friend SectionReader sectionReader(std::istream& is);
  2094     friend SectionReader sectionReader(const std::string& fn);
  2095     friend SectionReader sectionReader(const char* fn);
  2096 
  2097     SectionReader(SectionReader& other) 
  2098       : _is(other._is), local_is(other.local_is) {
  2099 
  2100       other._is = 0;
  2101       other.local_is = false;
  2102       
  2103       _sections.swap(other._sections);
  2104     }
  2105     
  2106     SectionReader& operator=(const SectionReader&);
  2107 
  2108   public:
  2109 
  2110     /// \name Section readers
  2111     /// @{
  2112 
  2113     /// \brief Add a section processor with line oriented reading
  2114     ///
  2115     /// The first parameter is the type descriptor of the section, the
  2116     /// second is a functor, which takes just one \c std::string
  2117     /// parameter. At the reading process, each line of the section
  2118     /// will be given to the functor object. However, the empty lines
  2119     /// and the comment lines are filtered out, and the leading
  2120     /// whitespaces are trimmed from each processed string.
  2121     ///
  2122     /// For example let's see a section, which contain several
  2123     /// integers, which should be inserted into a vector.
  2124     ///\code
  2125     ///  @numbers
  2126     ///  12 45 23
  2127     ///  4
  2128     ///  23 6
  2129     ///\endcode
  2130     ///
  2131     /// The functor is implemented as a struct:
  2132     ///\code
  2133     ///  struct NumberSection {
  2134     ///    std::vector<int>& _data;
  2135     ///    NumberSection(std::vector<int>& data) : _data(data) {}
  2136     ///    void operator()(const std::string& line) {
  2137     ///      std::istringstream ls(line);
  2138     ///      int value;
  2139     ///      while (ls >> value) _data.push_back(value);
  2140     ///    }
  2141     ///  };
  2142     ///
  2143     ///  // ...
  2144     ///
  2145     ///  reader.sectionLines("numbers", NumberSection(vec));  
  2146     ///\endcode
  2147     template <typename Functor>
  2148     SectionReader& sectionLines(const std::string& type, Functor functor) {
  2149       LEMON_ASSERT(!type.empty(), "Type is empty.");
  2150       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  2151 		   "Multiple reading of section.");
  2152       _sections.insert(std::make_pair(type, 
  2153         new _reader_bits::LineSection<Functor>(functor)));
  2154       return *this;
  2155     }
  2156 
  2157 
  2158     /// \brief Add a section processor with stream oriented reading
  2159     ///
  2160     /// The first parameter is the type of the section, the second is
  2161     /// a functor, which takes an \c std::istream& and an \c int&
  2162     /// parameter, the latter regard to the line number of stream. The
  2163     /// functor can read the input while the section go on, and the
  2164     /// line number should be modified accordingly.
  2165     template <typename Functor>
  2166     SectionReader& sectionStream(const std::string& type, Functor functor) {
  2167       LEMON_ASSERT(!type.empty(), "Type is empty.");
  2168       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  2169 		   "Multiple reading of section.");
  2170       _sections.insert(std::make_pair(type, 
  2171 	 new _reader_bits::StreamSection<Functor>(functor)));
  2172       return *this;
  2173     }    
  2174     
  2175     /// @}
  2176 
  2177   private:
  2178 
  2179     bool readLine() {
  2180       std::string str;
  2181       while(++line_num, std::getline(*_is, str)) {
  2182 	line.clear(); line.str(str);
  2183 	char c;
  2184 	if (line >> std::ws >> c && c != '#') {
  2185 	  line.putback(c);
  2186 	  return true;
  2187 	}
  2188       }
  2189       return false;
  2190     }
  2191 
  2192     bool readSuccess() {
  2193       return static_cast<bool>(*_is);
  2194     }
  2195     
  2196     void skipSection() {
  2197       char c;
  2198       while (readSuccess() && line >> c && c != '@') {
  2199 	readLine();
  2200       }
  2201       line.putback(c);
  2202     }
  2203 
  2204   public:
  2205 
  2206 
  2207     /// \name Execution of the reader    
  2208     /// @{
  2209 
  2210     /// \brief Start the batch processing
  2211     ///
  2212     /// This function starts the batch processing.
  2213     void run() {
  2214       
  2215       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  2216       
  2217       std::set<std::string> extra_sections;
  2218 
  2219       line_num = 0;      
  2220       readLine();
  2221       skipSection();
  2222 
  2223       while (readSuccess()) {
  2224 	try {
  2225 	  char c;
  2226 	  std::string section, caption;
  2227 	  line >> c;
  2228 	  _reader_bits::readToken(line, section);
  2229 	  _reader_bits::readToken(line, caption);
  2230 
  2231 	  if (line >> c) 
  2232 	    throw DataFormatError("Extra character on the end of line");
  2233 
  2234 	  if (extra_sections.find(section) != extra_sections.end()) {
  2235 	    std::ostringstream msg;
  2236 	    msg << "Multiple occurence of section " << section;
  2237 	    throw DataFormatError(msg.str().c_str());
  2238 	  }
  2239 	  Sections::iterator it = _sections.find(section);
  2240 	  if (it != _sections.end()) {
  2241 	    extra_sections.insert(section);
  2242 	    it->second->process(*_is, line_num);
  2243 	  }
  2244 	  readLine();
  2245 	  skipSection();
  2246 	} catch (DataFormatError& error) {
  2247 	  error.line(line_num);
  2248 	  throw;
  2249 	}	
  2250       }
  2251       for (Sections::iterator it = _sections.begin();
  2252 	   it != _sections.end(); ++it) {
  2253 	if (extra_sections.find(it->first) == extra_sections.end()) {
  2254 	  std::ostringstream os;
  2255 	  os << "Cannot find section: " << it->first;
  2256 	  throw DataFormatError(os.str().c_str());
  2257 	}
  2258       }
  2259     }
  2260 
  2261     /// @}
  2262         
  2263   };
  2264 
  2265   /// \brief Return a \ref SectionReader class
  2266   /// 
  2267   /// This function just returns a \ref SectionReader class.
  2268   /// \relates SectionReader
  2269   inline SectionReader sectionReader(std::istream& is) {
  2270     SectionReader tmp(is);
  2271     return tmp;
  2272   }
  2273 
  2274   /// \brief Return a \ref SectionReader class
  2275   /// 
  2276   /// This function just returns a \ref SectionReader class.
  2277   /// \relates SectionReader
  2278   inline SectionReader sectionReader(const std::string& fn) {
  2279     SectionReader tmp(fn);
  2280     return tmp;
  2281   }
  2282 
  2283   /// \brief Return a \ref SectionReader class
  2284   /// 
  2285   /// This function just returns a \ref SectionReader class.
  2286   /// \relates SectionReader
  2287   inline SectionReader sectionReader(const char* fn) {
  2288     SectionReader tmp(fn);
  2289     return tmp;
  2290   }
  2291 
  2292   /// \ingroup lemon_io
  2293   ///
  2294   /// \brief Reader for the contents of the \ref lgf-format "LGF" file 
  2295   ///
  2296   /// This class can be used to read the sections, the map names and
  2297   /// the attributes from a file. Usually, the Lemon programs know
  2298   /// that, which type of graph, which maps and which attributes
  2299   /// should be read from a file, but in general tools (like glemon)
  2300   /// the contents of an LGF file should be guessed somehow. This class
  2301   /// reads the graph and stores the appropriate information for
  2302   /// reading the graph.
  2303   ///
  2304   ///\code 
  2305   /// LgfContents contents("graph.lgf"); 
  2306   /// contents.run();
  2307   ///
  2308   /// // Does it contain any node section and arc section?
  2309   /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
  2310   ///   std::cerr << "Failure, cannot find graph." << std::endl;
  2311   ///   return -1;
  2312   /// }
  2313   /// std::cout << "The name of the default node section: " 
  2314   ///           << contents.nodeSection(0) << std::endl;
  2315   /// std::cout << "The number of the arc maps: " 
  2316   ///           << contents.arcMaps(0).size() << std::endl;
  2317   /// std::cout << "The name of second arc map: " 
  2318   ///           << contents.arcMaps(0)[1] << std::endl;
  2319   ///\endcode
  2320   class LgfContents {    
  2321   private:
  2322 
  2323     std::istream* _is;
  2324     bool local_is;
  2325 
  2326     std::vector<std::string> _node_sections;
  2327     std::vector<std::string> _edge_sections;
  2328     std::vector<std::string> _attribute_sections;
  2329     std::vector<std::string> _extra_sections;
  2330 
  2331     std::vector<bool> _arc_sections;
  2332 
  2333     std::vector<std::vector<std::string> > _node_maps;
  2334     std::vector<std::vector<std::string> > _edge_maps;
  2335 
  2336     std::vector<std::vector<std::string> > _attributes;
  2337 
  2338 
  2339     int line_num;
  2340     std::istringstream line;
  2341     
  2342   public:
  2343 
  2344     /// \brief Constructor
  2345     ///
  2346     /// Construct an \e LGF contents reader, which reads from the given
  2347     /// input stream.
  2348     LgfContents(std::istream& is) 
  2349       : _is(&is), local_is(false) {}
  2350 
  2351     /// \brief Constructor
  2352     ///
  2353     /// Construct an \e LGF contents reader, which reads from the given
  2354     /// file.
  2355     LgfContents(const std::string& fn) 
  2356       : _is(new std::ifstream(fn.c_str())), local_is(true) {}
  2357 
  2358     /// \brief Constructor
  2359     ///
  2360     /// Construct an \e LGF contents reader, which reads from the given
  2361     /// file.
  2362     LgfContents(const char* fn)
  2363       : _is(new std::ifstream(fn)), local_is(true) {}
  2364     
  2365     /// \brief Destructor
  2366     ~LgfContents() {
  2367       if (local_is) delete _is;
  2368     }
  2369 
  2370   private:
  2371     
  2372     LgfContents(const LgfContents&);
  2373     LgfContents& operator=(const LgfContents&);
  2374 
  2375   public:
  2376 
  2377 
  2378     /// \name Node sections
  2379     /// @{
  2380 
  2381     /// \brief Gives back the number of node sections in the file.
  2382     ///
  2383     /// Gives back the number of node sections in the file.
  2384     int nodeSectionNum() const {
  2385       return _node_sections.size();
  2386     }
  2387 
  2388     /// \brief Returns the node section name at the given position. 
  2389     ///
  2390     /// Returns the node section name at the given position. 
  2391     const std::string& nodeSection(int i) const {
  2392       return _node_sections[i];
  2393     }
  2394 
  2395     /// \brief Gives back the node maps for the given section.
  2396     ///
  2397     /// Gives back the node maps for the given section.
  2398     const std::vector<std::string>& nodeMapNames(int i) const {
  2399       return _node_maps[i];
  2400     }
  2401 
  2402     /// @}
  2403 
  2404     /// \name Arc/Edge sections 
  2405     /// @{
  2406 
  2407     /// \brief Gives back the number of arc/edge sections in the file.
  2408     ///
  2409     /// Gives back the number of arc/edge sections in the file.
  2410     /// \note It is synonym of \c edgeSectionNum().
  2411     int arcSectionNum() const {
  2412       return _edge_sections.size();
  2413     }
  2414 
  2415     /// \brief Returns the arc/edge section name at the given position. 
  2416     ///
  2417     /// Returns the arc/edge section name at the given position. 
  2418     /// \note It is synonym of \c edgeSection().
  2419     const std::string& arcSection(int i) const {
  2420       return _edge_sections[i];
  2421     }
  2422 
  2423     /// \brief Gives back the arc/edge maps for the given section.
  2424     ///
  2425     /// Gives back the arc/edge maps for the given section.
  2426     /// \note It is synonym of \c edgeMapNames().
  2427     const std::vector<std::string>& arcMapNames(int i) const {
  2428       return _edge_maps[i];
  2429     }
  2430 
  2431     /// @}
  2432 
  2433     /// \name Synonyms
  2434     /// @{
  2435 
  2436     /// \brief Gives back the number of arc/edge sections in the file.
  2437     ///
  2438     /// Gives back the number of arc/edge sections in the file.
  2439     /// \note It is synonym of \c arcSectionNum().
  2440     int edgeSectionNum() const {
  2441       return _edge_sections.size();
  2442     }
  2443 
  2444     /// \brief Returns the section name at the given position. 
  2445     ///
  2446     /// Returns the section name at the given position. 
  2447     /// \note It is synonym of \c arcSection().
  2448     const std::string& edgeSection(int i) const {
  2449       return _edge_sections[i];
  2450     }
  2451 
  2452     /// \brief Gives back the edge maps for the given section.
  2453     ///
  2454     /// Gives back the edge maps for the given section.
  2455     /// \note It is synonym of \c arcMapNames().
  2456     const std::vector<std::string>& edgeMapNames(int i) const {
  2457       return _edge_maps[i];
  2458     }
  2459 
  2460     /// @}
  2461 
  2462     /// \name Attribute sections   
  2463     /// @{
  2464 
  2465     /// \brief Gives back the number of attribute sections in the file.
  2466     ///
  2467     /// Gives back the number of attribute sections in the file.
  2468     int attributeSectionNum() const {
  2469       return _attribute_sections.size();
  2470     }
  2471 
  2472     /// \brief Returns the attribute section name at the given position. 
  2473     ///
  2474     /// Returns the attribute section name at the given position. 
  2475     const std::string& attributeSectionNames(int i) const {
  2476       return _attribute_sections[i];
  2477     }
  2478 
  2479     /// \brief Gives back the attributes for the given section.
  2480     ///
  2481     /// Gives back the attributes for the given section.
  2482     const std::vector<std::string>& attributes(int i) const {
  2483       return _attributes[i];
  2484     }
  2485 
  2486     /// @}
  2487 
  2488     /// \name Extra sections   
  2489     /// @{
  2490 
  2491     /// \brief Gives back the number of extra sections in the file.
  2492     ///
  2493     /// Gives back the number of extra sections in the file.
  2494     int extraSectionNum() const {
  2495       return _extra_sections.size();
  2496     }
  2497 
  2498     /// \brief Returns the extra section type at the given position. 
  2499     ///
  2500     /// Returns the section type at the given position. 
  2501     const std::string& extraSection(int i) const {
  2502       return _extra_sections[i];
  2503     }
  2504 
  2505     /// @}
  2506 
  2507   private:
  2508 
  2509     bool readLine() {
  2510       std::string str;
  2511       while(++line_num, std::getline(*_is, str)) {
  2512 	line.clear(); line.str(str);
  2513 	char c;
  2514 	if (line >> std::ws >> c && c != '#') {
  2515 	  line.putback(c);
  2516 	  return true;
  2517 	}
  2518       }
  2519       return false;
  2520     }
  2521 
  2522     bool readSuccess() {
  2523       return static_cast<bool>(*_is);
  2524     }
  2525 
  2526     void skipSection() {
  2527       char c;
  2528       while (readSuccess() && line >> c && c != '@') {
  2529 	readLine();
  2530       }
  2531       line.putback(c);
  2532     }
  2533 
  2534     void readMaps(std::vector<std::string>& maps) {
  2535       char c;
  2536       if (!readLine() || !(line >> c) || c == '@') {
  2537 	if (readSuccess() && line) line.putback(c);
  2538 	return;
  2539       }
  2540       line.putback(c);
  2541       std::string map;
  2542       while (_reader_bits::readToken(line, map)) {
  2543 	maps.push_back(map);
  2544       }
  2545     }
  2546 
  2547     void readAttributes(std::vector<std::string>& attrs) {
  2548       readLine();
  2549       char c;
  2550       while (readSuccess() && line >> c && c != '@') {
  2551 	line.putback(c);
  2552 	std::string attr;
  2553 	_reader_bits::readToken(line, attr);
  2554 	attrs.push_back(attr);
  2555 	readLine();
  2556       }
  2557       line.putback(c);
  2558     }
  2559 
  2560   public:
  2561 
  2562     /// \name Execution of the contents reader    
  2563     /// @{
  2564 
  2565     /// \brief Starts the reading
  2566     ///
  2567     /// This function starts the reading.
  2568     void run() {
  2569 
  2570       readLine();
  2571       skipSection();
  2572 
  2573       while (readSuccess()) {
  2574 
  2575 	char c;
  2576 	line >> c;
  2577 
  2578 	std::string section, caption;
  2579 	_reader_bits::readToken(line, section);
  2580 	_reader_bits::readToken(line, caption);
  2581 
  2582 	if (section == "nodes") {
  2583 	  _node_sections.push_back(caption);
  2584 	  _node_maps.push_back(std::vector<std::string>());
  2585 	  readMaps(_node_maps.back());
  2586 	  readLine(); skipSection();
  2587 	} else if (section == "arcs" || section == "edges") {
  2588 	  _edge_sections.push_back(caption);
  2589 	  _arc_sections.push_back(section == "arcs");
  2590 	  _edge_maps.push_back(std::vector<std::string>());
  2591 	  readMaps(_edge_maps.back());
  2592 	  readLine(); skipSection();
  2593 	} else if (section == "attributes") {
  2594 	  _attribute_sections.push_back(caption);
  2595 	  _attributes.push_back(std::vector<std::string>());
  2596 	  readAttributes(_attributes.back());
  2597 	} else {
  2598 	  _extra_sections.push_back(section);
  2599 	  readLine(); skipSection();
  2600 	}
  2601       }
  2602     }
  2603 
  2604     /// @}
  2605     
  2606   };
  2607 }
  2608 
  2609 #endif