lemon/lgf_reader.h
author Daniel Poroszkai <poroszd@inf.elte.hu>
Sun, 05 Feb 2012 00:04:44 +0100
changeset 1197 374a9519986b
parent 1194 699c7eac2c6d
child 1198 4936be66d2f5
permissions -rw-r--r--
Update LGF reader to work with typesafe bipartite node sets (#69)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2011
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 ///\ingroup lemon_io
    20 ///\file
    21 ///\brief \ref lgf-format "LEMON Graph Format" reader.
    22 
    23 
    24 #ifndef LEMON_LGF_READER_H
    25 #define LEMON_LGF_READER_H
    26 
    27 #include <iostream>
    28 #include <fstream>
    29 #include <sstream>
    30 
    31 #include <set>
    32 #include <map>
    33 
    34 #include <lemon/core.h>
    35 
    36 #include <lemon/lgf_writer.h>
    37 
    38 #include <lemon/concept_check.h>
    39 #include <lemon/concepts/maps.h>
    40 
    41 namespace lemon {
    42 
    43   namespace _reader_bits {
    44 
    45     template <typename Value>
    46     struct DefaultConverter {
    47       Value operator()(const std::string& str) {
    48         std::istringstream is(str);
    49         Value value;
    50         if (!(is >> value)) {
    51           throw FormatError("Cannot read token");
    52         }
    53 
    54         char c;
    55         if (is >> std::ws >> c) {
    56           throw FormatError("Remaining characters in token");
    57         }
    58         return value;
    59       }
    60     };
    61 
    62     template <>
    63     struct DefaultConverter<std::string> {
    64       std::string operator()(const std::string& str) {
    65         return str;
    66       }
    67     };
    68 
    69     template <typename _Item>
    70     class MapStorageBase {
    71     public:
    72       typedef _Item Item;
    73 
    74     public:
    75       MapStorageBase() {}
    76       virtual ~MapStorageBase() {}
    77 
    78       virtual void set(const Item& item, const std::string& value) = 0;
    79 
    80     };
    81 
    82     template <typename _Item, typename _Map,
    83               typename _Converter = DefaultConverter<typename _Map::Value> >
    84     class MapStorage : public MapStorageBase<_Item> {
    85     public:
    86       typedef _Map Map;
    87       typedef _Converter Converter;
    88       typedef _Item Item;
    89 
    90     private:
    91       Map& _map;
    92       Converter _converter;
    93 
    94     public:
    95       MapStorage(Map& map, const Converter& converter = Converter())
    96         : _map(map), _converter(converter) {}
    97       virtual ~MapStorage() {}
    98 
    99       virtual void set(const Item& item ,const std::string& value) {
   100         _map.set(item, _converter(value));
   101       }
   102     };
   103 
   104     template <typename _GR, bool _dir, typename _Map,
   105               typename _Converter = DefaultConverter<typename _Map::Value> >
   106     class GraphArcMapStorage : public MapStorageBase<typename _GR::Edge> {
   107     public:
   108       typedef _Map Map;
   109       typedef _Converter Converter;
   110       typedef _GR GR;
   111       typedef typename GR::Edge Item;
   112       static const bool dir = _dir;
   113 
   114     private:
   115       const GR& _graph;
   116       Map& _map;
   117       Converter _converter;
   118 
   119     public:
   120       GraphArcMapStorage(const GR& 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 GR>
   177     struct GraphArcLookUpConverter {
   178       const GR& _graph;
   179       const std::map<std::string, typename GR::Edge>& _map;
   180 
   181       GraphArcLookUpConverter(const GR& graph,
   182                               const std::map<std::string,
   183                                              typename GR::Edge>& map)
   184         : _graph(graph), _map(map) {}
   185 
   186       typename GR::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 GR::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 DGR>
   391   class DigraphReader;
   392 
   393   template <typename TDGR>
   394   DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin);
   395   template <typename TDGR>
   396   DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn);
   397   template <typename TDGR>
   398   DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
   399 
   400   /// \ingroup lemon_io
   401   ///
   402   /// \brief \ref lgf-format "LGF" reader for directed graphs
   403   ///
   404   /// This utility reads an \ref lgf-format "LGF" file.
   405   ///
   406   /// The reading method does a batch processing. The user creates a
   407   /// reader object, then various reading rules can be added to the
   408   /// reader, and eventually the reading is executed with the \c run()
   409   /// member function. A map reading rule can be added to the reader
   410   /// with the \c nodeMap() or \c arcMap() members. An optional
   411   /// converter parameter can also be added as a standard functor
   412   /// converting from \c std::string to the value type of the map. If it
   413   /// is set, it will determine how the tokens in the file should be
   414   /// converted to the value type of the map. If the functor is not set,
   415   /// then a default conversion will be used. One map can be read into
   416   /// multiple map objects at the same time. The \c attribute(), \c
   417   /// node() and \c arc() functions are used to add attribute reading
   418   /// rules.
   419   ///
   420   ///\code
   421   /// DigraphReader<DGR>(digraph, std::cin).
   422   ///   nodeMap("coordinates", coord_map).
   423   ///   arcMap("capacity", cap_map).
   424   ///   node("source", src).
   425   ///   node("target", trg).
   426   ///   attribute("caption", caption).
   427   ///   run();
   428   ///\endcode
   429   ///
   430   /// By default, the reader uses the first section in the file of the
   431   /// proper type. If a section has an optional name, then it can be
   432   /// selected for reading by giving an optional name parameter to the
   433   /// \c nodes(), \c arcs() or \c attributes() functions.
   434   ///
   435   /// The \c useNodes() and \c useArcs() functions are used to tell the reader
   436   /// that the nodes or arcs should not be constructed (added to the
   437   /// graph) during the reading, but instead the label map of the items
   438   /// are given as a parameter of these functions. An
   439   /// application of these functions is multipass reading, which is
   440   /// important if two \c \@arcs sections must be read from the
   441   /// file. In this case the first phase would read the node set and one
   442   /// of the arc sets, while the second phase would read the second arc
   443   /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
   444   /// The previously read label node map should be passed to the \c
   445   /// useNodes() functions. Another application of multipass reading when
   446   /// paths are given as a node map or an arc map.
   447   /// It is impossible to read this in
   448   /// a single pass, because the arcs are not constructed when the node
   449   /// maps are read.
   450   template <typename DGR>
   451   class DigraphReader {
   452   public:
   453 
   454     typedef DGR Digraph;
   455 
   456   private:
   457 
   458     TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
   459 
   460     std::istream* _is;
   461     bool local_is;
   462     std::string _filename;
   463 
   464     DGR& _digraph;
   465 
   466     std::string _nodes_caption;
   467     std::string _arcs_caption;
   468     std::string _attributes_caption;
   469 
   470     typedef std::map<std::string, Node> NodeIndex;
   471     NodeIndex _node_index;
   472     typedef std::map<std::string, Arc> ArcIndex;
   473     ArcIndex _arc_index;
   474 
   475     typedef std::vector<std::pair<std::string,
   476       _reader_bits::MapStorageBase<Node>*> > NodeMaps;
   477     NodeMaps _node_maps;
   478 
   479     typedef std::vector<std::pair<std::string,
   480       _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
   481     ArcMaps _arc_maps;
   482 
   483     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
   484       Attributes;
   485     Attributes _attributes;
   486 
   487     bool _use_nodes;
   488     bool _use_arcs;
   489 
   490     bool _skip_nodes;
   491     bool _skip_arcs;
   492 
   493     int line_num;
   494     std::istringstream line;
   495 
   496   public:
   497 
   498     /// \brief Constructor
   499     ///
   500     /// Construct a directed graph reader, which reads from the given
   501     /// input stream.
   502     DigraphReader(DGR& digraph, std::istream& is = std::cin)
   503       : _is(&is), local_is(false), _digraph(digraph),
   504         _use_nodes(false), _use_arcs(false),
   505         _skip_nodes(false), _skip_arcs(false) {}
   506 
   507     /// \brief Constructor
   508     ///
   509     /// Construct a directed graph reader, which reads from the given
   510     /// file.
   511     DigraphReader(DGR& digraph, const std::string& fn)
   512       : _is(new std::ifstream(fn.c_str())), local_is(true),
   513         _filename(fn), _digraph(digraph),
   514         _use_nodes(false), _use_arcs(false),
   515         _skip_nodes(false), _skip_arcs(false) {
   516       if (!(*_is)) {
   517         delete _is;
   518         throw IoError("Cannot open file", fn);
   519       }
   520     }
   521 
   522     /// \brief Constructor
   523     ///
   524     /// Construct a directed graph reader, which reads from the given
   525     /// file.
   526     DigraphReader(DGR& digraph, const char* fn)
   527       : _is(new std::ifstream(fn)), local_is(true),
   528         _filename(fn), _digraph(digraph),
   529         _use_nodes(false), _use_arcs(false),
   530         _skip_nodes(false), _skip_arcs(false) {
   531       if (!(*_is)) {
   532         delete _is;
   533         throw IoError("Cannot open file", fn);
   534       }
   535     }
   536 
   537     /// \brief Destructor
   538     ~DigraphReader() {
   539       for (typename NodeMaps::iterator it = _node_maps.begin();
   540            it != _node_maps.end(); ++it) {
   541         delete it->second;
   542       }
   543 
   544       for (typename ArcMaps::iterator it = _arc_maps.begin();
   545            it != _arc_maps.end(); ++it) {
   546         delete it->second;
   547       }
   548 
   549       for (typename Attributes::iterator it = _attributes.begin();
   550            it != _attributes.end(); ++it) {
   551         delete it->second;
   552       }
   553 
   554       if (local_is) {
   555         delete _is;
   556       }
   557 
   558     }
   559 
   560   private:
   561 
   562     template <typename TDGR>
   563     friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
   564     template <typename TDGR>
   565     friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
   566                                              const std::string& fn);
   567     template <typename TDGR>
   568     friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
   569 
   570     DigraphReader(DigraphReader& other)
   571       : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
   572         _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
   573         _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
   574 
   575       other._is = 0;
   576       other.local_is = false;
   577 
   578       _node_index.swap(other._node_index);
   579       _arc_index.swap(other._arc_index);
   580 
   581       _node_maps.swap(other._node_maps);
   582       _arc_maps.swap(other._arc_maps);
   583       _attributes.swap(other._attributes);
   584 
   585       _nodes_caption = other._nodes_caption;
   586       _arcs_caption = other._arcs_caption;
   587       _attributes_caption = other._attributes_caption;
   588 
   589     }
   590 
   591     DigraphReader& operator=(const DigraphReader&);
   592 
   593   public:
   594 
   595     /// \name Reading Rules
   596     /// @{
   597 
   598     /// \brief Node map reading rule
   599     ///
   600     /// Add a node map reading rule to the reader.
   601     template <typename Map>
   602     DigraphReader& nodeMap(const std::string& caption, Map& map) {
   603       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
   604       _reader_bits::MapStorageBase<Node>* storage =
   605         new _reader_bits::MapStorage<Node, Map>(map);
   606       _node_maps.push_back(std::make_pair(caption, storage));
   607       return *this;
   608     }
   609 
   610     /// \brief Node map reading rule
   611     ///
   612     /// Add a node map reading rule with specialized converter to the
   613     /// reader.
   614     template <typename Map, typename Converter>
   615     DigraphReader& nodeMap(const std::string& caption, Map& map,
   616                            const Converter& converter = Converter()) {
   617       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
   618       _reader_bits::MapStorageBase<Node>* storage =
   619         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
   620       _node_maps.push_back(std::make_pair(caption, storage));
   621       return *this;
   622     }
   623 
   624     /// \brief Arc map reading rule
   625     ///
   626     /// Add an arc map reading rule to the reader.
   627     template <typename Map>
   628     DigraphReader& arcMap(const std::string& caption, Map& map) {
   629       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
   630       _reader_bits::MapStorageBase<Arc>* storage =
   631         new _reader_bits::MapStorage<Arc, Map>(map);
   632       _arc_maps.push_back(std::make_pair(caption, storage));
   633       return *this;
   634     }
   635 
   636     /// \brief Arc map reading rule
   637     ///
   638     /// Add an arc map reading rule with specialized converter to the
   639     /// reader.
   640     template <typename Map, typename Converter>
   641     DigraphReader& arcMap(const std::string& caption, Map& map,
   642                           const Converter& converter = Converter()) {
   643       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
   644       _reader_bits::MapStorageBase<Arc>* storage =
   645         new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
   646       _arc_maps.push_back(std::make_pair(caption, storage));
   647       return *this;
   648     }
   649 
   650     /// \brief Attribute reading rule
   651     ///
   652     /// Add an attribute reading rule to the reader.
   653     template <typename Value>
   654     DigraphReader& attribute(const std::string& caption, Value& value) {
   655       _reader_bits::ValueStorageBase* storage =
   656         new _reader_bits::ValueStorage<Value>(value);
   657       _attributes.insert(std::make_pair(caption, storage));
   658       return *this;
   659     }
   660 
   661     /// \brief Attribute reading rule
   662     ///
   663     /// Add an attribute reading rule with specialized converter to the
   664     /// reader.
   665     template <typename Value, typename Converter>
   666     DigraphReader& attribute(const std::string& caption, Value& value,
   667                              const Converter& converter = Converter()) {
   668       _reader_bits::ValueStorageBase* storage =
   669         new _reader_bits::ValueStorage<Value, Converter>(value, converter);
   670       _attributes.insert(std::make_pair(caption, storage));
   671       return *this;
   672     }
   673 
   674     /// \brief Node reading rule
   675     ///
   676     /// Add a node reading rule to reader.
   677     DigraphReader& node(const std::string& caption, Node& node) {
   678       typedef _reader_bits::MapLookUpConverter<Node> Converter;
   679       Converter converter(_node_index);
   680       _reader_bits::ValueStorageBase* storage =
   681         new _reader_bits::ValueStorage<Node, Converter>(node, converter);
   682       _attributes.insert(std::make_pair(caption, storage));
   683       return *this;
   684     }
   685 
   686     /// \brief Arc reading rule
   687     ///
   688     /// Add an arc reading rule to reader.
   689     DigraphReader& arc(const std::string& caption, Arc& arc) {
   690       typedef _reader_bits::MapLookUpConverter<Arc> Converter;
   691       Converter converter(_arc_index);
   692       _reader_bits::ValueStorageBase* storage =
   693         new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
   694       _attributes.insert(std::make_pair(caption, storage));
   695       return *this;
   696     }
   697 
   698     /// @}
   699 
   700     /// \name Select Section by Name
   701     /// @{
   702 
   703     /// \brief Set \c \@nodes section to be read
   704     ///
   705     /// Set \c \@nodes section to be read
   706     DigraphReader& nodes(const std::string& caption) {
   707       _nodes_caption = caption;
   708       return *this;
   709     }
   710 
   711     /// \brief Set \c \@arcs section to be read
   712     ///
   713     /// Set \c \@arcs section to be read
   714     DigraphReader& arcs(const std::string& caption) {
   715       _arcs_caption = caption;
   716       return *this;
   717     }
   718 
   719     /// \brief Set \c \@attributes section to be read
   720     ///
   721     /// Set \c \@attributes section to be read
   722     DigraphReader& attributes(const std::string& caption) {
   723       _attributes_caption = caption;
   724       return *this;
   725     }
   726 
   727     /// @}
   728 
   729     /// \name Using Previously Constructed Node or Arc Set
   730     /// @{
   731 
   732     /// \brief Use previously constructed node set
   733     ///
   734     /// Use previously constructed node set, and specify the node
   735     /// label map.
   736     template <typename Map>
   737     DigraphReader& useNodes(const Map& map) {
   738       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   739       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
   740       _use_nodes = true;
   741       _writer_bits::DefaultConverter<typename Map::Value> converter;
   742       for (NodeIt n(_digraph); n != INVALID; ++n) {
   743         _node_index.insert(std::make_pair(converter(map[n]), n));
   744       }
   745       return *this;
   746     }
   747 
   748     /// \brief Use previously constructed node set
   749     ///
   750     /// Use previously constructed node set, and specify the node
   751     /// label map and a functor which converts the label map values to
   752     /// \c std::string.
   753     template <typename Map, typename Converter>
   754     DigraphReader& useNodes(const Map& map,
   755                             const Converter& converter = Converter()) {
   756       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
   757       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
   758       _use_nodes = true;
   759       for (NodeIt n(_digraph); n != INVALID; ++n) {
   760         _node_index.insert(std::make_pair(converter(map[n]), n));
   761       }
   762       return *this;
   763     }
   764 
   765     /// \brief Use previously constructed arc set
   766     ///
   767     /// Use previously constructed arc set, and specify the arc
   768     /// label map.
   769     template <typename Map>
   770     DigraphReader& useArcs(const Map& map) {
   771       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   772       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
   773       _use_arcs = true;
   774       _writer_bits::DefaultConverter<typename Map::Value> converter;
   775       for (ArcIt a(_digraph); a != INVALID; ++a) {
   776         _arc_index.insert(std::make_pair(converter(map[a]), a));
   777       }
   778       return *this;
   779     }
   780 
   781     /// \brief Use previously constructed arc set
   782     ///
   783     /// Use previously constructed arc set, and specify the arc
   784     /// label map and a functor which converts the label map values to
   785     /// \c std::string.
   786     template <typename Map, typename Converter>
   787     DigraphReader& useArcs(const Map& map,
   788                            const Converter& converter = Converter()) {
   789       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
   790       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
   791       _use_arcs = true;
   792       for (ArcIt a(_digraph); a != INVALID; ++a) {
   793         _arc_index.insert(std::make_pair(converter(map[a]), a));
   794       }
   795       return *this;
   796     }
   797 
   798     /// \brief Skips the reading of node section
   799     ///
   800     /// Omit the reading of the node section. This implies that each node
   801     /// map reading rule will be abandoned, and the nodes of the graph
   802     /// will not be constructed, which usually cause that the arc set
   803     /// could not be read due to lack of node name resolving.
   804     /// Therefore \c skipArcs() function should also be used, or
   805     /// \c useNodes() should be used to specify the label of the nodes.
   806     DigraphReader& skipNodes() {
   807       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
   808       _skip_nodes = true;
   809       return *this;
   810     }
   811 
   812     /// \brief Skips the reading of arc section
   813     ///
   814     /// Omit the reading of the arc section. This implies that each arc
   815     /// map reading rule will be abandoned, and the arcs of the graph
   816     /// will not be constructed.
   817     DigraphReader& skipArcs() {
   818       LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
   819       _skip_arcs = true;
   820       return *this;
   821     }
   822 
   823     /// @}
   824 
   825   private:
   826 
   827     bool readLine() {
   828       std::string str;
   829       while(++line_num, std::getline(*_is, str)) {
   830         line.clear(); line.str(str);
   831         char c;
   832         if (line >> std::ws >> c && c != '#') {
   833           line.putback(c);
   834           return true;
   835         }
   836       }
   837       return false;
   838     }
   839 
   840     bool readSuccess() {
   841       return static_cast<bool>(*_is);
   842     }
   843 
   844     void skipSection() {
   845       char c;
   846       while (readSuccess() && line >> c && c != '@') {
   847         readLine();
   848       }
   849       if (readSuccess()) {
   850         line.putback(c);
   851       }
   852     }
   853 
   854     void readNodes() {
   855 
   856       std::vector<int> map_index(_node_maps.size());
   857       int map_num, label_index;
   858 
   859       char c;
   860       if (!readLine() || !(line >> c) || c == '@') {
   861         if (readSuccess() && line) line.putback(c);
   862         if (!_node_maps.empty())
   863           throw FormatError("Cannot find map names");
   864         return;
   865       }
   866       line.putback(c);
   867 
   868       {
   869         std::map<std::string, int> maps;
   870 
   871         std::string map;
   872         int index = 0;
   873         while (_reader_bits::readToken(line, map)) {
   874           if (maps.find(map) != maps.end()) {
   875             std::ostringstream msg;
   876             msg << "Multiple occurence of node map: " << map;
   877             throw FormatError(msg.str());
   878           }
   879           maps.insert(std::make_pair(map, index));
   880           ++index;
   881         }
   882 
   883         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   884           std::map<std::string, int>::iterator jt =
   885             maps.find(_node_maps[i].first);
   886           if (jt == maps.end()) {
   887             std::ostringstream msg;
   888             msg << "Map not found: " << _node_maps[i].first;
   889             throw FormatError(msg.str());
   890           }
   891           map_index[i] = jt->second;
   892         }
   893 
   894         {
   895           std::map<std::string, int>::iterator jt = maps.find("label");
   896           if (jt != maps.end()) {
   897             label_index = jt->second;
   898           } else {
   899             label_index = -1;
   900           }
   901         }
   902         map_num = maps.size();
   903       }
   904 
   905       while (readLine() && line >> c && c != '@') {
   906         line.putback(c);
   907 
   908         std::vector<std::string> tokens(map_num);
   909         for (int i = 0; i < map_num; ++i) {
   910           if (!_reader_bits::readToken(line, tokens[i])) {
   911             std::ostringstream msg;
   912             msg << "Column not found (" << i + 1 << ")";
   913             throw FormatError(msg.str());
   914           }
   915         }
   916         if (line >> std::ws >> c)
   917           throw FormatError("Extra character at the end of line");
   918 
   919         Node n;
   920         if (!_use_nodes) {
   921           n = _digraph.addNode();
   922           if (label_index != -1)
   923             _node_index.insert(std::make_pair(tokens[label_index], n));
   924         } else {
   925           if (label_index == -1)
   926             throw FormatError("Label map not found");
   927           typename std::map<std::string, Node>::iterator it =
   928             _node_index.find(tokens[label_index]);
   929           if (it == _node_index.end()) {
   930             std::ostringstream msg;
   931             msg << "Node with label not found: " << tokens[label_index];
   932             throw FormatError(msg.str());
   933           }
   934           n = it->second;
   935         }
   936 
   937         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
   938           _node_maps[i].second->set(n, tokens[map_index[i]]);
   939         }
   940 
   941       }
   942       if (readSuccess()) {
   943         line.putback(c);
   944       }
   945     }
   946 
   947     void readArcs() {
   948 
   949       std::vector<int> map_index(_arc_maps.size());
   950       int map_num, label_index;
   951 
   952       char c;
   953       if (!readLine() || !(line >> c) || c == '@') {
   954         if (readSuccess() && line) line.putback(c);
   955         if (!_arc_maps.empty())
   956           throw FormatError("Cannot find map names");
   957         return;
   958       }
   959       line.putback(c);
   960 
   961       {
   962         std::map<std::string, int> maps;
   963 
   964         std::string map;
   965         int index = 0;
   966         while (_reader_bits::readToken(line, map)) {
   967           if(map == "-") {
   968               if(index!=0)
   969                 throw FormatError("'-' is not allowed as a map name");
   970               else if (line >> std::ws >> c)
   971                 throw FormatError("Extra character at the end of line");
   972               else break;
   973             }
   974           if (maps.find(map) != maps.end()) {
   975             std::ostringstream msg;
   976             msg << "Multiple occurence of arc map: " << map;
   977             throw FormatError(msg.str());
   978           }
   979           maps.insert(std::make_pair(map, index));
   980           ++index;
   981         }
   982 
   983         for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
   984           std::map<std::string, int>::iterator jt =
   985             maps.find(_arc_maps[i].first);
   986           if (jt == maps.end()) {
   987             std::ostringstream msg;
   988             msg << "Map not found: " << _arc_maps[i].first;
   989             throw FormatError(msg.str());
   990           }
   991           map_index[i] = jt->second;
   992         }
   993 
   994         {
   995           std::map<std::string, int>::iterator jt = maps.find("label");
   996           if (jt != maps.end()) {
   997             label_index = jt->second;
   998           } else {
   999             label_index = -1;
  1000           }
  1001         }
  1002         map_num = maps.size();
  1003       }
  1004 
  1005       while (readLine() && line >> c && c != '@') {
  1006         line.putback(c);
  1007 
  1008         std::string source_token;
  1009         std::string target_token;
  1010 
  1011         if (!_reader_bits::readToken(line, source_token))
  1012           throw FormatError("Source not found");
  1013 
  1014         if (!_reader_bits::readToken(line, target_token))
  1015           throw FormatError("Target not found");
  1016 
  1017         std::vector<std::string> tokens(map_num);
  1018         for (int i = 0; i < map_num; ++i) {
  1019           if (!_reader_bits::readToken(line, tokens[i])) {
  1020             std::ostringstream msg;
  1021             msg << "Column not found (" << i + 1 << ")";
  1022             throw FormatError(msg.str());
  1023           }
  1024         }
  1025         if (line >> std::ws >> c)
  1026           throw FormatError("Extra character at the end of line");
  1027 
  1028         Arc a;
  1029         if (!_use_arcs) {
  1030 
  1031           typename NodeIndex::iterator it;
  1032 
  1033           it = _node_index.find(source_token);
  1034           if (it == _node_index.end()) {
  1035             std::ostringstream msg;
  1036             msg << "Item not found: " << source_token;
  1037             throw FormatError(msg.str());
  1038           }
  1039           Node source = it->second;
  1040 
  1041           it = _node_index.find(target_token);
  1042           if (it == _node_index.end()) {
  1043             std::ostringstream msg;
  1044             msg << "Item not found: " << target_token;
  1045             throw FormatError(msg.str());
  1046           }
  1047           Node target = it->second;
  1048 
  1049           a = _digraph.addArc(source, target);
  1050           if (label_index != -1)
  1051             _arc_index.insert(std::make_pair(tokens[label_index], a));
  1052         } else {
  1053           if (label_index == -1)
  1054             throw FormatError("Label map not found");
  1055           typename std::map<std::string, Arc>::iterator it =
  1056             _arc_index.find(tokens[label_index]);
  1057           if (it == _arc_index.end()) {
  1058             std::ostringstream msg;
  1059             msg << "Arc with label not found: " << tokens[label_index];
  1060             throw FormatError(msg.str());
  1061           }
  1062           a = it->second;
  1063         }
  1064 
  1065         for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
  1066           _arc_maps[i].second->set(a, tokens[map_index[i]]);
  1067         }
  1068 
  1069       }
  1070       if (readSuccess()) {
  1071         line.putback(c);
  1072       }
  1073     }
  1074 
  1075     void readAttributes() {
  1076 
  1077       std::set<std::string> read_attr;
  1078 
  1079       char c;
  1080       while (readLine() && line >> c && c != '@') {
  1081         line.putback(c);
  1082 
  1083         std::string attr, token;
  1084         if (!_reader_bits::readToken(line, attr))
  1085           throw FormatError("Attribute name not found");
  1086         if (!_reader_bits::readToken(line, token))
  1087           throw FormatError("Attribute value not found");
  1088         if (line >> c)
  1089           throw FormatError("Extra character at the end of line");
  1090 
  1091         {
  1092           std::set<std::string>::iterator it = read_attr.find(attr);
  1093           if (it != read_attr.end()) {
  1094             std::ostringstream msg;
  1095             msg << "Multiple occurence of attribute: " << attr;
  1096             throw FormatError(msg.str());
  1097           }
  1098           read_attr.insert(attr);
  1099         }
  1100 
  1101         {
  1102           typename Attributes::iterator it = _attributes.lower_bound(attr);
  1103           while (it != _attributes.end() && it->first == attr) {
  1104             it->second->set(token);
  1105             ++it;
  1106           }
  1107         }
  1108 
  1109       }
  1110       if (readSuccess()) {
  1111         line.putback(c);
  1112       }
  1113       for (typename Attributes::iterator it = _attributes.begin();
  1114            it != _attributes.end(); ++it) {
  1115         if (read_attr.find(it->first) == read_attr.end()) {
  1116           std::ostringstream msg;
  1117           msg << "Attribute not found: " << it->first;
  1118           throw FormatError(msg.str());
  1119         }
  1120       }
  1121     }
  1122 
  1123   public:
  1124 
  1125     /// \name Execution of the Reader
  1126     /// @{
  1127 
  1128     /// \brief Start the batch processing
  1129     ///
  1130     /// This function starts the batch processing
  1131     void run() {
  1132       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  1133 
  1134       bool nodes_done = _skip_nodes;
  1135       bool arcs_done = _skip_arcs;
  1136       bool attributes_done = false;
  1137 
  1138       line_num = 0;
  1139       readLine();
  1140       skipSection();
  1141 
  1142       while (readSuccess()) {
  1143         try {
  1144           char c;
  1145           std::string section, caption;
  1146           line >> c;
  1147           _reader_bits::readToken(line, section);
  1148           _reader_bits::readToken(line, caption);
  1149 
  1150           if (line >> c)
  1151             throw FormatError("Extra character at the end of line");
  1152 
  1153           if (section == "nodes" && !nodes_done) {
  1154             if (_nodes_caption.empty() || _nodes_caption == caption) {
  1155               readNodes();
  1156               nodes_done = true;
  1157             }
  1158           } else if ((section == "arcs" || section == "edges") &&
  1159                      !arcs_done) {
  1160             if (_arcs_caption.empty() || _arcs_caption == caption) {
  1161               readArcs();
  1162               arcs_done = true;
  1163             }
  1164           } else if (section == "attributes" && !attributes_done) {
  1165             if (_attributes_caption.empty() || _attributes_caption == caption) {
  1166               readAttributes();
  1167               attributes_done = true;
  1168             }
  1169           } else {
  1170             readLine();
  1171             skipSection();
  1172           }
  1173         } catch (FormatError& error) {
  1174           error.line(line_num);
  1175           error.file(_filename);
  1176           throw;
  1177         }
  1178       }
  1179 
  1180       if (!nodes_done) {
  1181         throw FormatError("Section @nodes not found");
  1182       }
  1183 
  1184       if (!arcs_done) {
  1185         throw FormatError("Section @arcs not found");
  1186       }
  1187 
  1188       if (!attributes_done && !_attributes.empty()) {
  1189         throw FormatError("Section @attributes not found");
  1190       }
  1191 
  1192     }
  1193 
  1194     /// @}
  1195 
  1196   };
  1197 
  1198   /// \ingroup lemon_io
  1199   ///
  1200   /// \brief Return a \ref DigraphReader class
  1201   ///
  1202   /// This function just returns a \ref DigraphReader class.
  1203   ///
  1204   /// With this function a digraph can be read from an
  1205   /// \ref lgf-format "LGF" file or input stream with several maps and
  1206   /// attributes. For example, there is network flow problem on a
  1207   /// digraph, i.e. a digraph with a \e capacity map on the arcs and
  1208   /// \e source and \e target nodes. This digraph can be read with the
  1209   /// following code:
  1210   ///
  1211   ///\code
  1212   ///ListDigraph digraph;
  1213   ///ListDigraph::ArcMap<int> cm(digraph);
  1214   ///ListDigraph::Node src, trg;
  1215   ///digraphReader(digraph, std::cin).
  1216   ///  arcMap("capacity", cap).
  1217   ///  node("source", src).
  1218   ///  node("target", trg).
  1219   ///  run();
  1220   ///\endcode
  1221   ///
  1222   /// For a complete documentation, please see the \ref DigraphReader
  1223   /// class documentation.
  1224   /// \warning Don't forget to put the \ref DigraphReader::run() "run()"
  1225   /// to the end of the parameter list.
  1226   /// \relates DigraphReader
  1227   /// \sa digraphReader(TDGR& digraph, const std::string& fn)
  1228   /// \sa digraphReader(TDGR& digraph, const char* fn)
  1229   template <typename TDGR>
  1230   DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) {
  1231     DigraphReader<TDGR> tmp(digraph, is);
  1232     return tmp;
  1233   }
  1234 
  1235   /// \brief Return a \ref DigraphReader class
  1236   ///
  1237   /// This function just returns a \ref DigraphReader class.
  1238   /// \relates DigraphReader
  1239   /// \sa digraphReader(TDGR& digraph, std::istream& is)
  1240   template <typename TDGR>
  1241   DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) {
  1242     DigraphReader<TDGR> tmp(digraph, fn);
  1243     return tmp;
  1244   }
  1245 
  1246   /// \brief Return a \ref DigraphReader class
  1247   ///
  1248   /// This function just returns a \ref DigraphReader class.
  1249   /// \relates DigraphReader
  1250   /// \sa digraphReader(TDGR& digraph, std::istream& is)
  1251   template <typename TDGR>
  1252   DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
  1253     DigraphReader<TDGR> tmp(digraph, fn);
  1254     return tmp;
  1255   }
  1256 
  1257   template <typename GR>
  1258   class GraphReader;
  1259 
  1260   template <typename TGR>
  1261   GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
  1262   template <typename TGR>
  1263   GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
  1264   template <typename TGR>
  1265   GraphReader<TGR> graphReader(TGR& graph, const char *fn);
  1266 
  1267   /// \ingroup lemon_io
  1268   ///
  1269   /// \brief \ref lgf-format "LGF" reader for undirected graphs
  1270   ///
  1271   /// This utility reads an \ref lgf-format "LGF" file.
  1272   ///
  1273   /// It can be used almost the same way as \c DigraphReader.
  1274   /// The only difference is that this class can handle edges and
  1275   /// edge maps as well as arcs and arc maps.
  1276   ///
  1277   /// The columns in the \c \@edges (or \c \@arcs) section are the
  1278   /// edge maps. However, if there are two maps with the same name
  1279   /// prefixed with \c '+' and \c '-', then these can be read into an
  1280   /// arc map.  Similarly, an attribute can be read into an arc, if
  1281   /// it's value is an edge label prefixed with \c '+' or \c '-'.
  1282   template <typename GR>
  1283   class GraphReader {
  1284   public:
  1285 
  1286     typedef GR Graph;
  1287 
  1288   private:
  1289 
  1290     TEMPLATE_GRAPH_TYPEDEFS(GR);
  1291 
  1292     std::istream* _is;
  1293     bool local_is;
  1294     std::string _filename;
  1295 
  1296     GR& _graph;
  1297 
  1298     std::string _nodes_caption;
  1299     std::string _edges_caption;
  1300     std::string _attributes_caption;
  1301 
  1302     typedef std::map<std::string, Node> NodeIndex;
  1303     NodeIndex _node_index;
  1304     typedef std::map<std::string, Edge> EdgeIndex;
  1305     EdgeIndex _edge_index;
  1306 
  1307     typedef std::vector<std::pair<std::string,
  1308       _reader_bits::MapStorageBase<Node>*> > NodeMaps;
  1309     NodeMaps _node_maps;
  1310 
  1311     typedef std::vector<std::pair<std::string,
  1312       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  1313     EdgeMaps _edge_maps;
  1314 
  1315     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
  1316       Attributes;
  1317     Attributes _attributes;
  1318 
  1319     bool _use_nodes;
  1320     bool _use_edges;
  1321 
  1322     bool _skip_nodes;
  1323     bool _skip_edges;
  1324 
  1325     int line_num;
  1326     std::istringstream line;
  1327 
  1328   public:
  1329 
  1330     /// \brief Constructor
  1331     ///
  1332     /// Construct an undirected graph reader, which reads from the given
  1333     /// input stream.
  1334     GraphReader(GR& graph, std::istream& is = std::cin)
  1335       : _is(&is), local_is(false), _graph(graph),
  1336         _use_nodes(false), _use_edges(false),
  1337         _skip_nodes(false), _skip_edges(false) {}
  1338 
  1339     /// \brief Constructor
  1340     ///
  1341     /// Construct an undirected graph reader, which reads from the given
  1342     /// file.
  1343     GraphReader(GR& graph, const std::string& fn)
  1344       : _is(new std::ifstream(fn.c_str())), local_is(true),
  1345         _filename(fn), _graph(graph),
  1346         _use_nodes(false), _use_edges(false),
  1347         _skip_nodes(false), _skip_edges(false) {
  1348       if (!(*_is)) {
  1349         delete _is;
  1350         throw IoError("Cannot open file", fn);
  1351       }
  1352     }
  1353 
  1354     /// \brief Constructor
  1355     ///
  1356     /// Construct an undirected graph reader, which reads from the given
  1357     /// file.
  1358     GraphReader(GR& graph, const char* fn)
  1359       : _is(new std::ifstream(fn)), local_is(true),
  1360         _filename(fn), _graph(graph),
  1361         _use_nodes(false), _use_edges(false),
  1362         _skip_nodes(false), _skip_edges(false) {
  1363       if (!(*_is)) {
  1364         delete _is;
  1365         throw IoError("Cannot open file", fn);
  1366       }
  1367     }
  1368 
  1369     /// \brief Destructor
  1370     ~GraphReader() {
  1371       for (typename NodeMaps::iterator it = _node_maps.begin();
  1372            it != _node_maps.end(); ++it) {
  1373         delete it->second;
  1374       }
  1375 
  1376       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  1377            it != _edge_maps.end(); ++it) {
  1378         delete it->second;
  1379       }
  1380 
  1381       for (typename Attributes::iterator it = _attributes.begin();
  1382            it != _attributes.end(); ++it) {
  1383         delete it->second;
  1384       }
  1385 
  1386       if (local_is) {
  1387         delete _is;
  1388       }
  1389 
  1390     }
  1391 
  1392   private:
  1393     template <typename TGR>
  1394     friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
  1395     template <typename TGR>
  1396     friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
  1397     template <typename TGR>
  1398     friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
  1399 
  1400     GraphReader(GraphReader& other)
  1401       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  1402         _use_nodes(other._use_nodes), _use_edges(other._use_edges),
  1403         _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  1404 
  1405       other._is = 0;
  1406       other.local_is = false;
  1407 
  1408       _node_index.swap(other._node_index);
  1409       _edge_index.swap(other._edge_index);
  1410 
  1411       _node_maps.swap(other._node_maps);
  1412       _edge_maps.swap(other._edge_maps);
  1413       _attributes.swap(other._attributes);
  1414 
  1415       _nodes_caption = other._nodes_caption;
  1416       _edges_caption = other._edges_caption;
  1417       _attributes_caption = other._attributes_caption;
  1418 
  1419     }
  1420 
  1421     GraphReader& operator=(const GraphReader&);
  1422 
  1423   public:
  1424 
  1425     /// \name Reading Rules
  1426     /// @{
  1427 
  1428     /// \brief Node map reading rule
  1429     ///
  1430     /// Add a node map reading rule to the reader.
  1431     template <typename Map>
  1432     GraphReader& nodeMap(const std::string& caption, Map& map) {
  1433       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1434       _reader_bits::MapStorageBase<Node>* storage =
  1435         new _reader_bits::MapStorage<Node, Map>(map);
  1436       _node_maps.push_back(std::make_pair(caption, storage));
  1437       return *this;
  1438     }
  1439 
  1440     /// \brief Node map reading rule
  1441     ///
  1442     /// Add a node map reading rule with specialized converter to the
  1443     /// reader.
  1444     template <typename Map, typename Converter>
  1445     GraphReader& nodeMap(const std::string& caption, Map& map,
  1446                            const Converter& converter = Converter()) {
  1447       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  1448       _reader_bits::MapStorageBase<Node>* storage =
  1449         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  1450       _node_maps.push_back(std::make_pair(caption, storage));
  1451       return *this;
  1452     }
  1453 
  1454     /// \brief Edge map reading rule
  1455     ///
  1456     /// Add an edge map reading rule to the reader.
  1457     template <typename Map>
  1458     GraphReader& edgeMap(const std::string& caption, Map& map) {
  1459       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1460       _reader_bits::MapStorageBase<Edge>* storage =
  1461         new _reader_bits::MapStorage<Edge, Map>(map);
  1462       _edge_maps.push_back(std::make_pair(caption, storage));
  1463       return *this;
  1464     }
  1465 
  1466     /// \brief Edge map reading rule
  1467     ///
  1468     /// Add an edge map reading rule with specialized converter to the
  1469     /// reader.
  1470     template <typename Map, typename Converter>
  1471     GraphReader& edgeMap(const std::string& caption, Map& map,
  1472                           const Converter& converter = Converter()) {
  1473       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  1474       _reader_bits::MapStorageBase<Edge>* storage =
  1475         new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  1476       _edge_maps.push_back(std::make_pair(caption, storage));
  1477       return *this;
  1478     }
  1479 
  1480     /// \brief Arc map reading rule
  1481     ///
  1482     /// Add an arc map reading rule to the reader.
  1483     template <typename Map>
  1484     GraphReader& arcMap(const std::string& caption, Map& map) {
  1485       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1486       _reader_bits::MapStorageBase<Edge>* forward_storage =
  1487         new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  1488       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1489       _reader_bits::MapStorageBase<Edge>* backward_storage =
  1490         new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
  1491       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1492       return *this;
  1493     }
  1494 
  1495     /// \brief Arc map reading rule
  1496     ///
  1497     /// Add an arc map reading rule with specialized converter to the
  1498     /// reader.
  1499     template <typename Map, typename Converter>
  1500     GraphReader& arcMap(const std::string& caption, Map& map,
  1501                           const Converter& converter = Converter()) {
  1502       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  1503       _reader_bits::MapStorageBase<Edge>* forward_storage =
  1504         new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter>
  1505         (_graph, map, converter);
  1506       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  1507       _reader_bits::MapStorageBase<Edge>* backward_storage =
  1508         new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter>
  1509         (_graph, map, converter);
  1510       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  1511       return *this;
  1512     }
  1513 
  1514     /// \brief Attribute reading rule
  1515     ///
  1516     /// Add an attribute reading rule to the reader.
  1517     template <typename Value>
  1518     GraphReader& attribute(const std::string& caption, Value& value) {
  1519       _reader_bits::ValueStorageBase* storage =
  1520         new _reader_bits::ValueStorage<Value>(value);
  1521       _attributes.insert(std::make_pair(caption, storage));
  1522       return *this;
  1523     }
  1524 
  1525     /// \brief Attribute reading rule
  1526     ///
  1527     /// Add an attribute reading rule with specialized converter to the
  1528     /// reader.
  1529     template <typename Value, typename Converter>
  1530     GraphReader& attribute(const std::string& caption, Value& value,
  1531                              const Converter& converter = Converter()) {
  1532       _reader_bits::ValueStorageBase* storage =
  1533         new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  1534       _attributes.insert(std::make_pair(caption, storage));
  1535       return *this;
  1536     }
  1537 
  1538     /// \brief Node reading rule
  1539     ///
  1540     /// Add a node reading rule to reader.
  1541     GraphReader& node(const std::string& caption, Node& node) {
  1542       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  1543       Converter converter(_node_index);
  1544       _reader_bits::ValueStorageBase* storage =
  1545         new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  1546       _attributes.insert(std::make_pair(caption, storage));
  1547       return *this;
  1548     }
  1549 
  1550     /// \brief Edge reading rule
  1551     ///
  1552     /// Add an edge reading rule to reader.
  1553     GraphReader& edge(const std::string& caption, Edge& edge) {
  1554       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  1555       Converter converter(_edge_index);
  1556       _reader_bits::ValueStorageBase* storage =
  1557         new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  1558       _attributes.insert(std::make_pair(caption, storage));
  1559       return *this;
  1560     }
  1561 
  1562     /// \brief Arc reading rule
  1563     ///
  1564     /// Add an arc reading rule to reader.
  1565     GraphReader& arc(const std::string& caption, Arc& arc) {
  1566       typedef _reader_bits::GraphArcLookUpConverter<GR> Converter;
  1567       Converter converter(_graph, _edge_index);
  1568       _reader_bits::ValueStorageBase* storage =
  1569         new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  1570       _attributes.insert(std::make_pair(caption, storage));
  1571       return *this;
  1572     }
  1573 
  1574     /// @}
  1575 
  1576     /// \name Select Section by Name
  1577     /// @{
  1578 
  1579     /// \brief Set \c \@nodes section to be read
  1580     ///
  1581     /// Set \c \@nodes section to be read.
  1582     GraphReader& nodes(const std::string& caption) {
  1583       _nodes_caption = caption;
  1584       return *this;
  1585     }
  1586 
  1587     /// \brief Set \c \@edges section to be read
  1588     ///
  1589     /// Set \c \@edges section to be read.
  1590     GraphReader& edges(const std::string& caption) {
  1591       _edges_caption = caption;
  1592       return *this;
  1593     }
  1594 
  1595     /// \brief Set \c \@attributes section to be read
  1596     ///
  1597     /// Set \c \@attributes section to be read.
  1598     GraphReader& attributes(const std::string& caption) {
  1599       _attributes_caption = caption;
  1600       return *this;
  1601     }
  1602 
  1603     /// @}
  1604 
  1605     /// \name Using Previously Constructed Node or Edge Set
  1606     /// @{
  1607 
  1608     /// \brief Use previously constructed node set
  1609     ///
  1610     /// Use previously constructed node set, and specify the node
  1611     /// label map.
  1612     template <typename Map>
  1613     GraphReader& useNodes(const Map& map) {
  1614       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1615       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
  1616       _use_nodes = true;
  1617       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1618       for (NodeIt n(_graph); n != INVALID; ++n) {
  1619         _node_index.insert(std::make_pair(converter(map[n]), n));
  1620       }
  1621       return *this;
  1622     }
  1623 
  1624     /// \brief Use previously constructed node set
  1625     ///
  1626     /// Use previously constructed node set, and specify the node
  1627     /// label map and a functor which converts the label map values to
  1628     /// \c std::string.
  1629     template <typename Map, typename Converter>
  1630     GraphReader& useNodes(const Map& map,
  1631                             const Converter& converter = Converter()) {
  1632       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  1633       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
  1634       _use_nodes = true;
  1635       for (NodeIt n(_graph); n != INVALID; ++n) {
  1636         _node_index.insert(std::make_pair(converter(map[n]), n));
  1637       }
  1638       return *this;
  1639     }
  1640 
  1641     /// \brief Use previously constructed edge set
  1642     ///
  1643     /// Use previously constructed edge set, and specify the edge
  1644     /// label map.
  1645     template <typename Map>
  1646     GraphReader& useEdges(const Map& map) {
  1647       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1648       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1649       _use_edges = true;
  1650       _writer_bits::DefaultConverter<typename Map::Value> converter;
  1651       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1652         _edge_index.insert(std::make_pair(converter(map[a]), a));
  1653       }
  1654       return *this;
  1655     }
  1656 
  1657     /// \brief Use previously constructed edge set
  1658     ///
  1659     /// Use previously constructed edge set, and specify the edge
  1660     /// label map and a functor which converts the label map values to
  1661     /// \c std::string.
  1662     template <typename Map, typename Converter>
  1663     GraphReader& useEdges(const Map& map,
  1664                             const Converter& converter = Converter()) {
  1665       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  1666       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  1667       _use_edges = true;
  1668       for (EdgeIt a(_graph); a != INVALID; ++a) {
  1669         _edge_index.insert(std::make_pair(converter(map[a]), a));
  1670       }
  1671       return *this;
  1672     }
  1673 
  1674     /// \brief Skip the reading of node section
  1675     ///
  1676     /// Omit the reading of the node section. This implies that each node
  1677     /// map reading rule will be abandoned, and the nodes of the graph
  1678     /// will not be constructed, which usually cause that the edge set
  1679     /// could not be read due to lack of node name
  1680     /// could not be read due to lack of node name resolving.
  1681     /// Therefore \c skipEdges() function should also be used, or
  1682     /// \c useNodes() should be used to specify the label of the nodes.
  1683     GraphReader& skipNodes() {
  1684       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
  1685       _skip_nodes = true;
  1686       return *this;
  1687     }
  1688 
  1689     /// \brief Skip the reading of edge section
  1690     ///
  1691     /// Omit the reading of the edge section. This implies that each edge
  1692     /// map reading rule will be abandoned, and the edges of the graph
  1693     /// will not be constructed.
  1694     GraphReader& skipEdges() {
  1695       LEMON_ASSERT(!_skip_edges, "Skip edges already set");
  1696       _skip_edges = true;
  1697       return *this;
  1698     }
  1699 
  1700     /// @}
  1701 
  1702   private:
  1703 
  1704     bool readLine() {
  1705       std::string str;
  1706       while(++line_num, std::getline(*_is, str)) {
  1707         line.clear(); line.str(str);
  1708         char c;
  1709         if (line >> std::ws >> c && c != '#') {
  1710           line.putback(c);
  1711           return true;
  1712         }
  1713       }
  1714       return false;
  1715     }
  1716 
  1717     bool readSuccess() {
  1718       return static_cast<bool>(*_is);
  1719     }
  1720 
  1721     void skipSection() {
  1722       char c;
  1723       while (readSuccess() && line >> c && c != '@') {
  1724         readLine();
  1725       }
  1726       if (readSuccess()) {
  1727         line.putback(c);
  1728       }
  1729     }
  1730 
  1731     void readNodes() {
  1732 
  1733       std::vector<int> map_index(_node_maps.size());
  1734       int map_num, label_index;
  1735 
  1736       char c;
  1737       if (!readLine() || !(line >> c) || c == '@') {
  1738         if (readSuccess() && line) line.putback(c);
  1739         if (!_node_maps.empty())
  1740           throw FormatError("Cannot find map names");
  1741         return;
  1742       }
  1743       line.putback(c);
  1744 
  1745       {
  1746         std::map<std::string, int> maps;
  1747 
  1748         std::string map;
  1749         int index = 0;
  1750         while (_reader_bits::readToken(line, map)) {
  1751           if (maps.find(map) != maps.end()) {
  1752             std::ostringstream msg;
  1753             msg << "Multiple occurence of node map: " << map;
  1754             throw FormatError(msg.str());
  1755           }
  1756           maps.insert(std::make_pair(map, index));
  1757           ++index;
  1758         }
  1759 
  1760         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1761           std::map<std::string, int>::iterator jt =
  1762             maps.find(_node_maps[i].first);
  1763           if (jt == maps.end()) {
  1764             std::ostringstream msg;
  1765             msg << "Map not found: " << _node_maps[i].first;
  1766             throw FormatError(msg.str());
  1767           }
  1768           map_index[i] = jt->second;
  1769         }
  1770 
  1771         {
  1772           std::map<std::string, int>::iterator jt = maps.find("label");
  1773           if (jt != maps.end()) {
  1774             label_index = jt->second;
  1775           } else {
  1776             label_index = -1;
  1777           }
  1778         }
  1779         map_num = maps.size();
  1780       }
  1781 
  1782       while (readLine() && line >> c && c != '@') {
  1783         line.putback(c);
  1784 
  1785         std::vector<std::string> tokens(map_num);
  1786         for (int i = 0; i < map_num; ++i) {
  1787           if (!_reader_bits::readToken(line, tokens[i])) {
  1788             std::ostringstream msg;
  1789             msg << "Column not found (" << i + 1 << ")";
  1790             throw FormatError(msg.str());
  1791           }
  1792         }
  1793         if (line >> std::ws >> c)
  1794           throw FormatError("Extra character at the end of line");
  1795 
  1796         Node n;
  1797         if (!_use_nodes) {
  1798           n = _graph.addNode();
  1799           if (label_index != -1)
  1800             _node_index.insert(std::make_pair(tokens[label_index], n));
  1801         } else {
  1802           if (label_index == -1)
  1803             throw FormatError("Label map not found");
  1804           typename std::map<std::string, Node>::iterator it =
  1805             _node_index.find(tokens[label_index]);
  1806           if (it == _node_index.end()) {
  1807             std::ostringstream msg;
  1808             msg << "Node with label not found: " << tokens[label_index];
  1809             throw FormatError(msg.str());
  1810           }
  1811           n = it->second;
  1812         }
  1813 
  1814         for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
  1815           _node_maps[i].second->set(n, tokens[map_index[i]]);
  1816         }
  1817 
  1818       }
  1819       if (readSuccess()) {
  1820         line.putback(c);
  1821       }
  1822     }
  1823 
  1824     void readEdges() {
  1825 
  1826       std::vector<int> map_index(_edge_maps.size());
  1827       int map_num, label_index;
  1828 
  1829       char c;
  1830       if (!readLine() || !(line >> c) || c == '@') {
  1831         if (readSuccess() && line) line.putback(c);
  1832         if (!_edge_maps.empty())
  1833           throw FormatError("Cannot find map names");
  1834         return;
  1835       }
  1836       line.putback(c);
  1837 
  1838       {
  1839         std::map<std::string, int> maps;
  1840 
  1841         std::string map;
  1842         int index = 0;
  1843         while (_reader_bits::readToken(line, map)) {
  1844           if(map == "-") {
  1845               if(index!=0)
  1846                 throw FormatError("'-' is not allowed as a map name");
  1847               else if (line >> std::ws >> c)
  1848                 throw FormatError("Extra character at the end of line");
  1849               else break;
  1850             }
  1851           if (maps.find(map) != maps.end()) {
  1852             std::ostringstream msg;
  1853             msg << "Multiple occurence of edge map: " << map;
  1854             throw FormatError(msg.str());
  1855           }
  1856           maps.insert(std::make_pair(map, index));
  1857           ++index;
  1858         }
  1859 
  1860         for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1861           std::map<std::string, int>::iterator jt =
  1862             maps.find(_edge_maps[i].first);
  1863           if (jt == maps.end()) {
  1864             std::ostringstream msg;
  1865             msg << "Map not found: " << _edge_maps[i].first;
  1866             throw FormatError(msg.str());
  1867           }
  1868           map_index[i] = jt->second;
  1869         }
  1870 
  1871         {
  1872           std::map<std::string, int>::iterator jt = maps.find("label");
  1873           if (jt != maps.end()) {
  1874             label_index = jt->second;
  1875           } else {
  1876             label_index = -1;
  1877           }
  1878         }
  1879         map_num = maps.size();
  1880       }
  1881 
  1882       while (readLine() && line >> c && c != '@') {
  1883         line.putback(c);
  1884 
  1885         std::string source_token;
  1886         std::string target_token;
  1887 
  1888         if (!_reader_bits::readToken(line, source_token))
  1889           throw FormatError("Node u not found");
  1890 
  1891         if (!_reader_bits::readToken(line, target_token))
  1892           throw FormatError("Node v not found");
  1893 
  1894         std::vector<std::string> tokens(map_num);
  1895         for (int i = 0; i < map_num; ++i) {
  1896           if (!_reader_bits::readToken(line, tokens[i])) {
  1897             std::ostringstream msg;
  1898             msg << "Column not found (" << i + 1 << ")";
  1899             throw FormatError(msg.str());
  1900           }
  1901         }
  1902         if (line >> std::ws >> c)
  1903           throw FormatError("Extra character at the end of line");
  1904 
  1905         Edge e;
  1906         if (!_use_edges) {
  1907 
  1908           typename NodeIndex::iterator it;
  1909 
  1910           it = _node_index.find(source_token);
  1911           if (it == _node_index.end()) {
  1912             std::ostringstream msg;
  1913             msg << "Item not found: " << source_token;
  1914             throw FormatError(msg.str());
  1915           }
  1916           Node source = it->second;
  1917 
  1918           it = _node_index.find(target_token);
  1919           if (it == _node_index.end()) {
  1920             std::ostringstream msg;
  1921             msg << "Item not found: " << target_token;
  1922             throw FormatError(msg.str());
  1923           }
  1924           Node target = it->second;
  1925 
  1926           e = _graph.addEdge(source, target);
  1927           if (label_index != -1)
  1928             _edge_index.insert(std::make_pair(tokens[label_index], e));
  1929         } else {
  1930           if (label_index == -1)
  1931             throw FormatError("Label map not found");
  1932           typename std::map<std::string, Edge>::iterator it =
  1933             _edge_index.find(tokens[label_index]);
  1934           if (it == _edge_index.end()) {
  1935             std::ostringstream msg;
  1936             msg << "Edge with label not found: " << tokens[label_index];
  1937             throw FormatError(msg.str());
  1938           }
  1939           e = it->second;
  1940         }
  1941 
  1942         for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  1943           _edge_maps[i].second->set(e, tokens[map_index[i]]);
  1944         }
  1945 
  1946       }
  1947       if (readSuccess()) {
  1948         line.putback(c);
  1949       }
  1950     }
  1951 
  1952     void readAttributes() {
  1953 
  1954       std::set<std::string> read_attr;
  1955 
  1956       char c;
  1957       while (readLine() && line >> c && c != '@') {
  1958         line.putback(c);
  1959 
  1960         std::string attr, token;
  1961         if (!_reader_bits::readToken(line, attr))
  1962           throw FormatError("Attribute name not found");
  1963         if (!_reader_bits::readToken(line, token))
  1964           throw FormatError("Attribute value not found");
  1965         if (line >> c)
  1966           throw FormatError("Extra character at the end of line");
  1967 
  1968         {
  1969           std::set<std::string>::iterator it = read_attr.find(attr);
  1970           if (it != read_attr.end()) {
  1971             std::ostringstream msg;
  1972             msg << "Multiple occurence of attribute: " << attr;
  1973             throw FormatError(msg.str());
  1974           }
  1975           read_attr.insert(attr);
  1976         }
  1977 
  1978         {
  1979           typename Attributes::iterator it = _attributes.lower_bound(attr);
  1980           while (it != _attributes.end() && it->first == attr) {
  1981             it->second->set(token);
  1982             ++it;
  1983           }
  1984         }
  1985 
  1986       }
  1987       if (readSuccess()) {
  1988         line.putback(c);
  1989       }
  1990       for (typename Attributes::iterator it = _attributes.begin();
  1991            it != _attributes.end(); ++it) {
  1992         if (read_attr.find(it->first) == read_attr.end()) {
  1993           std::ostringstream msg;
  1994           msg << "Attribute not found: " << it->first;
  1995           throw FormatError(msg.str());
  1996         }
  1997       }
  1998     }
  1999 
  2000   public:
  2001 
  2002     /// \name Execution of the Reader
  2003     /// @{
  2004 
  2005     /// \brief Start the batch processing
  2006     ///
  2007     /// This function starts the batch processing
  2008     void run() {
  2009 
  2010       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  2011 
  2012       bool nodes_done = _skip_nodes;
  2013       bool edges_done = _skip_edges;
  2014       bool attributes_done = false;
  2015 
  2016       line_num = 0;
  2017       readLine();
  2018       skipSection();
  2019 
  2020       while (readSuccess()) {
  2021         try {
  2022           char c;
  2023           std::string section, caption;
  2024           line >> c;
  2025           _reader_bits::readToken(line, section);
  2026           _reader_bits::readToken(line, caption);
  2027 
  2028           if (line >> c)
  2029             throw FormatError("Extra character at the end of line");
  2030 
  2031           if (section == "nodes" && !nodes_done) {
  2032             if (_nodes_caption.empty() || _nodes_caption == caption) {
  2033               readNodes();
  2034               nodes_done = true;
  2035             }
  2036           } else if ((section == "edges" || section == "arcs") &&
  2037                      !edges_done) {
  2038             if (_edges_caption.empty() || _edges_caption == caption) {
  2039               readEdges();
  2040               edges_done = true;
  2041             }
  2042           } else if (section == "attributes" && !attributes_done) {
  2043             if (_attributes_caption.empty() || _attributes_caption == caption) {
  2044               readAttributes();
  2045               attributes_done = true;
  2046             }
  2047           } else {
  2048             readLine();
  2049             skipSection();
  2050           }
  2051         } catch (FormatError& error) {
  2052           error.line(line_num);
  2053           error.file(_filename);
  2054           throw;
  2055         }
  2056       }
  2057 
  2058       if (!nodes_done) {
  2059         throw FormatError("Section @nodes not found");
  2060       }
  2061 
  2062       if (!edges_done) {
  2063         throw FormatError("Section @edges not found");
  2064       }
  2065 
  2066       if (!attributes_done && !_attributes.empty()) {
  2067         throw FormatError("Section @attributes not found");
  2068       }
  2069 
  2070     }
  2071 
  2072     /// @}
  2073 
  2074   };
  2075 
  2076   /// \ingroup lemon_io
  2077   ///
  2078   /// \brief Return a \ref GraphReader class
  2079   ///
  2080   /// This function just returns a \ref GraphReader class.
  2081   ///
  2082   /// With this function a graph can be read from an
  2083   /// \ref lgf-format "LGF" file or input stream with several maps and
  2084   /// attributes. For example, there is weighted matching problem on a
  2085   /// graph, i.e. a graph with a \e weight map on the edges. This
  2086   /// graph can be read with the following code:
  2087   ///
  2088   ///\code
  2089   ///ListGraph graph;
  2090   ///ListGraph::EdgeMap<int> weight(graph);
  2091   ///graphReader(graph, std::cin).
  2092   ///  edgeMap("weight", weight).
  2093   ///  run();
  2094   ///\endcode
  2095   ///
  2096   /// For a complete documentation, please see the \ref GraphReader
  2097   /// class documentation.
  2098   /// \warning Don't forget to put the \ref GraphReader::run() "run()"
  2099   /// to the end of the parameter list.
  2100   /// \relates GraphReader
  2101   /// \sa graphReader(TGR& graph, const std::string& fn)
  2102   /// \sa graphReader(TGR& graph, const char* fn)
  2103   template <typename TGR>
  2104   GraphReader<TGR> graphReader(TGR& graph, std::istream& is) {
  2105     GraphReader<TGR> tmp(graph, is);
  2106     return tmp;
  2107   }
  2108 
  2109   /// \brief Return a \ref GraphReader class
  2110   ///
  2111   /// This function just returns a \ref GraphReader class.
  2112   /// \relates GraphReader
  2113   /// \sa graphReader(TGR& graph, std::istream& is)
  2114   template <typename TGR>
  2115   GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) {
  2116     GraphReader<TGR> tmp(graph, fn);
  2117     return tmp;
  2118   }
  2119 
  2120   /// \brief Return a \ref GraphReader class
  2121   ///
  2122   /// This function just returns a \ref GraphReader class.
  2123   /// \relates GraphReader
  2124   /// \sa graphReader(TGR& graph, std::istream& is)
  2125   template <typename TGR>
  2126   GraphReader<TGR> graphReader(TGR& graph, const char* fn) {
  2127     GraphReader<TGR> tmp(graph, fn);
  2128     return tmp;
  2129   }
  2130 
  2131   template <typename BGR>
  2132   class BpGraphReader;
  2133 
  2134   template <typename TBGR>
  2135   BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin);
  2136   template <typename TBGR>
  2137   BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn);
  2138   template <typename TBGR>
  2139   BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
  2140 
  2141   /// \ingroup lemon_io
  2142   ///
  2143   /// \brief \ref lgf-format "LGF" reader for bipartite graphs
  2144   ///
  2145   /// This utility reads an \ref lgf-format "LGF" file.
  2146   ///
  2147   /// It can be used almost the same way as \c GraphReader, but it
  2148   /// reads the red and blue nodes from separate sections, and these
  2149   /// sections can contain different set of maps.
  2150   ///
  2151   /// The red and blue node maps are read from the corresponding
  2152   /// sections. If a map is defined with the same name in both of
  2153   /// these sections, then it can be read as a node map.
  2154   template <typename BGR>
  2155   class BpGraphReader {
  2156   public:
  2157 
  2158     typedef BGR Graph;
  2159 
  2160   private:
  2161 
  2162     TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
  2163 
  2164     std::istream* _is;
  2165     bool local_is;
  2166     std::string _filename;
  2167 
  2168     BGR& _graph;
  2169 
  2170     std::string _nodes_caption;
  2171     std::string _edges_caption;
  2172     std::string _attributes_caption;
  2173 
  2174     typedef std::map<std::string, Node> NodeIndex;
  2175     NodeIndex _node_index;
  2176     typedef std::map<std::string, Edge> EdgeIndex;
  2177     EdgeIndex _edge_index;
  2178 
  2179     typedef std::vector<std::pair<std::string,
  2180       _reader_bits::MapStorageBase<Node>*> > NodeMaps;
  2181     NodeMaps _red_maps;
  2182     NodeMaps _blue_maps;
  2183 
  2184     typedef std::vector<std::pair<std::string,
  2185       _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
  2186     EdgeMaps _edge_maps;
  2187 
  2188     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
  2189       Attributes;
  2190     Attributes _attributes;
  2191 
  2192     bool _use_nodes;
  2193     bool _use_edges;
  2194 
  2195     bool _skip_nodes;
  2196     bool _skip_edges;
  2197 
  2198     int line_num;
  2199     std::istringstream line;
  2200 
  2201   public:
  2202 
  2203     /// \brief Constructor
  2204     ///
  2205     /// Construct an undirected graph reader, which reads from the given
  2206     /// input stream.
  2207     BpGraphReader(BGR& graph, std::istream& is = std::cin)
  2208       : _is(&is), local_is(false), _graph(graph),
  2209         _use_nodes(false), _use_edges(false),
  2210         _skip_nodes(false), _skip_edges(false) {}
  2211 
  2212     /// \brief Constructor
  2213     ///
  2214     /// Construct an undirected graph reader, which reads from the given
  2215     /// file.
  2216     BpGraphReader(BGR& graph, const std::string& fn)
  2217       : _is(new std::ifstream(fn.c_str())), local_is(true),
  2218         _filename(fn), _graph(graph),
  2219         _use_nodes(false), _use_edges(false),
  2220         _skip_nodes(false), _skip_edges(false) {
  2221       if (!(*_is)) {
  2222         delete _is;
  2223         throw IoError("Cannot open file", fn);
  2224       }
  2225     }
  2226 
  2227     /// \brief Constructor
  2228     ///
  2229     /// Construct an undirected graph reader, which reads from the given
  2230     /// file.
  2231     BpGraphReader(BGR& graph, const char* fn)
  2232       : _is(new std::ifstream(fn)), local_is(true),
  2233         _filename(fn), _graph(graph),
  2234         _use_nodes(false), _use_edges(false),
  2235         _skip_nodes(false), _skip_edges(false) {
  2236       if (!(*_is)) {
  2237         delete _is;
  2238         throw IoError("Cannot open file", fn);
  2239       }
  2240     }
  2241 
  2242     /// \brief Destructor
  2243     ~BpGraphReader() {
  2244       for (typename NodeMaps::iterator it = _red_maps.begin();
  2245            it != _red_maps.end(); ++it) {
  2246         delete it->second;
  2247       }
  2248 
  2249       for (typename NodeMaps::iterator it = _blue_maps.begin();
  2250            it != _blue_maps.end(); ++it) {
  2251         delete it->second;
  2252       }
  2253 
  2254       for (typename EdgeMaps::iterator it = _edge_maps.begin();
  2255            it != _edge_maps.end(); ++it) {
  2256         delete it->second;
  2257       }
  2258 
  2259       for (typename Attributes::iterator it = _attributes.begin();
  2260            it != _attributes.end(); ++it) {
  2261         delete it->second;
  2262       }
  2263 
  2264       if (local_is) {
  2265         delete _is;
  2266       }
  2267 
  2268     }
  2269 
  2270   private:
  2271     template <typename TBGR>
  2272     friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is);
  2273     template <typename TBGR>
  2274     friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph,
  2275                                              const std::string& fn);
  2276     template <typename TBGR>
  2277     friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
  2278 
  2279     BpGraphReader(BpGraphReader& other)
  2280       : _is(other._is), local_is(other.local_is), _graph(other._graph),
  2281         _use_nodes(other._use_nodes), _use_edges(other._use_edges),
  2282         _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
  2283 
  2284       other._is = 0;
  2285       other.local_is = false;
  2286 
  2287       _node_index.swap(other._node_index);
  2288       _edge_index.swap(other._edge_index);
  2289 
  2290       _red_maps.swap(other._red_maps);
  2291       _blue_maps.swap(other._blue_maps);
  2292       _edge_maps.swap(other._edge_maps);
  2293       _attributes.swap(other._attributes);
  2294 
  2295       _nodes_caption = other._nodes_caption;
  2296       _edges_caption = other._edges_caption;
  2297       _attributes_caption = other._attributes_caption;
  2298 
  2299     }
  2300 
  2301     BpGraphReader& operator=(const BpGraphReader&);
  2302 
  2303   public:
  2304 
  2305     /// \name Reading Rules
  2306     /// @{
  2307 
  2308     /// \brief Node map reading rule
  2309     ///
  2310     /// Add a node map reading rule to the reader.
  2311     template <typename Map>
  2312     BpGraphReader& nodeMap(const std::string& caption, Map& map) {
  2313       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  2314       _reader_bits::MapStorageBase<Node>* red_storage =
  2315         new _reader_bits::MapStorage<Node, Map>(map);
  2316       _red_maps.push_back(std::make_pair(caption, red_storage));
  2317       _reader_bits::MapStorageBase<Node>* blue_storage =
  2318         new _reader_bits::MapStorage<Node, Map>(map);
  2319       _blue_maps.push_back(std::make_pair(caption, blue_storage));
  2320       return *this;
  2321     }
  2322 
  2323     /// \brief Node map reading rule
  2324     ///
  2325     /// Add a node map reading rule with specialized converter to the
  2326     /// reader.
  2327     template <typename Map, typename Converter>
  2328     BpGraphReader& nodeMap(const std::string& caption, Map& map,
  2329                            const Converter& converter = Converter()) {
  2330       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  2331       _reader_bits::MapStorageBase<Node>* red_storage =
  2332         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  2333       _red_maps.push_back(std::make_pair(caption, red_storage));
  2334       _reader_bits::MapStorageBase<Node>* blue_storage =
  2335         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  2336       _blue_maps.push_back(std::make_pair(caption, blue_storage));
  2337       return *this;
  2338     }
  2339 
  2340     /// Add a red node map reading rule to the reader.
  2341     template <typename Map>
  2342     BpGraphReader& redNodeMap(const std::string& caption, Map& map) {
  2343       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  2344       _reader_bits::MapStorageBase<Node>* storage =
  2345         new _reader_bits::MapStorage<Node, Map>(map);
  2346       _red_maps.push_back(std::make_pair(caption, storage));
  2347       return *this;
  2348     }
  2349 
  2350     /// \brief Red node map reading rule
  2351     ///
  2352     /// Add a red node map node reading rule with specialized converter to
  2353     /// the reader.
  2354     template <typename Map, typename Converter>
  2355     BpGraphReader& redNodeMap(const std::string& caption, Map& map,
  2356                               const Converter& converter = Converter()) {
  2357       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  2358       _reader_bits::MapStorageBase<Node>* storage =
  2359         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  2360       _red_maps.push_back(std::make_pair(caption, storage));
  2361       return *this;
  2362     }
  2363 
  2364     /// Add a blue node map reading rule to the reader.
  2365     template <typename Map>
  2366     BpGraphReader& blueNodeMap(const std::string& caption, Map& map) {
  2367       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  2368       _reader_bits::MapStorageBase<Node>* storage =
  2369         new _reader_bits::MapStorage<Node, Map>(map);
  2370       _blue_maps.push_back(std::make_pair(caption, storage));
  2371       return *this;
  2372     }
  2373 
  2374     /// \brief Blue node map reading rule
  2375     ///
  2376     /// Add a blue node map reading rule with specialized converter to
  2377     /// the reader.
  2378     template <typename Map, typename Converter>
  2379     BpGraphReader& blueNodeMap(const std::string& caption, Map& map,
  2380                                const Converter& converter = Converter()) {
  2381       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
  2382       _reader_bits::MapStorageBase<Node>* storage =
  2383         new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
  2384       _blue_maps.push_back(std::make_pair(caption, storage));
  2385       return *this;
  2386     }
  2387 
  2388     /// \brief Edge map reading rule
  2389     ///
  2390     /// Add an edge map reading rule to the reader.
  2391     template <typename Map>
  2392     BpGraphReader& edgeMap(const std::string& caption, Map& map) {
  2393       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  2394       _reader_bits::MapStorageBase<Edge>* storage =
  2395         new _reader_bits::MapStorage<Edge, Map>(map);
  2396       _edge_maps.push_back(std::make_pair(caption, storage));
  2397       return *this;
  2398     }
  2399 
  2400     /// \brief Edge map reading rule
  2401     ///
  2402     /// Add an edge map reading rule with specialized converter to the
  2403     /// reader.
  2404     template <typename Map, typename Converter>
  2405     BpGraphReader& edgeMap(const std::string& caption, Map& map,
  2406                           const Converter& converter = Converter()) {
  2407       checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
  2408       _reader_bits::MapStorageBase<Edge>* storage =
  2409         new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
  2410       _edge_maps.push_back(std::make_pair(caption, storage));
  2411       return *this;
  2412     }
  2413 
  2414     /// \brief Arc map reading rule
  2415     ///
  2416     /// Add an arc map reading rule to the reader.
  2417     template <typename Map>
  2418     BpGraphReader& arcMap(const std::string& caption, Map& map) {
  2419       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  2420       _reader_bits::MapStorageBase<Edge>* forward_storage =
  2421         new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
  2422       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  2423       _reader_bits::MapStorageBase<Edge>* backward_storage =
  2424         new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
  2425       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  2426       return *this;
  2427     }
  2428 
  2429     /// \brief Arc map reading rule
  2430     ///
  2431     /// Add an arc map reading rule with specialized converter to the
  2432     /// reader.
  2433     template <typename Map, typename Converter>
  2434     BpGraphReader& arcMap(const std::string& caption, Map& map,
  2435                           const Converter& converter = Converter()) {
  2436       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
  2437       _reader_bits::MapStorageBase<Edge>* forward_storage =
  2438         new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter>
  2439         (_graph, map, converter);
  2440       _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
  2441       _reader_bits::MapStorageBase<Edge>* backward_storage =
  2442         new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter>
  2443         (_graph, map, converter);
  2444       _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
  2445       return *this;
  2446     }
  2447 
  2448     /// \brief Attribute reading rule
  2449     ///
  2450     /// Add an attribute reading rule to the reader.
  2451     template <typename Value>
  2452     BpGraphReader& attribute(const std::string& caption, Value& value) {
  2453       _reader_bits::ValueStorageBase* storage =
  2454         new _reader_bits::ValueStorage<Value>(value);
  2455       _attributes.insert(std::make_pair(caption, storage));
  2456       return *this;
  2457     }
  2458 
  2459     /// \brief Attribute reading rule
  2460     ///
  2461     /// Add an attribute reading rule with specialized converter to the
  2462     /// reader.
  2463     template <typename Value, typename Converter>
  2464     BpGraphReader& attribute(const std::string& caption, Value& value,
  2465                              const Converter& converter = Converter()) {
  2466       _reader_bits::ValueStorageBase* storage =
  2467         new _reader_bits::ValueStorage<Value, Converter>(value, converter);
  2468       _attributes.insert(std::make_pair(caption, storage));
  2469       return *this;
  2470     }
  2471 
  2472     /// \brief Node reading rule
  2473     ///
  2474     /// Add a node reading rule to reader.
  2475     BpGraphReader& node(const std::string& caption, Node& node) {
  2476       typedef _reader_bits::MapLookUpConverter<Node> Converter;
  2477       Converter converter(_node_index);
  2478       _reader_bits::ValueStorageBase* storage =
  2479         new _reader_bits::ValueStorage<Node, Converter>(node, converter);
  2480       _attributes.insert(std::make_pair(caption, storage));
  2481       return *this;
  2482     }
  2483 
  2484     /// \brief Edge reading rule
  2485     ///
  2486     /// Add an edge reading rule to reader.
  2487     BpGraphReader& edge(const std::string& caption, Edge& edge) {
  2488       typedef _reader_bits::MapLookUpConverter<Edge> Converter;
  2489       Converter converter(_edge_index);
  2490       _reader_bits::ValueStorageBase* storage =
  2491         new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
  2492       _attributes.insert(std::make_pair(caption, storage));
  2493       return *this;
  2494     }
  2495 
  2496     /// \brief Arc reading rule
  2497     ///
  2498     /// Add an arc reading rule to reader.
  2499     BpGraphReader& arc(const std::string& caption, Arc& arc) {
  2500       typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter;
  2501       Converter converter(_graph, _edge_index);
  2502       _reader_bits::ValueStorageBase* storage =
  2503         new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
  2504       _attributes.insert(std::make_pair(caption, storage));
  2505       return *this;
  2506     }
  2507 
  2508     /// @}
  2509 
  2510     /// \name Select Section by Name
  2511     /// @{
  2512 
  2513     /// \brief Set \c \@nodes section to be read
  2514     ///
  2515     /// Set \c \@nodes section to be read.
  2516     BpGraphReader& nodes(const std::string& caption) {
  2517       _nodes_caption = caption;
  2518       return *this;
  2519     }
  2520 
  2521     /// \brief Set \c \@edges section to be read
  2522     ///
  2523     /// Set \c \@edges section to be read.
  2524     BpGraphReader& edges(const std::string& caption) {
  2525       _edges_caption = caption;
  2526       return *this;
  2527     }
  2528 
  2529     /// \brief Set \c \@attributes section to be read
  2530     ///
  2531     /// Set \c \@attributes section to be read.
  2532     BpGraphReader& attributes(const std::string& caption) {
  2533       _attributes_caption = caption;
  2534       return *this;
  2535     }
  2536 
  2537     /// @}
  2538 
  2539     /// \name Using Previously Constructed Node or Edge Set
  2540     /// @{
  2541 
  2542     /// \brief Use previously constructed node set
  2543     ///
  2544     /// Use previously constructed node set, and specify the node
  2545     /// label map.
  2546     template <typename Map>
  2547     BpGraphReader& useNodes(const Map& map) {
  2548       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  2549       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
  2550       _use_nodes = true;
  2551       _writer_bits::DefaultConverter<typename Map::Value> converter;
  2552       for (NodeIt n(_graph); n != INVALID; ++n) {
  2553         _node_index.insert(std::make_pair(converter(map[n]), n));
  2554       }
  2555       return *this;
  2556     }
  2557 
  2558     /// \brief Use previously constructed node set
  2559     ///
  2560     /// Use previously constructed node set, and specify the node
  2561     /// label map and a functor which converts the label map values to
  2562     /// \c std::string.
  2563     template <typename Map, typename Converter>
  2564     BpGraphReader& useNodes(const Map& map,
  2565                             const Converter& converter = Converter()) {
  2566       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
  2567       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
  2568       _use_nodes = true;
  2569       for (NodeIt n(_graph); n != INVALID; ++n) {
  2570         _node_index.insert(std::make_pair(converter(map[n]), n));
  2571       }
  2572       return *this;
  2573     }
  2574 
  2575     /// \brief Use previously constructed edge set
  2576     ///
  2577     /// Use previously constructed edge set, and specify the edge
  2578     /// label map.
  2579     template <typename Map>
  2580     BpGraphReader& useEdges(const Map& map) {
  2581       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  2582       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  2583       _use_edges = true;
  2584       _writer_bits::DefaultConverter<typename Map::Value> converter;
  2585       for (EdgeIt a(_graph); a != INVALID; ++a) {
  2586         _edge_index.insert(std::make_pair(converter(map[a]), a));
  2587       }
  2588       return *this;
  2589     }
  2590 
  2591     /// \brief Use previously constructed edge set
  2592     ///
  2593     /// Use previously constructed edge set, and specify the edge
  2594     /// label map and a functor which converts the label map values to
  2595     /// \c std::string.
  2596     template <typename Map, typename Converter>
  2597     BpGraphReader& useEdges(const Map& map,
  2598                             const Converter& converter = Converter()) {
  2599       checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
  2600       LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
  2601       _use_edges = true;
  2602       for (EdgeIt a(_graph); a != INVALID; ++a) {
  2603         _edge_index.insert(std::make_pair(converter(map[a]), a));
  2604       }
  2605       return *this;
  2606     }
  2607 
  2608     /// \brief Skip the reading of node section
  2609     ///
  2610     /// Omit the reading of the node section. This implies that each node
  2611     /// map reading rule will be abandoned, and the nodes of the graph
  2612     /// will not be constructed, which usually cause that the edge set
  2613     /// could not be read due to lack of node name
  2614     /// could not be read due to lack of node name resolving.
  2615     /// Therefore \c skipEdges() function should also be used, or
  2616     /// \c useNodes() should be used to specify the label of the nodes.
  2617     BpGraphReader& skipNodes() {
  2618       LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
  2619       _skip_nodes = true;
  2620       return *this;
  2621     }
  2622 
  2623     /// \brief Skip the reading of edge section
  2624     ///
  2625     /// Omit the reading of the edge section. This implies that each edge
  2626     /// map reading rule will be abandoned, and the edges of the graph
  2627     /// will not be constructed.
  2628     BpGraphReader& skipEdges() {
  2629       LEMON_ASSERT(!_skip_edges, "Skip edges already set");
  2630       _skip_edges = true;
  2631       return *this;
  2632     }
  2633 
  2634     /// @}
  2635 
  2636   private:
  2637 
  2638     bool readLine() {
  2639       std::string str;
  2640       while(++line_num, std::getline(*_is, str)) {
  2641         line.clear(); line.str(str);
  2642         char c;
  2643         if (line >> std::ws >> c && c != '#') {
  2644           line.putback(c);
  2645           return true;
  2646         }
  2647       }
  2648       return false;
  2649     }
  2650 
  2651     bool readSuccess() {
  2652       return static_cast<bool>(*_is);
  2653     }
  2654 
  2655     void skipSection() {
  2656       char c;
  2657       while (readSuccess() && line >> c && c != '@') {
  2658         readLine();
  2659       }
  2660       if (readSuccess()) {
  2661         line.putback(c);
  2662       }
  2663     }
  2664 
  2665     void readRedNodes() {
  2666 
  2667       std::vector<int> map_index(_red_maps.size());
  2668       int map_num, label_index;
  2669 
  2670       char c;
  2671       if (!readLine() || !(line >> c) || c == '@') {
  2672         if (readSuccess() && line) line.putback(c);
  2673         if (!_red_maps.empty())
  2674           throw FormatError("Cannot find map names");
  2675         return;
  2676       }
  2677       line.putback(c);
  2678 
  2679       {
  2680         std::map<std::string, int> maps;
  2681 
  2682         std::string map;
  2683         int index = 0;
  2684         while (_reader_bits::readToken(line, map)) {
  2685           if (maps.find(map) != maps.end()) {
  2686             std::ostringstream msg;
  2687             msg << "Multiple occurence of red node map: " << map;
  2688             throw FormatError(msg.str());
  2689           }
  2690           maps.insert(std::make_pair(map, index));
  2691           ++index;
  2692         }
  2693 
  2694         for (int i = 0; i < static_cast<int>(_red_maps.size()); ++i) {
  2695           std::map<std::string, int>::iterator jt =
  2696             maps.find(_red_maps[i].first);
  2697           if (jt == maps.end()) {
  2698             std::ostringstream msg;
  2699             msg << "Map not found: " << _red_maps[i].first;
  2700             throw FormatError(msg.str());
  2701           }
  2702           map_index[i] = jt->second;
  2703         }
  2704 
  2705         {
  2706           std::map<std::string, int>::iterator jt = maps.find("label");
  2707           if (jt != maps.end()) {
  2708             label_index = jt->second;
  2709           } else {
  2710             label_index = -1;
  2711           }
  2712         }
  2713         map_num = maps.size();
  2714       }
  2715 
  2716       while (readLine() && line >> c && c != '@') {
  2717         line.putback(c);
  2718 
  2719         std::vector<std::string> tokens(map_num);
  2720         for (int i = 0; i < map_num; ++i) {
  2721           if (!_reader_bits::readToken(line, tokens[i])) {
  2722             std::ostringstream msg;
  2723             msg << "Column not found (" << i + 1 << ")";
  2724             throw FormatError(msg.str());
  2725           }
  2726         }
  2727         if (line >> std::ws >> c)
  2728           throw FormatError("Extra character at the end of line");
  2729 
  2730         Node n;
  2731         if (!_use_nodes) {
  2732           n = _graph.addRedNode();
  2733           if (label_index != -1)
  2734             _node_index.insert(std::make_pair(tokens[label_index], n));
  2735         } else {
  2736           if (label_index == -1)
  2737             throw FormatError("Label map not found");
  2738           typename std::map<std::string, Node>::iterator it =
  2739             _node_index.find(tokens[label_index]);
  2740           if (it == _node_index.end()) {
  2741             std::ostringstream msg;
  2742             msg << "Node with label not found: " << tokens[label_index];
  2743             throw FormatError(msg.str());
  2744           }
  2745           n = it->second;
  2746         }
  2747 
  2748         for (int i = 0; i < static_cast<int>(_red_maps.size()); ++i) {
  2749           _red_maps[i].second->set(n, tokens[map_index[i]]);
  2750         }
  2751 
  2752       }
  2753       if (readSuccess()) {
  2754         line.putback(c);
  2755       }
  2756     }
  2757 
  2758     void readBlueNodes() {
  2759 
  2760       std::vector<int> map_index(_blue_maps.size());
  2761       int map_num, label_index;
  2762 
  2763       char c;
  2764       if (!readLine() || !(line >> c) || c == '@') {
  2765         if (readSuccess() && line) line.putback(c);
  2766         if (!_blue_maps.empty())
  2767           throw FormatError("Cannot find map names");
  2768         return;
  2769       }
  2770       line.putback(c);
  2771 
  2772       {
  2773         std::map<std::string, int> maps;
  2774 
  2775         std::string map;
  2776         int index = 0;
  2777         while (_reader_bits::readToken(line, map)) {
  2778           if (maps.find(map) != maps.end()) {
  2779             std::ostringstream msg;
  2780             msg << "Multiple occurence of blue node map: " << map;
  2781             throw FormatError(msg.str());
  2782           }
  2783           maps.insert(std::make_pair(map, index));
  2784           ++index;
  2785         }
  2786 
  2787         for (int i = 0; i < static_cast<int>(_blue_maps.size()); ++i) {
  2788           std::map<std::string, int>::iterator jt =
  2789             maps.find(_blue_maps[i].first);
  2790           if (jt == maps.end()) {
  2791             std::ostringstream msg;
  2792             msg << "Map not found: " << _blue_maps[i].first;
  2793             throw FormatError(msg.str());
  2794           }
  2795           map_index[i] = jt->second;
  2796         }
  2797 
  2798         {
  2799           std::map<std::string, int>::iterator jt = maps.find("label");
  2800           if (jt != maps.end()) {
  2801             label_index = jt->second;
  2802           } else {
  2803             label_index = -1;
  2804           }
  2805         }
  2806         map_num = maps.size();
  2807       }
  2808 
  2809       while (readLine() && line >> c && c != '@') {
  2810         line.putback(c);
  2811 
  2812         std::vector<std::string> tokens(map_num);
  2813         for (int i = 0; i < map_num; ++i) {
  2814           if (!_reader_bits::readToken(line, tokens[i])) {
  2815             std::ostringstream msg;
  2816             msg << "Column not found (" << i + 1 << ")";
  2817             throw FormatError(msg.str());
  2818           }
  2819         }
  2820         if (line >> std::ws >> c)
  2821           throw FormatError("Extra character at the end of line");
  2822 
  2823         Node n;
  2824         if (!_use_nodes) {
  2825           n = _graph.addBlueNode();
  2826           if (label_index != -1)
  2827             _node_index.insert(std::make_pair(tokens[label_index], n));
  2828         } else {
  2829           if (label_index == -1)
  2830             throw FormatError("Label map not found");
  2831           typename std::map<std::string, Node>::iterator it =
  2832             _node_index.find(tokens[label_index]);
  2833           if (it == _node_index.end()) {
  2834             std::ostringstream msg;
  2835             msg << "Node with label not found: " << tokens[label_index];
  2836             throw FormatError(msg.str());
  2837           }
  2838           n = it->second;
  2839         }
  2840 
  2841         for (int i = 0; i < static_cast<int>(_blue_maps.size()); ++i) {
  2842           _blue_maps[i].second->set(n, tokens[map_index[i]]);
  2843         }
  2844 
  2845       }
  2846       if (readSuccess()) {
  2847         line.putback(c);
  2848       }
  2849     }
  2850 
  2851     void readEdges() {
  2852 
  2853       std::vector<int> map_index(_edge_maps.size());
  2854       int map_num, label_index;
  2855 
  2856       char c;
  2857       if (!readLine() || !(line >> c) || c == '@') {
  2858         if (readSuccess() && line) line.putback(c);
  2859         if (!_edge_maps.empty())
  2860           throw FormatError("Cannot find map names");
  2861         return;
  2862       }
  2863       line.putback(c);
  2864 
  2865       {
  2866         std::map<std::string, int> maps;
  2867 
  2868         std::string map;
  2869         int index = 0;
  2870         while (_reader_bits::readToken(line, map)) {
  2871           if (maps.find(map) != maps.end()) {
  2872             std::ostringstream msg;
  2873             msg << "Multiple occurence of edge map: " << map;
  2874             throw FormatError(msg.str());
  2875           }
  2876           maps.insert(std::make_pair(map, index));
  2877           ++index;
  2878         }
  2879 
  2880         for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  2881           std::map<std::string, int>::iterator jt =
  2882             maps.find(_edge_maps[i].first);
  2883           if (jt == maps.end()) {
  2884             std::ostringstream msg;
  2885             msg << "Map not found: " << _edge_maps[i].first;
  2886             throw FormatError(msg.str());
  2887           }
  2888           map_index[i] = jt->second;
  2889         }
  2890 
  2891         {
  2892           std::map<std::string, int>::iterator jt = maps.find("label");
  2893           if (jt != maps.end()) {
  2894             label_index = jt->second;
  2895           } else {
  2896             label_index = -1;
  2897           }
  2898         }
  2899         map_num = maps.size();
  2900       }
  2901 
  2902       while (readLine() && line >> c && c != '@') {
  2903         line.putback(c);
  2904 
  2905         std::string source_token;
  2906         std::string target_token;
  2907 
  2908         if (!_reader_bits::readToken(line, source_token))
  2909           throw FormatError("Red node not found");
  2910 
  2911         if (!_reader_bits::readToken(line, target_token))
  2912           throw FormatError("Blue node not found");
  2913 
  2914         std::vector<std::string> tokens(map_num);
  2915         for (int i = 0; i < map_num; ++i) {
  2916           if (!_reader_bits::readToken(line, tokens[i])) {
  2917             std::ostringstream msg;
  2918             msg << "Column not found (" << i + 1 << ")";
  2919             throw FormatError(msg.str());
  2920           }
  2921         }
  2922         if (line >> std::ws >> c)
  2923           throw FormatError("Extra character at the end of line");
  2924 
  2925         Edge e;
  2926         if (!_use_edges) {
  2927 
  2928           typename NodeIndex::iterator it;
  2929 
  2930           it = _node_index.find(source_token);
  2931           if (it == _node_index.end()) {
  2932             std::ostringstream msg;
  2933             msg << "Item not found: " << source_token;
  2934             throw FormatError(msg.str());
  2935           }
  2936           Node source = it->second;
  2937           if (!_graph.red(source)) {
  2938             std::ostringstream msg;
  2939             msg << "Item is not red node: " << source_token;
  2940             throw FormatError(msg.str());
  2941           }
  2942 
  2943           it = _node_index.find(target_token);
  2944           if (it == _node_index.end()) {
  2945             std::ostringstream msg;
  2946             msg << "Item not found: " << target_token;
  2947             throw FormatError(msg.str());
  2948           }
  2949           Node target = it->second;
  2950           if (!_graph.blue(target)) {
  2951             std::ostringstream msg;
  2952             msg << "Item is not red node: " << source_token;
  2953             throw FormatError(msg.str());
  2954           }
  2955 
  2956           // It is checked that source is red and
  2957           // target is blue, so this should be safe:
  2958           e = _graph.addEdge(_graph.asRedNodeUnsafe(source),
  2959                              _graph.asBlueNodeUnsafe(target));
  2960           if (label_index != -1)
  2961             _edge_index.insert(std::make_pair(tokens[label_index], e));
  2962         } else {
  2963           if (label_index == -1)
  2964             throw FormatError("Label map not found");
  2965           typename std::map<std::string, Edge>::iterator it =
  2966             _edge_index.find(tokens[label_index]);
  2967           if (it == _edge_index.end()) {
  2968             std::ostringstream msg;
  2969             msg << "Edge with label not found: " << tokens[label_index];
  2970             throw FormatError(msg.str());
  2971           }
  2972           e = it->second;
  2973         }
  2974 
  2975         for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
  2976           _edge_maps[i].second->set(e, tokens[map_index[i]]);
  2977         }
  2978 
  2979       }
  2980       if (readSuccess()) {
  2981         line.putback(c);
  2982       }
  2983     }
  2984 
  2985     void readAttributes() {
  2986 
  2987       std::set<std::string> read_attr;
  2988 
  2989       char c;
  2990       while (readLine() && line >> c && c != '@') {
  2991         line.putback(c);
  2992 
  2993         std::string attr, token;
  2994         if (!_reader_bits::readToken(line, attr))
  2995           throw FormatError("Attribute name not found");
  2996         if (!_reader_bits::readToken(line, token))
  2997           throw FormatError("Attribute value not found");
  2998         if (line >> c)
  2999           throw FormatError("Extra character at the end of line");
  3000 
  3001         {
  3002           std::set<std::string>::iterator it = read_attr.find(attr);
  3003           if (it != read_attr.end()) {
  3004             std::ostringstream msg;
  3005             msg << "Multiple occurence of attribute: " << attr;
  3006             throw FormatError(msg.str());
  3007           }
  3008           read_attr.insert(attr);
  3009         }
  3010 
  3011         {
  3012           typename Attributes::iterator it = _attributes.lower_bound(attr);
  3013           while (it != _attributes.end() && it->first == attr) {
  3014             it->second->set(token);
  3015             ++it;
  3016           }
  3017         }
  3018 
  3019       }
  3020       if (readSuccess()) {
  3021         line.putback(c);
  3022       }
  3023       for (typename Attributes::iterator it = _attributes.begin();
  3024            it != _attributes.end(); ++it) {
  3025         if (read_attr.find(it->first) == read_attr.end()) {
  3026           std::ostringstream msg;
  3027           msg << "Attribute not found: " << it->first;
  3028           throw FormatError(msg.str());
  3029         }
  3030       }
  3031     }
  3032 
  3033   public:
  3034 
  3035     /// \name Execution of the Reader
  3036     /// @{
  3037 
  3038     /// \brief Start the batch processing
  3039     ///
  3040     /// This function starts the batch processing
  3041     void run() {
  3042 
  3043       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  3044 
  3045       bool red_nodes_done = _skip_nodes;
  3046       bool blue_nodes_done = _skip_nodes;
  3047       bool edges_done = _skip_edges;
  3048       bool attributes_done = false;
  3049 
  3050       line_num = 0;
  3051       readLine();
  3052       skipSection();
  3053 
  3054       while (readSuccess()) {
  3055         try {
  3056           char c;
  3057           std::string section, caption;
  3058           line >> c;
  3059           _reader_bits::readToken(line, section);
  3060           _reader_bits::readToken(line, caption);
  3061 
  3062           if (line >> c)
  3063             throw FormatError("Extra character at the end of line");
  3064 
  3065           if (section == "red_nodes" && !red_nodes_done) {
  3066             if (_nodes_caption.empty() || _nodes_caption == caption) {
  3067               readRedNodes();
  3068               red_nodes_done = true;
  3069             }
  3070           } else if (section == "blue_nodes" && !blue_nodes_done) {
  3071             if (_nodes_caption.empty() || _nodes_caption == caption) {
  3072               readBlueNodes();
  3073               blue_nodes_done = true;
  3074             }
  3075           } else if ((section == "edges" || section == "arcs") &&
  3076                      !edges_done) {
  3077             if (_edges_caption.empty() || _edges_caption == caption) {
  3078               readEdges();
  3079               edges_done = true;
  3080             }
  3081           } else if (section == "attributes" && !attributes_done) {
  3082             if (_attributes_caption.empty() || _attributes_caption == caption) {
  3083               readAttributes();
  3084               attributes_done = true;
  3085             }
  3086           } else {
  3087             readLine();
  3088             skipSection();
  3089           }
  3090         } catch (FormatError& error) {
  3091           error.line(line_num);
  3092           error.file(_filename);
  3093           throw;
  3094         }
  3095       }
  3096 
  3097       if (!red_nodes_done) {
  3098         throw FormatError("Section @red_nodes not found");
  3099       }
  3100 
  3101       if (!blue_nodes_done) {
  3102         throw FormatError("Section @blue_nodes not found");
  3103       }
  3104 
  3105       if (!edges_done) {
  3106         throw FormatError("Section @edges not found");
  3107       }
  3108 
  3109       if (!attributes_done && !_attributes.empty()) {
  3110         throw FormatError("Section @attributes not found");
  3111       }
  3112 
  3113     }
  3114 
  3115     /// @}
  3116 
  3117   };
  3118 
  3119   /// \ingroup lemon_io
  3120   ///
  3121   /// \brief Return a \ref BpGraphReader class
  3122   ///
  3123   /// This function just returns a \ref BpGraphReader class.
  3124   ///
  3125   /// With this function a graph can be read from an
  3126   /// \ref lgf-format "LGF" file or input stream with several maps and
  3127   /// attributes. For example, there is bipartite weighted matching problem
  3128   /// on a graph, i.e. a graph with a \e weight map on the edges. This
  3129   /// graph can be read with the following code:
  3130   ///
  3131   ///\code
  3132   ///ListBpGraph graph;
  3133   ///ListBpGraph::EdgeMap<int> weight(graph);
  3134   ///bpGraphReader(graph, std::cin).
  3135   ///  edgeMap("weight", weight).
  3136   ///  run();
  3137   ///\endcode
  3138   ///
  3139   /// For a complete documentation, please see the \ref BpGraphReader
  3140   /// class documentation.
  3141   /// \warning Don't forget to put the \ref BpGraphReader::run() "run()"
  3142   /// to the end of the parameter list.
  3143   /// \relates BpGraphReader
  3144   /// \sa bpGraphReader(TBGR& graph, const std::string& fn)
  3145   /// \sa bpGraphReader(TBGR& graph, const char* fn)
  3146   template <typename TBGR>
  3147   BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) {
  3148     BpGraphReader<TBGR> tmp(graph, is);
  3149     return tmp;
  3150   }
  3151 
  3152   /// \brief Return a \ref BpGraphReader class
  3153   ///
  3154   /// This function just returns a \ref BpGraphReader class.
  3155   /// \relates BpGraphReader
  3156   /// \sa bpGraphReader(TBGR& graph, std::istream& is)
  3157   template <typename TBGR>
  3158   BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) {
  3159     BpGraphReader<TBGR> tmp(graph, fn);
  3160     return tmp;
  3161   }
  3162 
  3163   /// \brief Return a \ref BpGraphReader class
  3164   ///
  3165   /// This function just returns a \ref BpGraphReader class.
  3166   /// \relates BpGraphReader
  3167   /// \sa bpGraphReader(TBGR& graph, std::istream& is)
  3168   template <typename TBGR>
  3169   BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) {
  3170     BpGraphReader<TBGR> tmp(graph, fn);
  3171     return tmp;
  3172   }
  3173 
  3174   class SectionReader;
  3175 
  3176   SectionReader sectionReader(std::istream& is);
  3177   SectionReader sectionReader(const std::string& fn);
  3178   SectionReader sectionReader(const char* fn);
  3179 
  3180   /// \ingroup lemon_io
  3181   ///
  3182   /// \brief Section reader class
  3183   ///
  3184   /// In the \ref lgf-format "LGF" file extra sections can be placed,
  3185   /// which contain any data in arbitrary format. Such sections can be
  3186   /// read with this class. A reading rule can be added to the class
  3187   /// with two different functions. With the \c sectionLines() function a
  3188   /// functor can process the section line-by-line, while with the \c
  3189   /// sectionStream() member the section can be read from an input
  3190   /// stream.
  3191   class SectionReader {
  3192   private:
  3193 
  3194     std::istream* _is;
  3195     bool local_is;
  3196     std::string _filename;
  3197 
  3198     typedef std::map<std::string, _reader_bits::Section*> Sections;
  3199     Sections _sections;
  3200 
  3201     int line_num;
  3202     std::istringstream line;
  3203 
  3204   public:
  3205 
  3206     /// \brief Constructor
  3207     ///
  3208     /// Construct a section reader, which reads from the given input
  3209     /// stream.
  3210     SectionReader(std::istream& is)
  3211       : _is(&is), local_is(false) {}
  3212 
  3213     /// \brief Constructor
  3214     ///
  3215     /// Construct a section reader, which reads from the given file.
  3216     SectionReader(const std::string& fn)
  3217       : _is(new std::ifstream(fn.c_str())), local_is(true),
  3218         _filename(fn) {
  3219       if (!(*_is)) {
  3220         delete _is;
  3221         throw IoError("Cannot open file", fn);
  3222       }
  3223     }
  3224 
  3225     /// \brief Constructor
  3226     ///
  3227     /// Construct a section reader, which reads from the given file.
  3228     SectionReader(const char* fn)
  3229       : _is(new std::ifstream(fn)), local_is(true),
  3230         _filename(fn) {
  3231       if (!(*_is)) {
  3232         delete _is;
  3233         throw IoError("Cannot open file", fn);
  3234       }
  3235     }
  3236 
  3237     /// \brief Destructor
  3238     ~SectionReader() {
  3239       for (Sections::iterator it = _sections.begin();
  3240            it != _sections.end(); ++it) {
  3241         delete it->second;
  3242       }
  3243 
  3244       if (local_is) {
  3245         delete _is;
  3246       }
  3247 
  3248     }
  3249 
  3250   private:
  3251 
  3252     friend SectionReader sectionReader(std::istream& is);
  3253     friend SectionReader sectionReader(const std::string& fn);
  3254     friend SectionReader sectionReader(const char* fn);
  3255 
  3256     SectionReader(SectionReader& other)
  3257       : _is(other._is), local_is(other.local_is) {
  3258 
  3259       other._is = 0;
  3260       other.local_is = false;
  3261 
  3262       _sections.swap(other._sections);
  3263     }
  3264 
  3265     SectionReader& operator=(const SectionReader&);
  3266 
  3267   public:
  3268 
  3269     /// \name Section Readers
  3270     /// @{
  3271 
  3272     /// \brief Add a section processor with line oriented reading
  3273     ///
  3274     /// The first parameter is the type descriptor of the section, the
  3275     /// second is a functor, which takes just one \c std::string
  3276     /// parameter. At the reading process, each line of the section
  3277     /// will be given to the functor object. However, the empty lines
  3278     /// and the comment lines are filtered out, and the leading
  3279     /// whitespaces are trimmed from each processed string.
  3280     ///
  3281     /// For example, let's see a section, which contain several
  3282     /// integers, which should be inserted into a vector.
  3283     ///\code
  3284     ///  @numbers
  3285     ///  12 45 23
  3286     ///  4
  3287     ///  23 6
  3288     ///\endcode
  3289     ///
  3290     /// The functor is implemented as a struct:
  3291     ///\code
  3292     ///  struct NumberSection {
  3293     ///    std::vector<int>& _data;
  3294     ///    NumberSection(std::vector<int>& data) : _data(data) {}
  3295     ///    void operator()(const std::string& line) {
  3296     ///      std::istringstream ls(line);
  3297     ///      int value;
  3298     ///      while (ls >> value) _data.push_back(value);
  3299     ///    }
  3300     ///  };
  3301     ///
  3302     ///  // ...
  3303     ///
  3304     ///  reader.sectionLines("numbers", NumberSection(vec));
  3305     ///\endcode
  3306     template <typename Functor>
  3307     SectionReader& sectionLines(const std::string& type, Functor functor) {
  3308       LEMON_ASSERT(!type.empty(), "Type is empty.");
  3309       LEMON_ASSERT(_sections.find(type) == _sections.end(),
  3310                    "Multiple reading of section.");
  3311       _sections.insert(std::make_pair(type,
  3312         new _reader_bits::LineSection<Functor>(functor)));
  3313       return *this;
  3314     }
  3315 
  3316 
  3317     /// \brief Add a section processor with stream oriented reading
  3318     ///
  3319     /// The first parameter is the type of the section, the second is
  3320     /// a functor, which takes an \c std::istream& and an \c int&
  3321     /// parameter, the latter regard to the line number of stream. The
  3322     /// functor can read the input while the section go on, and the
  3323     /// line number should be modified accordingly.
  3324     template <typename Functor>
  3325     SectionReader& sectionStream(const std::string& type, Functor functor) {
  3326       LEMON_ASSERT(!type.empty(), "Type is empty.");
  3327       LEMON_ASSERT(_sections.find(type) == _sections.end(),
  3328                    "Multiple reading of section.");
  3329       _sections.insert(std::make_pair(type,
  3330          new _reader_bits::StreamSection<Functor>(functor)));
  3331       return *this;
  3332     }
  3333 
  3334     /// @}
  3335 
  3336   private:
  3337 
  3338     bool readLine() {
  3339       std::string str;
  3340       while(++line_num, std::getline(*_is, str)) {
  3341         line.clear(); line.str(str);
  3342         char c;
  3343         if (line >> std::ws >> c && c != '#') {
  3344           line.putback(c);
  3345           return true;
  3346         }
  3347       }
  3348       return false;
  3349     }
  3350 
  3351     bool readSuccess() {
  3352       return static_cast<bool>(*_is);
  3353     }
  3354 
  3355     void skipSection() {
  3356       char c;
  3357       while (readSuccess() && line >> c && c != '@') {
  3358         readLine();
  3359       }
  3360       if (readSuccess()) {
  3361         line.putback(c);
  3362       }
  3363     }
  3364 
  3365   public:
  3366 
  3367 
  3368     /// \name Execution of the Reader
  3369     /// @{
  3370 
  3371     /// \brief Start the batch processing
  3372     ///
  3373     /// This function starts the batch processing.
  3374     void run() {
  3375 
  3376       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
  3377 
  3378       std::set<std::string> extra_sections;
  3379 
  3380       line_num = 0;
  3381       readLine();
  3382       skipSection();
  3383 
  3384       while (readSuccess()) {
  3385         try {
  3386           char c;
  3387           std::string section, caption;
  3388           line >> c;
  3389           _reader_bits::readToken(line, section);
  3390           _reader_bits::readToken(line, caption);
  3391 
  3392           if (line >> c)
  3393             throw FormatError("Extra character at the end of line");
  3394 
  3395           if (extra_sections.find(section) != extra_sections.end()) {
  3396             std::ostringstream msg;
  3397             msg << "Multiple occurence of section: " << section;
  3398             throw FormatError(msg.str());
  3399           }
  3400           Sections::iterator it = _sections.find(section);
  3401           if (it != _sections.end()) {
  3402             extra_sections.insert(section);
  3403             it->second->process(*_is, line_num);
  3404           }
  3405           readLine();
  3406           skipSection();
  3407         } catch (FormatError& error) {
  3408           error.line(line_num);
  3409           error.file(_filename);
  3410           throw;
  3411         }
  3412       }
  3413       for (Sections::iterator it = _sections.begin();
  3414            it != _sections.end(); ++it) {
  3415         if (extra_sections.find(it->first) == extra_sections.end()) {
  3416           std::ostringstream os;
  3417           os << "Cannot find section: " << it->first;
  3418           throw FormatError(os.str());
  3419         }
  3420       }
  3421     }
  3422 
  3423     /// @}
  3424 
  3425   };
  3426 
  3427   /// \ingroup lemon_io
  3428   ///
  3429   /// \brief Return a \ref SectionReader class
  3430   ///
  3431   /// This function just returns a \ref SectionReader class.
  3432   ///
  3433   /// Please see SectionReader documentation about the custom section
  3434   /// input.
  3435   ///
  3436   /// \relates SectionReader
  3437   /// \sa sectionReader(const std::string& fn)
  3438   /// \sa sectionReader(const char *fn)
  3439   inline SectionReader sectionReader(std::istream& is) {
  3440     SectionReader tmp(is);
  3441     return tmp;
  3442   }
  3443 
  3444   /// \brief Return a \ref SectionReader class
  3445   ///
  3446   /// This function just returns a \ref SectionReader class.
  3447   /// \relates SectionReader
  3448   /// \sa sectionReader(std::istream& is)
  3449   inline SectionReader sectionReader(const std::string& fn) {
  3450     SectionReader tmp(fn);
  3451     return tmp;
  3452   }
  3453 
  3454   /// \brief Return a \ref SectionReader class
  3455   ///
  3456   /// This function just returns a \ref SectionReader class.
  3457   /// \relates SectionReader
  3458   /// \sa sectionReader(std::istream& is)
  3459   inline SectionReader sectionReader(const char* fn) {
  3460     SectionReader tmp(fn);
  3461     return tmp;
  3462   }
  3463 
  3464   /// \ingroup lemon_io
  3465   ///
  3466   /// \brief Reader for the contents of the \ref lgf-format "LGF" file
  3467   ///
  3468   /// This class can be used to read the sections, the map names and
  3469   /// the attributes from a file. Usually, the LEMON programs know
  3470   /// that, which type of graph, which maps and which attributes
  3471   /// should be read from a file, but in general tools (like glemon)
  3472   /// the contents of an LGF file should be guessed somehow. This class
  3473   /// reads the graph and stores the appropriate information for
  3474   /// reading the graph.
  3475   ///
  3476   ///\code
  3477   /// LgfContents contents("graph.lgf");
  3478   /// contents.run();
  3479   ///
  3480   /// // Does it contain any node section and arc section?
  3481   /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
  3482   ///   std::cerr << "Failure, cannot find graph." << std::endl;
  3483   ///   return -1;
  3484   /// }
  3485   /// std::cout << "The name of the default node section: "
  3486   ///           << contents.nodeSection(0) << std::endl;
  3487   /// std::cout << "The number of the arc maps: "
  3488   ///           << contents.arcMaps(0).size() << std::endl;
  3489   /// std::cout << "The name of second arc map: "
  3490   ///           << contents.arcMaps(0)[1] << std::endl;
  3491   ///\endcode
  3492   class LgfContents {
  3493   private:
  3494 
  3495     std::istream* _is;
  3496     bool local_is;
  3497 
  3498     std::vector<std::string> _node_sections;
  3499     std::vector<std::string> _edge_sections;
  3500     std::vector<std::string> _attribute_sections;
  3501     std::vector<std::string> _extra_sections;
  3502 
  3503     std::vector<bool> _arc_sections;
  3504 
  3505     std::vector<std::vector<std::string> > _node_maps;
  3506     std::vector<std::vector<std::string> > _edge_maps;
  3507 
  3508     std::vector<std::vector<std::string> > _attributes;
  3509 
  3510 
  3511     int line_num;
  3512     std::istringstream line;
  3513 
  3514   public:
  3515 
  3516     /// \brief Constructor
  3517     ///
  3518     /// Construct an \e LGF contents reader, which reads from the given
  3519     /// input stream.
  3520     LgfContents(std::istream& is)
  3521       : _is(&is), local_is(false) {}
  3522 
  3523     /// \brief Constructor
  3524     ///
  3525     /// Construct an \e LGF contents reader, which reads from the given
  3526     /// file.
  3527     LgfContents(const std::string& fn)
  3528       : _is(new std::ifstream(fn.c_str())), local_is(true) {
  3529       if (!(*_is)) {
  3530         delete _is;
  3531         throw IoError("Cannot open file", fn);
  3532       }
  3533     }
  3534 
  3535     /// \brief Constructor
  3536     ///
  3537     /// Construct an \e LGF contents reader, which reads from the given
  3538     /// file.
  3539     LgfContents(const char* fn)
  3540       : _is(new std::ifstream(fn)), local_is(true) {
  3541       if (!(*_is)) {
  3542         delete _is;
  3543         throw IoError("Cannot open file", fn);
  3544       }
  3545     }
  3546 
  3547     /// \brief Destructor
  3548     ~LgfContents() {
  3549       if (local_is) delete _is;
  3550     }
  3551 
  3552   private:
  3553 
  3554     LgfContents(const LgfContents&);
  3555     LgfContents& operator=(const LgfContents&);
  3556 
  3557   public:
  3558 
  3559 
  3560     /// \name Node Sections
  3561     /// @{
  3562 
  3563     /// \brief Gives back the number of node sections in the file.
  3564     ///
  3565     /// Gives back the number of node sections in the file.
  3566     int nodeSectionNum() const {
  3567       return _node_sections.size();
  3568     }
  3569 
  3570     /// \brief Returns the node section name at the given position.
  3571     ///
  3572     /// Returns the node section name at the given position.
  3573     const std::string& nodeSection(int i) const {
  3574       return _node_sections[i];
  3575     }
  3576 
  3577     /// \brief Gives back the node maps for the given section.
  3578     ///
  3579     /// Gives back the node maps for the given section.
  3580     const std::vector<std::string>& nodeMapNames(int i) const {
  3581       return _node_maps[i];
  3582     }
  3583 
  3584     /// @}
  3585 
  3586     /// \name Arc/Edge Sections
  3587     /// @{
  3588 
  3589     /// \brief Gives back the number of arc/edge sections in the file.
  3590     ///
  3591     /// Gives back the number of arc/edge sections in the file.
  3592     /// \note It is synonym of \c edgeSectionNum().
  3593     int arcSectionNum() const {
  3594       return _edge_sections.size();
  3595     }
  3596 
  3597     /// \brief Returns the arc/edge section name at the given position.
  3598     ///
  3599     /// Returns the arc/edge section name at the given position.
  3600     /// \note It is synonym of \c edgeSection().
  3601     const std::string& arcSection(int i) const {
  3602       return _edge_sections[i];
  3603     }
  3604 
  3605     /// \brief Gives back the arc/edge maps for the given section.
  3606     ///
  3607     /// Gives back the arc/edge maps for the given section.
  3608     /// \note It is synonym of \c edgeMapNames().
  3609     const std::vector<std::string>& arcMapNames(int i) const {
  3610       return _edge_maps[i];
  3611     }
  3612 
  3613     /// @}
  3614 
  3615     /// \name Synonyms
  3616     /// @{
  3617 
  3618     /// \brief Gives back the number of arc/edge sections in the file.
  3619     ///
  3620     /// Gives back the number of arc/edge sections in the file.
  3621     /// \note It is synonym of \c arcSectionNum().
  3622     int edgeSectionNum() const {
  3623       return _edge_sections.size();
  3624     }
  3625 
  3626     /// \brief Returns the section name at the given position.
  3627     ///
  3628     /// Returns the section name at the given position.
  3629     /// \note It is synonym of \c arcSection().
  3630     const std::string& edgeSection(int i) const {
  3631       return _edge_sections[i];
  3632     }
  3633 
  3634     /// \brief Gives back the edge maps for the given section.
  3635     ///
  3636     /// Gives back the edge maps for the given section.
  3637     /// \note It is synonym of \c arcMapNames().
  3638     const std::vector<std::string>& edgeMapNames(int i) const {
  3639       return _edge_maps[i];
  3640     }
  3641 
  3642     /// @}
  3643 
  3644     /// \name Attribute Sections
  3645     /// @{
  3646 
  3647     /// \brief Gives back the number of attribute sections in the file.
  3648     ///
  3649     /// Gives back the number of attribute sections in the file.
  3650     int attributeSectionNum() const {
  3651       return _attribute_sections.size();
  3652     }
  3653 
  3654     /// \brief Returns the attribute section name at the given position.
  3655     ///
  3656     /// Returns the attribute section name at the given position.
  3657     const std::string& attributeSectionNames(int i) const {
  3658       return _attribute_sections[i];
  3659     }
  3660 
  3661     /// \brief Gives back the attributes for the given section.
  3662     ///
  3663     /// Gives back the attributes for the given section.
  3664     const std::vector<std::string>& attributes(int i) const {
  3665       return _attributes[i];
  3666     }
  3667 
  3668     /// @}
  3669 
  3670     /// \name Extra Sections
  3671     /// @{
  3672 
  3673     /// \brief Gives back the number of extra sections in the file.
  3674     ///
  3675     /// Gives back the number of extra sections in the file.
  3676     int extraSectionNum() const {
  3677       return _extra_sections.size();
  3678     }
  3679 
  3680     /// \brief Returns the extra section type at the given position.
  3681     ///
  3682     /// Returns the section type at the given position.
  3683     const std::string& extraSection(int i) const {
  3684       return _extra_sections[i];
  3685     }
  3686 
  3687     /// @}
  3688 
  3689   private:
  3690 
  3691     bool readLine() {
  3692       std::string str;
  3693       while(++line_num, std::getline(*_is, str)) {
  3694         line.clear(); line.str(str);
  3695         char c;
  3696         if (line >> std::ws >> c && c != '#') {
  3697           line.putback(c);
  3698           return true;
  3699         }
  3700       }
  3701       return false;
  3702     }
  3703 
  3704     bool readSuccess() {
  3705       return static_cast<bool>(*_is);
  3706     }
  3707 
  3708     void skipSection() {
  3709       char c;
  3710       while (readSuccess() && line >> c && c != '@') {
  3711         readLine();
  3712       }
  3713       if (readSuccess()) {
  3714         line.putback(c);
  3715       }
  3716     }
  3717 
  3718     void readMaps(std::vector<std::string>& maps) {
  3719       char c;
  3720       if (!readLine() || !(line >> c) || c == '@') {
  3721         if (readSuccess() && line) line.putback(c);
  3722         return;
  3723       }
  3724       line.putback(c);
  3725       std::string map;
  3726       while (_reader_bits::readToken(line, map)) {
  3727         maps.push_back(map);
  3728       }
  3729     }
  3730 
  3731     void readAttributes(std::vector<std::string>& attrs) {
  3732       readLine();
  3733       char c;
  3734       while (readSuccess() && line >> c && c != '@') {
  3735         line.putback(c);
  3736         std::string attr;
  3737         _reader_bits::readToken(line, attr);
  3738         attrs.push_back(attr);
  3739         readLine();
  3740       }
  3741       line.putback(c);
  3742     }
  3743 
  3744   public:
  3745 
  3746     /// \name Execution of the Contents Reader
  3747     /// @{
  3748 
  3749     /// \brief Starts the reading
  3750     ///
  3751     /// This function starts the reading.
  3752     void run() {
  3753 
  3754       readLine();
  3755       skipSection();
  3756 
  3757       while (readSuccess()) {
  3758 
  3759         char c;
  3760         line >> c;
  3761 
  3762         std::string section, caption;
  3763         _reader_bits::readToken(line, section);
  3764         _reader_bits::readToken(line, caption);
  3765 
  3766         if (section == "nodes") {
  3767           _node_sections.push_back(caption);
  3768           _node_maps.push_back(std::vector<std::string>());
  3769           readMaps(_node_maps.back());
  3770           readLine(); skipSection();
  3771         } else if (section == "arcs" || section == "edges") {
  3772           _edge_sections.push_back(caption);
  3773           _arc_sections.push_back(section == "arcs");
  3774           _edge_maps.push_back(std::vector<std::string>());
  3775           readMaps(_edge_maps.back());
  3776           readLine(); skipSection();
  3777         } else if (section == "attributes") {
  3778           _attribute_sections.push_back(caption);
  3779           _attributes.push_back(std::vector<std::string>());
  3780           readAttributes(_attributes.back());
  3781         } else {
  3782           _extra_sections.push_back(section);
  3783           readLine(); skipSection();
  3784         }
  3785       }
  3786     }
  3787 
  3788     /// @}
  3789 
  3790   };
  3791 }
  3792 
  3793 #endif