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