lemon/lgf_reader.h
author Balazs Dezso <deba@inf.elte.hu>
Fri, 11 Jul 2008 15:01:49 +0200
changeset 203 215bfc30b14f
parent 197 5893bacaa720
child 209 765619b7cbb2
permissions -rw-r--r--
Cleaning of heap test and bug fix in heap concept check (ticket #100)

* The dijkstra heap test's digraph is inlined into the source file
* The random sequences are fixed
* The content of the header is moved to the source file
* Only the binary heap is checked
     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     inline bool isWhiteSpace(char c) {
   199       return c == ' ' || c == '\t' || c == '\v' || 
   200         c == '\n' || c == '\r' || c == '\f'; 
   201     }
   202     
   203     inline bool isOct(char c) {
   204       return '0' <= c && c <='7'; 
   205     }
   206     
   207     inline int valueOct(char c) {
   208       LEMON_ASSERT(isOct(c), "The character is not octal.");
   209       return c - '0';
   210     }
   211 
   212     inline bool isHex(char c) {
   213       return ('0' <= c && c <= '9') || 
   214 	('a' <= c && c <= 'z') || 
   215 	('A' <= c && c <= 'Z'); 
   216     }
   217     
   218     inline 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     inline bool isIdentifierFirstChar(char c) {
   226       return ('a' <= c && c <= 'z') ||
   227 	('A' <= c && c <= 'Z') || c == '_';
   228     }
   229 
   230     inline bool isIdentifierChar(char c) {
   231       return isIdentifierFirstChar(c) ||
   232 	('0' <= c && c <= '9');
   233     }
   234 
   235     inline 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     inline 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   ///
  1230   /// The columns in the \c \@edges (or \c \@arcs) section are the
  1231   /// edge maps. However, if there are two maps with the same name
  1232   /// prefixed with \c '+' and \c '-', then these can be read into an
  1233   /// arc map.  Similarly, an attribute can be read into an arc, if
  1234   /// it's value is an edge label prefixed with \c '+' or \c '-'.
  1235   template <typename _Graph>
  1236   class GraphReader {
  1237   public:
  1238 
  1239     typedef _Graph Graph;
  1240     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  1241     
  1242   private:
  1243 
  1244     std::istream* _is;
  1245     bool local_is;
  1246 
  1247     Graph& _graph;
  1248 
  1249     std::string _nodes_caption;
  1250     std::string _edges_caption;
  1251     std::string _attributes_caption;
  1252 
  1253     typedef std::map<std::string, Node> NodeIndex;
  1254     NodeIndex _node_index;
  1255     typedef std::map<std::string, Edge> EdgeIndex;
  1256     EdgeIndex _edge_index;
  1257     
  1258     typedef std::vector<std::pair<std::string, 
  1259       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
  1260     NodeMaps _node_maps; 
  1261 
  1262     typedef std::vector<std::pair<std::string,
  1263       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  1264     EdgeMaps _edge_maps;
  1265 
  1266     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
  1267       Attributes;
  1268     Attributes _attributes;
  1269 
  1270     bool _use_nodes;
  1271     bool _use_edges;
  1272 
  1273     bool _skip_nodes;
  1274     bool _skip_edges;
  1275 
  1276     int line_num;
  1277     std::istringstream line;
  1278 
  1279   public:
  1280 
  1281     /// \brief Constructor
  1282     ///
  1283     /// Construct an undirected graph reader, which reads from the given
  1284     /// input stream.
  1285     GraphReader(std::istream& is, Graph& graph) 
  1286       : _is(&is), local_is(false), _graph(graph),
  1287 	_use_nodes(false), _use_edges(false),
  1288 	_skip_nodes(false), _skip_edges(false) {}
  1289 
  1290     /// \brief Constructor
  1291     ///
  1292     /// Construct an undirected graph reader, which reads from the given
  1293     /// file.
  1294     GraphReader(const std::string& fn, Graph& graph) 
  1295       : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
  1296     	_use_nodes(false), _use_edges(false),
  1297 	_skip_nodes(false), _skip_edges(false) {}
  1298     
  1299     /// \brief Constructor
  1300     ///
  1301     /// Construct an undirected graph reader, which reads from the given
  1302     /// file.
  1303     GraphReader(const char* fn, Graph& graph) 
  1304       : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
  1305     	_use_nodes(false), _use_edges(false),
  1306 	_skip_nodes(false), _skip_edges(false) {}
  1307 
  1308     /// \brief Destructor
  1309     ~GraphReader() {
  1310       for (typename NodeMaps::iterator it = _node_maps.begin(); 
  1311 	   it != _node_maps.end(); ++it) {
  1312 	delete it->second;
  1313       }
  1314 
  1315       for (typename EdgeMaps::iterator it = _edge_maps.begin(); 
  1316 	   it != _edge_maps.end(); ++it) {
  1317 	delete it->second;
  1318       }
  1319 
  1320       for (typename Attributes::iterator it = _attributes.begin(); 
  1321 	   it != _attributes.end(); ++it) {
  1322 	delete it->second;
  1323       }
  1324 
  1325       if (local_is) {
  1326 	delete _is;
  1327       }
  1328 
  1329     }
  1330 
  1331   private:
  1332     friend GraphReader<Graph> graphReader<>(std::istream& is, Graph& graph);    
  1333     friend GraphReader<Graph> graphReader<>(const std::string& fn, 
  1334 					    Graph& graph);   
  1335     friend GraphReader<Graph> graphReader<>(const char *fn, Graph& graph);    
  1336 
  1337     GraphReader(GraphReader& other) 
  1338       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  1339 	_use_nodes(other._use_nodes), _use_edges(other._use_edges),
  1340 	_skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1341 
  1342       other._is = 0;
  1343       other.local_is = false;
  1344       
  1345       _node_index.swap(other._node_index);
  1346       _edge_index.swap(other._edge_index);
  1347 
  1348       _node_maps.swap(other._node_maps);
  1349       _edge_maps.swap(other._edge_maps);
  1350       _attributes.swap(other._attributes);
  1351 
  1352       _nodes_caption = other._nodes_caption;
  1353       _edges_caption = other._edges_caption;
  1354       _attributes_caption = other._attributes_caption;
  1355 
  1356     }
  1357 
  1358     GraphReader& operator=(const GraphReader&);
  1359 
  1360   public:
  1361 
  1362     /// \name Reading rules
  1363     /// @{
  1364     
  1365     /// \brief Node map reading rule
  1366     ///
  1367     /// Add a node map reading rule to the reader.
  1368     template <typename Map>
  1369     GraphReader& nodeMap(const std::string& caption, Map& map) {
  1370       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1371       _reader_bits::MapStorageBase<Node>* storage = 
  1372 	new _reader_bits::MapStorage<Node, Map>(map);
  1373       _node_maps.push_back(std::make_pair(caption, storage));
  1374       return *this;
  1375     }
  1376 
  1377     /// \brief Node map reading rule
  1378     ///
  1379     /// Add a node map reading rule with specialized converter to the
  1380     /// reader.
  1381     template <typename Map, typename Converter>
  1382     GraphReader& nodeMap(const std::string& caption, Map& map, 
  1383 			   const Converter& converter = Converter()) {
  1384       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1385       _reader_bits::MapStorageBase<Node>* storage = 
  1386 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  1387       _node_maps.push_back(std::make_pair(caption, storage));
  1388       return *this;
  1389     }
  1390 
  1391     /// \brief Edge map reading rule
  1392     ///
  1393     /// Add an edge map reading rule to the reader.
  1394     template <typename Map>
  1395     GraphReader& edgeMap(const std::string& caption, Map& map) {
  1396       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1397       _reader_bits::MapStorageBase<Edge>* storage = 
  1398 	new _reader_bits::MapStorage<Edge, Map>(map);
  1399       _edge_maps.push_back(std::make_pair(caption, storage));
  1400       return *this;
  1401     }
  1402 
  1403     /// \brief Edge map reading rule
  1404     ///
  1405     /// Add an edge map reading rule with specialized converter to the
  1406     /// reader.
  1407     template <typename Map, typename Converter>
  1408     GraphReader& edgeMap(const std::string& caption, Map& map, 
  1409 			  const Converter& converter = Converter()) {
  1410       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1411       _reader_bits::MapStorageBase<Edge>* storage = 
  1412 	new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1413       _edge_maps.push_back(std::make_pair(caption, storage));
  1414       return *this;
  1415     }
  1416 
  1417     /// \brief Arc map reading rule
  1418     ///
  1419     /// Add an arc map reading rule to the reader.
  1420     template <typename Map>
  1421     GraphReader& arcMap(const std::string& caption, Map& map) {
  1422       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1423       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1424 	new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1425       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1426       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1427 	new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1428       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1429       return *this;
  1430     }
  1431 
  1432     /// \brief Arc map reading rule
  1433     ///
  1434     /// Add an arc map reading rule with specialized converter to the
  1435     /// reader.
  1436     template <typename Map, typename Converter>
  1437     GraphReader& arcMap(const std::string& caption, Map& map, 
  1438 			  const Converter& converter = Converter()) {
  1439       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1440       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1441 	new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1442 	(_graph, map, converter);
  1443       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1444       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1445 	new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1446 	(_graph, map, converter);
  1447       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1448       return *this;
  1449     }
  1450 
  1451     /// \brief Attribute reading rule
  1452     ///
  1453     /// Add an attribute reading rule to the reader.
  1454     template <typename Value>
  1455     GraphReader& attribute(const std::string& caption, Value& value) {
  1456       _reader_bits::ValueStorageBase* storage = 
  1457 	new _reader_bits::ValueStorage<Value>(value);
  1458       _attributes.insert(std::make_pair(caption, storage));
  1459       return *this;
  1460     }
  1461 
  1462     /// \brief Attribute reading rule
  1463     ///
  1464     /// Add an attribute reading rule with specialized converter to the
  1465     /// reader.
  1466     template <typename Value, typename Converter>
  1467     GraphReader& attribute(const std::string& caption, Value& value, 
  1468 			     const Converter& converter = Converter()) {
  1469       _reader_bits::ValueStorageBase* storage = 
  1470 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  1471       _attributes.insert(std::make_pair(caption, storage));
  1472       return *this;
  1473     }
  1474 
  1475     /// \brief Node reading rule
  1476     ///
  1477     /// Add a node reading rule to reader.
  1478     GraphReader& node(const std::string& caption, Node& node) {
  1479       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  1480       Converter converter(_node_index);
  1481       _reader_bits::ValueStorageBase* storage = 
  1482 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  1483       _attributes.insert(std::make_pair(caption, storage));
  1484       return *this;
  1485     }
  1486 
  1487     /// \brief Edge reading rule
  1488     ///
  1489     /// Add an edge reading rule to reader.
  1490     GraphReader& edge(const std::string& caption, Edge& edge) {
  1491       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  1492       Converter converter(_edge_index);
  1493       _reader_bits::ValueStorageBase* storage = 
  1494 	new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  1495       _attributes.insert(std::make_pair(caption, storage));
  1496       return *this;
  1497     }
  1498 
  1499     /// \brief Arc reading rule
  1500     ///
  1501     /// Add an arc reading rule to reader.
  1502     GraphReader& arc(const std::string& caption, Arc& arc) {
  1503       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
  1504       Converter converter(_graph, _edge_index);
  1505       _reader_bits::ValueStorageBase* storage = 
  1506 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  1507       _attributes.insert(std::make_pair(caption, storage));
  1508       return *this;
  1509     }
  1510 
  1511     /// @}
  1512 
  1513     /// \name Select section by name
  1514     /// @{
  1515 
  1516     /// \brief Set \c \@nodes section to be read
  1517     ///
  1518     /// Set \c \@nodes section to be read.
  1519     GraphReader& nodes(const std::string& caption) {
  1520       _nodes_caption = caption;
  1521       return *this;
  1522     }
  1523 
  1524     /// \brief Set \c \@edges section to be read
  1525     ///
  1526     /// Set \c \@edges section to be read.
  1527     GraphReader& edges(const std::string& caption) {
  1528       _edges_caption = caption;
  1529       return *this;
  1530     }
  1531 
  1532     /// \brief Set \c \@attributes section to be read
  1533     ///
  1534     /// Set \c \@attributes section to be read.
  1535     GraphReader& attributes(const std::string& caption) {
  1536       _attributes_caption = caption;
  1537       return *this;
  1538     }
  1539 
  1540     /// @}
  1541 
  1542     /// \name Using previously constructed node or edge set
  1543     /// @{
  1544 
  1545     /// \brief Use previously constructed node set
  1546     ///
  1547     /// Use previously constructed node set, and specify the node
  1548     /// label map.
  1549     template <typename Map>
  1550     GraphReader& useNodes(const Map& map) {
  1551       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1552       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1553       _use_nodes = true;
  1554       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1555       for (NodeIt n(_graph); n != INVALID; ++n) {
  1556 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1557       }
  1558       return *this;
  1559     }
  1560 
  1561     /// \brief Use previously constructed node set
  1562     ///
  1563     /// Use previously constructed node set, and specify the node
  1564     /// label map and a functor which converts the label map values to
  1565     /// \c std::string.
  1566     template <typename Map, typename Converter>
  1567     GraphReader& useNodes(const Map& map, 
  1568 			    const Converter& converter = Converter()) {
  1569       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1570       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1571       _use_nodes = true;
  1572       for (NodeIt n(_graph); n != INVALID; ++n) {
  1573 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1574       }
  1575       return *this;
  1576     }
  1577 
  1578     /// \brief Use previously constructed edge set
  1579     ///
  1580     /// Use previously constructed edge set, and specify the edge
  1581     /// label map.
  1582     template <typename Map>
  1583     GraphReader& useEdges(const Map& map) {
  1584       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1585       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1586       _use_edges = true;
  1587       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1588       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1589 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1590       }
  1591       return *this;
  1592     }
  1593 
  1594     /// \brief Use previously constructed edge set
  1595     ///
  1596     /// Use previously constructed edge set, and specify the edge
  1597     /// label map and a functor which converts the label map values to
  1598     /// \c std::string.
  1599     template <typename Map, typename Converter>
  1600     GraphReader& useEdges(const Map& map, 
  1601 			    const Converter& converter = Converter()) {
  1602       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1603       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 
  1604       _use_edges = true;
  1605       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1606 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1607       }
  1608       return *this;
  1609     }
  1610 
  1611     /// \brief Skip the reading of node section
  1612     ///
  1613     /// Omit the reading of the node section. This implies that each node
  1614     /// map reading rule will be abandoned, and the nodes of the graph
  1615     /// will not be constructed, which usually cause that the edge set
  1616     /// could not be read due to lack of node name
  1617     /// could not be read due to lack of node name resolving.
  1618     /// Therefore \c skipEdges() function should also be used, or
  1619     /// \c useNodes() should be used to specify the label of the nodes.
  1620     GraphReader& skipNodes() {
  1621       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set"); 
  1622       _skip_nodes = true;
  1623       return *this;
  1624     }
  1625 
  1626     /// \brief Skip the reading of edge section
  1627     ///
  1628     /// Omit the reading of the edge section. This implies that each edge
  1629     /// map reading rule will be abandoned, and the edges of the graph
  1630     /// will not be constructed.
  1631     GraphReader& skipEdges() {
  1632       LEMON_ASSERT(!_skip_edges, "Skip edges already set"); 
  1633       _skip_edges = true;
  1634       return *this;
  1635     }
  1636 
  1637     /// @}
  1638 
  1639   private:
  1640 
  1641     bool readLine() {
  1642       std::string str;
  1643       while(++line_num, std::getline(*_is, str)) {
  1644 	line.clear(); line.str(str);
  1645 	char c;
  1646 	if (line >> std::ws >> c && c != '#') {
  1647 	  line.putback(c);
  1648 	  return true;
  1649 	}
  1650       }
  1651       return false;
  1652     }
  1653 
  1654     bool readSuccess() {
  1655       return static_cast<bool>(*_is);
  1656     }
  1657     
  1658     void skipSection() {
  1659       char c;
  1660       while (readSuccess() && line >> c && c != '@') {
  1661 	readLine();
  1662       }
  1663       line.putback(c);
  1664     }
  1665 
  1666     void readNodes() {
  1667 
  1668       std::vector<int> map_index(_node_maps.size());
  1669       int map_num, label_index;
  1670 
  1671       char c;
  1672       if (!readLine() || !(line >> c) || c == '@') {
  1673 	if (readSuccess() && line) line.putback(c);
  1674 	if (!_node_maps.empty()) 
  1675 	  throw DataFormatError("Cannot find map names");
  1676 	return;
  1677       }
  1678       line.putback(c);
  1679       
  1680       {
  1681 	std::map<std::string, int> maps;
  1682 	
  1683 	std::string map;
  1684 	int index = 0;
  1685 	while (_reader_bits::readToken(line, map)) {
  1686 	  if (maps.find(map) != maps.end()) {
  1687 	    std::ostringstream msg;
  1688 	    msg << "Multiple occurence of node map: " << map;
  1689 	    throw DataFormatError(msg.str().c_str());
  1690 	  }
  1691 	  maps.insert(std::make_pair(map, index));
  1692 	  ++index;
  1693 	}
  1694 	
  1695 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1696 	  std::map<std::string, int>::iterator jt = 
  1697 	    maps.find(_node_maps[i].first);
  1698 	  if (jt == maps.end()) {
  1699 	    std::ostringstream msg;
  1700 	    msg << "Map not found in file: " << _node_maps[i].first;
  1701 	    throw DataFormatError(msg.str().c_str());
  1702 	  }
  1703 	  map_index[i] = jt->second;
  1704 	}
  1705 
  1706 	{
  1707 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1708 	  if (jt != maps.end()) {
  1709 	    label_index = jt->second;
  1710 	  } else {
  1711 	    label_index = -1;
  1712 	  }
  1713 	}
  1714 	map_num = maps.size();
  1715       }
  1716 
  1717       while (readLine() && line >> c && c != '@') {
  1718 	line.putback(c);
  1719 
  1720 	std::vector<std::string> tokens(map_num);
  1721 	for (int i = 0; i < map_num; ++i) {
  1722 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1723 	    std::ostringstream msg;
  1724 	    msg << "Column not found (" << i + 1 << ")";
  1725 	    throw DataFormatError(msg.str().c_str());
  1726 	  }
  1727 	}
  1728 	if (line >> std::ws >> c)
  1729 	  throw DataFormatError("Extra character on the end of line");
  1730 	
  1731 	Node n;
  1732 	if (!_use_nodes) {
  1733 	  n = _graph.addNode();
  1734 	  if (label_index != -1) 
  1735 	    _node_index.insert(std::make_pair(tokens[label_index], n));
  1736 	} else {
  1737 	  if (label_index == -1) 
  1738 	    throw DataFormatError("Label map not found in file");
  1739 	  typename std::map<std::string, Node>::iterator it =
  1740 	    _node_index.find(tokens[label_index]);
  1741 	  if (it == _node_index.end()) {
  1742 	    std::ostringstream msg;
  1743 	    msg << "Node with label not found: " << tokens[label_index];
  1744 	    throw DataFormatError(msg.str().c_str());	    
  1745 	  }
  1746 	  n = it->second;
  1747 	}
  1748 
  1749 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1750 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
  1751 	}
  1752 
  1753       }
  1754       if (readSuccess()) {
  1755 	line.putback(c);
  1756       }
  1757     }
  1758 
  1759     void readEdges() {
  1760 
  1761       std::vector<int> map_index(_edge_maps.size());
  1762       int map_num, label_index;
  1763 
  1764       char c;
  1765       if (!readLine() || !(line >> c) || c == '@') {
  1766 	if (readSuccess() && line) line.putback(c);
  1767 	if (!_edge_maps.empty()) 
  1768 	  throw DataFormatError("Cannot find map names");
  1769 	return;
  1770       }
  1771       line.putback(c);
  1772       
  1773       {
  1774 	std::map<std::string, int> maps;
  1775 	
  1776 	std::string map;
  1777 	int index = 0;
  1778 	while (_reader_bits::readToken(line, map)) {
  1779 	  if (maps.find(map) != maps.end()) {
  1780 	    std::ostringstream msg;
  1781 	    msg << "Multiple occurence of edge map: " << map;
  1782 	    throw DataFormatError(msg.str().c_str());
  1783 	  }
  1784 	  maps.insert(std::make_pair(map, index));
  1785 	  ++index;
  1786 	}
  1787 	
  1788 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1789 	  std::map<std::string, int>::iterator jt = 
  1790 	    maps.find(_edge_maps[i].first);
  1791 	  if (jt == maps.end()) {
  1792 	    std::ostringstream msg;
  1793 	    msg << "Map not found in file: " << _edge_maps[i].first;
  1794 	    throw DataFormatError(msg.str().c_str());
  1795 	  }
  1796 	  map_index[i] = jt->second;
  1797 	}
  1798 
  1799 	{
  1800 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1801 	  if (jt != maps.end()) {
  1802 	    label_index = jt->second;
  1803 	  } else {
  1804 	    label_index = -1;
  1805 	  }
  1806 	}
  1807 	map_num = maps.size();
  1808       }
  1809 
  1810       while (readLine() && line >> c && c != '@') {
  1811 	line.putback(c);
  1812 
  1813 	std::string source_token;
  1814 	std::string target_token;
  1815 
  1816 	if (!_reader_bits::readToken(line, source_token))
  1817 	  throw DataFormatError("Node u not found");
  1818 
  1819 	if (!_reader_bits::readToken(line, target_token))
  1820 	  throw DataFormatError("Node v not found");
  1821 	
  1822 	std::vector<std::string> tokens(map_num);
  1823 	for (int i = 0; i < map_num; ++i) {
  1824 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1825 	    std::ostringstream msg;
  1826 	    msg << "Column not found (" << i + 1 << ")";
  1827 	    throw DataFormatError(msg.str().c_str());
  1828 	  }
  1829 	}
  1830 	if (line >> std::ws >> c)
  1831 	  throw DataFormatError("Extra character on the end of line");
  1832 	
  1833 	Edge e;
  1834 	if (!_use_edges) {
  1835 
  1836           typename NodeIndex::iterator it;
  1837  
  1838           it = _node_index.find(source_token);
  1839           if (it == _node_index.end()) {
  1840             std::ostringstream msg;
  1841             msg << "Item not found: " << source_token;
  1842             throw DataFormatError(msg.str().c_str());
  1843           }
  1844           Node source = it->second;
  1845 
  1846           it = _node_index.find(target_token);
  1847           if (it == _node_index.end()) {       
  1848             std::ostringstream msg;            
  1849             msg << "Item not found: " << target_token;
  1850             throw DataFormatError(msg.str().c_str());
  1851           }                                          
  1852           Node target = it->second;                            
  1853 
  1854 	  e = _graph.addEdge(source, target);
  1855 	  if (label_index != -1) 
  1856 	    _edge_index.insert(std::make_pair(tokens[label_index], e));
  1857 	} else {
  1858 	  if (label_index == -1) 
  1859 	    throw DataFormatError("Label map not found in file");
  1860 	  typename std::map<std::string, Edge>::iterator it =
  1861 	    _edge_index.find(tokens[label_index]);
  1862 	  if (it == _edge_index.end()) {
  1863 	    std::ostringstream msg;
  1864 	    msg << "Edge with label not found: " << tokens[label_index];
  1865 	    throw DataFormatError(msg.str().c_str());	    
  1866 	  }
  1867 	  e = it->second;
  1868 	}
  1869 
  1870 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1871 	  _edge_maps[i].second->set(e, tokens[map_index[i]]);
  1872 	}
  1873 
  1874       }
  1875       if (readSuccess()) {
  1876 	line.putback(c);
  1877       }
  1878     }
  1879 
  1880     void readAttributes() {
  1881 
  1882       std::set<std::string> read_attr;
  1883 
  1884       char c;
  1885       while (readLine() && line >> c && c != '@') {
  1886 	line.putback(c);
  1887 	
  1888 	std::string attr, token;
  1889 	if (!_reader_bits::readToken(line, attr))
  1890 	  throw DataFormatError("Attribute name not found");
  1891 	if (!_reader_bits::readToken(line, token))
  1892 	  throw DataFormatError("Attribute value not found");
  1893 	if (line >> c)
  1894 	  throw DataFormatError("Extra character on the end of line");	  
  1895 
  1896 	{
  1897 	  std::set<std::string>::iterator it = read_attr.find(attr);
  1898 	  if (it != read_attr.end()) {
  1899 	    std::ostringstream msg;
  1900 	    msg << "Multiple occurence of attribute " << attr;
  1901 	    throw DataFormatError(msg.str().c_str());
  1902 	  }
  1903 	  read_attr.insert(attr);
  1904 	}
  1905 	
  1906 	{
  1907 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
  1908 	  while (it != _attributes.end() && it->first == attr) {
  1909 	    it->second->set(token);
  1910 	    ++it;
  1911 	  }
  1912 	}
  1913 
  1914       }
  1915       if (readSuccess()) {
  1916 	line.putback(c);
  1917       }
  1918       for (typename Attributes::iterator it = _attributes.begin();
  1919 	   it != _attributes.end(); ++it) {
  1920 	if (read_attr.find(it->first) == read_attr.end()) {
  1921 	  std::ostringstream msg;
  1922 	  msg << "Attribute not found in file: " << it->first;
  1923 	  throw DataFormatError(msg.str().c_str());
  1924 	}	
  1925       }
  1926     }
  1927 
  1928   public:
  1929 
  1930     /// \name Execution of the reader    
  1931     /// @{
  1932 
  1933     /// \brief Start the batch processing
  1934     ///
  1935     /// This function starts the batch processing
  1936     void run() {
  1937       
  1938       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1939       
  1940       bool nodes_done = _skip_nodes;
  1941       bool edges_done = _skip_edges;
  1942       bool attributes_done = false;
  1943 
  1944       line_num = 0;      
  1945       readLine();
  1946       skipSection();
  1947 
  1948       while (readSuccess()) {
  1949 	try {
  1950 	  char c;
  1951 	  std::string section, caption;
  1952 	  line >> c;
  1953 	  _reader_bits::readToken(line, section);
  1954 	  _reader_bits::readToken(line, caption);
  1955 
  1956 	  if (line >> c) 
  1957 	    throw DataFormatError("Extra character on the end of line");
  1958 
  1959 	  if (section == "nodes" && !nodes_done) {
  1960 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
  1961 	      readNodes();
  1962 	      nodes_done = true;
  1963 	    }
  1964 	  } else if ((section == "edges" || section == "arcs") && 
  1965 		     !edges_done) {
  1966 	    if (_edges_caption.empty() || _edges_caption == caption) {
  1967 	      readEdges();
  1968 	      edges_done = true;
  1969 	    }
  1970 	  } else if (section == "attributes" && !attributes_done) {
  1971 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
  1972 	      readAttributes();
  1973 	      attributes_done = true;
  1974 	    }
  1975 	  } else {
  1976 	    readLine();
  1977 	    skipSection();
  1978 	  }
  1979 	} catch (DataFormatError& error) {
  1980 	  error.line(line_num);
  1981 	  throw;
  1982 	}	
  1983       }
  1984 
  1985       if (!nodes_done) {
  1986 	throw DataFormatError("Section @nodes not found");
  1987       }
  1988 
  1989       if (!edges_done) {
  1990 	throw DataFormatError("Section @edges not found");
  1991       }
  1992 
  1993       if (!attributes_done && !_attributes.empty()) {
  1994 	throw DataFormatError("Section @attributes not found");
  1995       }
  1996 
  1997     }
  1998 
  1999     /// @}
  2000     
  2001   };
  2002 
  2003   /// \brief Return a \ref GraphReader class
  2004   /// 
  2005   /// This function just returns a \ref GraphReader class.
  2006   /// \relates GraphReader
  2007   template <typename Graph>
  2008   GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
  2009     GraphReader<Graph> tmp(is, graph);
  2010     return tmp;
  2011   }
  2012 
  2013   /// \brief Return a \ref GraphReader class
  2014   /// 
  2015   /// This function just returns a \ref GraphReader class.
  2016   /// \relates GraphReader
  2017   template <typename Graph>
  2018   GraphReader<Graph> graphReader(const std::string& fn, 
  2019 				       Graph& graph) {
  2020     GraphReader<Graph> tmp(fn, graph);
  2021     return tmp;
  2022   }
  2023 
  2024   /// \brief Return a \ref GraphReader class
  2025   /// 
  2026   /// This function just returns a \ref GraphReader class.
  2027   /// \relates GraphReader
  2028   template <typename Graph>
  2029   GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
  2030     GraphReader<Graph> tmp(fn, graph);
  2031     return tmp;
  2032   }
  2033 
  2034   class SectionReader;
  2035 
  2036   SectionReader sectionReader(std::istream& is);
  2037   SectionReader sectionReader(const std::string& fn);
  2038   SectionReader sectionReader(const char* fn);
  2039   
  2040   /// \ingroup lemon_io
  2041   ///
  2042   /// \brief Section reader class
  2043   ///
  2044   /// In the \ref lgf-format "LGF" file extra sections can be placed, 
  2045   /// which contain any data in arbitrary format. Such sections can be
  2046   /// read with this class. A reading rule can be added to the class 
  2047   /// with two different functions. With the \c sectionLines() function a
  2048   /// functor can process the section line-by-line, while with the \c
  2049   /// sectionStream() member the section can be read from an input
  2050   /// stream.
  2051   class SectionReader {
  2052   private:
  2053     
  2054     std::istream* _is;
  2055     bool local_is;
  2056 
  2057     typedef std::map<std::string, _reader_bits::Section*> Sections;
  2058     Sections _sections;
  2059 
  2060     int line_num;
  2061     std::istringstream line;
  2062 
  2063   public:
  2064 
  2065     /// \brief Constructor
  2066     ///
  2067     /// Construct a section reader, which reads from the given input
  2068     /// stream.
  2069     SectionReader(std::istream& is) 
  2070       : _is(&is), local_is(false) {}
  2071 
  2072     /// \brief Constructor
  2073     ///
  2074     /// Construct a section reader, which reads from the given file.
  2075     SectionReader(const std::string& fn) 
  2076       : _is(new std::ifstream(fn.c_str())), local_is(true) {}
  2077     
  2078     /// \brief Constructor
  2079     ///
  2080     /// Construct a section reader, which reads from the given file.
  2081     SectionReader(const char* fn) 
  2082       : _is(new std::ifstream(fn)), local_is(true) {}
  2083 
  2084     /// \brief Destructor
  2085     ~SectionReader() {
  2086       for (Sections::iterator it = _sections.begin(); 
  2087 	   it != _sections.end(); ++it) {
  2088 	delete it->second;
  2089       }
  2090 
  2091       if (local_is) {
  2092 	delete _is;
  2093       }
  2094 
  2095     }
  2096 
  2097   private:
  2098 
  2099     friend SectionReader sectionReader(std::istream& is);
  2100     friend SectionReader sectionReader(const std::string& fn);
  2101     friend SectionReader sectionReader(const char* fn);
  2102 
  2103     SectionReader(SectionReader& other) 
  2104       : _is(other._is), local_is(other.local_is) {
  2105 
  2106       other._is = 0;
  2107       other.local_is = false;
  2108       
  2109       _sections.swap(other._sections);
  2110     }
  2111     
  2112     SectionReader& operator=(const SectionReader&);
  2113 
  2114   public:
  2115 
  2116     /// \name Section readers
  2117     /// @{
  2118 
  2119     /// \brief Add a section processor with line oriented reading
  2120     ///
  2121     /// The first parameter is the type descriptor of the section, the
  2122     /// second is a functor, which takes just one \c std::string
  2123     /// parameter. At the reading process, each line of the section
  2124     /// will be given to the functor object. However, the empty lines
  2125     /// and the comment lines are filtered out, and the leading
  2126     /// whitespaces are trimmed from each processed string.
  2127     ///
  2128     /// For example let's see a section, which contain several
  2129     /// integers, which should be inserted into a vector.
  2130     ///\code
  2131     ///  @numbers
  2132     ///  12 45 23
  2133     ///  4
  2134     ///  23 6
  2135     ///\endcode
  2136     ///
  2137     /// The functor is implemented as a struct:
  2138     ///\code
  2139     ///  struct NumberSection {
  2140     ///    std::vector<int>& _data;
  2141     ///    NumberSection(std::vector<int>& data) : _data(data) {}
  2142     ///    void operator()(const std::string& line) {
  2143     ///      std::istringstream ls(line);
  2144     ///      int value;
  2145     ///      while (ls >> value) _data.push_back(value);
  2146     ///    }
  2147     ///  };
  2148     ///
  2149     ///  // ...
  2150     ///
  2151     ///  reader.sectionLines("numbers", NumberSection(vec));  
  2152     ///\endcode
  2153     template <typename Functor>
  2154     SectionReader& sectionLines(const std::string& type, Functor functor) {
  2155       LEMON_ASSERT(!type.empty(), "Type is empty.");
  2156       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  2157 		   "Multiple reading of section.");
  2158       _sections.insert(std::make_pair(type, 
  2159         new _reader_bits::LineSection<Functor>(functor)));
  2160       return *this;
  2161     }
  2162 
  2163 
  2164     /// \brief Add a section processor with stream oriented reading
  2165     ///
  2166     /// The first parameter is the type of the section, the second is
  2167     /// a functor, which takes an \c std::istream& and an \c int&
  2168     /// parameter, the latter regard to the line number of stream. The
  2169     /// functor can read the input while the section go on, and the
  2170     /// line number should be modified accordingly.
  2171     template <typename Functor>
  2172     SectionReader& sectionStream(const std::string& type, Functor functor) {
  2173       LEMON_ASSERT(!type.empty(), "Type is empty.");
  2174       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  2175 		   "Multiple reading of section.");
  2176       _sections.insert(std::make_pair(type, 
  2177 	 new _reader_bits::StreamSection<Functor>(functor)));
  2178       return *this;
  2179     }    
  2180     
  2181     /// @}
  2182 
  2183   private:
  2184 
  2185     bool readLine() {
  2186       std::string str;
  2187       while(++line_num, std::getline(*_is, str)) {
  2188 	line.clear(); line.str(str);
  2189 	char c;
  2190 	if (line >> std::ws >> c && c != '#') {
  2191 	  line.putback(c);
  2192 	  return true;
  2193 	}
  2194       }
  2195       return false;
  2196     }
  2197 
  2198     bool readSuccess() {
  2199       return static_cast<bool>(*_is);
  2200     }
  2201     
  2202     void skipSection() {
  2203       char c;
  2204       while (readSuccess() && line >> c && c != '@') {
  2205 	readLine();
  2206       }
  2207       line.putback(c);
  2208     }
  2209 
  2210   public:
  2211 
  2212 
  2213     /// \name Execution of the reader    
  2214     /// @{
  2215 
  2216     /// \brief Start the batch processing
  2217     ///
  2218     /// This function starts the batch processing.
  2219     void run() {
  2220       
  2221       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  2222       
  2223       std::set<std::string> extra_sections;
  2224 
  2225       line_num = 0;      
  2226       readLine();
  2227       skipSection();
  2228 
  2229       while (readSuccess()) {
  2230 	try {
  2231 	  char c;
  2232 	  std::string section, caption;
  2233 	  line >> c;
  2234 	  _reader_bits::readToken(line, section);
  2235 	  _reader_bits::readToken(line, caption);
  2236 
  2237 	  if (line >> c) 
  2238 	    throw DataFormatError("Extra character on the end of line");
  2239 
  2240 	  if (extra_sections.find(section) != extra_sections.end()) {
  2241 	    std::ostringstream msg;
  2242 	    msg << "Multiple occurence of section " << section;
  2243 	    throw DataFormatError(msg.str().c_str());
  2244 	  }
  2245 	  Sections::iterator it = _sections.find(section);
  2246 	  if (it != _sections.end()) {
  2247 	    extra_sections.insert(section);
  2248 	    it->second->process(*_is, line_num);
  2249 	  }
  2250 	  readLine();
  2251 	  skipSection();
  2252 	} catch (DataFormatError& error) {
  2253 	  error.line(line_num);
  2254 	  throw;
  2255 	}	
  2256       }
  2257       for (Sections::iterator it = _sections.begin();
  2258 	   it != _sections.end(); ++it) {
  2259 	if (extra_sections.find(it->first) == extra_sections.end()) {
  2260 	  std::ostringstream os;
  2261 	  os << "Cannot find section: " << it->first;
  2262 	  throw DataFormatError(os.str().c_str());
  2263 	}
  2264       }
  2265     }
  2266 
  2267     /// @}
  2268         
  2269   };
  2270 
  2271   /// \brief Return a \ref SectionReader class
  2272   /// 
  2273   /// This function just returns a \ref SectionReader class.
  2274   /// \relates SectionReader
  2275   inline SectionReader sectionReader(std::istream& is) {
  2276     SectionReader tmp(is);
  2277     return tmp;
  2278   }
  2279 
  2280   /// \brief Return a \ref SectionReader class
  2281   /// 
  2282   /// This function just returns a \ref SectionReader class.
  2283   /// \relates SectionReader
  2284   inline SectionReader sectionReader(const std::string& fn) {
  2285     SectionReader tmp(fn);
  2286     return tmp;
  2287   }
  2288 
  2289   /// \brief Return a \ref SectionReader class
  2290   /// 
  2291   /// This function just returns a \ref SectionReader class.
  2292   /// \relates SectionReader
  2293   inline SectionReader sectionReader(const char* fn) {
  2294     SectionReader tmp(fn);
  2295     return tmp;
  2296   }
  2297 
  2298   /// \ingroup lemon_io
  2299   ///
  2300   /// \brief Reader for the contents of the \ref lgf-format "LGF" file 
  2301   ///
  2302   /// This class can be used to read the sections, the map names and
  2303   /// the attributes from a file. Usually, the Lemon programs know
  2304   /// that, which type of graph, which maps and which attributes
  2305   /// should be read from a file, but in general tools (like glemon)
  2306   /// the contents of an LGF file should be guessed somehow. This class
  2307   /// reads the graph and stores the appropriate information for
  2308   /// reading the graph.
  2309   ///
  2310   ///\code 
  2311   /// LgfContents contents("graph.lgf"); 
  2312   /// contents.run();
  2313   ///
  2314   /// // Does it contain any node section and arc section?
  2315   /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
  2316   ///   std::cerr << "Failure, cannot find graph." << std::endl;
  2317   ///   return -1;
  2318   /// }
  2319   /// std::cout << "The name of the default node section: " 
  2320   ///           << contents.nodeSection(0) << std::endl;
  2321   /// std::cout << "The number of the arc maps: " 
  2322   ///           << contents.arcMaps(0).size() << std::endl;
  2323   /// std::cout << "The name of second arc map: " 
  2324   ///           << contents.arcMaps(0)[1] << std::endl;
  2325   ///\endcode
  2326   class LgfContents {    
  2327   private:
  2328 
  2329     std::istream* _is;
  2330     bool local_is;
  2331 
  2332     std::vector<std::string> _node_sections;
  2333     std::vector<std::string> _edge_sections;
  2334     std::vector<std::string> _attribute_sections;
  2335     std::vector<std::string> _extra_sections;
  2336 
  2337     std::vector<bool> _arc_sections;
  2338 
  2339     std::vector<std::vector<std::string> > _node_maps;
  2340     std::vector<std::vector<std::string> > _edge_maps;
  2341 
  2342     std::vector<std::vector<std::string> > _attributes;
  2343 
  2344 
  2345     int line_num;
  2346     std::istringstream line;
  2347     
  2348   public:
  2349 
  2350     /// \brief Constructor
  2351     ///
  2352     /// Construct an \e LGF contents reader, which reads from the given
  2353     /// input stream.
  2354     LgfContents(std::istream& is) 
  2355       : _is(&is), local_is(false) {}
  2356 
  2357     /// \brief Constructor
  2358     ///
  2359     /// Construct an \e LGF contents reader, which reads from the given
  2360     /// file.
  2361     LgfContents(const std::string& fn) 
  2362       : _is(new std::ifstream(fn.c_str())), local_is(true) {}
  2363 
  2364     /// \brief Constructor
  2365     ///
  2366     /// Construct an \e LGF contents reader, which reads from the given
  2367     /// file.
  2368     LgfContents(const char* fn)
  2369       : _is(new std::ifstream(fn)), local_is(true) {}
  2370     
  2371     /// \brief Destructor
  2372     ~LgfContents() {
  2373       if (local_is) delete _is;
  2374     }
  2375 
  2376   private:
  2377     
  2378     LgfContents(const LgfContents&);
  2379     LgfContents& operator=(const LgfContents&);
  2380 
  2381   public:
  2382 
  2383 
  2384     /// \name Node sections
  2385     /// @{
  2386 
  2387     /// \brief Gives back the number of node sections in the file.
  2388     ///
  2389     /// Gives back the number of node sections in the file.
  2390     int nodeSectionNum() const {
  2391       return _node_sections.size();
  2392     }
  2393 
  2394     /// \brief Returns the node section name at the given position. 
  2395     ///
  2396     /// Returns the node section name at the given position. 
  2397     const std::string& nodeSection(int i) const {
  2398       return _node_sections[i];
  2399     }
  2400 
  2401     /// \brief Gives back the node maps for the given section.
  2402     ///
  2403     /// Gives back the node maps for the given section.
  2404     const std::vector<std::string>& nodeMapNames(int i) const {
  2405       return _node_maps[i];
  2406     }
  2407 
  2408     /// @}
  2409 
  2410     /// \name Arc/Edge sections 
  2411     /// @{
  2412 
  2413     /// \brief Gives back the number of arc/edge sections in the file.
  2414     ///
  2415     /// Gives back the number of arc/edge sections in the file.
  2416     /// \note It is synonym of \c edgeSectionNum().
  2417     int arcSectionNum() const {
  2418       return _edge_sections.size();
  2419     }
  2420 
  2421     /// \brief Returns the arc/edge section name at the given position. 
  2422     ///
  2423     /// Returns the arc/edge section name at the given position. 
  2424     /// \note It is synonym of \c edgeSection().
  2425     const std::string& arcSection(int i) const {
  2426       return _edge_sections[i];
  2427     }
  2428 
  2429     /// \brief Gives back the arc/edge maps for the given section.
  2430     ///
  2431     /// Gives back the arc/edge maps for the given section.
  2432     /// \note It is synonym of \c edgeMapNames().
  2433     const std::vector<std::string>& arcMapNames(int i) const {
  2434       return _edge_maps[i];
  2435     }
  2436 
  2437     /// @}
  2438 
  2439     /// \name Synonyms
  2440     /// @{
  2441 
  2442     /// \brief Gives back the number of arc/edge sections in the file.
  2443     ///
  2444     /// Gives back the number of arc/edge sections in the file.
  2445     /// \note It is synonym of \c arcSectionNum().
  2446     int edgeSectionNum() const {
  2447       return _edge_sections.size();
  2448     }
  2449 
  2450     /// \brief Returns the section name at the given position. 
  2451     ///
  2452     /// Returns the section name at the given position. 
  2453     /// \note It is synonym of \c arcSection().
  2454     const std::string& edgeSection(int i) const {
  2455       return _edge_sections[i];
  2456     }
  2457 
  2458     /// \brief Gives back the edge maps for the given section.
  2459     ///
  2460     /// Gives back the edge maps for the given section.
  2461     /// \note It is synonym of \c arcMapNames().
  2462     const std::vector<std::string>& edgeMapNames(int i) const {
  2463       return _edge_maps[i];
  2464     }
  2465 
  2466     /// @}
  2467 
  2468     /// \name Attribute sections   
  2469     /// @{
  2470 
  2471     /// \brief Gives back the number of attribute sections in the file.
  2472     ///
  2473     /// Gives back the number of attribute sections in the file.
  2474     int attributeSectionNum() const {
  2475       return _attribute_sections.size();
  2476     }
  2477 
  2478     /// \brief Returns the attribute section name at the given position. 
  2479     ///
  2480     /// Returns the attribute section name at the given position. 
  2481     const std::string& attributeSectionNames(int i) const {
  2482       return _attribute_sections[i];
  2483     }
  2484 
  2485     /// \brief Gives back the attributes for the given section.
  2486     ///
  2487     /// Gives back the attributes for the given section.
  2488     const std::vector<std::string>& attributes(int i) const {
  2489       return _attributes[i];
  2490     }
  2491 
  2492     /// @}
  2493 
  2494     /// \name Extra sections   
  2495     /// @{
  2496 
  2497     /// \brief Gives back the number of extra sections in the file.
  2498     ///
  2499     /// Gives back the number of extra sections in the file.
  2500     int extraSectionNum() const {
  2501       return _extra_sections.size();
  2502     }
  2503 
  2504     /// \brief Returns the extra section type at the given position. 
  2505     ///
  2506     /// Returns the section type at the given position. 
  2507     const std::string& extraSection(int i) const {
  2508       return _extra_sections[i];
  2509     }
  2510 
  2511     /// @}
  2512 
  2513   private:
  2514 
  2515     bool readLine() {
  2516       std::string str;
  2517       while(++line_num, std::getline(*_is, str)) {
  2518 	line.clear(); line.str(str);
  2519 	char c;
  2520 	if (line >> std::ws >> c && c != '#') {
  2521 	  line.putback(c);
  2522 	  return true;
  2523 	}
  2524       }
  2525       return false;
  2526     }
  2527 
  2528     bool readSuccess() {
  2529       return static_cast<bool>(*_is);
  2530     }
  2531 
  2532     void skipSection() {
  2533       char c;
  2534       while (readSuccess() && line >> c && c != '@') {
  2535 	readLine();
  2536       }
  2537       line.putback(c);
  2538     }
  2539 
  2540     void readMaps(std::vector<std::string>& maps) {
  2541       char c;
  2542       if (!readLine() || !(line >> c) || c == '@') {
  2543 	if (readSuccess() && line) line.putback(c);
  2544 	return;
  2545       }
  2546       line.putback(c);
  2547       std::string map;
  2548       while (_reader_bits::readToken(line, map)) {
  2549 	maps.push_back(map);
  2550       }
  2551     }
  2552 
  2553     void readAttributes(std::vector<std::string>& attrs) {
  2554       readLine();
  2555       char c;
  2556       while (readSuccess() && line >> c && c != '@') {
  2557 	line.putback(c);
  2558 	std::string attr;
  2559 	_reader_bits::readToken(line, attr);
  2560 	attrs.push_back(attr);
  2561 	readLine();
  2562       }
  2563       line.putback(c);
  2564     }
  2565 
  2566   public:
  2567 
  2568     /// \name Execution of the contents reader    
  2569     /// @{
  2570 
  2571     /// \brief Starts the reading
  2572     ///
  2573     /// This function starts the reading.
  2574     void run() {
  2575 
  2576       readLine();
  2577       skipSection();
  2578 
  2579       while (readSuccess()) {
  2580 
  2581 	char c;
  2582 	line >> c;
  2583 
  2584 	std::string section, caption;
  2585 	_reader_bits::readToken(line, section);
  2586 	_reader_bits::readToken(line, caption);
  2587 
  2588 	if (section == "nodes") {
  2589 	  _node_sections.push_back(caption);
  2590 	  _node_maps.push_back(std::vector<std::string>());
  2591 	  readMaps(_node_maps.back());
  2592 	  readLine(); skipSection();
  2593 	} else if (section == "arcs" || section == "edges") {
  2594 	  _edge_sections.push_back(caption);
  2595 	  _arc_sections.push_back(section == "arcs");
  2596 	  _edge_maps.push_back(std::vector<std::string>());
  2597 	  readMaps(_edge_maps.back());
  2598 	  readLine(); skipSection();
  2599 	} else if (section == "attributes") {
  2600 	  _attribute_sections.push_back(caption);
  2601 	  _attributes.push_back(std::vector<std::string>());
  2602 	  readAttributes(_attributes.back());
  2603 	} else {
  2604 	  _extra_sections.push_back(section);
  2605 	  readLine(); skipSection();
  2606 	}
  2607       }
  2608     }
  2609 
  2610     /// @}
  2611     
  2612   };
  2613 }
  2614 
  2615 #endif