COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 1107:2b6bffe0e7e8

Last change on this file since 1107:2b6bffe0e7e8 was 1107:2b6bffe0e7e8, checked in by Alpar Juttner <alpar@…>, 8 years ago

Merge

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