lemon/lgf_reader.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 20 Feb 2010 18:39:03 +0100
changeset 839 f3bc4e9b5f3a
parent 599 f63e87b9748e
child 877 141f9c0db4a3
permissions -rw-r--r--
New heuristics for MCF algorithms (#340)
and some implementation improvements.

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