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