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