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