lemon/lgf_reader.h
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 07 Nov 2008 12:15:16 +0100
changeset 374 49d9a36b3b84
parent 303 a3a69f5bba62
child 427 33e9699c7d3a
child 498 afd134142111
permissions -rw-r--r--
Extend test cases for graphs and digraphs (#172)
     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       line.putback(c);
   874     }
   875 
   876     void readNodes() {
   877 
   878       std::vector<int> map_index(_node_maps.size());
   879       int map_num, label_index;
   880 
   881       char c;
   882       if (!readLine() || !(line >> c) || c == '@') {
   883         if (readSuccess() && line) line.putback(c);
   884         if (!_node_maps.empty())
   885           throw FormatError("Cannot find map names");
   886         return;
   887       }
   888       line.putback(c);
   889 
   890       {
   891         std::map<std::string, int> maps;
   892 
   893         std::string map;
   894         int index = 0;
   895         while (_reader_bits::readToken(line, map)) {
   896           if (maps.find(map) != maps.end()) {
   897             std::ostringstream msg;
   898             msg << "Multiple occurence of node map: " << map;
   899             throw FormatError(msg.str());
   900           }
   901           maps.insert(std::make_pair(map, index));
   902           ++index;
   903         }
   904 
   905         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   906           std::map<std::string, int>::iterator jt =
   907             maps.find(_node_maps[i].first);
   908           if (jt == maps.end()) {
   909             std::ostringstream msg;
   910             msg << "Map not found: " << _node_maps[i].first;
   911             throw FormatError(msg.str());
   912           }
   913           map_index[i] = jt->second;
   914         }
   915 
   916         {
   917           std::map<std::string, int>::iterator jt = maps.find("label");
   918           if (jt != maps.end()) {
   919             label_index = jt->second;
   920           } else {
   921             label_index = -1;
   922           }
   923         }
   924         map_num = maps.size();
   925       }
   926 
   927       while (readLine() && line >> c && c != '@') {
   928         line.putback(c);
   929 
   930         std::vector<std::string> tokens(map_num);
   931         for (int i = 0; i < map_num; ++i) {
   932           if (!_reader_bits::readToken(line, tokens[i])) {
   933             std::ostringstream msg;
   934             msg << "Column not found (" << i + 1 << ")";
   935             throw FormatError(msg.str());
   936           }
   937         }
   938         if (line >> std::ws >> c)
   939           throw FormatError("Extra character at the end of line");
   940 
   941         Node n;
   942         if (!_use_nodes) {
   943           n = _digraph.addNode();
   944           if (label_index != -1)
   945             _node_index.insert(std::make_pair(tokens[label_index], n));
   946         } else {
   947           if (label_index == -1)
   948             throw FormatError("Label map not found");
   949           typename std::map<std::string, Node>::iterator it =
   950             _node_index.find(tokens[label_index]);
   951           if (it == _node_index.end()) {
   952             std::ostringstream msg;
   953             msg << "Node with label not found: " << tokens[label_index];
   954             throw FormatError(msg.str());
   955           }
   956           n = it->second;
   957         }
   958 
   959         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   960           _node_maps[i].second->set(n, tokens[map_index[i]]);
   961         }
   962 
   963       }
   964       if (readSuccess()) {
   965         line.putback(c);
   966       }
   967     }
   968 
   969     void readArcs() {
   970 
   971       std::vector<int> map_index(_arc_maps.size());
   972       int map_num, label_index;
   973 
   974       char c;
   975       if (!readLine() || !(line >> c) || c == '@') {
   976         if (readSuccess() && line) line.putback(c);
   977         if (!_arc_maps.empty())
   978           throw FormatError("Cannot find map names");
   979         return;
   980       }
   981       line.putback(c);
   982 
   983       {
   984         std::map<std::string, int> maps;
   985 
   986         std::string map;
   987         int index = 0;
   988         while (_reader_bits::readToken(line, map)) {
   989           if (maps.find(map) != maps.end()) {
   990             std::ostringstream msg;
   991             msg << "Multiple occurence of arc map: " << map;
   992             throw FormatError(msg.str());
   993           }
   994           maps.insert(std::make_pair(map, index));
   995           ++index;
   996         }
   997 
   998         for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
   999           std::map<std::string, int>::iterator jt =
  1000             maps.find(_arc_maps[i].first);
  1001           if (jt == maps.end()) {
  1002             std::ostringstream msg;
  1003             msg << "Map not found: " << _arc_maps[i].first;
  1004             throw FormatError(msg.str());
  1005           }
  1006           map_index[i] = jt->second;
  1007         }
  1008 
  1009         {
  1010           std::map<std::string, int>::iterator jt = maps.find("label");
  1011           if (jt != maps.end()) {
  1012             label_index = jt->second;
  1013           } else {
  1014             label_index = -1;
  1015           }
  1016         }
  1017         map_num = maps.size();
  1018       }
  1019 
  1020       while (readLine() && line >> c && c != '@') {
  1021         line.putback(c);
  1022 
  1023         std::string source_token;
  1024         std::string target_token;
  1025 
  1026         if (!_reader_bits::readToken(line, source_token))
  1027           throw FormatError("Source not found");
  1028 
  1029         if (!_reader_bits::readToken(line, target_token))
  1030           throw FormatError("Target not found");
  1031 
  1032         std::vector<std::string> tokens(map_num);
  1033         for (int i = 0; i < map_num; ++i) {
  1034           if (!_reader_bits::readToken(line, tokens[i])) {
  1035             std::ostringstream msg;
  1036             msg << "Column not found (" << i + 1 << ")";
  1037             throw FormatError(msg.str());
  1038           }
  1039         }
  1040         if (line >> std::ws >> c)
  1041           throw FormatError("Extra character at the end of line");
  1042 
  1043         Arc a;
  1044         if (!_use_arcs) {
  1045 
  1046           typename NodeIndex::iterator it;
  1047 
  1048           it = _node_index.find(source_token);
  1049           if (it == _node_index.end()) {
  1050             std::ostringstream msg;
  1051             msg << "Item not found: " << source_token;
  1052             throw FormatError(msg.str());
  1053           }
  1054           Node source = it->second;
  1055 
  1056           it = _node_index.find(target_token);
  1057           if (it == _node_index.end()) {
  1058             std::ostringstream msg;
  1059             msg << "Item not found: " << target_token;
  1060             throw FormatError(msg.str());
  1061           }
  1062           Node target = it->second;
  1063 
  1064           a = _digraph.addArc(source, target);
  1065           if (label_index != -1)
  1066             _arc_index.insert(std::make_pair(tokens[label_index], a));
  1067         } else {
  1068           if (label_index == -1)
  1069             throw FormatError("Label map not found");
  1070           typename std::map<std::string, Arc>::iterator it =
  1071             _arc_index.find(tokens[label_index]);
  1072           if (it == _arc_index.end()) {
  1073             std::ostringstream msg;
  1074             msg << "Arc with label not found: " << tokens[label_index];
  1075             throw FormatError(msg.str());
  1076           }
  1077           a = it->second;
  1078         }
  1079 
  1080         for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
  1081           _arc_maps[i].second->set(a, tokens[map_index[i]]);
  1082         }
  1083 
  1084       }
  1085       if (readSuccess()) {
  1086         line.putback(c);
  1087       }
  1088     }
  1089 
  1090     void readAttributes() {
  1091 
  1092       std::set<std::string> read_attr;
  1093 
  1094       char c;
  1095       while (readLine() && line >> c && c != '@') {
  1096         line.putback(c);
  1097 
  1098         std::string attr, token;
  1099         if (!_reader_bits::readToken(line, attr))
  1100           throw FormatError("Attribute name not found");
  1101         if (!_reader_bits::readToken(line, token))
  1102           throw FormatError("Attribute value not found");
  1103         if (line >> c)
  1104           throw FormatError("Extra character at the end of line");
  1105 
  1106         {
  1107           std::set<std::string>::iterator it = read_attr.find(attr);
  1108           if (it != read_attr.end()) {
  1109             std::ostringstream msg;
  1110             msg << "Multiple occurence of attribute: " << attr;
  1111             throw FormatError(msg.str());
  1112           }
  1113           read_attr.insert(attr);
  1114         }
  1115 
  1116         {
  1117           typename Attributes::iterator it = _attributes.lower_bound(attr);
  1118           while (it != _attributes.end() && it->first == attr) {
  1119             it->second->set(token);
  1120             ++it;
  1121           }
  1122         }
  1123 
  1124       }
  1125       if (readSuccess()) {
  1126         line.putback(c);
  1127       }
  1128       for (typename Attributes::iterator it = _attributes.begin();
  1129            it != _attributes.end(); ++it) {
  1130         if (read_attr.find(it->first) == read_attr.end()) {
  1131           std::ostringstream msg;
  1132           msg << "Attribute not found: " << it->first;
  1133           throw FormatError(msg.str());
  1134         }
  1135       }
  1136     }
  1137 
  1138   public:
  1139 
  1140     /// \name Execution of the reader
  1141     /// @{
  1142 
  1143     /// \brief Start the batch processing
  1144     ///
  1145     /// This function starts the batch processing
  1146     void run() {
  1147       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1148 
  1149       bool nodes_done = _skip_nodes;
  1150       bool arcs_done = _skip_arcs;
  1151       bool attributes_done = false;
  1152 
  1153       line_num = 0;
  1154       readLine();
  1155       skipSection();
  1156 
  1157       while (readSuccess()) {
  1158         try {
  1159           char c;
  1160           std::string section, caption;
  1161           line >> c;
  1162           _reader_bits::readToken(line, section);
  1163           _reader_bits::readToken(line, caption);
  1164 
  1165           if (line >> c)
  1166             throw FormatError("Extra character at the end of line");
  1167 
  1168           if (section == "nodes" && !nodes_done) {
  1169             if (_nodes_caption.empty() || _nodes_caption == caption) {
  1170               readNodes();
  1171               nodes_done = true;
  1172             }
  1173           } else if ((section == "arcs" || section == "edges") &&
  1174                      !arcs_done) {
  1175             if (_arcs_caption.empty() || _arcs_caption == caption) {
  1176               readArcs();
  1177               arcs_done = true;
  1178             }
  1179           } else if (section == "attributes" && !attributes_done) {
  1180             if (_attributes_caption.empty() || _attributes_caption == caption) {
  1181               readAttributes();
  1182               attributes_done = true;
  1183             }
  1184           } else {
  1185             readLine();
  1186             skipSection();
  1187           }
  1188         } catch (FormatError& error) {
  1189           error.line(line_num);
  1190           error.file(_filename);
  1191           throw;
  1192         }
  1193       }
  1194 
  1195       if (!nodes_done) {
  1196         throw FormatError("Section @nodes not found");
  1197       }
  1198 
  1199       if (!arcs_done) {
  1200         throw FormatError("Section @arcs not found");
  1201       }
  1202 
  1203       if (!attributes_done && !_attributes.empty()) {
  1204         throw FormatError("Section @attributes not found");
  1205       }
  1206 
  1207     }
  1208 
  1209     /// @}
  1210 
  1211   };
  1212 
  1213   template <typename Graph>
  1214   class GraphReader;
  1215 
  1216   /// \brief Return a \ref GraphReader class
  1217   ///
  1218   /// This function just returns a \ref GraphReader class.
  1219   /// \relates GraphReader
  1220   template <typename Graph>
  1221   GraphReader<Graph> graphReader(Graph& graph, std::istream& is = std::cin) {
  1222     GraphReader<Graph> tmp(graph, is);
  1223     return tmp;
  1224   }
  1225 
  1226   /// \brief Return a \ref GraphReader class
  1227   ///
  1228   /// This function just returns a \ref GraphReader class.
  1229   /// \relates GraphReader
  1230   template <typename Graph>
  1231   GraphReader<Graph> graphReader(Graph& graph, const std::string& fn) {
  1232     GraphReader<Graph> tmp(graph, fn);
  1233     return tmp;
  1234   }
  1235 
  1236   /// \brief Return a \ref GraphReader class
  1237   ///
  1238   /// This function just returns a \ref GraphReader class.
  1239   /// \relates GraphReader
  1240   template <typename Graph>
  1241   GraphReader<Graph> graphReader(Graph& graph, const char* fn) {
  1242     GraphReader<Graph> tmp(graph, fn);
  1243     return tmp;
  1244   }
  1245 
  1246   /// \ingroup lemon_io
  1247   ///
  1248   /// \brief \ref lgf-format "LGF" reader for undirected graphs
  1249   ///
  1250   /// This utility reads an \ref lgf-format "LGF" file.
  1251   ///
  1252   /// It can be used almost the same way as \c DigraphReader.
  1253   /// The only difference is that this class can handle edges and
  1254   /// edge maps as well as arcs and arc maps.
  1255   ///
  1256   /// The columns in the \c \@edges (or \c \@arcs) section are the
  1257   /// edge maps. However, if there are two maps with the same name
  1258   /// prefixed with \c '+' and \c '-', then these can be read into an
  1259   /// arc map.  Similarly, an attribute can be read into an arc, if
  1260   /// it's value is an edge label prefixed with \c '+' or \c '-'.
  1261   template <typename _Graph>
  1262   class GraphReader {
  1263   public:
  1264 
  1265     typedef _Graph Graph;
  1266     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  1267 
  1268   private:
  1269 
  1270     std::istream* _is;
  1271     bool local_is;
  1272     std::string _filename;
  1273 
  1274     Graph& _graph;
  1275 
  1276     std::string _nodes_caption;
  1277     std::string _edges_caption;
  1278     std::string _attributes_caption;
  1279 
  1280     typedef std::map<std::string, Node> NodeIndex;
  1281     NodeIndex _node_index;
  1282     typedef std::map<std::string, Edge> EdgeIndex;
  1283     EdgeIndex _edge_index;
  1284 
  1285     typedef std::vector<std::pair<std::string,
  1286       _reader_bits::MapStorageBase<Node>*> > NodeMaps;
  1287     NodeMaps _node_maps;
  1288 
  1289     typedef std::vector<std::pair<std::string,
  1290       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  1291     EdgeMaps _edge_maps;
  1292 
  1293     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
  1294       Attributes;
  1295     Attributes _attributes;
  1296 
  1297     bool _use_nodes;
  1298     bool _use_edges;
  1299 
  1300     bool _skip_nodes;
  1301     bool _skip_edges;
  1302 
  1303     int line_num;
  1304     std::istringstream line;
  1305 
  1306   public:
  1307 
  1308     /// \brief Constructor
  1309     ///
  1310     /// Construct an undirected graph reader, which reads from the given
  1311     /// input stream.
  1312     GraphReader(Graph& graph, std::istream& is = std::cin)
  1313       : _is(&is), local_is(false), _graph(graph),
  1314         _use_nodes(false), _use_edges(false),
  1315         _skip_nodes(false), _skip_edges(false) {}
  1316 
  1317     /// \brief Constructor
  1318     ///
  1319     /// Construct an undirected graph reader, which reads from the given
  1320     /// file.
  1321     GraphReader(Graph& graph, const std::string& fn)
  1322       : _is(new std::ifstream(fn.c_str())), local_is(true),
  1323         _filename(fn), _graph(graph),
  1324         _use_nodes(false), _use_edges(false),
  1325         _skip_nodes(false), _skip_edges(false) {
  1326       if (!(*_is)) {
  1327         delete _is;
  1328         throw IoError("Cannot open file", fn);
  1329       }
  1330     }
  1331 
  1332     /// \brief Constructor
  1333     ///
  1334     /// Construct an undirected graph reader, which reads from the given
  1335     /// file.
  1336     GraphReader(Graph& graph, const char* fn)
  1337       : _is(new std::ifstream(fn)), local_is(true),
  1338         _filename(fn), _graph(graph),
  1339         _use_nodes(false), _use_edges(false),
  1340         _skip_nodes(false), _skip_edges(false) {
  1341       if (!(*_is)) {
  1342         delete _is;
  1343         throw IoError("Cannot open file", fn);
  1344       }
  1345     }
  1346 
  1347     /// \brief Destructor
  1348     ~GraphReader() {
  1349       for (typename NodeMaps::iterator it = _node_maps.begin();
  1350            it != _node_maps.end(); ++it) {
  1351         delete it->second;
  1352       }
  1353 
  1354       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1355            it != _edge_maps.end(); ++it) {
  1356         delete it->second;
  1357       }
  1358 
  1359       for (typename Attributes::iterator it = _attributes.begin();
  1360            it != _attributes.end(); ++it) {
  1361         delete it->second;
  1362       }
  1363 
  1364       if (local_is) {
  1365         delete _is;
  1366       }
  1367 
  1368     }
  1369 
  1370   private:
  1371     friend GraphReader<Graph> graphReader<>(Graph& graph, std::istream& is);
  1372     friend GraphReader<Graph> graphReader<>(Graph& graph,
  1373                                             const std::string& fn);
  1374     friend GraphReader<Graph> graphReader<>(Graph& graph, const char *fn);
  1375 
  1376     GraphReader(GraphReader& other)
  1377       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  1378         _use_nodes(other._use_nodes), _use_edges(other._use_edges),
  1379         _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1380 
  1381       other._is = 0;
  1382       other.local_is = false;
  1383 
  1384       _node_index.swap(other._node_index);
  1385       _edge_index.swap(other._edge_index);
  1386 
  1387       _node_maps.swap(other._node_maps);
  1388       _edge_maps.swap(other._edge_maps);
  1389       _attributes.swap(other._attributes);
  1390 
  1391       _nodes_caption = other._nodes_caption;
  1392       _edges_caption = other._edges_caption;
  1393       _attributes_caption = other._attributes_caption;
  1394 
  1395     }
  1396 
  1397     GraphReader& operator=(const GraphReader&);
  1398 
  1399   public:
  1400 
  1401     /// \name Reading rules
  1402     /// @{
  1403 
  1404     /// \brief Node map reading rule
  1405     ///
  1406     /// Add a node map reading rule to the reader.
  1407     template <typename Map>
  1408     GraphReader& nodeMap(const std::string& caption, Map& map) {
  1409       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1410       _reader_bits::MapStorageBase<Node>* storage =
  1411         new _reader_bits::MapStorage<Node, Map>(map);
  1412       _node_maps.push_back(std::make_pair(caption, storage));
  1413       return *this;
  1414     }
  1415 
  1416     /// \brief Node map reading rule
  1417     ///
  1418     /// Add a node map reading rule with specialized converter to the
  1419     /// reader.
  1420     template <typename Map, typename Converter>
  1421     GraphReader& nodeMap(const std::string& caption, Map& map,
  1422                            const Converter& converter = Converter()) {
  1423       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1424       _reader_bits::MapStorageBase<Node>* storage =
  1425         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  1426       _node_maps.push_back(std::make_pair(caption, storage));
  1427       return *this;
  1428     }
  1429 
  1430     /// \brief Edge map reading rule
  1431     ///
  1432     /// Add an edge map reading rule to the reader.
  1433     template <typename Map>
  1434     GraphReader& edgeMap(const std::string& caption, Map& map) {
  1435       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1436       _reader_bits::MapStorageBase<Edge>* storage =
  1437         new _reader_bits::MapStorage<Edge, Map>(map);
  1438       _edge_maps.push_back(std::make_pair(caption, storage));
  1439       return *this;
  1440     }
  1441 
  1442     /// \brief Edge map reading rule
  1443     ///
  1444     /// Add an edge map reading rule with specialized converter to the
  1445     /// reader.
  1446     template <typename Map, typename Converter>
  1447     GraphReader& edgeMap(const std::string& caption, Map& map,
  1448                           const Converter& converter = Converter()) {
  1449       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1450       _reader_bits::MapStorageBase<Edge>* storage =
  1451         new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1452       _edge_maps.push_back(std::make_pair(caption, storage));
  1453       return *this;
  1454     }
  1455 
  1456     /// \brief Arc map reading rule
  1457     ///
  1458     /// Add an arc map reading rule to the reader.
  1459     template <typename Map>
  1460     GraphReader& arcMap(const std::string& caption, Map& map) {
  1461       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1462       _reader_bits::MapStorageBase<Edge>* forward_storage =
  1463         new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1464       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1465       _reader_bits::MapStorageBase<Edge>* backward_storage =
  1466         new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
  1467       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1468       return *this;
  1469     }
  1470 
  1471     /// \brief Arc map reading rule
  1472     ///
  1473     /// Add an arc map reading rule with specialized converter to the
  1474     /// reader.
  1475     template <typename Map, typename Converter>
  1476     GraphReader& arcMap(const std::string& caption, Map& map,
  1477                           const Converter& converter = Converter()) {
  1478       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1479       _reader_bits::MapStorageBase<Edge>* forward_storage =
  1480         new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
  1481         (_graph, map, converter);
  1482       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1483       _reader_bits::MapStorageBase<Edge>* backward_storage =
  1484         new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
  1485         (_graph, map, converter);
  1486       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1487       return *this;
  1488     }
  1489 
  1490     /// \brief Attribute reading rule
  1491     ///
  1492     /// Add an attribute reading rule to the reader.
  1493     template <typename Value>
  1494     GraphReader& attribute(const std::string& caption, Value& value) {
  1495       _reader_bits::ValueStorageBase* storage =
  1496         new _reader_bits::ValueStorage<Value>(value);
  1497       _attributes.insert(std::make_pair(caption, storage));
  1498       return *this;
  1499     }
  1500 
  1501     /// \brief Attribute reading rule
  1502     ///
  1503     /// Add an attribute reading rule with specialized converter to the
  1504     /// reader.
  1505     template <typename Value, typename Converter>
  1506     GraphReader& attribute(const std::string& caption, Value& value,
  1507                              const Converter& converter = Converter()) {
  1508       _reader_bits::ValueStorageBase* storage =
  1509         new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  1510       _attributes.insert(std::make_pair(caption, storage));
  1511       return *this;
  1512     }
  1513 
  1514     /// \brief Node reading rule
  1515     ///
  1516     /// Add a node reading rule to reader.
  1517     GraphReader& node(const std::string& caption, Node& node) {
  1518       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  1519       Converter converter(_node_index);
  1520       _reader_bits::ValueStorageBase* storage =
  1521         new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  1522       _attributes.insert(std::make_pair(caption, storage));
  1523       return *this;
  1524     }
  1525 
  1526     /// \brief Edge reading rule
  1527     ///
  1528     /// Add an edge reading rule to reader.
  1529     GraphReader& edge(const std::string& caption, Edge& edge) {
  1530       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  1531       Converter converter(_edge_index);
  1532       _reader_bits::ValueStorageBase* storage =
  1533         new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  1534       _attributes.insert(std::make_pair(caption, storage));
  1535       return *this;
  1536     }
  1537 
  1538     /// \brief Arc reading rule
  1539     ///
  1540     /// Add an arc reading rule to reader.
  1541     GraphReader& arc(const std::string& caption, Arc& arc) {
  1542       typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
  1543       Converter converter(_graph, _edge_index);
  1544       _reader_bits::ValueStorageBase* storage =
  1545         new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  1546       _attributes.insert(std::make_pair(caption, storage));
  1547       return *this;
  1548     }
  1549 
  1550     /// @}
  1551 
  1552     /// \name Select section by name
  1553     /// @{
  1554 
  1555     /// \brief Set \c \@nodes section to be read
  1556     ///
  1557     /// Set \c \@nodes section to be read.
  1558     GraphReader& nodes(const std::string& caption) {
  1559       _nodes_caption = caption;
  1560       return *this;
  1561     }
  1562 
  1563     /// \brief Set \c \@edges section to be read
  1564     ///
  1565     /// Set \c \@edges section to be read.
  1566     GraphReader& edges(const std::string& caption) {
  1567       _edges_caption = caption;
  1568       return *this;
  1569     }
  1570 
  1571     /// \brief Set \c \@attributes section to be read
  1572     ///
  1573     /// Set \c \@attributes section to be read.
  1574     GraphReader& attributes(const std::string& caption) {
  1575       _attributes_caption = caption;
  1576       return *this;
  1577     }
  1578 
  1579     /// @}
  1580 
  1581     /// \name Using previously constructed node or edge set
  1582     /// @{
  1583 
  1584     /// \brief Use previously constructed node set
  1585     ///
  1586     /// Use previously constructed node set, and specify the node
  1587     /// label map.
  1588     template <typename Map>
  1589     GraphReader& useNodes(const Map& map) {
  1590       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1591       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
  1592       _use_nodes = true;
  1593       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1594       for (NodeIt n(_graph); n != INVALID; ++n) {
  1595         _node_index.insert(std::make_pair(converter(map[n]), n));
  1596       }
  1597       return *this;
  1598     }
  1599 
  1600     /// \brief Use previously constructed node set
  1601     ///
  1602     /// Use previously constructed node set, and specify the node
  1603     /// label map and a functor which converts the label map values to
  1604     /// \c std::string.
  1605     template <typename Map, typename Converter>
  1606     GraphReader& useNodes(const Map& map,
  1607                             const Converter& converter = Converter()) {
  1608       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1609       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
  1610       _use_nodes = true;
  1611       for (NodeIt n(_graph); n != INVALID; ++n) {
  1612         _node_index.insert(std::make_pair(converter(map[n]), n));
  1613       }
  1614       return *this;
  1615     }
  1616 
  1617     /// \brief Use previously constructed edge set
  1618     ///
  1619     /// Use previously constructed edge set, and specify the edge
  1620     /// label map.
  1621     template <typename Map>
  1622     GraphReader& useEdges(const Map& map) {
  1623       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1624       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1625       _use_edges = true;
  1626       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1627       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1628         _edge_index.insert(std::make_pair(converter(map[a]), a));
  1629       }
  1630       return *this;
  1631     }
  1632 
  1633     /// \brief Use previously constructed edge set
  1634     ///
  1635     /// Use previously constructed edge set, and specify the edge
  1636     /// label map and a functor which converts the label map values to
  1637     /// \c std::string.
  1638     template <typename Map, typename Converter>
  1639     GraphReader& useEdges(const Map& map,
  1640                             const Converter& converter = Converter()) {
  1641       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1642       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1643       _use_edges = true;
  1644       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1645         _edge_index.insert(std::make_pair(converter(map[a]), a));
  1646       }
  1647       return *this;
  1648     }
  1649 
  1650     /// \brief Skip the reading of node section
  1651     ///
  1652     /// Omit the reading of the node section. This implies that each node
  1653     /// map reading rule will be abandoned, and the nodes of the graph
  1654     /// will not be constructed, which usually cause that the edge set
  1655     /// could not be read due to lack of node name
  1656     /// could not be read due to lack of node name resolving.
  1657     /// Therefore \c skipEdges() function should also be used, or
  1658     /// \c useNodes() should be used to specify the label of the nodes.
  1659     GraphReader& skipNodes() {
  1660       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
  1661       _skip_nodes = true;
  1662       return *this;
  1663     }
  1664 
  1665     /// \brief Skip the reading of edge section
  1666     ///
  1667     /// Omit the reading of the edge section. This implies that each edge
  1668     /// map reading rule will be abandoned, and the edges of the graph
  1669     /// will not be constructed.
  1670     GraphReader& skipEdges() {
  1671       LEMON_ASSERT(!_skip_edges, "Skip edges already set");
  1672       _skip_edges = true;
  1673       return *this;
  1674     }
  1675 
  1676     /// @}
  1677 
  1678   private:
  1679 
  1680     bool readLine() {
  1681       std::string str;
  1682       while(++line_num, std::getline(*_is, str)) {
  1683         line.clear(); line.str(str);
  1684         char c;
  1685         if (line >> std::ws >> c && c != '#') {
  1686           line.putback(c);
  1687           return true;
  1688         }
  1689       }
  1690       return false;
  1691     }
  1692 
  1693     bool readSuccess() {
  1694       return static_cast<bool>(*_is);
  1695     }
  1696 
  1697     void skipSection() {
  1698       char c;
  1699       while (readSuccess() && line >> c && c != '@') {
  1700         readLine();
  1701       }
  1702       line.putback(c);
  1703     }
  1704 
  1705     void readNodes() {
  1706 
  1707       std::vector<int> map_index(_node_maps.size());
  1708       int map_num, label_index;
  1709 
  1710       char c;
  1711       if (!readLine() || !(line >> c) || c == '@') {
  1712         if (readSuccess() && line) line.putback(c);
  1713         if (!_node_maps.empty())
  1714           throw FormatError("Cannot find map names");
  1715         return;
  1716       }
  1717       line.putback(c);
  1718 
  1719       {
  1720         std::map<std::string, int> maps;
  1721 
  1722         std::string map;
  1723         int index = 0;
  1724         while (_reader_bits::readToken(line, map)) {
  1725           if (maps.find(map) != maps.end()) {
  1726             std::ostringstream msg;
  1727             msg << "Multiple occurence of node map: " << map;
  1728             throw FormatError(msg.str());
  1729           }
  1730           maps.insert(std::make_pair(map, index));
  1731           ++index;
  1732         }
  1733 
  1734         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1735           std::map<std::string, int>::iterator jt =
  1736             maps.find(_node_maps[i].first);
  1737           if (jt == maps.end()) {
  1738             std::ostringstream msg;
  1739             msg << "Map not found: " << _node_maps[i].first;
  1740             throw FormatError(msg.str());
  1741           }
  1742           map_index[i] = jt->second;
  1743         }
  1744 
  1745         {
  1746           std::map<std::string, int>::iterator jt = maps.find("label");
  1747           if (jt != maps.end()) {
  1748             label_index = jt->second;
  1749           } else {
  1750             label_index = -1;
  1751           }
  1752         }
  1753         map_num = maps.size();
  1754       }
  1755 
  1756       while (readLine() && line >> c && c != '@') {
  1757         line.putback(c);
  1758 
  1759         std::vector<std::string> tokens(map_num);
  1760         for (int i = 0; i < map_num; ++i) {
  1761           if (!_reader_bits::readToken(line, tokens[i])) {
  1762             std::ostringstream msg;
  1763             msg << "Column not found (" << i + 1 << ")";
  1764             throw FormatError(msg.str());
  1765           }
  1766         }
  1767         if (line >> std::ws >> c)
  1768           throw FormatError("Extra character at the end of line");
  1769 
  1770         Node n;
  1771         if (!_use_nodes) {
  1772           n = _graph.addNode();
  1773           if (label_index != -1)
  1774             _node_index.insert(std::make_pair(tokens[label_index], n));
  1775         } else {
  1776           if (label_index == -1)
  1777             throw FormatError("Label map not found");
  1778           typename std::map<std::string, Node>::iterator it =
  1779             _node_index.find(tokens[label_index]);
  1780           if (it == _node_index.end()) {
  1781             std::ostringstream msg;
  1782             msg << "Node with label not found: " << tokens[label_index];
  1783             throw FormatError(msg.str());
  1784           }
  1785           n = it->second;
  1786         }
  1787 
  1788         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1789           _node_maps[i].second->set(n, tokens[map_index[i]]);
  1790         }
  1791 
  1792       }
  1793       if (readSuccess()) {
  1794         line.putback(c);
  1795       }
  1796     }
  1797 
  1798     void readEdges() {
  1799 
  1800       std::vector<int> map_index(_edge_maps.size());
  1801       int map_num, label_index;
  1802 
  1803       char c;
  1804       if (!readLine() || !(line >> c) || c == '@') {
  1805         if (readSuccess() && line) line.putback(c);
  1806         if (!_edge_maps.empty())
  1807           throw FormatError("Cannot find map names");
  1808         return;
  1809       }
  1810       line.putback(c);
  1811 
  1812       {
  1813         std::map<std::string, int> maps;
  1814 
  1815         std::string map;
  1816         int index = 0;
  1817         while (_reader_bits::readToken(line, map)) {
  1818           if (maps.find(map) != maps.end()) {
  1819             std::ostringstream msg;
  1820             msg << "Multiple occurence of edge map: " << map;
  1821             throw FormatError(msg.str());
  1822           }
  1823           maps.insert(std::make_pair(map, index));
  1824           ++index;
  1825         }
  1826 
  1827         for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1828           std::map<std::string, int>::iterator jt =
  1829             maps.find(_edge_maps[i].first);
  1830           if (jt == maps.end()) {
  1831             std::ostringstream msg;
  1832             msg << "Map not found: " << _edge_maps[i].first;
  1833             throw FormatError(msg.str());
  1834           }
  1835           map_index[i] = jt->second;
  1836         }
  1837 
  1838         {
  1839           std::map<std::string, int>::iterator jt = maps.find("label");
  1840           if (jt != maps.end()) {
  1841             label_index = jt->second;
  1842           } else {
  1843             label_index = -1;
  1844           }
  1845         }
  1846         map_num = maps.size();
  1847       }
  1848 
  1849       while (readLine() && line >> c && c != '@') {
  1850         line.putback(c);
  1851 
  1852         std::string source_token;
  1853         std::string target_token;
  1854 
  1855         if (!_reader_bits::readToken(line, source_token))
  1856           throw FormatError("Node u not found");
  1857 
  1858         if (!_reader_bits::readToken(line, target_token))
  1859           throw FormatError("Node v not found");
  1860 
  1861         std::vector<std::string> tokens(map_num);
  1862         for (int i = 0; i < map_num; ++i) {
  1863           if (!_reader_bits::readToken(line, tokens[i])) {
  1864             std::ostringstream msg;
  1865             msg << "Column not found (" << i + 1 << ")";
  1866             throw FormatError(msg.str());
  1867           }
  1868         }
  1869         if (line >> std::ws >> c)
  1870           throw FormatError("Extra character at the end of line");
  1871 
  1872         Edge e;
  1873         if (!_use_edges) {
  1874 
  1875           typename NodeIndex::iterator it;
  1876 
  1877           it = _node_index.find(source_token);
  1878           if (it == _node_index.end()) {
  1879             std::ostringstream msg;
  1880             msg << "Item not found: " << source_token;
  1881             throw FormatError(msg.str());
  1882           }
  1883           Node source = it->second;
  1884 
  1885           it = _node_index.find(target_token);
  1886           if (it == _node_index.end()) {
  1887             std::ostringstream msg;
  1888             msg << "Item not found: " << target_token;
  1889             throw FormatError(msg.str());
  1890           }
  1891           Node target = it->second;
  1892 
  1893           e = _graph.addEdge(source, target);
  1894           if (label_index != -1)
  1895             _edge_index.insert(std::make_pair(tokens[label_index], e));
  1896         } else {
  1897           if (label_index == -1)
  1898             throw FormatError("Label map not found");
  1899           typename std::map<std::string, Edge>::iterator it =
  1900             _edge_index.find(tokens[label_index]);
  1901           if (it == _edge_index.end()) {
  1902             std::ostringstream msg;
  1903             msg << "Edge with label not found: " << tokens[label_index];
  1904             throw FormatError(msg.str());
  1905           }
  1906           e = it->second;
  1907         }
  1908 
  1909         for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1910           _edge_maps[i].second->set(e, tokens[map_index[i]]);
  1911         }
  1912 
  1913       }
  1914       if (readSuccess()) {
  1915         line.putback(c);
  1916       }
  1917     }
  1918 
  1919     void readAttributes() {
  1920 
  1921       std::set<std::string> read_attr;
  1922 
  1923       char c;
  1924       while (readLine() && line >> c && c != '@') {
  1925         line.putback(c);
  1926 
  1927         std::string attr, token;
  1928         if (!_reader_bits::readToken(line, attr))
  1929           throw FormatError("Attribute name not found");
  1930         if (!_reader_bits::readToken(line, token))
  1931           throw FormatError("Attribute value not found");
  1932         if (line >> c)
  1933           throw FormatError("Extra character at the end of line");
  1934 
  1935         {
  1936           std::set<std::string>::iterator it = read_attr.find(attr);
  1937           if (it != read_attr.end()) {
  1938             std::ostringstream msg;
  1939             msg << "Multiple occurence of attribute: " << attr;
  1940             throw FormatError(msg.str());
  1941           }
  1942           read_attr.insert(attr);
  1943         }
  1944 
  1945         {
  1946           typename Attributes::iterator it = _attributes.lower_bound(attr);
  1947           while (it != _attributes.end() && it->first == attr) {
  1948             it->second->set(token);
  1949             ++it;
  1950           }
  1951         }
  1952 
  1953       }
  1954       if (readSuccess()) {
  1955         line.putback(c);
  1956       }
  1957       for (typename Attributes::iterator it = _attributes.begin();
  1958            it != _attributes.end(); ++it) {
  1959         if (read_attr.find(it->first) == read_attr.end()) {
  1960           std::ostringstream msg;
  1961           msg << "Attribute not found: " << it->first;
  1962           throw FormatError(msg.str());
  1963         }
  1964       }
  1965     }
  1966 
  1967   public:
  1968 
  1969     /// \name Execution of the reader
  1970     /// @{
  1971 
  1972     /// \brief Start the batch processing
  1973     ///
  1974     /// This function starts the batch processing
  1975     void run() {
  1976 
  1977       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1978 
  1979       bool nodes_done = _skip_nodes;
  1980       bool edges_done = _skip_edges;
  1981       bool attributes_done = false;
  1982 
  1983       line_num = 0;
  1984       readLine();
  1985       skipSection();
  1986 
  1987       while (readSuccess()) {
  1988         try {
  1989           char c;
  1990           std::string section, caption;
  1991           line >> c;
  1992           _reader_bits::readToken(line, section);
  1993           _reader_bits::readToken(line, caption);
  1994 
  1995           if (line >> c)
  1996             throw FormatError("Extra character at the end of line");
  1997 
  1998           if (section == "nodes" && !nodes_done) {
  1999             if (_nodes_caption.empty() || _nodes_caption == caption) {
  2000               readNodes();
  2001               nodes_done = true;
  2002             }
  2003           } else if ((section == "edges" || section == "arcs") &&
  2004                      !edges_done) {
  2005             if (_edges_caption.empty() || _edges_caption == caption) {
  2006               readEdges();
  2007               edges_done = true;
  2008             }
  2009           } else if (section == "attributes" && !attributes_done) {
  2010             if (_attributes_caption.empty() || _attributes_caption == caption) {
  2011               readAttributes();
  2012               attributes_done = true;
  2013             }
  2014           } else {
  2015             readLine();
  2016             skipSection();
  2017           }
  2018         } catch (FormatError& error) {
  2019           error.line(line_num);
  2020           error.file(_filename);
  2021           throw;
  2022         }
  2023       }
  2024 
  2025       if (!nodes_done) {
  2026         throw FormatError("Section @nodes not found");
  2027       }
  2028 
  2029       if (!edges_done) {
  2030         throw FormatError("Section @edges not found");
  2031       }
  2032 
  2033       if (!attributes_done && !_attributes.empty()) {
  2034         throw FormatError("Section @attributes not found");
  2035       }
  2036 
  2037     }
  2038 
  2039     /// @}
  2040 
  2041   };
  2042 
  2043   class SectionReader;
  2044 
  2045   SectionReader sectionReader(std::istream& is);
  2046   SectionReader sectionReader(const std::string& fn);
  2047   SectionReader sectionReader(const char* fn);
  2048 
  2049   /// \ingroup lemon_io
  2050   ///
  2051   /// \brief Section reader class
  2052   ///
  2053   /// In the \ref lgf-format "LGF" file extra sections can be placed,
  2054   /// which contain any data in arbitrary format. Such sections can be
  2055   /// read with this class. A reading rule can be added to the class
  2056   /// with two different functions. With the \c sectionLines() function a
  2057   /// functor can process the section line-by-line, while with the \c
  2058   /// sectionStream() member the section can be read from an input
  2059   /// stream.
  2060   class SectionReader {
  2061   private:
  2062 
  2063     std::istream* _is;
  2064     bool local_is;
  2065     std::string _filename;
  2066 
  2067     typedef std::map<std::string, _reader_bits::Section*> Sections;
  2068     Sections _sections;
  2069 
  2070     int line_num;
  2071     std::istringstream line;
  2072 
  2073   public:
  2074 
  2075     /// \brief Constructor
  2076     ///
  2077     /// Construct a section reader, which reads from the given input
  2078     /// stream.
  2079     SectionReader(std::istream& is)
  2080       : _is(&is), local_is(false) {}
  2081 
  2082     /// \brief Constructor
  2083     ///
  2084     /// Construct a section reader, which reads from the given file.
  2085     SectionReader(const std::string& fn)
  2086       : _is(new std::ifstream(fn.c_str())), local_is(true),
  2087         _filename(fn) {
  2088       if (!(*_is)) {
  2089         delete _is;
  2090         throw IoError("Cannot open file", fn);
  2091       }
  2092     }
  2093 
  2094     /// \brief Constructor
  2095     ///
  2096     /// Construct a section reader, which reads from the given file.
  2097     SectionReader(const char* fn)
  2098       : _is(new std::ifstream(fn)), local_is(true),
  2099         _filename(fn) {
  2100       if (!(*_is)) {
  2101         delete _is;
  2102         throw IoError("Cannot open file", fn);
  2103       }
  2104     }
  2105 
  2106     /// \brief Destructor
  2107     ~SectionReader() {
  2108       for (Sections::iterator it = _sections.begin();
  2109            it != _sections.end(); ++it) {
  2110         delete it->second;
  2111       }
  2112 
  2113       if (local_is) {
  2114         delete _is;
  2115       }
  2116 
  2117     }
  2118 
  2119   private:
  2120 
  2121     friend SectionReader sectionReader(std::istream& is);
  2122     friend SectionReader sectionReader(const std::string& fn);
  2123     friend SectionReader sectionReader(const char* fn);
  2124 
  2125     SectionReader(SectionReader& other)
  2126       : _is(other._is), local_is(other.local_is) {
  2127 
  2128       other._is = 0;
  2129       other.local_is = false;
  2130 
  2131       _sections.swap(other._sections);
  2132     }
  2133 
  2134     SectionReader& operator=(const SectionReader&);
  2135 
  2136   public:
  2137 
  2138     /// \name Section readers
  2139     /// @{
  2140 
  2141     /// \brief Add a section processor with line oriented reading
  2142     ///
  2143     /// The first parameter is the type descriptor of the section, the
  2144     /// second is a functor, which takes just one \c std::string
  2145     /// parameter. At the reading process, each line of the section
  2146     /// will be given to the functor object. However, the empty lines
  2147     /// and the comment lines are filtered out, and the leading
  2148     /// whitespaces are trimmed from each processed string.
  2149     ///
  2150     /// For example let's see a section, which contain several
  2151     /// integers, which should be inserted into a vector.
  2152     ///\code
  2153     ///  @numbers
  2154     ///  12 45 23
  2155     ///  4
  2156     ///  23 6
  2157     ///\endcode
  2158     ///
  2159     /// The functor is implemented as a struct:
  2160     ///\code
  2161     ///  struct NumberSection {
  2162     ///    std::vector<int>& _data;
  2163     ///    NumberSection(std::vector<int>& data) : _data(data) {}
  2164     ///    void operator()(const std::string& line) {
  2165     ///      std::istringstream ls(line);
  2166     ///      int value;
  2167     ///      while (ls >> value) _data.push_back(value);
  2168     ///    }
  2169     ///  };
  2170     ///
  2171     ///  // ...
  2172     ///
  2173     ///  reader.sectionLines("numbers", NumberSection(vec));
  2174     ///\endcode
  2175     template <typename Functor>
  2176     SectionReader& sectionLines(const std::string& type, Functor functor) {
  2177       LEMON_ASSERT(!type.empty(), "Type is empty.");
  2178       LEMON_ASSERT(_sections.find(type) == _sections.end(),
  2179                    "Multiple reading of section.");
  2180       _sections.insert(std::make_pair(type,
  2181         new _reader_bits::LineSection<Functor>(functor)));
  2182       return *this;
  2183     }
  2184 
  2185 
  2186     /// \brief Add a section processor with stream oriented reading
  2187     ///
  2188     /// The first parameter is the type of the section, the second is
  2189     /// a functor, which takes an \c std::istream& and an \c int&
  2190     /// parameter, the latter regard to the line number of stream. The
  2191     /// functor can read the input while the section go on, and the
  2192     /// line number should be modified accordingly.
  2193     template <typename Functor>
  2194     SectionReader& sectionStream(const std::string& type, Functor functor) {
  2195       LEMON_ASSERT(!type.empty(), "Type is empty.");
  2196       LEMON_ASSERT(_sections.find(type) == _sections.end(),
  2197                    "Multiple reading of section.");
  2198       _sections.insert(std::make_pair(type,
  2199          new _reader_bits::StreamSection<Functor>(functor)));
  2200       return *this;
  2201     }
  2202 
  2203     /// @}
  2204 
  2205   private:
  2206 
  2207     bool readLine() {
  2208       std::string str;
  2209       while(++line_num, std::getline(*_is, str)) {
  2210         line.clear(); line.str(str);
  2211         char c;
  2212         if (line >> std::ws >> c && c != '#') {
  2213           line.putback(c);
  2214           return true;
  2215         }
  2216       }
  2217       return false;
  2218     }
  2219 
  2220     bool readSuccess() {
  2221       return static_cast<bool>(*_is);
  2222     }
  2223 
  2224     void skipSection() {
  2225       char c;
  2226       while (readSuccess() && line >> c && c != '@') {
  2227         readLine();
  2228       }
  2229       line.putback(c);
  2230     }
  2231 
  2232   public:
  2233 
  2234 
  2235     /// \name Execution of the reader
  2236     /// @{
  2237 
  2238     /// \brief Start the batch processing
  2239     ///
  2240     /// This function starts the batch processing.
  2241     void run() {
  2242 
  2243       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  2244 
  2245       std::set<std::string> extra_sections;
  2246 
  2247       line_num = 0;
  2248       readLine();
  2249       skipSection();
  2250 
  2251       while (readSuccess()) {
  2252         try {
  2253           char c;
  2254           std::string section, caption;
  2255           line >> c;
  2256           _reader_bits::readToken(line, section);
  2257           _reader_bits::readToken(line, caption);
  2258 
  2259           if (line >> c)
  2260             throw FormatError("Extra character at the end of line");
  2261 
  2262           if (extra_sections.find(section) != extra_sections.end()) {
  2263             std::ostringstream msg;
  2264             msg << "Multiple occurence of section: " << section;
  2265             throw FormatError(msg.str());
  2266           }
  2267           Sections::iterator it = _sections.find(section);
  2268           if (it != _sections.end()) {
  2269             extra_sections.insert(section);
  2270             it->second->process(*_is, line_num);
  2271           }
  2272           readLine();
  2273           skipSection();
  2274         } catch (FormatError& error) {
  2275           error.line(line_num);
  2276           error.file(_filename);
  2277           throw;
  2278         }
  2279       }
  2280       for (Sections::iterator it = _sections.begin();
  2281            it != _sections.end(); ++it) {
  2282         if (extra_sections.find(it->first) == extra_sections.end()) {
  2283           std::ostringstream os;
  2284           os << "Cannot find section: " << it->first;
  2285           throw FormatError(os.str());
  2286         }
  2287       }
  2288     }
  2289 
  2290     /// @}
  2291 
  2292   };
  2293 
  2294   /// \brief Return a \ref SectionReader class
  2295   ///
  2296   /// This function just returns a \ref SectionReader class.
  2297   /// \relates SectionReader
  2298   inline SectionReader sectionReader(std::istream& is) {
  2299     SectionReader tmp(is);
  2300     return tmp;
  2301   }
  2302 
  2303   /// \brief Return a \ref SectionReader class
  2304   ///
  2305   /// This function just returns a \ref SectionReader class.
  2306   /// \relates SectionReader
  2307   inline SectionReader sectionReader(const std::string& fn) {
  2308     SectionReader tmp(fn);
  2309     return tmp;
  2310   }
  2311 
  2312   /// \brief Return a \ref SectionReader class
  2313   ///
  2314   /// This function just returns a \ref SectionReader class.
  2315   /// \relates SectionReader
  2316   inline SectionReader sectionReader(const char* fn) {
  2317     SectionReader tmp(fn);
  2318     return tmp;
  2319   }
  2320 
  2321   /// \ingroup lemon_io
  2322   ///
  2323   /// \brief Reader for the contents of the \ref lgf-format "LGF" file
  2324   ///
  2325   /// This class can be used to read the sections, the map names and
  2326   /// the attributes from a file. Usually, the LEMON programs know
  2327   /// that, which type of graph, which maps and which attributes
  2328   /// should be read from a file, but in general tools (like glemon)
  2329   /// the contents of an LGF file should be guessed somehow. This class
  2330   /// reads the graph and stores the appropriate information for
  2331   /// reading the graph.
  2332   ///
  2333   ///\code
  2334   /// LgfContents contents("graph.lgf");
  2335   /// contents.run();
  2336   ///
  2337   /// // Does it contain any node section and arc section?
  2338   /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
  2339   ///   std::cerr << "Failure, cannot find graph." << std::endl;
  2340   ///   return -1;
  2341   /// }
  2342   /// std::cout << "The name of the default node section: "
  2343   ///           << contents.nodeSection(0) << std::endl;
  2344   /// std::cout << "The number of the arc maps: "
  2345   ///           << contents.arcMaps(0).size() << std::endl;
  2346   /// std::cout << "The name of second arc map: "
  2347   ///           << contents.arcMaps(0)[1] << std::endl;
  2348   ///\endcode
  2349   class LgfContents {
  2350   private:
  2351 
  2352     std::istream* _is;
  2353     bool local_is;
  2354 
  2355     std::vector<std::string> _node_sections;
  2356     std::vector<std::string> _edge_sections;
  2357     std::vector<std::string> _attribute_sections;
  2358     std::vector<std::string> _extra_sections;
  2359 
  2360     std::vector<bool> _arc_sections;
  2361 
  2362     std::vector<std::vector<std::string> > _node_maps;
  2363     std::vector<std::vector<std::string> > _edge_maps;
  2364 
  2365     std::vector<std::vector<std::string> > _attributes;
  2366 
  2367 
  2368     int line_num;
  2369     std::istringstream line;
  2370 
  2371   public:
  2372 
  2373     /// \brief Constructor
  2374     ///
  2375     /// Construct an \e LGF contents reader, which reads from the given
  2376     /// input stream.
  2377     LgfContents(std::istream& is)
  2378       : _is(&is), local_is(false) {}
  2379 
  2380     /// \brief Constructor
  2381     ///
  2382     /// Construct an \e LGF contents reader, which reads from the given
  2383     /// file.
  2384     LgfContents(const std::string& fn)
  2385       : _is(new std::ifstream(fn.c_str())), local_is(true) {
  2386       if (!(*_is)) {
  2387         delete _is;
  2388         throw IoError("Cannot open file", fn);
  2389       }
  2390     }
  2391 
  2392     /// \brief Constructor
  2393     ///
  2394     /// Construct an \e LGF contents reader, which reads from the given
  2395     /// file.
  2396     LgfContents(const char* fn)
  2397       : _is(new std::ifstream(fn)), local_is(true) {
  2398       if (!(*_is)) {
  2399         delete _is;
  2400         throw IoError("Cannot open file", fn);
  2401       }
  2402     }
  2403 
  2404     /// \brief Destructor
  2405     ~LgfContents() {
  2406       if (local_is) delete _is;
  2407     }
  2408 
  2409   private:
  2410 
  2411     LgfContents(const LgfContents&);
  2412     LgfContents& operator=(const LgfContents&);
  2413 
  2414   public:
  2415 
  2416 
  2417     /// \name Node sections
  2418     /// @{
  2419 
  2420     /// \brief Gives back the number of node sections in the file.
  2421     ///
  2422     /// Gives back the number of node sections in the file.
  2423     int nodeSectionNum() const {
  2424       return _node_sections.size();
  2425     }
  2426 
  2427     /// \brief Returns the node section name at the given position.
  2428     ///
  2429     /// Returns the node section name at the given position.
  2430     const std::string& nodeSection(int i) const {
  2431       return _node_sections[i];
  2432     }
  2433 
  2434     /// \brief Gives back the node maps for the given section.
  2435     ///
  2436     /// Gives back the node maps for the given section.
  2437     const std::vector<std::string>& nodeMapNames(int i) const {
  2438       return _node_maps[i];
  2439     }
  2440 
  2441     /// @}
  2442 
  2443     /// \name Arc/Edge sections
  2444     /// @{
  2445 
  2446     /// \brief Gives back the number of arc/edge sections in the file.
  2447     ///
  2448     /// Gives back the number of arc/edge sections in the file.
  2449     /// \note It is synonym of \c edgeSectionNum().
  2450     int arcSectionNum() const {
  2451       return _edge_sections.size();
  2452     }
  2453 
  2454     /// \brief Returns the arc/edge section name at the given position.
  2455     ///
  2456     /// Returns the arc/edge section name at the given position.
  2457     /// \note It is synonym of \c edgeSection().
  2458     const std::string& arcSection(int i) const {
  2459       return _edge_sections[i];
  2460     }
  2461 
  2462     /// \brief Gives back the arc/edge maps for the given section.
  2463     ///
  2464     /// Gives back the arc/edge maps for the given section.
  2465     /// \note It is synonym of \c edgeMapNames().
  2466     const std::vector<std::string>& arcMapNames(int i) const {
  2467       return _edge_maps[i];
  2468     }
  2469 
  2470     /// @}
  2471 
  2472     /// \name Synonyms
  2473     /// @{
  2474 
  2475     /// \brief Gives back the number of arc/edge sections in the file.
  2476     ///
  2477     /// Gives back the number of arc/edge sections in the file.
  2478     /// \note It is synonym of \c arcSectionNum().
  2479     int edgeSectionNum() const {
  2480       return _edge_sections.size();
  2481     }
  2482 
  2483     /// \brief Returns the section name at the given position.
  2484     ///
  2485     /// Returns the section name at the given position.
  2486     /// \note It is synonym of \c arcSection().
  2487     const std::string& edgeSection(int i) const {
  2488       return _edge_sections[i];
  2489     }
  2490 
  2491     /// \brief Gives back the edge maps for the given section.
  2492     ///
  2493     /// Gives back the edge maps for the given section.
  2494     /// \note It is synonym of \c arcMapNames().
  2495     const std::vector<std::string>& edgeMapNames(int i) const {
  2496       return _edge_maps[i];
  2497     }
  2498 
  2499     /// @}
  2500 
  2501     /// \name Attribute sections
  2502     /// @{
  2503 
  2504     /// \brief Gives back the number of attribute sections in the file.
  2505     ///
  2506     /// Gives back the number of attribute sections in the file.
  2507     int attributeSectionNum() const {
  2508       return _attribute_sections.size();
  2509     }
  2510 
  2511     /// \brief Returns the attribute section name at the given position.
  2512     ///
  2513     /// Returns the attribute section name at the given position.
  2514     const std::string& attributeSectionNames(int i) const {
  2515       return _attribute_sections[i];
  2516     }
  2517 
  2518     /// \brief Gives back the attributes for the given section.
  2519     ///
  2520     /// Gives back the attributes for the given section.
  2521     const std::vector<std::string>& attributes(int i) const {
  2522       return _attributes[i];
  2523     }
  2524 
  2525     /// @}
  2526 
  2527     /// \name Extra sections
  2528     /// @{
  2529 
  2530     /// \brief Gives back the number of extra sections in the file.
  2531     ///
  2532     /// Gives back the number of extra sections in the file.
  2533     int extraSectionNum() const {
  2534       return _extra_sections.size();
  2535     }
  2536 
  2537     /// \brief Returns the extra section type at the given position.
  2538     ///
  2539     /// Returns the section type at the given position.
  2540     const std::string& extraSection(int i) const {
  2541       return _extra_sections[i];
  2542     }
  2543 
  2544     /// @}
  2545 
  2546   private:
  2547 
  2548     bool readLine() {
  2549       std::string str;
  2550       while(++line_num, std::getline(*_is, str)) {
  2551         line.clear(); line.str(str);
  2552         char c;
  2553         if (line >> std::ws >> c && c != '#') {
  2554           line.putback(c);
  2555           return true;
  2556         }
  2557       }
  2558       return false;
  2559     }
  2560 
  2561     bool readSuccess() {
  2562       return static_cast<bool>(*_is);
  2563     }
  2564 
  2565     void skipSection() {
  2566       char c;
  2567       while (readSuccess() && line >> c && c != '@') {
  2568         readLine();
  2569       }
  2570       line.putback(c);
  2571     }
  2572 
  2573     void readMaps(std::vector<std::string>& maps) {
  2574       char c;
  2575       if (!readLine() || !(line >> c) || c == '@') {
  2576         if (readSuccess() && line) line.putback(c);
  2577         return;
  2578       }
  2579       line.putback(c);
  2580       std::string map;
  2581       while (_reader_bits::readToken(line, map)) {
  2582         maps.push_back(map);
  2583       }
  2584     }
  2585 
  2586     void readAttributes(std::vector<std::string>& attrs) {
  2587       readLine();
  2588       char c;
  2589       while (readSuccess() && line >> c && c != '@') {
  2590         line.putback(c);
  2591         std::string attr;
  2592         _reader_bits::readToken(line, attr);
  2593         attrs.push_back(attr);
  2594         readLine();
  2595       }
  2596       line.putback(c);
  2597     }
  2598 
  2599   public:
  2600 
  2601     /// \name Execution of the contents reader
  2602     /// @{
  2603 
  2604     /// \brief Starts the reading
  2605     ///
  2606     /// This function starts the reading.
  2607     void run() {
  2608 
  2609       readLine();
  2610       skipSection();
  2611 
  2612       while (readSuccess()) {
  2613 
  2614         char c;
  2615         line >> c;
  2616 
  2617         std::string section, caption;
  2618         _reader_bits::readToken(line, section);
  2619         _reader_bits::readToken(line, caption);
  2620 
  2621         if (section == "nodes") {
  2622           _node_sections.push_back(caption);
  2623           _node_maps.push_back(std::vector<std::string>());
  2624           readMaps(_node_maps.back());
  2625           readLine(); skipSection();
  2626         } else if (section == "arcs" || section == "edges") {
  2627           _edge_sections.push_back(caption);
  2628           _arc_sections.push_back(section == "arcs");
  2629           _edge_maps.push_back(std::vector<std::string>());
  2630           readMaps(_edge_maps.back());
  2631           readLine(); skipSection();
  2632         } else if (section == "attributes") {
  2633           _attribute_sections.push_back(caption);
  2634           _attributes.push_back(std::vector<std::string>());
  2635           readAttributes(_attributes.back());
  2636         } else {
  2637           _extra_sections.push_back(section);
  2638           readLine(); skipSection();
  2639         }
  2640       }
  2641     }
  2642 
  2643     /// @}
  2644 
  2645   };
  2646 }
  2647 
  2648 #endif