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