lemon/lgf_reader.h
author Balazs Dezso <deba@inf.elte.hu>
Thu, 19 Jun 2008 10:59:22 +0200
changeset 177 b685e12e08c0
parent 173 b026e9779b28
parent 172 c94a80f38d7f
child 179 289266783a0b
permissions -rw-r--r--
Seeding from file source or from pid and time (ticket #19)
     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       skipSection();
  1143 
  1144       while (readSuccess()) {
  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 	    }
  1182 	    readLine();
  1183 	    skipSection();
  1184 	  }
  1185 	} catch (DataFormatError& error) {
  1186 	  error.line(line_num);
  1187 	  throw;
  1188 	}	
  1189       }
  1190 
  1191       if (!nodes_done) {
  1192 	throw DataFormatError("Section @nodes not found");
  1193       }
  1194 
  1195       if (!arcs_done) {
  1196 	throw DataFormatError("Section @arcs not found");
  1197       }
  1198 
  1199       if (!attributes_done && !_attributes.empty()) {
  1200 	throw DataFormatError("Section @attributes not found");
  1201       }
  1202 
  1203     }
  1204 
  1205     /// @}
  1206     
  1207   };
  1208 
  1209   /// \relates DigraphReader
  1210   template <typename Digraph>
  1211   DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
  1212     DigraphReader<Digraph> tmp(is, digraph);
  1213     return tmp;
  1214   }
  1215 
  1216   /// \relates DigraphReader
  1217   template <typename Digraph>
  1218   DigraphReader<Digraph> digraphReader(const std::string& fn, 
  1219 				       Digraph& digraph) {
  1220     DigraphReader<Digraph> tmp(fn, digraph);
  1221     return tmp;
  1222   }
  1223 
  1224   /// \relates DigraphReader
  1225   template <typename Digraph>
  1226   DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
  1227     DigraphReader<Digraph> tmp(fn, digraph);
  1228     return tmp;
  1229   }
  1230 
  1231   /// \ingroup lemon_io
  1232   ///  
  1233   /// \brief LGF reader for undirected graphs
  1234   ///
  1235   /// This utility reads an \ref lgf-format "LGF" file.
  1236   template <typename _Graph>
  1237   class GraphReader {
  1238   public:
  1239 
  1240     typedef _Graph Graph;
  1241     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  1242     
  1243   private:
  1244 
  1245 
  1246     std::istream* _is;
  1247     bool local_is;
  1248 
  1249     Graph& _graph;
  1250 
  1251     std::string _nodes_caption;
  1252     std::string _edges_caption;
  1253     std::string _attributes_caption;
  1254 
  1255     typedef std::map<std::string, Node> NodeIndex;
  1256     NodeIndex _node_index;
  1257     typedef std::map<std::string, Edge> EdgeIndex;
  1258     EdgeIndex _edge_index;
  1259     
  1260     typedef std::vector<std::pair<std::string, 
  1261       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
  1262     NodeMaps _node_maps; 
  1263 
  1264     typedef std::vector<std::pair<std::string,
  1265       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  1266     EdgeMaps _edge_maps;
  1267 
  1268     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
  1269       Attributes;
  1270     Attributes _attributes;
  1271 
  1272     typedef std::map<std::string, _reader_bits::Section*> Sections;
  1273     Sections _sections;
  1274 
  1275     bool _use_nodes;
  1276     bool _use_edges;
  1277 
  1278     int line_num;
  1279     std::istringstream line;
  1280 
  1281   public:
  1282 
  1283     /// \brief Constructor
  1284     ///
  1285     /// Construct a undirected graph reader, which reads from the given
  1286     /// input stream.
  1287     GraphReader(std::istream& is, Graph& graph) 
  1288       : _is(&is), local_is(false), _graph(graph),
  1289 	_use_nodes(false), _use_edges(false) {}
  1290 
  1291     /// \brief Constructor
  1292     ///
  1293     /// Construct a undirected graph reader, which reads from the given
  1294     /// file.
  1295     GraphReader(const std::string& fn, Graph& graph) 
  1296       : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
  1297     	_use_nodes(false), _use_edges(false) {}
  1298     
  1299     /// \brief Constructor
  1300     ///
  1301     /// Construct a 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 
  1307     /// \brief Copy constructor
  1308     ///
  1309     /// The copy constructor transfers all data from the other reader,
  1310     /// therefore the copied reader will not be usable more. 
  1311     GraphReader(GraphReader& other) 
  1312       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  1313 	_use_nodes(other._use_nodes), _use_edges(other._use_edges) {
  1314 
  1315       other._is = 0;
  1316       other.local_is = false;
  1317       
  1318       _node_index.swap(other._node_index);
  1319       _edge_index.swap(other._edge_index);
  1320 
  1321       _node_maps.swap(other._node_maps);
  1322       _edge_maps.swap(other._edge_maps);
  1323       _attributes.swap(other._attributes);
  1324 
  1325       _nodes_caption = other._nodes_caption;
  1326       _edges_caption = other._edges_caption;
  1327       _attributes_caption = other._attributes_caption;
  1328 
  1329       _sections.swap(other._sections);
  1330     }
  1331 
  1332     /// \brief Destructor
  1333     ~GraphReader() {
  1334       for (typename NodeMaps::iterator it = _node_maps.begin(); 
  1335 	   it != _node_maps.end(); ++it) {
  1336 	delete it->second;
  1337       }
  1338 
  1339       for (typename EdgeMaps::iterator it = _edge_maps.begin(); 
  1340 	   it != _edge_maps.end(); ++it) {
  1341 	delete it->second;
  1342       }
  1343 
  1344       for (typename Attributes::iterator it = _attributes.begin(); 
  1345 	   it != _attributes.end(); ++it) {
  1346 	delete it->second;
  1347       }
  1348 
  1349       for (typename Sections::iterator it = _sections.begin(); 
  1350 	   it != _sections.end(); ++it) {
  1351 	delete it->second;
  1352       }
  1353 
  1354       if (local_is) {
  1355 	delete _is;
  1356       }
  1357 
  1358     }
  1359 
  1360   private:
  1361     
  1362     GraphReader& operator=(const GraphReader&);
  1363 
  1364   public:
  1365 
  1366     /// \name Reading rules
  1367     /// @{
  1368     
  1369     /// \brief Node map reading rule
  1370     ///
  1371     /// Add a node map reading rule to the reader.
  1372     template <typename Map>
  1373     GraphReader& nodeMap(const std::string& caption, Map& map) {
  1374       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1375       _reader_bits::MapStorageBase<Node>* storage = 
  1376 	new _reader_bits::MapStorage<Node, Map>(map);
  1377       _node_maps.push_back(std::make_pair(caption, storage));
  1378       return *this;
  1379     }
  1380 
  1381     /// \brief Node map reading rule
  1382     ///
  1383     /// Add a node map reading rule with specialized converter to the
  1384     /// reader.
  1385     template <typename Map, typename Converter>
  1386     GraphReader& nodeMap(const std::string& caption, Map& map, 
  1387 			   const Converter& converter = Converter()) {
  1388       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1389       _reader_bits::MapStorageBase<Node>* storage = 
  1390 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  1391       _node_maps.push_back(std::make_pair(caption, storage));
  1392       return *this;
  1393     }
  1394 
  1395     /// \brief Edge map reading rule
  1396     ///
  1397     /// Add an edge map reading rule to the reader.
  1398     template <typename Map>
  1399     GraphReader& edgeMap(const std::string& caption, Map& map) {
  1400       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1401       _reader_bits::MapStorageBase<Edge>* storage = 
  1402 	new _reader_bits::MapStorage<Edge, Map>(map);
  1403       _edge_maps.push_back(std::make_pair(caption, storage));
  1404       return *this;
  1405     }
  1406 
  1407     /// \brief Edge map reading rule
  1408     ///
  1409     /// Add an edge map reading rule with specialized converter to the
  1410     /// reader.
  1411     template <typename Map, typename Converter>
  1412     GraphReader& edgeMap(const std::string& caption, Map& map, 
  1413 			  const Converter& converter = Converter()) {
  1414       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1415       _reader_bits::MapStorageBase<Edge>* storage = 
  1416 	new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1417       _edge_maps.push_back(std::make_pair(caption, storage));
  1418       return *this;
  1419     }
  1420 
  1421     /// \brief Arc map reading rule
  1422     ///
  1423     /// Add an arc map reading rule to the reader.
  1424     template <typename Map>
  1425     GraphReader& arcMap(const std::string& caption, Map& map) {
  1426       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1427       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1428 	new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1429       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1430       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1431 	new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1432       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1433       return *this;
  1434     }
  1435 
  1436     /// \brief Arc map reading rule
  1437     ///
  1438     /// Add an arc map reading rule with specialized converter to the
  1439     /// reader.
  1440     template <typename Map, typename Converter>
  1441     GraphReader& arcMap(const std::string& caption, Map& map, 
  1442 			  const Converter& converter = Converter()) {
  1443       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1444       _reader_bits::MapStorageBase<Edge>* forward_storage = 
  1445 	new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1446 	(_graph, map, converter);
  1447       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1448       _reader_bits::MapStorageBase<Edge>* backward_storage = 
  1449 	new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1450 	(_graph, map, converter);
  1451       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1452       return *this;
  1453     }
  1454 
  1455     /// \brief Attribute reading rule
  1456     ///
  1457     /// Add an attribute reading rule to the reader.
  1458     template <typename Value>
  1459     GraphReader& attribute(const std::string& caption, Value& value) {
  1460       _reader_bits::ValueStorageBase* storage = 
  1461 	new _reader_bits::ValueStorage<Value>(value);
  1462       _attributes.insert(std::make_pair(caption, storage));
  1463       return *this;
  1464     }
  1465 
  1466     /// \brief Attribute reading rule
  1467     ///
  1468     /// Add an attribute reading rule with specialized converter to the
  1469     /// reader.
  1470     template <typename Value, typename Converter>
  1471     GraphReader& attribute(const std::string& caption, Value& value, 
  1472 			     const Converter& converter = Converter()) {
  1473       _reader_bits::ValueStorageBase* storage = 
  1474 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  1475       _attributes.insert(std::make_pair(caption, storage));
  1476       return *this;
  1477     }
  1478 
  1479     /// \brief Node reading rule
  1480     ///
  1481     /// Add a node reading rule to reader.
  1482     GraphReader& node(const std::string& caption, Node& node) {
  1483       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  1484       Converter converter(_node_index);
  1485       _reader_bits::ValueStorageBase* storage = 
  1486 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  1487       _attributes.insert(std::make_pair(caption, storage));
  1488       return *this;
  1489     }
  1490 
  1491     /// \brief Edge reading rule
  1492     ///
  1493     /// Add an edge reading rule to reader.
  1494     GraphReader& edge(const std::string& caption, Edge& edge) {
  1495       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  1496       Converter converter(_edge_index);
  1497       _reader_bits::ValueStorageBase* storage = 
  1498 	new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  1499       _attributes.insert(std::make_pair(caption, storage));
  1500       return *this;
  1501     }
  1502 
  1503     /// \brief Arc reading rule
  1504     ///
  1505     /// Add an arc reading rule to reader.
  1506     GraphReader& arc(const std::string& caption, Arc& arc) {
  1507       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
  1508       Converter converter(_graph, _edge_index);
  1509       _reader_bits::ValueStorageBase* storage = 
  1510 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  1511       _attributes.insert(std::make_pair(caption, storage));
  1512       return *this;
  1513     }
  1514 
  1515     /// @}
  1516 
  1517     /// \name Select section by name
  1518     /// @{
  1519 
  1520     /// \brief Set \c \@nodes section to be read
  1521     ///
  1522     /// Set \c \@nodes section to be read
  1523     GraphReader& nodes(const std::string& caption) {
  1524       _nodes_caption = caption;
  1525       return *this;
  1526     }
  1527 
  1528     /// \brief Set \c \@edges section to be read
  1529     ///
  1530     /// Set \c \@edges section to be read
  1531     GraphReader& edges(const std::string& caption) {
  1532       _edges_caption = caption;
  1533       return *this;
  1534     }
  1535 
  1536     /// \brief Set \c \@attributes section to be read
  1537     ///
  1538     /// Set \c \@attributes section to be read
  1539     GraphReader& attributes(const std::string& caption) {
  1540       _attributes_caption = caption;
  1541       return *this;
  1542     }
  1543 
  1544     /// @}
  1545 
  1546     /// \name Section readers
  1547     /// @{
  1548 
  1549     /// \brief Add a section processor with line oriented reading
  1550     ///
  1551     /// In the \e LGF file extra sections can be placed, which contain
  1552     /// any data in arbitrary format. These sections can be read with
  1553     /// this function line by line. The first parameter is the type
  1554     /// descriptor of the section, the second is a functor, which
  1555     /// takes just one \c std::string parameter. At the reading
  1556     /// process, each line of the section will be given to the functor
  1557     /// object. However, the empty lines and the comment lines are
  1558     /// filtered out, and the leading whitespaces are stipped from
  1559     /// each processed string.
  1560     ///
  1561     /// For example let's see a section, which contain several
  1562     /// integers, which should be inserted into a vector.
  1563     ///\code
  1564     ///  @numbers
  1565     ///  12 45 23
  1566     ///  4
  1567     ///  23 6
  1568     ///\endcode
  1569     ///
  1570     /// The functor is implemented as an struct:
  1571     ///\code
  1572     ///  struct NumberSection {
  1573     ///    std::vector<int>& _data;
  1574     ///    NumberSection(std::vector<int>& data) : _data(data) {}
  1575     ///    void operator()(const std::string& line) {
  1576     ///      std::istringstream ls(line);
  1577     ///      int value;
  1578     ///      while (ls >> value) _data.push_back(value);
  1579     ///    }
  1580     ///  };
  1581     ///
  1582     ///  // ...
  1583     ///
  1584     ///  reader.sectionLines("numbers", NumberSection(vec));  
  1585     ///\endcode
  1586     template <typename Functor>
  1587     GraphReader& sectionLines(const std::string& type, Functor functor) {
  1588       LEMON_ASSERT(!type.empty(), "Type is not empty.");
  1589       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  1590 		   "Multiple reading of section.");
  1591       LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
  1592 		   type != "attributes", "Multiple reading of section.");
  1593       _sections.insert(std::make_pair(type, 
  1594         new _reader_bits::LineSection<Functor>(functor)));
  1595       return *this;
  1596     }
  1597 
  1598 
  1599     /// \brief Add a section processor with stream oriented reading
  1600     ///
  1601     /// In the \e LGF file extra sections can be placed, which contain
  1602     /// any data in arbitrary format. These sections can be read
  1603     /// directly with this function. The first parameter is the type
  1604     /// of the section, the second is a functor, which takes an \c
  1605     /// std::istream& and an int& parameter, the latter regard to the
  1606     /// line number of stream. The functor can read the input while
  1607     /// the section go on, and the line number should be modified
  1608     /// accordingly.
  1609     template <typename Functor>
  1610     GraphReader& sectionStream(const std::string& type, Functor functor) {
  1611       LEMON_ASSERT(!type.empty(), "Type is not empty.");
  1612       LEMON_ASSERT(_sections.find(type) == _sections.end(), 
  1613 		   "Multiple reading of section.");
  1614       LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
  1615 		   type != "attributes", "Multiple reading of section.");
  1616       _sections.insert(std::make_pair(type, 
  1617 	 new _reader_bits::StreamSection<Functor>(functor)));
  1618       return *this;
  1619     }    
  1620     
  1621     /// @}
  1622 
  1623     /// \name Using previously constructed node or edge set
  1624     /// @{
  1625 
  1626     /// \brief Use previously constructed node set
  1627     ///
  1628     /// Use previously constructed node set, and specify the node
  1629     /// label map.
  1630     template <typename Map>
  1631     GraphReader& useNodes(const Map& map) {
  1632       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1633       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1634       _use_nodes = true;
  1635       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1636       for (NodeIt n(_graph); n != INVALID; ++n) {
  1637 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1638       }
  1639       return *this;
  1640     }
  1641 
  1642     /// \brief Use previously constructed node set
  1643     ///
  1644     /// Use previously constructed node set, and specify the node
  1645     /// label map and a functor which converts the label map values to
  1646     /// std::string.
  1647     template <typename Map, typename Converter>
  1648     GraphReader& useNodes(const Map& map, 
  1649 			    const Converter& converter = Converter()) {
  1650       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1651       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
  1652       _use_nodes = true;
  1653       for (NodeIt n(_graph); n != INVALID; ++n) {
  1654 	_node_index.insert(std::make_pair(converter(map[n]), n));
  1655       }
  1656       return *this;
  1657     }
  1658 
  1659     /// \brief Use previously constructed edge set
  1660     ///
  1661     /// Use previously constructed edge set, and specify the edge
  1662     /// label map.
  1663     template <typename Map>
  1664     GraphReader& useEdges(const Map& map) {
  1665       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1666       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1667       _use_edges = true;
  1668       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1669       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1670 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1671       }
  1672       return *this;
  1673     }
  1674 
  1675     /// \brief Use previously constructed edge set
  1676     ///
  1677     /// Use previously constructed edge set, and specify the edge
  1678     /// label map and a functor which converts the label map values to
  1679     /// std::string.
  1680     template <typename Map, typename Converter>
  1681     GraphReader& useEdges(const Map& map, 
  1682 			    const Converter& converter = Converter()) {
  1683       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1684       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 
  1685       _use_edges = true;
  1686       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1687 	_edge_index.insert(std::make_pair(converter(map[a]), a));
  1688       }
  1689       return *this;
  1690     }
  1691 
  1692     /// @}
  1693 
  1694   private:
  1695 
  1696     bool readLine() {
  1697       std::string str;
  1698       while(++line_num, std::getline(*_is, str)) {
  1699 	line.clear(); line.str(str);
  1700 	char c;
  1701 	if (line >> std::ws >> c && c != '#') {
  1702 	  line.putback(c);
  1703 	  return true;
  1704 	}
  1705       }
  1706       return false;
  1707     }
  1708 
  1709     bool readSuccess() {
  1710       return static_cast<bool>(*_is);
  1711     }
  1712     
  1713     void skipSection() {
  1714       char c;
  1715       while (readSuccess() && line >> c && c != '@') {
  1716 	readLine();
  1717       }
  1718       line.putback(c);
  1719     }
  1720 
  1721     void readNodes() {
  1722 
  1723       std::vector<int> map_index(_node_maps.size());
  1724       int map_num, label_index;
  1725 
  1726       if (!readLine()) 
  1727 	throw DataFormatError("Cannot find map captions");
  1728       
  1729       {
  1730 	std::map<std::string, int> maps;
  1731 	
  1732 	std::string map;
  1733 	int index = 0;
  1734 	while (_reader_bits::readToken(line, map)) {
  1735 	  if (maps.find(map) != maps.end()) {
  1736 	    std::ostringstream msg;
  1737 	    msg << "Multiple occurence of node map: " << map;
  1738 	    throw DataFormatError(msg.str().c_str());
  1739 	  }
  1740 	  maps.insert(std::make_pair(map, index));
  1741 	  ++index;
  1742 	}
  1743 	
  1744 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1745 	  std::map<std::string, int>::iterator jt = 
  1746 	    maps.find(_node_maps[i].first);
  1747 	  if (jt == maps.end()) {
  1748 	    std::ostringstream msg;
  1749 	    msg << "Map not found in file: " << _node_maps[i].first;
  1750 	    throw DataFormatError(msg.str().c_str());
  1751 	  }
  1752 	  map_index[i] = jt->second;
  1753 	}
  1754 
  1755 	{
  1756 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1757 	  if (jt == maps.end())
  1758 	    throw DataFormatError("Label map not found in file");
  1759 	  label_index = jt->second;
  1760 	}
  1761 	map_num = maps.size();
  1762       }
  1763 
  1764       char c;
  1765       while (readLine() && line >> c && c != '@') {
  1766 	line.putback(c);
  1767 
  1768 	std::vector<std::string> tokens(map_num);
  1769 	for (int i = 0; i < map_num; ++i) {
  1770 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1771 	    std::ostringstream msg;
  1772 	    msg << "Column not found (" << i + 1 << ")";
  1773 	    throw DataFormatError(msg.str().c_str());
  1774 	  }
  1775 	}
  1776 	if (line >> std::ws >> c)
  1777 	  throw DataFormatError("Extra character on the end of line");
  1778 	
  1779 	Node n;
  1780 	if (!_use_nodes) {
  1781 	  n = _graph.addNode();
  1782 	  _node_index.insert(std::make_pair(tokens[label_index], n));
  1783 	} else {
  1784 	  typename std::map<std::string, Node>::iterator it =
  1785 	    _node_index.find(tokens[label_index]);
  1786 	  if (it == _node_index.end()) {
  1787 	    std::ostringstream msg;
  1788 	    msg << "Node with label not found: " << tokens[label_index];
  1789 	    throw DataFormatError(msg.str().c_str());	    
  1790 	  }
  1791 	  n = it->second;
  1792 	}
  1793 
  1794 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1795 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
  1796 	}
  1797 
  1798       }
  1799       if (readSuccess()) {
  1800 	line.putback(c);
  1801       }
  1802     }
  1803 
  1804     void readEdges() {
  1805 
  1806       std::vector<int> map_index(_edge_maps.size());
  1807       int map_num, label_index;
  1808 
  1809       if (!readLine()) 
  1810 	throw DataFormatError("Cannot find map captions");
  1811       
  1812       {
  1813 	std::map<std::string, int> maps;
  1814 	
  1815 	std::string map;
  1816 	int index = 0;
  1817 	while (_reader_bits::readToken(line, map)) {
  1818 	  if (maps.find(map) != maps.end()) {
  1819 	    std::ostringstream msg;
  1820 	    msg << "Multiple occurence of edge map: " << map;
  1821 	    throw DataFormatError(msg.str().c_str());
  1822 	  }
  1823 	  maps.insert(std::make_pair(map, index));
  1824 	  ++index;
  1825 	}
  1826 	
  1827 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1828 	  std::map<std::string, int>::iterator jt = 
  1829 	    maps.find(_edge_maps[i].first);
  1830 	  if (jt == maps.end()) {
  1831 	    std::ostringstream msg;
  1832 	    msg << "Map not found in file: " << _edge_maps[i].first;
  1833 	    throw DataFormatError(msg.str().c_str());
  1834 	  }
  1835 	  map_index[i] = jt->second;
  1836 	}
  1837 
  1838 	{
  1839 	  std::map<std::string, int>::iterator jt = maps.find("label");
  1840 	  if (jt == maps.end())
  1841 	    throw DataFormatError("Label map not found in file");
  1842 	  label_index = jt->second;
  1843 	}
  1844 	map_num = maps.size();
  1845       }
  1846 
  1847       char c;
  1848       while (readLine() && line >> c && c != '@') {
  1849 	line.putback(c);
  1850 
  1851 	std::string source_token;
  1852 	std::string target_token;
  1853 
  1854 	if (!_reader_bits::readToken(line, source_token))
  1855 	  throw DataFormatError("Source not found");
  1856 
  1857 	if (!_reader_bits::readToken(line, target_token))
  1858 	  throw DataFormatError("Source not found");
  1859 	
  1860 	std::vector<std::string> tokens(map_num);
  1861 	for (int i = 0; i < map_num; ++i) {
  1862 	  if (!_reader_bits::readToken(line, tokens[i])) {
  1863 	    std::ostringstream msg;
  1864 	    msg << "Column not found (" << i + 1 << ")";
  1865 	    throw DataFormatError(msg.str().c_str());
  1866 	  }
  1867 	}
  1868 	if (line >> std::ws >> c)
  1869 	  throw DataFormatError("Extra character on the end of line");
  1870 	
  1871 	Edge e;
  1872 	if (!_use_edges) {
  1873 
  1874           typename NodeIndex::iterator it;
  1875  
  1876           it = _node_index.find(source_token);
  1877           if (it == _node_index.end()) {
  1878             std::ostringstream msg;
  1879             msg << "Item not found: " << source_token;
  1880             throw DataFormatError(msg.str().c_str());
  1881           }
  1882           Node source = it->second;
  1883 
  1884           it = _node_index.find(target_token);
  1885           if (it == _node_index.end()) {       
  1886             std::ostringstream msg;            
  1887             msg << "Item not found: " << target_token;
  1888             throw DataFormatError(msg.str().c_str());
  1889           }                                          
  1890           Node target = it->second;                            
  1891 
  1892 	  e = _graph.addEdge(source, target);
  1893 	  _edge_index.insert(std::make_pair(tokens[label_index], e));
  1894 	} else {
  1895 	  typename std::map<std::string, Edge>::iterator it =
  1896 	    _edge_index.find(tokens[label_index]);
  1897 	  if (it == _edge_index.end()) {
  1898 	    std::ostringstream msg;
  1899 	    msg << "Edge with label not found: " << tokens[label_index];
  1900 	    throw DataFormatError(msg.str().c_str());	    
  1901 	  }
  1902 	  e = it->second;
  1903 	}
  1904 
  1905 	for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1906 	  _edge_maps[i].second->set(e, tokens[map_index[i]]);
  1907 	}
  1908 
  1909       }
  1910       if (readSuccess()) {
  1911 	line.putback(c);
  1912       }
  1913     }
  1914 
  1915     void readAttributes() {
  1916 
  1917       std::set<std::string> read_attr;
  1918 
  1919       char c;
  1920       while (readLine() && line >> c && c != '@') {
  1921 	line.putback(c);
  1922 	
  1923 	std::string attr, token;
  1924 	if (!_reader_bits::readToken(line, attr))
  1925 	  throw DataFormatError("Attribute name not found");
  1926 	if (!_reader_bits::readToken(line, token))
  1927 	  throw DataFormatError("Attribute value not found");
  1928 	if (line >> c)
  1929 	  throw DataFormatError("Extra character on the end of line");	  
  1930 
  1931 	{
  1932 	  std::set<std::string>::iterator it = read_attr.find(attr);
  1933 	  if (it != read_attr.end()) {
  1934 	    std::ostringstream msg;
  1935 	    msg << "Multiple occurence of attribute " << attr;
  1936 	    throw DataFormatError(msg.str().c_str());
  1937 	  }
  1938 	  read_attr.insert(attr);
  1939 	}
  1940 	
  1941 	{
  1942 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
  1943 	  while (it != _attributes.end() && it->first == attr) {
  1944 	    it->second->set(token);
  1945 	    ++it;
  1946 	  }
  1947 	}
  1948 
  1949       }
  1950       if (readSuccess()) {
  1951 	line.putback(c);
  1952       }
  1953       for (typename Attributes::iterator it = _attributes.begin();
  1954 	   it != _attributes.end(); ++it) {
  1955 	if (read_attr.find(it->first) == read_attr.end()) {
  1956 	  std::ostringstream msg;
  1957 	  msg << "Attribute not found in file: " << it->first;
  1958 	  throw DataFormatError(msg.str().c_str());
  1959 	}	
  1960       }
  1961     }
  1962 
  1963   public:
  1964 
  1965     /// \name Execution of the reader    
  1966     /// @{
  1967 
  1968     /// \brief Start the batch processing
  1969     ///
  1970     /// This function starts the batch processing
  1971     void run() {
  1972       
  1973       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1974       
  1975       bool nodes_done = false;
  1976       bool edges_done = false;
  1977       bool attributes_done = false;
  1978       std::set<std::string> extra_sections;
  1979 
  1980       line_num = 0;      
  1981       readLine();
  1982       skipSection();
  1983 
  1984       while (readSuccess()) {
  1985 	try {
  1986 	  char c;
  1987 	  std::string section, caption;
  1988 	  line >> c;
  1989 	  _reader_bits::readToken(line, section);
  1990 	  _reader_bits::readToken(line, caption);
  1991 
  1992 	  if (line >> c) 
  1993 	    throw DataFormatError("Extra character on the end of line");
  1994 
  1995 	  if (section == "nodes" && !nodes_done) {
  1996 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
  1997 	      readNodes();
  1998 	      nodes_done = true;
  1999 	    }
  2000 	  } else if ((section == "edges" || section == "arcs") && 
  2001 		     !edges_done) {
  2002 	    if (_edges_caption.empty() || _edges_caption == caption) {
  2003 	      readEdges();
  2004 	      edges_done = true;
  2005 	    }
  2006 	  } else if (section == "attributes" && !attributes_done) {
  2007 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
  2008 	      readAttributes();
  2009 	      attributes_done = true;
  2010 	    }
  2011 	  } else {
  2012 	    if (extra_sections.find(section) != extra_sections.end()) {
  2013 	      std::ostringstream msg;
  2014 	      msg << "Multiple occurence of section " << section;
  2015 	      throw DataFormatError(msg.str().c_str());
  2016 	    }
  2017 	    Sections::iterator it = _sections.find(section);
  2018 	    if (it != _sections.end()) {
  2019 	      extra_sections.insert(section);
  2020 	      it->second->process(*_is, line_num);
  2021 	    }
  2022 	    readLine();
  2023 	    skipSection();
  2024 	  }
  2025 	} catch (DataFormatError& error) {
  2026 	  error.line(line_num);
  2027 	  throw;
  2028 	}	
  2029       }
  2030 
  2031       if (!nodes_done) {
  2032 	throw DataFormatError("Section @nodes not found");
  2033       }
  2034 
  2035       if (!edges_done) {
  2036 	throw DataFormatError("Section @edges not found");
  2037       }
  2038 
  2039       if (!attributes_done && !_attributes.empty()) {
  2040 	throw DataFormatError("Section @attributes not found");
  2041       }
  2042 
  2043     }
  2044 
  2045     /// @}
  2046     
  2047   };
  2048 
  2049   /// \relates GraphReader
  2050   template <typename Graph>
  2051   GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
  2052     GraphReader<Graph> tmp(is, graph);
  2053     return tmp;
  2054   }
  2055 
  2056   /// \relates GraphReader
  2057   template <typename Graph>
  2058   GraphReader<Graph> graphReader(const std::string& fn, 
  2059 				       Graph& graph) {
  2060     GraphReader<Graph> tmp(fn, graph);
  2061     return tmp;
  2062   }
  2063 
  2064   /// \relates GraphReader
  2065   template <typename Graph>
  2066   GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
  2067     GraphReader<Graph> tmp(fn, graph);
  2068     return tmp;
  2069   }
  2070 
  2071   /// \ingroup lemon_io
  2072   ///
  2073   /// \brief Reader for the content of the \ref lgf-format "LGF" file 
  2074   ///
  2075   /// This class can be used to read the sections, the map names and
  2076   /// the attributes from a file. Usually, the Lemon programs know
  2077   /// that, which type of graph, which maps and which attributes
  2078   /// should be read from a file, but in general tools (like glemon)
  2079   /// the content of an LGF file should be guessed somehow. This class
  2080   /// reads the graph and stores the appropriate information for
  2081   /// reading the graph.
  2082   ///
  2083   ///\code LgfContent content("graph.lgf"); 
  2084   /// content.run();
  2085   ///
  2086   /// // does it contain any node section and arc section
  2087   /// if (content.nodeSectionNum() == 0 || content.arcSectionNum()) {
  2088   ///   std::cerr << "Failure, cannot find graph" << std::endl;
  2089   ///   return -1;
  2090   /// }
  2091   /// std::cout << "The name of the default node section : " 
  2092   ///           << content.nodeSection(0) << std::endl;
  2093   /// std::cout << "The number of the arc maps : " 
  2094   ///           << content.arcMaps(0).size() << std::endl;
  2095   /// std::cout << "The name of second arc map : " 
  2096   ///           << content.arcMaps(0)[1] << std::endl;
  2097   ///\endcode
  2098   class LgfContent {    
  2099   private:
  2100 
  2101     std::istream* _is;
  2102     bool local_is;
  2103 
  2104     std::vector<std::string> _node_sections;
  2105     std::vector<std::string> _edge_sections;
  2106     std::vector<std::string> _attribute_sections;
  2107     std::vector<std::string> _extra_sections;
  2108 
  2109     std::vector<bool> _arc_sections;
  2110 
  2111     std::vector<std::vector<std::string> > _node_maps;
  2112     std::vector<std::vector<std::string> > _edge_maps;
  2113 
  2114     std::vector<std::vector<std::string> > _attributes;
  2115 
  2116 
  2117     int line_num;
  2118     std::istringstream line;
  2119     
  2120   public:
  2121 
  2122     /// \brief Constructor
  2123     ///
  2124     /// Construct an \e LGF content reader, which reads from the given
  2125     /// input stream.
  2126     LgfContent(std::istream& is) 
  2127       : _is(&is), local_is(false) {}
  2128 
  2129     /// \brief Constructor
  2130     ///
  2131     /// Construct an \e LGF content reader, which reads from the given
  2132     /// file.
  2133     LgfContent(const std::string& fn) 
  2134       : _is(new std::ifstream(fn.c_str())), local_is(true) {}
  2135 
  2136     /// \brief Constructor
  2137     ///
  2138     /// Construct an \e LGF content reader, which reads from the given
  2139     /// file.
  2140     LgfContent(const char* fn)
  2141       : _is(new std::ifstream(fn)), local_is(true) {}
  2142 
  2143     /// \brief Copy constructor
  2144     ///
  2145     /// The copy constructor transfers all data from the other reader,
  2146     /// therefore the copied reader will not be usable more. 
  2147     LgfContent(LgfContent& other)
  2148       : _is(other._is), local_is(other.local_is) {
  2149       
  2150       other._is = 0;
  2151       other.local_is = false;
  2152       
  2153       _node_sections.swap(other._node_sections);
  2154       _edge_sections.swap(other._edge_sections);
  2155       _attribute_sections.swap(other._attribute_sections);
  2156       _extra_sections.swap(other._extra_sections);
  2157 
  2158       _arc_sections.swap(other._arc_sections);
  2159 
  2160       _node_maps.swap(other._node_maps);
  2161       _edge_maps.swap(other._edge_maps);
  2162       _attributes.swap(other._attributes);
  2163     }
  2164     
  2165     /// \brief Destructor
  2166     ~LgfContent() {
  2167       if (local_is) delete _is;
  2168     }
  2169 
  2170 
  2171     /// \name Node sections
  2172     /// @{
  2173 
  2174     /// \brief Gives back the number of node sections in the file.
  2175     ///
  2176     /// Gives back the number of node sections in the file.
  2177     int nodeSectionNum() const {
  2178       return _node_sections.size();
  2179     }
  2180 
  2181     /// \brief Returns the section name at the given position. 
  2182     ///
  2183     /// Returns the section name at the given position. 
  2184     const std::string& nodeSection(int i) const {
  2185       return _node_sections[i];
  2186     }
  2187 
  2188     /// \brief Gives back the node maps for the given section.
  2189     ///
  2190     /// Gives back the node maps for the given section.
  2191     const std::vector<std::string>& nodeMaps(int i) const {
  2192       return _node_maps[i];
  2193     }
  2194 
  2195     /// @}
  2196 
  2197     /// \name Arc sections 
  2198     /// @{
  2199 
  2200     /// \brief Gives back the number of arc sections in the file.
  2201     ///
  2202     /// Gives back the number of arc sections in the file.
  2203     /// \note It is synonim of \c edgeSectionNum().
  2204     int arcSectionNum() const {
  2205       return _edge_sections.size();
  2206     }
  2207 
  2208     /// \brief Returns the section name at the given position. 
  2209     ///
  2210     /// Returns the section name at the given position. 
  2211     /// \note It is synonim of \c edgeSection().
  2212     const std::string& arcSection(int i) const {
  2213       return _edge_sections[i];
  2214     }
  2215 
  2216     /// \brief Gives back the arc maps for the given section.
  2217     ///
  2218     /// Gives back the arc maps for the given section.
  2219     /// \note It is synonim of \c edgeMaps().
  2220     const std::vector<std::string>& arcMaps(int i) const {
  2221       return _edge_maps[i];
  2222     }
  2223 
  2224     /// \brief Returns true when the section type is \c "@arcs".
  2225     ///
  2226     /// Returns true when the section type is \c "@arcs", and not "@edges".
  2227     bool isArcSection(int i) const {
  2228       return _arc_sections[i];
  2229     }
  2230 
  2231     /// @}
  2232 
  2233     /// \name Edge sections   
  2234     /// @{
  2235 
  2236     /// \brief Gives back the number of edge sections in the file.
  2237     ///
  2238     /// Gives back the number of edge sections in the file.
  2239     int edgeSectionNum() const {
  2240       return _edge_sections.size();
  2241     }
  2242 
  2243     /// \brief Returns the section name at the given position. 
  2244     ///
  2245     /// Returns the section name at the given position. 
  2246     const std::string& edgeSection(int i) const {
  2247       return _edge_sections[i];
  2248     }
  2249 
  2250     /// \brief Gives back the edge maps for the given section.
  2251     ///
  2252     /// Gives back the edge maps for the given section.
  2253     const std::vector<std::string>& edgeMaps(int i) const {
  2254       return _edge_maps[i];
  2255     }
  2256 
  2257     /// \brief Returns true when the section type is \c "@edges".
  2258     ///
  2259     /// Returns true when the section type is \c "@edges", and not "@arcs".
  2260     bool isEdgeSection(int i) const {
  2261       return !_arc_sections[i];
  2262     }
  2263 
  2264     /// @}
  2265 
  2266     /// \name Attribute sections   
  2267     /// @{
  2268 
  2269     /// \brief Gives back the number of attribute sections in the file.
  2270     ///
  2271     /// Gives back the number of attribute sections in the file.
  2272     int attributeSectionNum() const {
  2273       return _attribute_sections.size();
  2274     }
  2275 
  2276     /// \brief Returns the section name at the given position. 
  2277     ///
  2278     /// Returns the section name at the given position. 
  2279     const std::string& attributeSection(int i) const {
  2280       return _attribute_sections[i];
  2281     }
  2282 
  2283     /// \brief Gives back the attributes for the given section.
  2284     ///
  2285     /// Gives back the attributes for the given section.
  2286     const std::vector<std::string>& attributes(int i) const {
  2287       return _attributes[i];
  2288     }
  2289 
  2290     /// @}
  2291 
  2292     /// \name Extra sections   
  2293     /// @{
  2294 
  2295     /// \brief Gives back the number of extra sections in the file.
  2296     ///
  2297     /// Gives back the number of extra sections in the file.
  2298     int extraSectionNum() const {
  2299       return _extra_sections.size();
  2300     }
  2301 
  2302     /// \brief Returns the extra section type at the given position. 
  2303     ///
  2304     /// Returns the section type at the given position. 
  2305     const std::string& extraSection(int i) const {
  2306       return _extra_sections[i];
  2307     }
  2308 
  2309     /// @}
  2310 
  2311   private:
  2312 
  2313     bool readLine() {
  2314       std::string str;
  2315       while(++line_num, std::getline(*_is, str)) {
  2316 	line.clear(); line.str(str);
  2317 	char c;
  2318 	if (line >> std::ws >> c && c != '#') {
  2319 	  line.putback(c);
  2320 	  return true;
  2321 	}
  2322       }
  2323       return false;
  2324     }
  2325 
  2326     bool readSuccess() {
  2327       return static_cast<bool>(*_is);
  2328     }
  2329 
  2330     void skipSection() {
  2331       char c;
  2332       while (readSuccess() && line >> c && c != '@') {
  2333 	readLine();
  2334       }
  2335       line.putback(c);
  2336     }
  2337 
  2338     void readMaps(std::vector<std::string>& maps) {
  2339       if (!readLine()) 
  2340 	throw DataFormatError("Cannot find map captions");
  2341       std::string map;
  2342       while (_reader_bits::readToken(line, map)) {
  2343 	maps.push_back(map);
  2344       }
  2345     }
  2346 
  2347     void readAttributes(std::vector<std::string>& attrs) {
  2348       readLine();
  2349       char c;
  2350       while (readSuccess() && line >> c && c != '@') {
  2351 	line.putback(c);
  2352 	std::string attr;
  2353 	_reader_bits::readToken(line, attr);
  2354 	attrs.push_back(attr);
  2355 	readLine();
  2356       }
  2357       line.putback(c);
  2358     }
  2359 
  2360   public:
  2361 
  2362     /// \name Execution of the content reader    
  2363     /// @{
  2364 
  2365     /// \brief Start the reading
  2366     ///
  2367     /// This function starts the reading
  2368     void run() {
  2369 
  2370       readLine();
  2371       skipSection();
  2372 
  2373       while (readSuccess()) {
  2374 
  2375 	char c;
  2376 	line >> c;
  2377 
  2378 	std::string section, caption;
  2379 	_reader_bits::readToken(line, section);
  2380 	_reader_bits::readToken(line, caption);
  2381 
  2382 	if (section == "nodes") {
  2383 	  _node_sections.push_back(caption);
  2384 	  _node_maps.push_back(std::vector<std::string>());
  2385 	  readMaps(_node_maps.back());
  2386 	  readLine(); skipSection();
  2387 	} else if (section == "arcs" || section == "edges") {
  2388 	  _edge_sections.push_back(caption);
  2389 	  _arc_sections.push_back(section == "arcs");
  2390 	  _edge_maps.push_back(std::vector<std::string>());
  2391 	  readMaps(_edge_maps.back());
  2392 	  readLine(); skipSection();
  2393 	} else if (section == "attributes") {
  2394 	  _attribute_sections.push_back(caption);
  2395 	  _attributes.push_back(std::vector<std::string>());
  2396 	  readAttributes(_attributes.back());
  2397 	} else {
  2398 	  _extra_sections.push_back(section);
  2399 	  readLine(); skipSection();
  2400 	}
  2401       }
  2402     }
  2403 
  2404     /// @}
  2405     
  2406   };
  2407 }
  2408 
  2409 #endif