lemon/lgf_reader.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Jun 2008 22:05:23 +0200
changeset 171 02f4d5d9bfd7
parent 163 c82fd9568d75
child 172 c94a80f38d7f
child 173 b026e9779b28
permissions -rw-r--r--
Improve and redesign test programs + unify their output (ticket #25)
- Move graph related utilities form test_tools.h to graph_test.h.
- Move the contents of graph_utils_test.h to graph_utils_test.cc.
- Rename map_test.h -> graph_maps_test.h.
- Rename digraph_test.h -> graph_test.h.
- Many improvements in the following files:
* digraph_test.cc
* graph_test.cc
* graph_test.h
* graph_maps_test.h
* graph_utils_test.cc
* bfs_test.cc
* dfs_test.cc
* counter_test.cc
- Test programs print messages only if it really seems necessary.
- Remove \file commands form .cc test files.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup lemon_io
    20 ///\file
    21 ///\brief Lemon Graph Format reader.
    22 
    23 
    24 #ifndef LEMON_LGF_READER_H
    25 #define LEMON_LGF_READER_H
    26 
    27 #include <iostream>
    28 #include <fstream>
    29 #include <sstream>
    30 
    31 #include <set>
    32 #include <map>
    33 
    34 #include <lemon/assert.h>
    35 #include <lemon/graph_utils.h>
    36 
    37 #include <lemon/lgf_writer.h>
    38 
    39 #include <lemon/concept_check.h>
    40 #include <lemon/concepts/maps.h>
    41 
    42 namespace lemon {
    43 
    44   namespace _reader_bits {
    45 
    46     template <typename Value>
    47     struct DefaultConverter {
    48       Value operator()(const std::string& str) {
    49 	std::istringstream is(str);
    50 	Value value;
    51 	is >> value;
    52 
    53 	char c;
    54 	if (is >> std::ws >> c) {
    55 	  throw DataFormatError("Remaining characters in token");
    56 	}
    57 	return value;
    58       }
    59     };
    60 
    61     template <>
    62     struct DefaultConverter<std::string> {
    63       std::string operator()(const std::string& str) {
    64 	return str;
    65       }
    66     };
    67 
    68     template <typename _Item>    
    69     class MapStorageBase {
    70     public:
    71       typedef _Item Item;
    72 
    73     public:
    74       MapStorageBase() {}
    75       virtual ~MapStorageBase() {}
    76 
    77       virtual void set(const Item& item, const std::string& value) = 0;
    78 
    79     };
    80 
    81     template <typename _Item, typename _Map, 
    82 	      typename _Converter = DefaultConverter<typename _Map::Value> >
    83     class MapStorage : public MapStorageBase<_Item> {
    84     public:
    85       typedef _Map Map;
    86       typedef _Converter Converter;
    87       typedef _Item Item;
    88       
    89     private:
    90       Map& _map;
    91       Converter _converter;
    92 
    93     public:
    94       MapStorage(Map& map, const Converter& converter = Converter()) 
    95 	: _map(map), _converter(converter) {}
    96       virtual ~MapStorage() {}
    97 
    98       virtual void set(const Item& item ,const std::string& value) {
    99 	_map.set(item, _converter(value));
   100       }
   101     };
   102 
   103     template <typename _Graph, bool _dir, typename _Map, 
   104 	      typename _Converter = DefaultConverter<typename _Map::Value> >
   105     class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
   106     public:
   107       typedef _Map Map;
   108       typedef _Converter Converter;
   109       typedef _Graph Graph;
   110       typedef typename Graph::Edge Item;
   111       static const bool dir = _dir;
   112       
   113     private:
   114       const Graph& _graph;
   115       Map& _map;
   116       Converter _converter;
   117 
   118     public:
   119       GraphArcMapStorage(const Graph& graph, Map& map, 
   120 			 const Converter& converter = Converter()) 
   121 	: _graph(graph), _map(map), _converter(converter) {}
   122       virtual ~GraphArcMapStorage() {}
   123 
   124       virtual void set(const Item& item ,const std::string& value) {
   125 	_map.set(_graph.direct(item, dir), _converter(value));
   126       }
   127     };
   128 
   129     class ValueStorageBase {
   130     public:
   131       ValueStorageBase() {}
   132       virtual ~ValueStorageBase() {}
   133 
   134       virtual void set(const std::string&) = 0;
   135     };
   136 
   137     template <typename _Value, typename _Converter = DefaultConverter<_Value> >
   138     class ValueStorage : public ValueStorageBase {
   139     public:
   140       typedef _Value Value;
   141       typedef _Converter Converter;
   142 
   143     private:
   144       Value& _value;
   145       Converter _converter;
   146 
   147     public:
   148       ValueStorage(Value& value, const Converter& converter = Converter())
   149  	: _value(value), _converter(converter) {}
   150 
   151       virtual void set(const std::string& value) {
   152 	_value = _converter(value);
   153       }
   154     };
   155 
   156     template <typename Value>
   157     struct MapLookUpConverter {
   158       const std::map<std::string, Value>& _map;
   159 
   160       MapLookUpConverter(const std::map<std::string, Value>& map)
   161         : _map(map) {}
   162 
   163       Value operator()(const std::string& str) {
   164         typename std::map<std::string, Value>::const_iterator it =
   165           _map.find(str);
   166         if (it == _map.end()) {
   167           std::ostringstream msg;
   168           msg << "Item not found: " << str;
   169           throw DataFormatError(msg.str().c_str());
   170         }
   171         return it->second;
   172       }
   173     };
   174 
   175     template <typename Graph>
   176     struct GraphArcLookUpConverter {
   177       const Graph& _graph;
   178       const std::map<std::string, typename Graph::Edge>& _map;
   179       
   180       GraphArcLookUpConverter(const Graph& graph, 
   181 			      const std::map<std::string,
   182 			                     typename Graph::Edge>& map) 
   183 	: _graph(graph), _map(map) {}
   184       
   185       typename Graph::Arc operator()(const std::string& str) {
   186 	if (str.empty() || (str[0] != '+' && str[0] != '-')) {
   187 	  throw DataFormatError("Item must start with '+' or '-'");
   188 	}
   189 	typename std::map<std::string, typename Graph::Edge>
   190 	  ::const_iterator it = _map.find(str.substr(1));
   191 	if (it == _map.end()) {
   192 	  throw DataFormatError("Item not found");
   193 	}
   194 	return _graph.direct(it->second, str[0] == '+');
   195       }
   196     };
   197 
   198     bool isWhiteSpace(char c) {
   199       return c == ' ' || c == '\t' || c == '\v' || 
   200         c == '\n' || c == '\r' || c == '\f'; 
   201     }
   202     
   203     bool isOct(char c) {
   204       return '0' <= c && c <='7'; 
   205     }
   206     
   207     int valueOct(char c) {
   208       LEMON_ASSERT(isOct(c), "The character is not octal.");
   209       return c - '0';
   210     }
   211 
   212     bool isHex(char c) {
   213       return ('0' <= c && c <= '9') || 
   214 	('a' <= c && c <= 'z') || 
   215 	('A' <= c && c <= 'Z'); 
   216     }
   217     
   218     int valueHex(char c) {
   219       LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
   220       if ('0' <= c && c <= '9') return c - '0';
   221       if ('a' <= c && c <= 'z') return c - 'a' + 10;
   222       return c - 'A' + 10;
   223     }
   224 
   225     bool isIdentifierFirstChar(char c) {
   226       return ('a' <= c && c <= 'z') ||
   227 	('A' <= c && c <= 'Z') || c == '_';
   228     }
   229 
   230     bool isIdentifierChar(char c) {
   231       return isIdentifierFirstChar(c) ||
   232 	('0' <= c && c <= '9');
   233     }
   234 
   235     char readEscape(std::istream& is) {
   236       char c;
   237       if (!is.get(c))
   238 	throw DataFormatError("Escape format error");
   239 
   240       switch (c) {
   241       case '\\':
   242 	return '\\';
   243       case '\"':
   244 	return '\"';
   245       case '\'':
   246 	return '\'';
   247       case '\?':
   248 	return '\?';
   249       case 'a':
   250 	return '\a';
   251       case 'b':
   252 	return '\b';
   253       case 'f':
   254 	return '\f';
   255       case 'n':
   256 	return '\n';
   257       case 'r':
   258 	return '\r';
   259       case 't':
   260 	return '\t';
   261       case 'v':
   262 	return '\v';
   263       case 'x':
   264 	{
   265 	  int code;
   266 	  if (!is.get(c) || !isHex(c)) 
   267 	    throw DataFormatError("Escape format error");
   268 	  else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
   269 	  else code = code * 16 + valueHex(c);
   270 	  return code;
   271 	}
   272       default:
   273 	{
   274 	  int code;
   275 	  if (!isOct(c)) 
   276 	    throw DataFormatError("Escape format error");
   277 	  else if (code = valueOct(c), !is.get(c) || !isOct(c)) 
   278 	    is.putback(c);
   279 	  else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 
   280 	    is.putback(c);
   281 	  else code = code * 8 + valueOct(c);
   282 	  return code;
   283 	}	      
   284       } 
   285     }
   286     
   287     std::istream& readToken(std::istream& is, std::string& str) {
   288       std::ostringstream os;
   289 
   290       char c;
   291       is >> std::ws;
   292       
   293       if (!is.get(c)) 
   294 	return is;
   295 
   296       if (c == '\"') {
   297 	while (is.get(c) && c != '\"') {
   298 	  if (c == '\\') 
   299 	    c = readEscape(is);
   300 	  os << c;
   301 	}
   302 	if (!is) 
   303 	  throw DataFormatError("Quoted format error");
   304       } else {
   305 	is.putback(c);
   306 	while (is.get(c) && !isWhiteSpace(c)) {
   307 	  if (c == '\\') 
   308 	    c = readEscape(is);
   309 	  os << c;
   310 	}
   311 	if (!is) {
   312 	  is.clear();
   313 	} else {
   314 	  is.putback(c);
   315 	}
   316       }
   317       str = os.str();
   318       return is;
   319     }
   320 
   321     class Section {
   322     public:
   323       virtual ~Section() {}
   324       virtual void process(std::istream& is, int& line_num) = 0;
   325     };
   326 
   327     template <typename Functor>
   328     class LineSection : public Section {
   329     private:
   330 
   331       Functor _functor;
   332 
   333     public:
   334       
   335       LineSection(const Functor& functor) : _functor(functor) {}
   336       virtual ~LineSection() {}
   337 
   338       virtual void process(std::istream& is, int& line_num) {
   339 	char c;
   340 	std::string line;
   341 	while (is.get(c) && c != '@') {
   342 	  if (c == '\n') {
   343 	    ++line_num;
   344 	  } else if (c == '#') {
   345 	    getline(is, line);
   346 	    ++line_num;
   347 	  } else if (!isWhiteSpace(c)) {
   348 	    is.putback(c);
   349 	    getline(is, line);
   350 	    _functor(line);
   351 	    ++line_num;
   352 	  }
   353 	}
   354 	if (is) is.putback(c);
   355 	else if (is.eof()) is.clear();
   356       }
   357     };
   358 
   359     template <typename Functor>
   360     class StreamSection : public Section {
   361     private:
   362 
   363       Functor _functor;
   364 
   365     public:
   366       
   367       StreamSection(const Functor& functor) : _functor(functor) {}
   368       virtual ~StreamSection() {} 
   369 
   370       virtual void process(std::istream& is, int& line_num) {
   371 	_functor(is, line_num);
   372 	char c;
   373 	std::string line;
   374 	while (is.get(c) && c != '@') {
   375 	  if (c == '\n') {
   376 	    ++line_num;
   377 	  } else if (!isWhiteSpace(c)) {
   378 	    getline(is, line);
   379 	    ++line_num;
   380 	  }
   381 	}
   382 	if (is) is.putback(c);
   383 	else if (is.eof()) is.clear();	
   384       }
   385     };
   386     
   387   }
   388 
   389   /// \ingroup lemon_io
   390   ///  
   391   /// \brief LGF reader for directed graphs
   392   ///
   393   /// This utility reads an \ref lgf-format "LGF" file.
   394   ///
   395   /// The reading method does a batch processing. The user creates a
   396   /// reader object, then various reading rules can be added to the
   397   /// reader, and eventually the reading is executed with the \c run()
   398   /// member function. A map reading rule can be added to the reader
   399   /// with the \c nodeMap() or \c arcMap() members. An optional
   400   /// converter parameter can also be added as a standard functor
   401   /// converting from std::string to the value type of the map. If it
   402   /// is set, it will determine how the tokens in the file should be
   403   /// is converted to the map's value type. If the functor is not set,
   404   /// then a default conversion will be used. One map can be read into
   405   /// multiple map objects at the same time. The \c attribute(), \c
   406   /// node() and \c arc() functions are used to add attribute reading
   407   /// rules.
   408   ///
   409   ///\code
   410   ///     DigraphReader<Digraph>(std::cin, digraph).
   411   ///       nodeMap("coordinates", coord_map).
   412   ///       arcMap("capacity", cap_map).
   413   ///       node("source", src).
   414   ///       node("target", trg).
   415   ///       attribute("caption", caption).
   416   ///       run();
   417   ///\endcode
   418   ///
   419   /// By default the reader uses the first section in the file of the
   420   /// proper type. If a section has an optional name, then it can be
   421   /// selected for reading by giving an optional name parameter to the
   422   /// \c nodes(), \c arcs() or \c attributes() functions. The readers
   423   /// also can load extra sections with the \c sectionLines() and
   424   /// sectionStream() functions.
   425   ///
   426   /// The \c useNodes() and \c useArcs() functions are used to tell the reader
   427   /// that the nodes or arcs should not be constructed (added to the
   428   /// graph) during the reading, but instead the label map of the items
   429   /// are given as a parameter of these functions. An
   430   /// application of these function is multipass reading, which is
   431   /// important if two \e \@arcs sections must be read from the
   432   /// file. In this example the first phase would read the node set and one
   433   /// of the arc sets, while the second phase would read the second arc
   434   /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
   435   /// The previously read label node map should be passed to the \c
   436   /// useNodes() functions. Another application of multipass reading when
   437   /// paths are given as a node map or an arc map. It is impossible read this in
   438   /// a single pass, because the arcs are not constructed when the node
   439   /// maps are read.
   440   template <typename _Digraph>
   441   class DigraphReader {
   442   public:
   443 
   444     typedef _Digraph Digraph;
   445     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   446     
   447   private:
   448 
   449 
   450     std::istream* _is;
   451     bool local_is;
   452 
   453     Digraph& _digraph;
   454 
   455     std::string _nodes_caption;
   456     std::string _arcs_caption;
   457     std::string _attributes_caption;
   458 
   459     typedef std::map<std::string, Node> NodeIndex;
   460     NodeIndex _node_index;
   461     typedef std::map<std::string, Arc> ArcIndex;
   462     ArcIndex _arc_index;
   463     
   464     typedef std::vector<std::pair<std::string, 
   465       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
   466     NodeMaps _node_maps; 
   467 
   468     typedef std::vector<std::pair<std::string,
   469       _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
   470     ArcMaps _arc_maps;
   471 
   472     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
   473       Attributes;
   474     Attributes _attributes;
   475 
   476     typedef std::map<std::string, _reader_bits::Section*> Sections;
   477     Sections _sections;
   478 
   479     bool _use_nodes;
   480     bool _use_arcs;
   481 
   482     int line_num;
   483     std::istringstream line;
   484 
   485   public:
   486 
   487     /// \brief Constructor
   488     ///
   489     /// Construct a directed graph reader, which reads from the given
   490     /// input stream.
   491     DigraphReader(std::istream& is, Digraph& digraph) 
   492       : _is(&is), local_is(false), _digraph(digraph),
   493 	_use_nodes(false), _use_arcs(false) {}
   494 
   495     /// \brief Constructor
   496     ///
   497     /// Construct a directed graph reader, which reads from the given
   498     /// file.
   499     DigraphReader(const std::string& fn, Digraph& digraph) 
   500       : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
   501     	_use_nodes(false), _use_arcs(false) {}
   502     
   503     /// \brief Constructor
   504     ///
   505     /// Construct a directed graph reader, which reads from the given
   506     /// file.
   507     DigraphReader(const char* fn, Digraph& digraph) 
   508       : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
   509     	_use_nodes(false), _use_arcs(false) {}
   510 
   511     /// \brief Copy constructor
   512     ///
   513     /// The copy constructor transfers all data from the other reader,
   514     /// therefore the copied reader will not be usable more. 
   515     DigraphReader(DigraphReader& other) 
   516       : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
   517 	_use_nodes(other._use_nodes), _use_arcs(other._use_arcs) {
   518 
   519       other._is = 0;
   520       other.local_is = false;
   521       
   522       _node_index.swap(other._node_index);
   523       _arc_index.swap(other._arc_index);
   524 
   525       _node_maps.swap(other._node_maps);
   526       _arc_maps.swap(other._arc_maps);
   527       _attributes.swap(other._attributes);
   528 
   529       _nodes_caption = other._nodes_caption;
   530       _arcs_caption = other._arcs_caption;
   531       _attributes_caption = other._attributes_caption;
   532 
   533       _sections.swap(other._sections);
   534     }
   535 
   536     /// \brief Destructor
   537     ~DigraphReader() {
   538       for (typename NodeMaps::iterator it = _node_maps.begin(); 
   539 	   it != _node_maps.end(); ++it) {
   540 	delete it->second;
   541       }
   542 
   543       for (typename ArcMaps::iterator it = _arc_maps.begin(); 
   544 	   it != _arc_maps.end(); ++it) {
   545 	delete it->second;
   546       }
   547 
   548       for (typename Attributes::iterator it = _attributes.begin(); 
   549 	   it != _attributes.end(); ++it) {
   550 	delete it->second;
   551       }
   552 
   553       for (typename Sections::iterator it = _sections.begin(); 
   554 	   it != _sections.end(); ++it) {
   555 	delete it->second;
   556       }
   557 
   558       if (local_is) {
   559 	delete _is;
   560       }
   561 
   562     }
   563 
   564   private:
   565     
   566     DigraphReader& operator=(const DigraphReader&);
   567 
   568   public:
   569 
   570     /// \name Reading rules
   571     /// @{
   572     
   573     /// \brief Node map reading rule
   574     ///
   575     /// Add a node map reading rule to the reader.
   576     template <typename Map>
   577     DigraphReader& nodeMap(const std::string& caption, Map& map) {
   578       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
   579       _reader_bits::MapStorageBase<Node>* storage = 
   580 	new _reader_bits::MapStorage<Node, Map>(map);
   581       _node_maps.push_back(std::make_pair(caption, storage));
   582       return *this;
   583     }
   584 
   585     /// \brief Node map reading rule
   586     ///
   587     /// Add a node map reading rule with specialized converter to the
   588     /// reader.
   589     template <typename Map, typename Converter>
   590     DigraphReader& nodeMap(const std::string& caption, Map& map, 
   591 			   const Converter& converter = Converter()) {
   592       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
   593       _reader_bits::MapStorageBase<Node>* storage = 
   594 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
   595       _node_maps.push_back(std::make_pair(caption, storage));
   596       return *this;
   597     }
   598 
   599     /// \brief Arc map reading rule
   600     ///
   601     /// Add an arc map reading rule to the reader.
   602     template <typename Map>
   603     DigraphReader& arcMap(const std::string& caption, Map& map) {
   604       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
   605       _reader_bits::MapStorageBase<Arc>* storage = 
   606 	new _reader_bits::MapStorage<Arc, Map>(map);
   607       _arc_maps.push_back(std::make_pair(caption, storage));
   608       return *this;
   609     }
   610 
   611     /// \brief Arc map reading rule
   612     ///
   613     /// Add an arc map reading rule with specialized converter to the
   614     /// reader.
   615     template <typename Map, typename Converter>
   616     DigraphReader& arcMap(const std::string& caption, Map& map, 
   617 			  const Converter& converter = Converter()) {
   618       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
   619       _reader_bits::MapStorageBase<Arc>* storage = 
   620 	new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
   621       _arc_maps.push_back(std::make_pair(caption, storage));
   622       return *this;
   623     }
   624 
   625     /// \brief Attribute reading rule
   626     ///
   627     /// Add an attribute reading rule to the reader.
   628     template <typename Value>
   629     DigraphReader& attribute(const std::string& caption, Value& value) {
   630       _reader_bits::ValueStorageBase* storage = 
   631 	new _reader_bits::ValueStorage<Value>(value);
   632       _attributes.insert(std::make_pair(caption, storage));
   633       return *this;
   634     }
   635 
   636     /// \brief Attribute reading rule
   637     ///
   638     /// Add an attribute reading rule with specialized converter to the
   639     /// reader.
   640     template <typename Value, typename Converter>
   641     DigraphReader& attribute(const std::string& caption, Value& value, 
   642 			     const Converter& converter = Converter()) {
   643       _reader_bits::ValueStorageBase* storage = 
   644 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
   645       _attributes.insert(std::make_pair(caption, storage));
   646       return *this;
   647     }
   648 
   649     /// \brief Node reading rule
   650     ///
   651     /// Add a node reading rule to reader.
   652     DigraphReader& node(const std::string& caption, Node& node) {
   653       typedef _reader_bits::MapLookUpConverter<Node> Converter;
   654       Converter converter(_node_index);
   655       _reader_bits::ValueStorageBase* storage = 
   656 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
   657       _attributes.insert(std::make_pair(caption, storage));
   658       return *this;
   659     }
   660 
   661     /// \brief Arc reading rule
   662     ///
   663     /// Add an arc reading rule to reader.
   664     DigraphReader& arc(const std::string& caption, Arc& arc) {
   665       typedef _reader_bits::MapLookUpConverter<Arc> Converter;
   666       Converter converter(_arc_index);
   667       _reader_bits::ValueStorageBase* storage = 
   668 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
   669       _attributes.insert(std::make_pair(caption, storage));
   670       return *this;
   671     }
   672 
   673     /// @}
   674 
   675     /// \name Select section by name
   676     /// @{
   677 
   678     /// \brief Set \c \@nodes section to be read
   679     ///
   680     /// Set \c \@nodes section to be read
   681     DigraphReader& nodes(const std::string& caption) {
   682       _nodes_caption = caption;
   683       return *this;
   684     }
   685 
   686     /// \brief Set \c \@arcs section to be read
   687     ///
   688     /// Set \c \@arcs section to be read
   689     DigraphReader& arcs(const std::string& caption) {
   690       _arcs_caption = caption;
   691       return *this;
   692     }
   693 
   694     /// \brief Set \c \@attributes section to be read
   695     ///
   696     /// Set \c \@attributes section to be read
   697     DigraphReader& attributes(const std::string& caption) {
   698       _attributes_caption = caption;
   699       return *this;
   700     }
   701 
   702     /// @}
   703 
   704     /// \name Section readers
   705     /// @{
   706 
   707     /// \brief Add a section processor with line oriented reading
   708     ///
   709     /// In the \e LGF file extra sections can be placed, which contain
   710     /// any data in arbitrary format. These sections can be read with
   711     /// this function line by line. The first parameter is the type
   712     /// descriptor of the section, the second is a functor, which
   713     /// takes just one \c std::string parameter. At the reading
   714     /// process, each line of the section will be given to the functor
   715     /// object. However, the empty lines and the comment lines are
   716     /// filtered out, and the leading whitespaces are stipped from
   717     /// each processed string.
   718     ///
   719     /// For example let's see a section, which contain several
   720     /// integers, which should be inserted into a vector.
   721     ///\code
   722     ///  @numbers
   723     ///  12 45 23
   724     ///  4
   725     ///  23 6
   726     ///\endcode
   727     ///
   728     /// The functor is implemented as an struct:
   729     ///\code
   730     ///  struct NumberSection {
   731     ///    std::vector<int>& _data;
   732     ///    NumberSection(std::vector<int>& data) : _data(data) {}
   733     ///    void operator()(const std::string& line) {
   734     ///      std::istringstream ls(line);
   735     ///      int value;
   736     ///      while (ls >> value) _data.push_back(value);
   737     ///    }
   738     ///  };
   739     ///
   740     ///  // ...
   741     ///
   742     ///  reader.sectionLines("numbers", NumberSection(vec));  
   743     ///\endcode
   744     template <typename Functor>
   745     DigraphReader& sectionLines(const std::string& type, Functor functor) {
   746       LEMON_ASSERT(!type.empty(), "Type is not empty.");
   747       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
   748 		   "Multiple reading of section.");
   749       LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
   750 		   type != "attributes", "Multiple reading of section.");
   751       _sections.insert(std::make_pair(type, 
   752         new _reader_bits::LineSection<Functor>(functor)));
   753       return *this;
   754     }
   755 
   756 
   757     /// \brief Add a section processor with stream oriented reading
   758     ///
   759     /// In the \e LGF file extra sections can be placed, which contain
   760     /// any data in arbitrary format. These sections can be read
   761     /// directly with this function. The first parameter is the type
   762     /// of the section, the second is a functor, which takes an \c
   763     /// std::istream& and an int& parameter, the latter regard to the
   764     /// line number of stream. The functor can read the input while
   765     /// the section go on, and the line number should be modified
   766     /// accordingly.
   767     template <typename Functor>
   768     DigraphReader& sectionStream(const std::string& type, Functor functor) {
   769       LEMON_ASSERT(!type.empty(), "Type is not empty.");
   770       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
   771 		   "Multiple reading of section.");
   772       LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
   773 		   type != "attributes", "Multiple reading of section.");
   774       _sections.insert(std::make_pair(type, 
   775 	 new _reader_bits::StreamSection<Functor>(functor)));
   776       return *this;
   777     }    
   778     
   779     /// @}
   780 
   781     /// \name Using previously constructed node or arc set
   782     /// @{
   783 
   784     /// \brief Use previously constructed node set
   785     ///
   786     /// Use previously constructed node set, and specify the node
   787     /// label map.
   788     template <typename Map>
   789     DigraphReader& useNodes(const Map& map) {
   790       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   791       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
   792       _use_nodes = true;
   793       _writer_bits::DefaultConverter<typename Map::Value> converter;
   794       for (NodeIt n(_digraph); n != INVALID; ++n) {
   795 	_node_index.insert(std::make_pair(converter(map[n]), n));
   796       }
   797       return *this;
   798     }
   799 
   800     /// \brief Use previously constructed node set
   801     ///
   802     /// Use previously constructed node set, and specify the node
   803     /// label map and a functor which converts the label map values to
   804     /// std::string.
   805     template <typename Map, typename Converter>
   806     DigraphReader& useNodes(const Map& map, 
   807 			    const Converter& converter = Converter()) {
   808       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   809       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
   810       _use_nodes = true;
   811       for (NodeIt n(_digraph); n != INVALID; ++n) {
   812 	_node_index.insert(std::make_pair(converter(map[n]), n));
   813       }
   814       return *this;
   815     }
   816 
   817     /// \brief Use previously constructed arc set
   818     ///
   819     /// Use previously constructed arc set, and specify the arc
   820     /// label map.
   821     template <typename Map>
   822     DigraphReader& useArcs(const Map& map) {
   823       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   824       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
   825       _use_arcs = true;
   826       _writer_bits::DefaultConverter<typename Map::Value> converter;
   827       for (ArcIt a(_digraph); a != INVALID; ++a) {
   828 	_arc_index.insert(std::make_pair(converter(map[a]), a));
   829       }
   830       return *this;
   831     }
   832 
   833     /// \brief Use previously constructed arc set
   834     ///
   835     /// Use previously constructed arc set, and specify the arc
   836     /// label map and a functor which converts the label map values to
   837     /// std::string.
   838     template <typename Map, typename Converter>
   839     DigraphReader& useArcs(const Map& map, 
   840 			    const Converter& converter = Converter()) {
   841       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   842       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member"); 
   843       _use_arcs = true;
   844       for (ArcIt a(_digraph); a != INVALID; ++a) {
   845 	_arc_index.insert(std::make_pair(converter(map[a]), a));
   846       }
   847       return *this;
   848     }
   849 
   850     /// @}
   851 
   852   private:
   853 
   854     bool readLine() {
   855       std::string str;
   856       while(++line_num, std::getline(*_is, str)) {
   857 	line.clear(); line.str(str);
   858 	char c;
   859 	if (line >> std::ws >> c && c != '#') {
   860 	  line.putback(c);
   861 	  return true;
   862 	}
   863       }
   864       return false;
   865     }
   866 
   867     bool readSuccess() {
   868       return static_cast<bool>(*_is);
   869     }
   870     
   871     void skipSection() {
   872       char c;
   873       while (readSuccess() && line >> c && c != '@') {
   874 	readLine();
   875       }
   876       line.putback(c);
   877     }
   878 
   879     void readNodes() {
   880 
   881       std::vector<int> map_index(_node_maps.size());
   882       int map_num, label_index;
   883 
   884       if (!readLine()) 
   885 	throw DataFormatError("Cannot find map captions");
   886       
   887       {
   888 	std::map<std::string, int> maps;
   889 	
   890 	std::string map;
   891 	int index = 0;
   892 	while (_reader_bits::readToken(line, map)) {
   893 	  if (maps.find(map) != maps.end()) {
   894 	    std::ostringstream msg;
   895 	    msg << "Multiple occurence of node map: " << map;
   896 	    throw DataFormatError(msg.str().c_str());
   897 	  }
   898 	  maps.insert(std::make_pair(map, index));
   899 	  ++index;
   900 	}
   901 	
   902 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   903 	  std::map<std::string, int>::iterator jt = 
   904 	    maps.find(_node_maps[i].first);
   905 	  if (jt == maps.end()) {
   906 	    std::ostringstream msg;
   907 	    msg << "Map not found in file: " << _node_maps[i].first;
   908 	    throw DataFormatError(msg.str().c_str());
   909 	  }
   910 	  map_index[i] = jt->second;
   911 	}
   912 
   913 	{
   914 	  std::map<std::string, int>::iterator jt = maps.find("label");
   915 	  if (jt == maps.end())
   916 	    throw DataFormatError("Label map not found in file");
   917 	  label_index = jt->second;
   918 	}
   919 	map_num = maps.size();
   920       }
   921 
   922       char c;
   923       while (readLine() && line >> c && c != '@') {
   924 	line.putback(c);
   925 
   926 	std::vector<std::string> tokens(map_num);
   927 	for (int i = 0; i < map_num; ++i) {
   928 	  if (!_reader_bits::readToken(line, tokens[i])) {
   929 	    std::ostringstream msg;
   930 	    msg << "Column not found (" << i + 1 << ")";
   931 	    throw DataFormatError(msg.str().c_str());
   932 	  }
   933 	}
   934 	if (line >> std::ws >> c)
   935 	  throw DataFormatError("Extra character on the end of line");
   936 	
   937 	Node n;
   938 	if (!_use_nodes) {
   939 	  n = _digraph.addNode();
   940 	  _node_index.insert(std::make_pair(tokens[label_index], n));
   941 	} else {
   942 	  typename std::map<std::string, Node>::iterator it =
   943 	    _node_index.find(tokens[label_index]);
   944 	  if (it == _node_index.end()) {
   945 	    std::ostringstream msg;
   946 	    msg << "Node with label not found: " << tokens[label_index];
   947 	    throw DataFormatError(msg.str().c_str());	    
   948 	  }
   949 	  n = it->second;
   950 	}
   951 
   952 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   953 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
   954 	}
   955 
   956       }
   957       if (readSuccess()) {
   958 	line.putback(c);
   959       }
   960     }
   961 
   962     void readArcs() {
   963 
   964       std::vector<int> map_index(_arc_maps.size());
   965       int map_num, label_index;
   966 
   967       if (!readLine()) 
   968 	throw DataFormatError("Cannot find map captions");
   969       
   970       {
   971 	std::map<std::string, int> maps;
   972 	
   973 	std::string map;
   974 	int index = 0;
   975 	while (_reader_bits::readToken(line, map)) {
   976 	  if (maps.find(map) != maps.end()) {
   977 	    std::ostringstream msg;
   978 	    msg << "Multiple occurence of arc map: " << map;
   979 	    throw DataFormatError(msg.str().c_str());
   980 	  }
   981 	  maps.insert(std::make_pair(map, index));
   982 	  ++index;
   983 	}
   984 	
   985 	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
   986 	  std::map<std::string, int>::iterator jt = 
   987 	    maps.find(_arc_maps[i].first);
   988 	  if (jt == maps.end()) {
   989 	    std::ostringstream msg;
   990 	    msg << "Map not found in file: " << _arc_maps[i].first;
   991 	    throw DataFormatError(msg.str().c_str());
   992 	  }
   993 	  map_index[i] = jt->second;
   994 	}
   995 
   996 	{
   997 	  std::map<std::string, int>::iterator jt = maps.find("label");
   998 	  if (jt == maps.end())
   999 	    throw DataFormatError("Label map not found in file");
  1000 	  label_index = jt->second;
  1001 	}
  1002 	map_num = maps.size();
  1003       }
  1004 
  1005       char c;
  1006       while (readLine() && line >> c && c != '@') {
  1007 	line.putback(c);
  1008 
  1009 	std::string source_token;
  1010 	std::string target_token;
  1011 
  1012 	if (!_reader_bits::readToken(line, source_token))
  1013 	  throw DataFormatError("Source not found");
  1014 
  1015 	if (!_reader_bits::readToken(line, target_token))
  1016 	  throw DataFormatError("Source not found");
  1017 	
  1018 	std::vector<std::string> tokens(map_num);
  1019 	for (int i = 0; i < map_num; ++i) {
  1020 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1021 	    std::ostringstream msg;
  1022 	    msg << "Column not found (" << i + 1 << ")";
  1023 	    throw DataFormatError(msg.str().c_str());
  1024 	  }
  1025 	}
  1026 	if (line >> std::ws >> c)
  1027 	  throw DataFormatError("Extra character on the end of line");
  1028 	
  1029 	Arc a;
  1030 	if (!_use_arcs) {
  1031 
  1032           typename NodeIndex::iterator it;
  1033  
  1034           it = _node_index.find(source_token);
  1035           if (it == _node_index.end()) {
  1036             std::ostringstream msg;
  1037             msg << "Item not found: " << source_token;
  1038             throw DataFormatError(msg.str().c_str());
  1039           }
  1040           Node source = it->second;
  1041 
  1042           it = _node_index.find(target_token);
  1043           if (it == _node_index.end()) {       
  1044             std::ostringstream msg;            
  1045             msg << "Item not found: " << target_token;
  1046             throw DataFormatError(msg.str().c_str());
  1047           }                                          
  1048           Node target = it->second;                            
  1049 
  1050 	  a = _digraph.addArc(source, target);
  1051 	  _arc_index.insert(std::make_pair(tokens[label_index], a));
  1052 	} else {
  1053 	  typename std::map<std::string, Arc>::iterator it =
  1054 	    _arc_index.find(tokens[label_index]);
  1055 	  if (it == _arc_index.end()) {
  1056 	    std::ostringstream msg;
  1057 	    msg << "Arc with label not found: " << tokens[label_index];
  1058 	    throw DataFormatError(msg.str().c_str());	    
  1059 	  }
  1060 	  a = it->second;
  1061 	}
  1062 
  1063 	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
  1064 	  _arc_maps[i].second->set(a, tokens[map_index[i]]);
  1065 	}
  1066 
  1067       }
  1068       if (readSuccess()) {
  1069 	line.putback(c);
  1070       }
  1071     }
  1072 
  1073     void readAttributes() {
  1074 
  1075       std::set<std::string> read_attr;
  1076 
  1077       char c;
  1078       while (readLine() && line >> c && c != '@') {
  1079 	line.putback(c);
  1080 	
  1081 	std::string attr, token;
  1082 	if (!_reader_bits::readToken(line, attr))
  1083 	  throw DataFormatError("Attribute name not found");
  1084 	if (!_reader_bits::readToken(line, token))
  1085 	  throw DataFormatError("Attribute value not found");
  1086 	if (line >> c)
  1087 	  throw DataFormatError("Extra character on the end of line");	  
  1088 
  1089 	{
  1090 	  std::set<std::string>::iterator it = read_attr.find(attr);
  1091 	  if (it != read_attr.end()) {
  1092 	    std::ostringstream msg;
  1093 	    msg << "Multiple occurence of attribute " << attr;
  1094 	    throw DataFormatError(msg.str().c_str());
  1095 	  }
  1096 	  read_attr.insert(attr);
  1097 	}
  1098 	
  1099 	{
  1100 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
  1101 	  while (it != _attributes.end() && it->first == attr) {
  1102 	    it->second->set(token);
  1103 	    ++it;
  1104 	  }
  1105 	}
  1106 
  1107       }
  1108       if (readSuccess()) {
  1109 	line.putback(c);
  1110       }
  1111       for (typename Attributes::iterator it = _attributes.begin();
  1112 	   it != _attributes.end(); ++it) {
  1113 	if (read_attr.find(it->first) == read_attr.end()) {
  1114 	  std::ostringstream msg;
  1115 	  msg << "Attribute not found in file: " << it->first;
  1116 	  throw DataFormatError(msg.str().c_str());
  1117 	}	
  1118       }
  1119     }
  1120 
  1121   public:
  1122 
  1123     /// \name Execution of the reader    
  1124     /// @{
  1125 
  1126     /// \brief Start the batch processing
  1127     ///
  1128     /// This function starts the batch processing
  1129     void run() {
  1130       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1131       if (!*_is) {
  1132 	throw DataFormatError("Cannot find file");
  1133       }
  1134       
  1135       bool nodes_done = false;
  1136       bool arcs_done = false;
  1137       bool attributes_done = false;
  1138       std::set<std::string> extra_sections;
  1139 
  1140       line_num = 0;      
  1141       readLine();
  1142 
  1143       while (readSuccess()) {
  1144 	skipSection();
  1145 	try {
  1146 	  char c;
  1147 	  std::string section, caption;
  1148 	  line >> c;
  1149 	  _reader_bits::readToken(line, section);
  1150 	  _reader_bits::readToken(line, caption);
  1151 
  1152 	  if (line >> c) 
  1153 	    throw DataFormatError("Extra character on the end of line");
  1154 
  1155 	  if (section == "nodes" && !nodes_done) {
  1156 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
  1157 	      readNodes();
  1158 	      nodes_done = true;
  1159 	    }
  1160 	  } else if ((section == "arcs" || section == "edges") && 
  1161 		     !arcs_done) {
  1162 	    if (_arcs_caption.empty() || _arcs_caption == caption) {
  1163 	      readArcs();
  1164 	      arcs_done = true;
  1165 	    }
  1166 	  } else if (section == "attributes" && !attributes_done) {
  1167 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
  1168 	      readAttributes();
  1169 	      attributes_done = true;
  1170 	    }
  1171 	  } else {
  1172 	    if (extra_sections.find(section) != extra_sections.end()) {
  1173 	      std::ostringstream msg;
  1174 	      msg << "Multiple occurence of section " << section;
  1175 	      throw DataFormatError(msg.str().c_str());
  1176 	    }
  1177 	    Sections::iterator it = _sections.find(section);
  1178 	    if (it != _sections.end()) {
  1179 	      extra_sections.insert(section);
  1180 	      it->second->process(*_is, line_num);
  1181 	      readLine();
  1182 	    } else {
  1183 	      readLine();
  1184 	      skipSection();
  1185 	    }
  1186 	  }
  1187 	} catch (DataFormatError& error) {
  1188 	  error.line(line_num);
  1189 	  throw;
  1190 	}	
  1191       }
  1192 
  1193       if (!nodes_done) {
  1194 	throw DataFormatError("Section @nodes not found");
  1195       }
  1196 
  1197       if (!arcs_done) {
  1198 	throw DataFormatError("Section @arcs not found");
  1199       }
  1200 
  1201       if (!attributes_done && !_attributes.empty()) {
  1202 	throw DataFormatError("Section @attributes not found");
  1203       }
  1204 
  1205     }
  1206 
  1207     /// @}
  1208     
  1209   };
  1210 
  1211   /// \relates DigraphReader
  1212   template <typename Digraph>
  1213   DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
  1214     DigraphReader<Digraph> tmp(is, digraph);
  1215     return tmp;
  1216   }
  1217 
  1218   /// \relates DigraphReader
  1219   template <typename Digraph>
  1220   DigraphReader<Digraph> digraphReader(const std::string& fn, 
  1221 				       Digraph& digraph) {
  1222     DigraphReader<Digraph> tmp(fn, digraph);
  1223     return tmp;
  1224   }
  1225 
  1226   /// \relates DigraphReader
  1227   template <typename Digraph>
  1228   DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
  1229     DigraphReader<Digraph> tmp(fn, digraph);
  1230     return tmp;
  1231   }
  1232 
  1233   /// \ingroup lemon_io
  1234   ///  
  1235   /// \brief LGF reader for undirected graphs
  1236   ///
  1237   /// This utility reads an \ref lgf-format "LGF" file.
  1238   template <typename _Graph>
  1239   class GraphReader {
  1240   public:
  1241 
  1242     typedef _Graph Graph;
  1243     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  1244     
  1245   private:
  1246 
  1247 
  1248     std::istream* _is;
  1249     bool local_is;
  1250 
  1251     Graph& _graph;
  1252 
  1253     std::string _nodes_caption;
  1254     std::string _edges_caption;
  1255     std::string _attributes_caption;
  1256 
  1257     typedef std::map<std::string, Node> NodeIndex;
  1258     NodeIndex _node_index;
  1259     typedef std::map<std::string, Edge> EdgeIndex;
  1260     EdgeIndex _edge_index;
  1261     
  1262     typedef std::vector<std::pair<std::string, 
  1263       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
  1264     NodeMaps _node_maps; 
  1265 
  1266     typedef std::vector<std::pair<std::string,
  1267       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  1268     EdgeMaps _edge_maps;
  1269 
  1270     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
  1271       Attributes;
  1272     Attributes _attributes;
  1273 
  1274     typedef std::map<std::string, _reader_bits::Section*> Sections;
  1275     Sections _sections;
  1276 
  1277     bool _use_nodes;
  1278     bool _use_edges;
  1279 
  1280     int line_num;
  1281     std::istringstream line;
  1282 
  1283   public:
  1284 
  1285     /// \brief Constructor
  1286     ///
  1287     /// Construct a undirected graph reader, which reads from the given
  1288     /// input stream.
  1289     GraphReader(std::istream& is, Graph& graph) 
  1290       : _is(&is), local_is(false), _graph(graph),
  1291 	_use_nodes(false), _use_edges(false) {}
  1292 
  1293     /// \brief Constructor
  1294     ///
  1295     /// Construct a undirected graph reader, which reads from the given
  1296     /// file.
  1297     GraphReader(const std::string& fn, Graph& graph) 
  1298       : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
  1299     	_use_nodes(false), _use_edges(false) {}
  1300     
  1301     /// \brief Constructor
  1302     ///
  1303     /// Construct a undirected graph reader, which reads from the given
  1304     /// file.
  1305     GraphReader(const char* fn, Graph& graph) 
  1306       : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
  1307     	_use_nodes(false), _use_edges(false) {}
  1308 
  1309     /// \brief Copy constructor
  1310     ///
  1311     /// The copy constructor transfers all data from the other reader,
  1312     /// therefore the copied reader will not be usable more. 
  1313     GraphReader(GraphReader& other) 
  1314       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  1315 	_use_nodes(other._use_nodes), _use_edges(other._use_edges) {
  1316 
  1317       other._is = 0;
  1318       other.local_is = false;
  1319       
  1320       _node_index.swap(other._node_index);
  1321       _edge_index.swap(other._edge_index);
  1322 
  1323       _node_maps.swap(other._node_maps);
  1324       _edge_maps.swap(other._edge_maps);
  1325       _attributes.swap(other._attributes);
  1326 
  1327       _nodes_caption = other._nodes_caption;
  1328       _edges_caption = other._edges_caption;
  1329       _attributes_caption = other._attributes_caption;
  1330 
  1331       _sections.swap(other._sections);
  1332     }
  1333 
  1334     /// \brief Destructor
  1335     ~GraphReader() {
  1336       for (typename NodeMaps::iterator it = _node_maps.begin(); 
  1337 	   it != _node_maps.end(); ++it) {
  1338 	delete it->second;
  1339       }
  1340 
  1341       for (typename EdgeMaps::iterator it = _edge_maps.begin(); 
  1342 	   it != _edge_maps.end(); ++it) {
  1343 	delete it->second;
  1344       }
  1345 
  1346       for (typename Attributes::iterator it = _attributes.begin(); 
  1347 	   it != _attributes.end(); ++it) {
  1348 	delete it->second;
  1349       }
  1350 
  1351       for (typename Sections::iterator it = _sections.begin(); 
  1352 	   it != _sections.end(); ++it) {
  1353 	delete it->second;
  1354       }
  1355 
  1356       if (local_is) {
  1357 	delete _is;
  1358       }
  1359 
  1360     }
  1361 
  1362   private:
  1363     
  1364     GraphReader& operator=(const GraphReader&);
  1365 
  1366   public:
  1367 
  1368     /// \name Reading rules
  1369     /// @{
  1370     
  1371     /// \brief Node map reading rule
  1372     ///
  1373     /// Add a node map reading rule to the reader.
  1374     template <typename Map>
  1375     GraphReader& nodeMap(const std::string& caption, Map& map) {
  1376       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1377       _reader_bits::MapStorageBase<Node>* storage = 
  1378 	new _reader_bits::MapStorage<Node, Map>(map);
  1379       _node_maps.push_back(std::make_pair(caption, storage));
  1380       return *this;
  1381     }
  1382 
  1383     /// \brief Node map reading rule
  1384     ///
  1385     /// Add a node map reading rule with specialized converter to the
  1386     /// reader.
  1387     template <typename Map, typename Converter>
  1388     GraphReader& nodeMap(const std::string& caption, Map& map, 
  1389 			   const Converter& converter = Converter()) {
  1390       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1391       _reader_bits::MapStorageBase<Node>* storage = 
  1392 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  1393       _node_maps.push_back(std::make_pair(caption, storage));
  1394       return *this;
  1395     }
  1396 
  1397     /// \brief Edge map reading rule
  1398     ///
  1399     /// Add an edge map reading rule to the reader.
  1400     template <typename Map>
  1401     GraphReader& edgeMap(const std::string& caption, Map& map) {
  1402       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1403       _reader_bits::MapStorageBase<Edge>* storage = 
  1404 	new _reader_bits::MapStorage<Edge, Map>(map);
  1405       _edge_maps.push_back(std::make_pair(caption, storage));
  1406       return *this;
  1407     }
  1408 
  1409     /// \brief Edge map reading rule
  1410     ///
  1411     /// Add an edge map reading rule with specialized converter to the
  1412     /// reader.
  1413     template <typename Map, typename Converter>
  1414     GraphReader& edgeMap(const std::string& caption, Map& map, 
  1415 			  const Converter& converter = Converter()) {
  1416       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1417       _reader_bits::MapStorageBase<Edge>* storage = 
  1418 	new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1419       _edge_maps.push_back(std::make_pair(caption, storage));
  1420       return *this;
  1421     }
  1422 
  1423     /// \brief Arc map reading rule
  1424     ///
  1425     /// Add an arc map reading rule to the reader.
  1426     template <typename Map>
  1427     GraphReader& arcMap(const std::string& caption, Map& map) {
  1428       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1429       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1430 	new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1431       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1432       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1433 	new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1434       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1435       return *this;
  1436     }
  1437 
  1438     /// \brief Arc map reading rule
  1439     ///
  1440     /// Add an arc map reading rule with specialized converter to the
  1441     /// reader.
  1442     template <typename Map, typename Converter>
  1443     GraphReader& arcMap(const std::string& caption, Map& map, 
  1444 			  const Converter& converter = Converter()) {
  1445       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1446       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1447 	new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1448 	(_graph, map, converter);
  1449       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1450       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1451 	new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1452 	(_graph, map, converter);
  1453       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1454       return *this;
  1455     }
  1456 
  1457     /// \brief Attribute reading rule
  1458     ///
  1459     /// Add an attribute reading rule to the reader.
  1460     template <typename Value>
  1461     GraphReader& attribute(const std::string& caption, Value& value) {
  1462       _reader_bits::ValueStorageBase* storage = 
  1463 	new _reader_bits::ValueStorage<Value>(value);
  1464       _attributes.insert(std::make_pair(caption, storage));
  1465       return *this;
  1466     }
  1467 
  1468     /// \brief Attribute reading rule
  1469     ///
  1470     /// Add an attribute reading rule with specialized converter to the
  1471     /// reader.
  1472     template <typename Value, typename Converter>
  1473     GraphReader& attribute(const std::string& caption, Value& value, 
  1474 			     const Converter& converter = Converter()) {
  1475       _reader_bits::ValueStorageBase* storage = 
  1476 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  1477       _attributes.insert(std::make_pair(caption, storage));
  1478       return *this;
  1479     }
  1480 
  1481     /// \brief Node reading rule
  1482     ///
  1483     /// Add a node reading rule to reader.
  1484     GraphReader& node(const std::string& caption, Node& node) {
  1485       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  1486       Converter converter(_node_index);
  1487       _reader_bits::ValueStorageBase* storage = 
  1488 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  1489       _attributes.insert(std::make_pair(caption, storage));
  1490       return *this;
  1491     }
  1492 
  1493     /// \brief Edge reading rule
  1494     ///
  1495     /// Add an edge reading rule to reader.
  1496     GraphReader& edge(const std::string& caption, Edge& edge) {
  1497       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  1498       Converter converter(_edge_index);
  1499       _reader_bits::ValueStorageBase* storage = 
  1500 	new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  1501       _attributes.insert(std::make_pair(caption, storage));
  1502       return *this;
  1503     }
  1504 
  1505     /// \brief Arc reading rule
  1506     ///
  1507     /// Add an arc reading rule to reader.
  1508     GraphReader& arc(const std::string& caption, Arc& arc) {
  1509       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
  1510       Converter converter(_graph, _edge_index);
  1511       _reader_bits::ValueStorageBase* storage = 
  1512 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  1513       _attributes.insert(std::make_pair(caption, storage));
  1514       return *this;
  1515     }
  1516 
  1517     /// @}
  1518 
  1519     /// \name Select section by name
  1520     /// @{
  1521 
  1522     /// \brief Set \c \@nodes section to be read
  1523     ///
  1524     /// Set \c \@nodes section to be read
  1525     GraphReader& nodes(const std::string& caption) {
  1526       _nodes_caption = caption;
  1527       return *this;
  1528     }
  1529 
  1530     /// \brief Set \c \@edges section to be read
  1531     ///
  1532     /// Set \c \@edges section to be read
  1533     GraphReader& edges(const std::string& caption) {
  1534       _edges_caption = caption;
  1535       return *this;
  1536     }
  1537 
  1538     /// \brief Set \c \@attributes section to be read
  1539     ///
  1540     /// Set \c \@attributes section to be read
  1541     GraphReader& attributes(const std::string& caption) {
  1542       _attributes_caption = caption;
  1543       return *this;
  1544     }
  1545 
  1546     /// @}
  1547 
  1548     /// \name Section readers
  1549     /// @{
  1550 
  1551     /// \brief Add a section processor with line oriented reading
  1552     ///
  1553     /// In the \e LGF file extra sections can be placed, which contain
  1554     /// any data in arbitrary format. These sections can be read with
  1555     /// this function line by line. The first parameter is the type
  1556     /// descriptor of the section, the second is a functor, which
  1557     /// takes just one \c std::string parameter. At the reading
  1558     /// process, each line of the section will be given to the functor
  1559     /// object. However, the empty lines and the comment lines are
  1560     /// filtered out, and the leading whitespaces are stipped from
  1561     /// each processed string.
  1562     ///
  1563     /// For example let's see a section, which contain several
  1564     /// integers, which should be inserted into a vector.
  1565     ///\code
  1566     ///  @numbers
  1567     ///  12 45 23
  1568     ///  4
  1569     ///  23 6
  1570     ///\endcode
  1571     ///
  1572     /// The functor is implemented as an struct:
  1573     ///\code
  1574     ///  struct NumberSection {
  1575     ///    std::vector<int>& _data;
  1576     ///    NumberSection(std::vector<int>& data) : _data(data) {}
  1577     ///    void operator()(const std::string& line) {
  1578     ///      std::istringstream ls(line);
  1579     ///      int value;
  1580     ///      while (ls >> value) _data.push_back(value);
  1581     ///    }
  1582     ///  };
  1583     ///
  1584     ///  // ...
  1585     ///
  1586     ///  reader.sectionLines("numbers", NumberSection(vec));  
  1587     ///\endcode
  1588     template <typename Functor>
  1589     GraphReader& sectionLines(const std::string& type, Functor functor) {
  1590       LEMON_ASSERT(!type.empty(), "Type is not empty.");
  1591       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  1592 		   "Multiple reading of section.");
  1593       LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
  1594 		   type != "attributes", "Multiple reading of section.");
  1595       _sections.insert(std::make_pair(type, 
  1596         new _reader_bits::LineSection<Functor>(functor)));
  1597       return *this;
  1598     }
  1599 
  1600 
  1601     /// \brief Add a section processor with stream oriented reading
  1602     ///
  1603     /// In the \e LGF file extra sections can be placed, which contain
  1604     /// any data in arbitrary format. These sections can be read
  1605     /// directly with this function. The first parameter is the type
  1606     /// of the section, the second is a functor, which takes an \c
  1607     /// std::istream& and an int& parameter, the latter regard to the
  1608     /// line number of stream. The functor can read the input while
  1609     /// the section go on, and the line number should be modified
  1610     /// accordingly.
  1611     template <typename Functor>
  1612     GraphReader& sectionStream(const std::string& type, Functor functor) {
  1613       LEMON_ASSERT(!type.empty(), "Type is not empty.");
  1614       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  1615 		   "Multiple reading of section.");
  1616       LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
  1617 		   type != "attributes", "Multiple reading of section.");
  1618       _sections.insert(std::make_pair(type, 
  1619 	 new _reader_bits::StreamSection<Functor>(functor)));
  1620       return *this;
  1621     }    
  1622     
  1623     /// @}
  1624 
  1625     /// \name Using previously constructed node or edge set
  1626     /// @{
  1627 
  1628     /// \brief Use previously constructed node set
  1629     ///
  1630     /// Use previously constructed node set, and specify the node
  1631     /// label map.
  1632     template <typename Map>
  1633     GraphReader& useNodes(const Map& map) {
  1634       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1635       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1636       _use_nodes = true;
  1637       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1638       for (NodeIt n(_graph); n != INVALID; ++n) {
  1639 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1640       }
  1641       return *this;
  1642     }
  1643 
  1644     /// \brief Use previously constructed node set
  1645     ///
  1646     /// Use previously constructed node set, and specify the node
  1647     /// label map and a functor which converts the label map values to
  1648     /// std::string.
  1649     template <typename Map, typename Converter>
  1650     GraphReader& useNodes(const Map& map, 
  1651 			    const Converter& converter = Converter()) {
  1652       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1653       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1654       _use_nodes = true;
  1655       for (NodeIt n(_graph); n != INVALID; ++n) {
  1656 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1657       }
  1658       return *this;
  1659     }
  1660 
  1661     /// \brief Use previously constructed edge set
  1662     ///
  1663     /// Use previously constructed edge set, and specify the edge
  1664     /// label map.
  1665     template <typename Map>
  1666     GraphReader& useEdges(const Map& map) {
  1667       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1668       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1669       _use_edges = true;
  1670       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1671       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1672 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1673       }
  1674       return *this;
  1675     }
  1676 
  1677     /// \brief Use previously constructed edge set
  1678     ///
  1679     /// Use previously constructed edge set, and specify the edge
  1680     /// label map and a functor which converts the label map values to
  1681     /// std::string.
  1682     template <typename Map, typename Converter>
  1683     GraphReader& useEdges(const Map& map, 
  1684 			    const Converter& converter = Converter()) {
  1685       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1686       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 
  1687       _use_edges = true;
  1688       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1689 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1690       }
  1691       return *this;
  1692     }
  1693 
  1694     /// @}
  1695 
  1696   private:
  1697 
  1698     bool readLine() {
  1699       std::string str;
  1700       while(++line_num, std::getline(*_is, str)) {
  1701 	line.clear(); line.str(str);
  1702 	char c;
  1703 	if (line >> std::ws >> c && c != '#') {
  1704 	  line.putback(c);
  1705 	  return true;
  1706 	}
  1707       }
  1708       return false;
  1709     }
  1710 
  1711     bool readSuccess() {
  1712       return static_cast<bool>(*_is);
  1713     }
  1714     
  1715     void skipSection() {
  1716       char c;
  1717       while (readSuccess() && line >> c && c != '@') {
  1718 	readLine();
  1719       }
  1720       line.putback(c);
  1721     }
  1722 
  1723     void readNodes() {
  1724 
  1725       std::vector<int> map_index(_node_maps.size());
  1726       int map_num, label_index;
  1727 
  1728       if (!readLine()) 
  1729 	throw DataFormatError("Cannot find map captions");
  1730       
  1731       {
  1732 	std::map<std::string, int> maps;
  1733 	
  1734 	std::string map;
  1735 	int index = 0;
  1736 	while (_reader_bits::readToken(line, map)) {
  1737 	  if (maps.find(map) != maps.end()) {
  1738 	    std::ostringstream msg;
  1739 	    msg << "Multiple occurence of node map: " << map;
  1740 	    throw DataFormatError(msg.str().c_str());
  1741 	  }
  1742 	  maps.insert(std::make_pair(map, index));
  1743 	  ++index;
  1744 	}
  1745 	
  1746 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1747 	  std::map<std::string, int>::iterator jt = 
  1748 	    maps.find(_node_maps[i].first);
  1749 	  if (jt == maps.end()) {
  1750 	    std::ostringstream msg;
  1751 	    msg << "Map not found in file: " << _node_maps[i].first;
  1752 	    throw DataFormatError(msg.str().c_str());
  1753 	  }
  1754 	  map_index[i] = jt->second;
  1755 	}
  1756 
  1757 	{
  1758 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1759 	  if (jt == maps.end())
  1760 	    throw DataFormatError("Label map not found in file");
  1761 	  label_index = jt->second;
  1762 	}
  1763 	map_num = maps.size();
  1764       }
  1765 
  1766       char c;
  1767       while (readLine() && line >> c && c != '@') {
  1768 	line.putback(c);
  1769 
  1770 	std::vector<std::string> tokens(map_num);
  1771 	for (int i = 0; i < map_num; ++i) {
  1772 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1773 	    std::ostringstream msg;
  1774 	    msg << "Column not found (" << i + 1 << ")";
  1775 	    throw DataFormatError(msg.str().c_str());
  1776 	  }
  1777 	}
  1778 	if (line >> std::ws >> c)
  1779 	  throw DataFormatError("Extra character on the end of line");
  1780 	
  1781 	Node n;
  1782 	if (!_use_nodes) {
  1783 	  n = _graph.addNode();
  1784 	  _node_index.insert(std::make_pair(tokens[label_index], n));
  1785 	} else {
  1786 	  typename std::map<std::string, Node>::iterator it =
  1787 	    _node_index.find(tokens[label_index]);
  1788 	  if (it == _node_index.end()) {
  1789 	    std::ostringstream msg;
  1790 	    msg << "Node with label not found: " << tokens[label_index];
  1791 	    throw DataFormatError(msg.str().c_str());	    
  1792 	  }
  1793 	  n = it->second;
  1794 	}
  1795 
  1796 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1797 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
  1798 	}
  1799 
  1800       }
  1801       if (readSuccess()) {
  1802 	line.putback(c);
  1803       }
  1804     }
  1805 
  1806     void readEdges() {
  1807 
  1808       std::vector<int> map_index(_edge_maps.size());
  1809       int map_num, label_index;
  1810 
  1811       if (!readLine()) 
  1812 	throw DataFormatError("Cannot find map captions");
  1813       
  1814       {
  1815 	std::map<std::string, int> maps;
  1816 	
  1817 	std::string map;
  1818 	int index = 0;
  1819 	while (_reader_bits::readToken(line, map)) {
  1820 	  if (maps.find(map) != maps.end()) {
  1821 	    std::ostringstream msg;
  1822 	    msg << "Multiple occurence of edge map: " << map;
  1823 	    throw DataFormatError(msg.str().c_str());
  1824 	  }
  1825 	  maps.insert(std::make_pair(map, index));
  1826 	  ++index;
  1827 	}
  1828 	
  1829 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1830 	  std::map<std::string, int>::iterator jt = 
  1831 	    maps.find(_edge_maps[i].first);
  1832 	  if (jt == maps.end()) {
  1833 	    std::ostringstream msg;
  1834 	    msg << "Map not found in file: " << _edge_maps[i].first;
  1835 	    throw DataFormatError(msg.str().c_str());
  1836 	  }
  1837 	  map_index[i] = jt->second;
  1838 	}
  1839 
  1840 	{
  1841 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1842 	  if (jt == maps.end())
  1843 	    throw DataFormatError("Label map not found in file");
  1844 	  label_index = jt->second;
  1845 	}
  1846 	map_num = maps.size();
  1847       }
  1848 
  1849       char c;
  1850       while (readLine() && line >> c && c != '@') {
  1851 	line.putback(c);
  1852 
  1853 	std::string source_token;
  1854 	std::string target_token;
  1855 
  1856 	if (!_reader_bits::readToken(line, source_token))
  1857 	  throw DataFormatError("Source not found");
  1858 
  1859 	if (!_reader_bits::readToken(line, target_token))
  1860 	  throw DataFormatError("Source not found");
  1861 	
  1862 	std::vector<std::string> tokens(map_num);
  1863 	for (int i = 0; i < map_num; ++i) {
  1864 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1865 	    std::ostringstream msg;
  1866 	    msg << "Column not found (" << i + 1 << ")";
  1867 	    throw DataFormatError(msg.str().c_str());
  1868 	  }
  1869 	}
  1870 	if (line >> std::ws >> c)
  1871 	  throw DataFormatError("Extra character on the end of line");
  1872 	
  1873 	Edge e;
  1874 	if (!_use_edges) {
  1875 
  1876           typename NodeIndex::iterator it;
  1877  
  1878           it = _node_index.find(source_token);
  1879           if (it == _node_index.end()) {
  1880             std::ostringstream msg;
  1881             msg << "Item not found: " << source_token;
  1882             throw DataFormatError(msg.str().c_str());
  1883           }
  1884           Node source = it->second;
  1885 
  1886           it = _node_index.find(target_token);
  1887           if (it == _node_index.end()) {       
  1888             std::ostringstream msg;            
  1889             msg << "Item not found: " << target_token;
  1890             throw DataFormatError(msg.str().c_str());
  1891           }                                          
  1892           Node target = it->second;                            
  1893 
  1894 	  e = _graph.addEdge(source, target);
  1895 	  _edge_index.insert(std::make_pair(tokens[label_index], e));
  1896 	} else {
  1897 	  typename std::map<std::string, Edge>::iterator it =
  1898 	    _edge_index.find(tokens[label_index]);
  1899 	  if (it == _edge_index.end()) {
  1900 	    std::ostringstream msg;
  1901 	    msg << "Edge with label not found: " << tokens[label_index];
  1902 	    throw DataFormatError(msg.str().c_str());	    
  1903 	  }
  1904 	  e = it->second;
  1905 	}
  1906 
  1907 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1908 	  _edge_maps[i].second->set(e, tokens[map_index[i]]);
  1909 	}
  1910 
  1911       }
  1912       if (readSuccess()) {
  1913 	line.putback(c);
  1914       }
  1915     }
  1916 
  1917     void readAttributes() {
  1918 
  1919       std::set<std::string> read_attr;
  1920 
  1921       char c;
  1922       while (readLine() && line >> c && c != '@') {
  1923 	line.putback(c);
  1924 	
  1925 	std::string attr, token;
  1926 	if (!_reader_bits::readToken(line, attr))
  1927 	  throw DataFormatError("Attribute name not found");
  1928 	if (!_reader_bits::readToken(line, token))
  1929 	  throw DataFormatError("Attribute value not found");
  1930 	if (line >> c)
  1931 	  throw DataFormatError("Extra character on the end of line");	  
  1932 
  1933 	{
  1934 	  std::set<std::string>::iterator it = read_attr.find(attr);
  1935 	  if (it != read_attr.end()) {
  1936 	    std::ostringstream msg;
  1937 	    msg << "Multiple occurence of attribute " << attr;
  1938 	    throw DataFormatError(msg.str().c_str());
  1939 	  }
  1940 	  read_attr.insert(attr);
  1941 	}
  1942 	
  1943 	{
  1944 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
  1945 	  while (it != _attributes.end() && it->first == attr) {
  1946 	    it->second->set(token);
  1947 	    ++it;
  1948 	  }
  1949 	}
  1950 
  1951       }
  1952       if (readSuccess()) {
  1953 	line.putback(c);
  1954       }
  1955       for (typename Attributes::iterator it = _attributes.begin();
  1956 	   it != _attributes.end(); ++it) {
  1957 	if (read_attr.find(it->first) == read_attr.end()) {
  1958 	  std::ostringstream msg;
  1959 	  msg << "Attribute not found in file: " << it->first;
  1960 	  throw DataFormatError(msg.str().c_str());
  1961 	}	
  1962       }
  1963     }
  1964 
  1965   public:
  1966 
  1967     /// \name Execution of the reader    
  1968     /// @{
  1969 
  1970     /// \brief Start the batch processing
  1971     ///
  1972     /// This function starts the batch processing
  1973     void run() {
  1974       
  1975       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1976       
  1977       bool nodes_done = false;
  1978       bool edges_done = false;
  1979       bool attributes_done = false;
  1980       std::set<std::string> extra_sections;
  1981 
  1982       line_num = 0;      
  1983       readLine();
  1984 
  1985       while (readSuccess()) {
  1986 	skipSection();
  1987 	try {
  1988 	  char c;
  1989 	  std::string section, caption;
  1990 	  line >> c;
  1991 	  _reader_bits::readToken(line, section);
  1992 	  _reader_bits::readToken(line, caption);
  1993 
  1994 	  if (line >> c) 
  1995 	    throw DataFormatError("Extra character on the end of line");
  1996 
  1997 	  if (section == "nodes" && !nodes_done) {
  1998 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
  1999 	      readNodes();
  2000 	      nodes_done = true;
  2001 	    }
  2002 	  } else if ((section == "edges" || section == "arcs") && 
  2003 		     !edges_done) {
  2004 	    if (_edges_caption.empty() || _edges_caption == caption) {
  2005 	      readEdges();
  2006 	      edges_done = true;
  2007 	    }
  2008 	  } else if (section == "attributes" && !attributes_done) {
  2009 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
  2010 	      readAttributes();
  2011 	      attributes_done = true;
  2012 	    }
  2013 	  } else {
  2014 	    if (extra_sections.find(section) != extra_sections.end()) {
  2015 	      std::ostringstream msg;
  2016 	      msg << "Multiple occurence of section " << section;
  2017 	      throw DataFormatError(msg.str().c_str());
  2018 	    }
  2019 	    Sections::iterator it = _sections.find(section);
  2020 	    if (it != _sections.end()) {
  2021 	      extra_sections.insert(section);
  2022 	      it->second->process(*_is, line_num);
  2023 	      readLine();
  2024 	    } else {
  2025 	      readLine();
  2026 	      skipSection();
  2027 	    }
  2028 	  }
  2029 	} catch (DataFormatError& error) {
  2030 	  error.line(line_num);
  2031 	  throw;
  2032 	}	
  2033       }
  2034 
  2035       if (!nodes_done) {
  2036 	throw DataFormatError("Section @nodes not found");
  2037       }
  2038 
  2039       if (!edges_done) {
  2040 	throw DataFormatError("Section @edges not found");
  2041       }
  2042 
  2043       if (!attributes_done && !_attributes.empty()) {
  2044 	throw DataFormatError("Section @attributes not found");
  2045       }
  2046 
  2047     }
  2048 
  2049     /// @}
  2050     
  2051   };
  2052 
  2053   /// \relates GraphReader
  2054   template <typename Graph>
  2055   GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
  2056     GraphReader<Graph> tmp(is, graph);
  2057     return tmp;
  2058   }
  2059 
  2060   /// \relates GraphReader
  2061   template <typename Graph>
  2062   GraphReader<Graph> graphReader(const std::string& fn, 
  2063 				       Graph& graph) {
  2064     GraphReader<Graph> tmp(fn, graph);
  2065     return tmp;
  2066   }
  2067 
  2068   /// \relates GraphReader
  2069   template <typename Graph>
  2070   GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
  2071     GraphReader<Graph> tmp(fn, graph);
  2072     return tmp;
  2073   }
  2074 }
  2075 
  2076 #endif