COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/lgf_reader.h @ 764:1fac515a59c1

Last change on this file since 764:1fac515a59c1 was 599:f63e87b9748e, checked in by Alpar Juttner <alpar@…>, 11 years ago

Merge

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