COIN-OR::LEMON - Graph Library

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

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

Merge

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