COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 1197:374a9519986b

Last change on this file since 1197:374a9519986b was 1197:374a9519986b, checked in by Daniel Poroszkai <poroszd@…>, 8 years ago

Update LGF reader to work with typesafe bipartite node sets (#69)

File size: 114.4 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  template <typename BGR>
2132  class BpGraphReader;
2133
2134  template <typename TBGR>
2135  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin);
2136  template <typename TBGR>
2137  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn);
2138  template <typename TBGR>
2139  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
2140
2141  /// \ingroup lemon_io
2142  ///
2143  /// \brief \ref lgf-format "LGF" reader for bipartite graphs
2144  ///
2145  /// This utility reads an \ref lgf-format "LGF" file.
2146  ///
2147  /// It can be used almost the same way as \c GraphReader, but it
2148  /// reads the red and blue nodes from separate sections, and these
2149  /// sections can contain different set of maps.
2150  ///
2151  /// The red and blue node maps are read from the corresponding
2152  /// sections. If a map is defined with the same name in both of
2153  /// these sections, then it can be read as a node map.
2154  template <typename BGR>
2155  class BpGraphReader {
2156  public:
2157
2158    typedef BGR Graph;
2159
2160  private:
2161
2162    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
2163
2164    std::istream* _is;
2165    bool local_is;
2166    std::string _filename;
2167
2168    BGR& _graph;
2169
2170    std::string _nodes_caption;
2171    std::string _edges_caption;
2172    std::string _attributes_caption;
2173
2174    typedef std::map<std::string, Node> NodeIndex;
2175    NodeIndex _node_index;
2176    typedef std::map<std::string, Edge> EdgeIndex;
2177    EdgeIndex _edge_index;
2178
2179    typedef std::vector<std::pair<std::string,
2180      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
2181    NodeMaps _red_maps;
2182    NodeMaps _blue_maps;
2183
2184    typedef std::vector<std::pair<std::string,
2185      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
2186    EdgeMaps _edge_maps;
2187
2188    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
2189      Attributes;
2190    Attributes _attributes;
2191
2192    bool _use_nodes;
2193    bool _use_edges;
2194
2195    bool _skip_nodes;
2196    bool _skip_edges;
2197
2198    int line_num;
2199    std::istringstream line;
2200
2201  public:
2202
2203    /// \brief Constructor
2204    ///
2205    /// Construct an undirected graph reader, which reads from the given
2206    /// input stream.
2207    BpGraphReader(BGR& graph, std::istream& is = std::cin)
2208      : _is(&is), local_is(false), _graph(graph),
2209        _use_nodes(false), _use_edges(false),
2210        _skip_nodes(false), _skip_edges(false) {}
2211
2212    /// \brief Constructor
2213    ///
2214    /// Construct an undirected graph reader, which reads from the given
2215    /// file.
2216    BpGraphReader(BGR& graph, const std::string& fn)
2217      : _is(new std::ifstream(fn.c_str())), local_is(true),
2218        _filename(fn), _graph(graph),
2219        _use_nodes(false), _use_edges(false),
2220        _skip_nodes(false), _skip_edges(false) {
2221      if (!(*_is)) {
2222        delete _is;
2223        throw IoError("Cannot open file", fn);
2224      }
2225    }
2226
2227    /// \brief Constructor
2228    ///
2229    /// Construct an undirected graph reader, which reads from the given
2230    /// file.
2231    BpGraphReader(BGR& graph, const char* fn)
2232      : _is(new std::ifstream(fn)), local_is(true),
2233        _filename(fn), _graph(graph),
2234        _use_nodes(false), _use_edges(false),
2235        _skip_nodes(false), _skip_edges(false) {
2236      if (!(*_is)) {
2237        delete _is;
2238        throw IoError("Cannot open file", fn);
2239      }
2240    }
2241
2242    /// \brief Destructor
2243    ~BpGraphReader() {
2244      for (typename NodeMaps::iterator it = _red_maps.begin();
2245           it != _red_maps.end(); ++it) {
2246        delete it->second;
2247      }
2248
2249      for (typename NodeMaps::iterator it = _blue_maps.begin();
2250           it != _blue_maps.end(); ++it) {
2251        delete it->second;
2252      }
2253
2254      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2255           it != _edge_maps.end(); ++it) {
2256        delete it->second;
2257      }
2258
2259      for (typename Attributes::iterator it = _attributes.begin();
2260           it != _attributes.end(); ++it) {
2261        delete it->second;
2262      }
2263
2264      if (local_is) {
2265        delete _is;
2266      }
2267
2268    }
2269
2270  private:
2271    template <typename TBGR>
2272    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is);
2273    template <typename TBGR>
2274    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph,
2275                                             const std::string& fn);
2276    template <typename TBGR>
2277    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
2278
2279    BpGraphReader(BpGraphReader& other)
2280      : _is(other._is), local_is(other.local_is), _graph(other._graph),
2281        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
2282        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
2283
2284      other._is = 0;
2285      other.local_is = false;
2286
2287      _node_index.swap(other._node_index);
2288      _edge_index.swap(other._edge_index);
2289
2290      _red_maps.swap(other._red_maps);
2291      _blue_maps.swap(other._blue_maps);
2292      _edge_maps.swap(other._edge_maps);
2293      _attributes.swap(other._attributes);
2294
2295      _nodes_caption = other._nodes_caption;
2296      _edges_caption = other._edges_caption;
2297      _attributes_caption = other._attributes_caption;
2298
2299    }
2300
2301    BpGraphReader& operator=(const BpGraphReader&);
2302
2303  public:
2304
2305    /// \name Reading Rules
2306    /// @{
2307
2308    /// \brief Node map reading rule
2309    ///
2310    /// Add a node map reading rule to the reader.
2311    template <typename Map>
2312    BpGraphReader& nodeMap(const std::string& caption, Map& map) {
2313      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2314      _reader_bits::MapStorageBase<Node>* red_storage =
2315        new _reader_bits::MapStorage<Node, Map>(map);
2316      _red_maps.push_back(std::make_pair(caption, red_storage));
2317      _reader_bits::MapStorageBase<Node>* blue_storage =
2318        new _reader_bits::MapStorage<Node, Map>(map);
2319      _blue_maps.push_back(std::make_pair(caption, blue_storage));
2320      return *this;
2321    }
2322
2323    /// \brief Node map reading rule
2324    ///
2325    /// Add a node map reading rule with specialized converter to the
2326    /// reader.
2327    template <typename Map, typename Converter>
2328    BpGraphReader& nodeMap(const std::string& caption, Map& map,
2329                           const Converter& converter = Converter()) {
2330      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2331      _reader_bits::MapStorageBase<Node>* red_storage =
2332        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
2333      _red_maps.push_back(std::make_pair(caption, red_storage));
2334      _reader_bits::MapStorageBase<Node>* blue_storage =
2335        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
2336      _blue_maps.push_back(std::make_pair(caption, blue_storage));
2337      return *this;
2338    }
2339
2340    /// Add a red node map reading rule to the reader.
2341    template <typename Map>
2342    BpGraphReader& redNodeMap(const std::string& caption, Map& map) {
2343      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2344      _reader_bits::MapStorageBase<Node>* storage =
2345        new _reader_bits::MapStorage<Node, Map>(map);
2346      _red_maps.push_back(std::make_pair(caption, storage));
2347      return *this;
2348    }
2349
2350    /// \brief Red node map reading rule
2351    ///
2352    /// Add a red node map node reading rule with specialized converter to
2353    /// the reader.
2354    template <typename Map, typename Converter>
2355    BpGraphReader& redNodeMap(const std::string& caption, Map& map,
2356                              const Converter& converter = Converter()) {
2357      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2358      _reader_bits::MapStorageBase<Node>* storage =
2359        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
2360      _red_maps.push_back(std::make_pair(caption, storage));
2361      return *this;
2362    }
2363
2364    /// Add a blue node map reading rule to the reader.
2365    template <typename Map>
2366    BpGraphReader& blueNodeMap(const std::string& caption, Map& map) {
2367      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2368      _reader_bits::MapStorageBase<Node>* storage =
2369        new _reader_bits::MapStorage<Node, Map>(map);
2370      _blue_maps.push_back(std::make_pair(caption, storage));
2371      return *this;
2372    }
2373
2374    /// \brief Blue node map reading rule
2375    ///
2376    /// Add a blue node map reading rule with specialized converter to
2377    /// the reader.
2378    template <typename Map, typename Converter>
2379    BpGraphReader& blueNodeMap(const std::string& caption, Map& map,
2380                               const Converter& converter = Converter()) {
2381      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2382      _reader_bits::MapStorageBase<Node>* storage =
2383        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
2384      _blue_maps.push_back(std::make_pair(caption, storage));
2385      return *this;
2386    }
2387
2388    /// \brief Edge map reading rule
2389    ///
2390    /// Add an edge map reading rule to the reader.
2391    template <typename Map>
2392    BpGraphReader& edgeMap(const std::string& caption, Map& map) {
2393      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
2394      _reader_bits::MapStorageBase<Edge>* storage =
2395        new _reader_bits::MapStorage<Edge, Map>(map);
2396      _edge_maps.push_back(std::make_pair(caption, storage));
2397      return *this;
2398    }
2399
2400    /// \brief Edge map reading rule
2401    ///
2402    /// Add an edge map reading rule with specialized converter to the
2403    /// reader.
2404    template <typename Map, typename Converter>
2405    BpGraphReader& edgeMap(const std::string& caption, Map& map,
2406                          const Converter& converter = Converter()) {
2407      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
2408      _reader_bits::MapStorageBase<Edge>* storage =
2409        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
2410      _edge_maps.push_back(std::make_pair(caption, storage));
2411      return *this;
2412    }
2413
2414    /// \brief Arc map reading rule
2415    ///
2416    /// Add an arc map reading rule to the reader.
2417    template <typename Map>
2418    BpGraphReader& arcMap(const std::string& caption, Map& map) {
2419      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
2420      _reader_bits::MapStorageBase<Edge>* forward_storage =
2421        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
2422      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
2423      _reader_bits::MapStorageBase<Edge>* backward_storage =
2424        new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
2425      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
2426      return *this;
2427    }
2428
2429    /// \brief Arc map reading rule
2430    ///
2431    /// Add an arc map reading rule with specialized converter to the
2432    /// reader.
2433    template <typename Map, typename Converter>
2434    BpGraphReader& arcMap(const std::string& caption, Map& map,
2435                          const Converter& converter = Converter()) {
2436      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
2437      _reader_bits::MapStorageBase<Edge>* forward_storage =
2438        new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter>
2439        (_graph, map, converter);
2440      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
2441      _reader_bits::MapStorageBase<Edge>* backward_storage =
2442        new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter>
2443        (_graph, map, converter);
2444      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
2445      return *this;
2446    }
2447
2448    /// \brief Attribute reading rule
2449    ///
2450    /// Add an attribute reading rule to the reader.
2451    template <typename Value>
2452    BpGraphReader& attribute(const std::string& caption, Value& value) {
2453      _reader_bits::ValueStorageBase* storage =
2454        new _reader_bits::ValueStorage<Value>(value);
2455      _attributes.insert(std::make_pair(caption, storage));
2456      return *this;
2457    }
2458
2459    /// \brief Attribute reading rule
2460    ///
2461    /// Add an attribute reading rule with specialized converter to the
2462    /// reader.
2463    template <typename Value, typename Converter>
2464    BpGraphReader& attribute(const std::string& caption, Value& value,
2465                             const Converter& converter = Converter()) {
2466      _reader_bits::ValueStorageBase* storage =
2467        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
2468      _attributes.insert(std::make_pair(caption, storage));
2469      return *this;
2470    }
2471
2472    /// \brief Node reading rule
2473    ///
2474    /// Add a node reading rule to reader.
2475    BpGraphReader& node(const std::string& caption, Node& node) {
2476      typedef _reader_bits::MapLookUpConverter<Node> Converter;
2477      Converter converter(_node_index);
2478      _reader_bits::ValueStorageBase* storage =
2479        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
2480      _attributes.insert(std::make_pair(caption, storage));
2481      return *this;
2482    }
2483
2484    /// \brief Edge reading rule
2485    ///
2486    /// Add an edge reading rule to reader.
2487    BpGraphReader& edge(const std::string& caption, Edge& edge) {
2488      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
2489      Converter converter(_edge_index);
2490      _reader_bits::ValueStorageBase* storage =
2491        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
2492      _attributes.insert(std::make_pair(caption, storage));
2493      return *this;
2494    }
2495
2496    /// \brief Arc reading rule
2497    ///
2498    /// Add an arc reading rule to reader.
2499    BpGraphReader& arc(const std::string& caption, Arc& arc) {
2500      typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter;
2501      Converter converter(_graph, _edge_index);
2502      _reader_bits::ValueStorageBase* storage =
2503        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
2504      _attributes.insert(std::make_pair(caption, storage));
2505      return *this;
2506    }
2507
2508    /// @}
2509
2510    /// \name Select Section by Name
2511    /// @{
2512
2513    /// \brief Set \c \@nodes section to be read
2514    ///
2515    /// Set \c \@nodes section to be read.
2516    BpGraphReader& nodes(const std::string& caption) {
2517      _nodes_caption = caption;
2518      return *this;
2519    }
2520
2521    /// \brief Set \c \@edges section to be read
2522    ///
2523    /// Set \c \@edges section to be read.
2524    BpGraphReader& edges(const std::string& caption) {
2525      _edges_caption = caption;
2526      return *this;
2527    }
2528
2529    /// \brief Set \c \@attributes section to be read
2530    ///
2531    /// Set \c \@attributes section to be read.
2532    BpGraphReader& attributes(const std::string& caption) {
2533      _attributes_caption = caption;
2534      return *this;
2535    }
2536
2537    /// @}
2538
2539    /// \name Using Previously Constructed Node or Edge Set
2540    /// @{
2541
2542    /// \brief Use previously constructed node set
2543    ///
2544    /// Use previously constructed node set, and specify the node
2545    /// label map.
2546    template <typename Map>
2547    BpGraphReader& useNodes(const Map& map) {
2548      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
2549      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
2550      _use_nodes = true;
2551      _writer_bits::DefaultConverter<typename Map::Value> converter;
2552      for (NodeIt n(_graph); n != INVALID; ++n) {
2553        _node_index.insert(std::make_pair(converter(map[n]), n));
2554      }
2555      return *this;
2556    }
2557
2558    /// \brief Use previously constructed node set
2559    ///
2560    /// Use previously constructed node set, and specify the node
2561    /// label map and a functor which converts the label map values to
2562    /// \c std::string.
2563    template <typename Map, typename Converter>
2564    BpGraphReader& useNodes(const Map& map,
2565                            const Converter& converter = Converter()) {
2566      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
2567      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
2568      _use_nodes = true;
2569      for (NodeIt n(_graph); n != INVALID; ++n) {
2570        _node_index.insert(std::make_pair(converter(map[n]), n));
2571      }
2572      return *this;
2573    }
2574
2575    /// \brief Use previously constructed edge set
2576    ///
2577    /// Use previously constructed edge set, and specify the edge
2578    /// label map.
2579    template <typename Map>
2580    BpGraphReader& useEdges(const Map& map) {
2581      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
2582      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
2583      _use_edges = true;
2584      _writer_bits::DefaultConverter<typename Map::Value> converter;
2585      for (EdgeIt a(_graph); a != INVALID; ++a) {
2586        _edge_index.insert(std::make_pair(converter(map[a]), a));
2587      }
2588      return *this;
2589    }
2590
2591    /// \brief Use previously constructed edge set
2592    ///
2593    /// Use previously constructed edge set, and specify the edge
2594    /// label map and a functor which converts the label map values to
2595    /// \c std::string.
2596    template <typename Map, typename Converter>
2597    BpGraphReader& useEdges(const Map& map,
2598                            const Converter& converter = Converter()) {
2599      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
2600      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
2601      _use_edges = true;
2602      for (EdgeIt a(_graph); a != INVALID; ++a) {
2603        _edge_index.insert(std::make_pair(converter(map[a]), a));
2604      }
2605      return *this;
2606    }
2607
2608    /// \brief Skip the reading of node section
2609    ///
2610    /// Omit the reading of the node section. This implies that each node
2611    /// map reading rule will be abandoned, and the nodes of the graph
2612    /// will not be constructed, which usually cause that the edge set
2613    /// could not be read due to lack of node name
2614    /// could not be read due to lack of node name resolving.
2615    /// Therefore \c skipEdges() function should also be used, or
2616    /// \c useNodes() should be used to specify the label of the nodes.
2617    BpGraphReader& skipNodes() {
2618      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
2619      _skip_nodes = true;
2620      return *this;
2621    }
2622
2623    /// \brief Skip the reading of edge section
2624    ///
2625    /// Omit the reading of the edge section. This implies that each edge
2626    /// map reading rule will be abandoned, and the edges of the graph
2627    /// will not be constructed.
2628    BpGraphReader& skipEdges() {
2629      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
2630      _skip_edges = true;
2631      return *this;
2632    }
2633
2634    /// @}
2635
2636  private:
2637
2638    bool readLine() {
2639      std::string str;
2640      while(++line_num, std::getline(*_is, str)) {
2641        line.clear(); line.str(str);
2642        char c;
2643        if (line >> std::ws >> c && c != '#') {
2644          line.putback(c);
2645          return true;
2646        }
2647      }
2648      return false;
2649    }
2650
2651    bool readSuccess() {
2652      return static_cast<bool>(*_is);
2653    }
2654
2655    void skipSection() {
2656      char c;
2657      while (readSuccess() && line >> c && c != '@') {
2658        readLine();
2659      }
2660      if (readSuccess()) {
2661        line.putback(c);
2662      }
2663    }
2664
2665    void readRedNodes() {
2666
2667      std::vector<int> map_index(_red_maps.size());
2668      int map_num, label_index;
2669
2670      char c;
2671      if (!readLine() || !(line >> c) || c == '@') {
2672        if (readSuccess() && line) line.putback(c);
2673        if (!_red_maps.empty())
2674          throw FormatError("Cannot find map names");
2675        return;
2676      }
2677      line.putback(c);
2678
2679      {
2680        std::map<std::string, int> maps;
2681
2682        std::string map;
2683        int index = 0;
2684        while (_reader_bits::readToken(line, map)) {
2685          if (maps.find(map) != maps.end()) {
2686            std::ostringstream msg;
2687            msg << "Multiple occurence of red node map: " << map;
2688            throw FormatError(msg.str());
2689          }
2690          maps.insert(std::make_pair(map, index));
2691          ++index;
2692        }
2693
2694        for (int i = 0; i < static_cast<int>(_red_maps.size()); ++i) {
2695          std::map<std::string, int>::iterator jt =
2696            maps.find(_red_maps[i].first);
2697          if (jt == maps.end()) {
2698            std::ostringstream msg;
2699            msg << "Map not found: " << _red_maps[i].first;
2700            throw FormatError(msg.str());
2701          }
2702          map_index[i] = jt->second;
2703        }
2704
2705        {
2706          std::map<std::string, int>::iterator jt = maps.find("label");
2707          if (jt != maps.end()) {
2708            label_index = jt->second;
2709          } else {
2710            label_index = -1;
2711          }
2712        }
2713        map_num = maps.size();
2714      }
2715
2716      while (readLine() && line >> c && c != '@') {
2717        line.putback(c);
2718
2719        std::vector<std::string> tokens(map_num);
2720        for (int i = 0; i < map_num; ++i) {
2721          if (!_reader_bits::readToken(line, tokens[i])) {
2722            std::ostringstream msg;
2723            msg << "Column not found (" << i + 1 << ")";
2724            throw FormatError(msg.str());
2725          }
2726        }
2727        if (line >> std::ws >> c)
2728          throw FormatError("Extra character at the end of line");
2729
2730        Node n;
2731        if (!_use_nodes) {
2732          n = _graph.addRedNode();
2733          if (label_index != -1)
2734            _node_index.insert(std::make_pair(tokens[label_index], n));
2735        } else {
2736          if (label_index == -1)
2737            throw FormatError("Label map not found");
2738          typename std::map<std::string, Node>::iterator it =
2739            _node_index.find(tokens[label_index]);
2740          if (it == _node_index.end()) {
2741            std::ostringstream msg;
2742            msg << "Node with label not found: " << tokens[label_index];
2743            throw FormatError(msg.str());
2744          }
2745          n = it->second;
2746        }
2747
2748        for (int i = 0; i < static_cast<int>(_red_maps.size()); ++i) {
2749          _red_maps[i].second->set(n, tokens[map_index[i]]);
2750        }
2751
2752      }
2753      if (readSuccess()) {
2754        line.putback(c);
2755      }
2756    }
2757
2758    void readBlueNodes() {
2759
2760      std::vector<int> map_index(_blue_maps.size());
2761      int map_num, label_index;
2762
2763      char c;
2764      if (!readLine() || !(line >> c) || c == '@') {
2765        if (readSuccess() && line) line.putback(c);
2766        if (!_blue_maps.empty())
2767          throw FormatError("Cannot find map names");
2768        return;
2769      }
2770      line.putback(c);
2771
2772      {
2773        std::map<std::string, int> maps;
2774
2775        std::string map;
2776        int index = 0;
2777        while (_reader_bits::readToken(line, map)) {
2778          if (maps.find(map) != maps.end()) {
2779            std::ostringstream msg;
2780            msg << "Multiple occurence of blue node map: " << map;
2781            throw FormatError(msg.str());
2782          }
2783          maps.insert(std::make_pair(map, index));
2784          ++index;
2785        }
2786
2787        for (int i = 0; i < static_cast<int>(_blue_maps.size()); ++i) {
2788          std::map<std::string, int>::iterator jt =
2789            maps.find(_blue_maps[i].first);
2790          if (jt == maps.end()) {
2791            std::ostringstream msg;
2792            msg << "Map not found: " << _blue_maps[i].first;
2793            throw FormatError(msg.str());
2794          }
2795          map_index[i] = jt->second;
2796        }
2797
2798        {
2799          std::map<std::string, int>::iterator jt = maps.find("label");
2800          if (jt != maps.end()) {
2801            label_index = jt->second;
2802          } else {
2803            label_index = -1;
2804          }
2805        }
2806        map_num = maps.size();
2807      }
2808
2809      while (readLine() && line >> c && c != '@') {
2810        line.putback(c);
2811
2812        std::vector<std::string> tokens(map_num);
2813        for (int i = 0; i < map_num; ++i) {
2814          if (!_reader_bits::readToken(line, tokens[i])) {
2815            std::ostringstream msg;
2816            msg << "Column not found (" << i + 1 << ")";
2817            throw FormatError(msg.str());
2818          }
2819        }
2820        if (line >> std::ws >> c)
2821          throw FormatError("Extra character at the end of line");
2822
2823        Node n;
2824        if (!_use_nodes) {
2825          n = _graph.addBlueNode();
2826          if (label_index != -1)
2827            _node_index.insert(std::make_pair(tokens[label_index], n));
2828        } else {
2829          if (label_index == -1)
2830            throw FormatError("Label map not found");
2831          typename std::map<std::string, Node>::iterator it =
2832            _node_index.find(tokens[label_index]);
2833          if (it == _node_index.end()) {
2834            std::ostringstream msg;
2835            msg << "Node with label not found: " << tokens[label_index];
2836            throw FormatError(msg.str());
2837          }
2838          n = it->second;
2839        }
2840
2841        for (int i = 0; i < static_cast<int>(_blue_maps.size()); ++i) {
2842          _blue_maps[i].second->set(n, tokens[map_index[i]]);
2843        }
2844
2845      }
2846      if (readSuccess()) {
2847        line.putback(c);
2848      }
2849    }
2850
2851    void readEdges() {
2852
2853      std::vector<int> map_index(_edge_maps.size());
2854      int map_num, label_index;
2855
2856      char c;
2857      if (!readLine() || !(line >> c) || c == '@') {
2858        if (readSuccess() && line) line.putback(c);
2859        if (!_edge_maps.empty())
2860          throw FormatError("Cannot find map names");
2861        return;
2862      }
2863      line.putback(c);
2864
2865      {
2866        std::map<std::string, int> maps;
2867
2868        std::string map;
2869        int index = 0;
2870        while (_reader_bits::readToken(line, map)) {
2871          if (maps.find(map) != maps.end()) {
2872            std::ostringstream msg;
2873            msg << "Multiple occurence of edge map: " << map;
2874            throw FormatError(msg.str());
2875          }
2876          maps.insert(std::make_pair(map, index));
2877          ++index;
2878        }
2879
2880        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
2881          std::map<std::string, int>::iterator jt =
2882            maps.find(_edge_maps[i].first);
2883          if (jt == maps.end()) {
2884            std::ostringstream msg;
2885            msg << "Map not found: " << _edge_maps[i].first;
2886            throw FormatError(msg.str());
2887          }
2888          map_index[i] = jt->second;
2889        }
2890
2891        {
2892          std::map<std::string, int>::iterator jt = maps.find("label");
2893          if (jt != maps.end()) {
2894            label_index = jt->second;
2895          } else {
2896            label_index = -1;
2897          }
2898        }
2899        map_num = maps.size();
2900      }
2901
2902      while (readLine() && line >> c && c != '@') {
2903        line.putback(c);
2904
2905        std::string source_token;
2906        std::string target_token;
2907
2908        if (!_reader_bits::readToken(line, source_token))
2909          throw FormatError("Red node not found");
2910
2911        if (!_reader_bits::readToken(line, target_token))
2912          throw FormatError("Blue node not found");
2913
2914        std::vector<std::string> tokens(map_num);
2915        for (int i = 0; i < map_num; ++i) {
2916          if (!_reader_bits::readToken(line, tokens[i])) {
2917            std::ostringstream msg;
2918            msg << "Column not found (" << i + 1 << ")";
2919            throw FormatError(msg.str());
2920          }
2921        }
2922        if (line >> std::ws >> c)
2923          throw FormatError("Extra character at the end of line");
2924
2925        Edge e;
2926        if (!_use_edges) {
2927
2928          typename NodeIndex::iterator it;
2929
2930          it = _node_index.find(source_token);
2931          if (it == _node_index.end()) {
2932            std::ostringstream msg;
2933            msg << "Item not found: " << source_token;
2934            throw FormatError(msg.str());
2935          }
2936          Node source = it->second;
2937          if (!_graph.red(source)) {
2938            std::ostringstream msg;
2939            msg << "Item is not red node: " << source_token;
2940            throw FormatError(msg.str());
2941          }
2942
2943          it = _node_index.find(target_token);
2944          if (it == _node_index.end()) {
2945            std::ostringstream msg;
2946            msg << "Item not found: " << target_token;
2947            throw FormatError(msg.str());
2948          }
2949          Node target = it->second;
2950          if (!_graph.blue(target)) {
2951            std::ostringstream msg;
2952            msg << "Item is not red node: " << source_token;
2953            throw FormatError(msg.str());
2954          }
2955
2956          // It is checked that source is red and
2957          // target is blue, so this should be safe:
2958          e = _graph.addEdge(_graph.asRedNodeUnsafe(source),
2959                             _graph.asBlueNodeUnsafe(target));
2960          if (label_index != -1)
2961            _edge_index.insert(std::make_pair(tokens[label_index], e));
2962        } else {
2963          if (label_index == -1)
2964            throw FormatError("Label map not found");
2965          typename std::map<std::string, Edge>::iterator it =
2966            _edge_index.find(tokens[label_index]);
2967          if (it == _edge_index.end()) {
2968            std::ostringstream msg;
2969            msg << "Edge with label not found: " << tokens[label_index];
2970            throw FormatError(msg.str());
2971          }
2972          e = it->second;
2973        }
2974
2975        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
2976          _edge_maps[i].second->set(e, tokens[map_index[i]]);
2977        }
2978
2979      }
2980      if (readSuccess()) {
2981        line.putback(c);
2982      }
2983    }
2984
2985    void readAttributes() {
2986
2987      std::set<std::string> read_attr;
2988
2989      char c;
2990      while (readLine() && line >> c && c != '@') {
2991        line.putback(c);
2992
2993        std::string attr, token;
2994        if (!_reader_bits::readToken(line, attr))
2995          throw FormatError("Attribute name not found");
2996        if (!_reader_bits::readToken(line, token))
2997          throw FormatError("Attribute value not found");
2998        if (line >> c)
2999          throw FormatError("Extra character at the end of line");
3000
3001        {
3002          std::set<std::string>::iterator it = read_attr.find(attr);
3003          if (it != read_attr.end()) {
3004            std::ostringstream msg;
3005            msg << "Multiple occurence of attribute: " << attr;
3006            throw FormatError(msg.str());
3007          }
3008          read_attr.insert(attr);
3009        }
3010
3011        {
3012          typename Attributes::iterator it = _attributes.lower_bound(attr);
3013          while (it != _attributes.end() && it->first == attr) {
3014            it->second->set(token);
3015            ++it;
3016          }
3017        }
3018
3019      }
3020      if (readSuccess()) {
3021        line.putback(c);
3022      }
3023      for (typename Attributes::iterator it = _attributes.begin();
3024           it != _attributes.end(); ++it) {
3025        if (read_attr.find(it->first) == read_attr.end()) {
3026          std::ostringstream msg;
3027          msg << "Attribute not found: " << it->first;
3028          throw FormatError(msg.str());
3029        }
3030      }
3031    }
3032
3033  public:
3034
3035    /// \name Execution of the Reader
3036    /// @{
3037
3038    /// \brief Start the batch processing
3039    ///
3040    /// This function starts the batch processing
3041    void run() {
3042
3043      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
3044
3045      bool red_nodes_done = _skip_nodes;
3046      bool blue_nodes_done = _skip_nodes;
3047      bool edges_done = _skip_edges;
3048      bool attributes_done = false;
3049
3050      line_num = 0;
3051      readLine();
3052      skipSection();
3053
3054      while (readSuccess()) {
3055        try {
3056          char c;
3057          std::string section, caption;
3058          line >> c;
3059          _reader_bits::readToken(line, section);
3060          _reader_bits::readToken(line, caption);
3061
3062          if (line >> c)
3063            throw FormatError("Extra character at the end of line");
3064
3065          if (section == "red_nodes" && !red_nodes_done) {
3066            if (_nodes_caption.empty() || _nodes_caption == caption) {
3067              readRedNodes();
3068              red_nodes_done = true;
3069            }
3070          } else if (section == "blue_nodes" && !blue_nodes_done) {
3071            if (_nodes_caption.empty() || _nodes_caption == caption) {
3072              readBlueNodes();
3073              blue_nodes_done = true;
3074            }
3075          } else if ((section == "edges" || section == "arcs") &&
3076                     !edges_done) {
3077            if (_edges_caption.empty() || _edges_caption == caption) {
3078              readEdges();
3079              edges_done = true;
3080            }
3081          } else if (section == "attributes" && !attributes_done) {
3082            if (_attributes_caption.empty() || _attributes_caption == caption) {
3083              readAttributes();
3084              attributes_done = true;
3085            }
3086          } else {
3087            readLine();
3088            skipSection();
3089          }
3090        } catch (FormatError& error) {
3091          error.line(line_num);
3092          error.file(_filename);
3093          throw;
3094        }
3095      }
3096
3097      if (!red_nodes_done) {
3098        throw FormatError("Section @red_nodes not found");
3099      }
3100
3101      if (!blue_nodes_done) {
3102        throw FormatError("Section @blue_nodes not found");
3103      }
3104
3105      if (!edges_done) {
3106        throw FormatError("Section @edges not found");
3107      }
3108
3109      if (!attributes_done && !_attributes.empty()) {
3110        throw FormatError("Section @attributes not found");
3111      }
3112
3113    }
3114
3115    /// @}
3116
3117  };
3118
3119  /// \ingroup lemon_io
3120  ///
3121  /// \brief Return a \ref BpGraphReader class
3122  ///
3123  /// This function just returns a \ref BpGraphReader class.
3124  ///
3125  /// With this function a graph can be read from an
3126  /// \ref lgf-format "LGF" file or input stream with several maps and
3127  /// attributes. For example, there is bipartite weighted matching problem
3128  /// on a graph, i.e. a graph with a \e weight map on the edges. This
3129  /// graph can be read with the following code:
3130  ///
3131  ///\code
3132  ///ListBpGraph graph;
3133  ///ListBpGraph::EdgeMap<int> weight(graph);
3134  ///bpGraphReader(graph, std::cin).
3135  ///  edgeMap("weight", weight).
3136  ///  run();
3137  ///\endcode
3138  ///
3139  /// For a complete documentation, please see the \ref BpGraphReader
3140  /// class documentation.
3141  /// \warning Don't forget to put the \ref BpGraphReader::run() "run()"
3142  /// to the end of the parameter list.
3143  /// \relates BpGraphReader
3144  /// \sa bpGraphReader(TBGR& graph, const std::string& fn)
3145  /// \sa bpGraphReader(TBGR& graph, const char* fn)
3146  template <typename TBGR>
3147  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) {
3148    BpGraphReader<TBGR> tmp(graph, is);
3149    return tmp;
3150  }
3151
3152  /// \brief Return a \ref BpGraphReader class
3153  ///
3154  /// This function just returns a \ref BpGraphReader class.
3155  /// \relates BpGraphReader
3156  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
3157  template <typename TBGR>
3158  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) {
3159    BpGraphReader<TBGR> tmp(graph, fn);
3160    return tmp;
3161  }
3162
3163  /// \brief Return a \ref BpGraphReader class
3164  ///
3165  /// This function just returns a \ref BpGraphReader class.
3166  /// \relates BpGraphReader
3167  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
3168  template <typename TBGR>
3169  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) {
3170    BpGraphReader<TBGR> tmp(graph, fn);
3171    return tmp;
3172  }
3173
3174  class SectionReader;
3175
3176  SectionReader sectionReader(std::istream& is);
3177  SectionReader sectionReader(const std::string& fn);
3178  SectionReader sectionReader(const char* fn);
3179
3180  /// \ingroup lemon_io
3181  ///
3182  /// \brief Section reader class
3183  ///
3184  /// In the \ref lgf-format "LGF" file extra sections can be placed,
3185  /// which contain any data in arbitrary format. Such sections can be
3186  /// read with this class. A reading rule can be added to the class
3187  /// with two different functions. With the \c sectionLines() function a
3188  /// functor can process the section line-by-line, while with the \c
3189  /// sectionStream() member the section can be read from an input
3190  /// stream.
3191  class SectionReader {
3192  private:
3193
3194    std::istream* _is;
3195    bool local_is;
3196    std::string _filename;
3197
3198    typedef std::map<std::string, _reader_bits::Section*> Sections;
3199    Sections _sections;
3200
3201    int line_num;
3202    std::istringstream line;
3203
3204  public:
3205
3206    /// \brief Constructor
3207    ///
3208    /// Construct a section reader, which reads from the given input
3209    /// stream.
3210    SectionReader(std::istream& is)
3211      : _is(&is), local_is(false) {}
3212
3213    /// \brief Constructor
3214    ///
3215    /// Construct a section reader, which reads from the given file.
3216    SectionReader(const std::string& fn)
3217      : _is(new std::ifstream(fn.c_str())), local_is(true),
3218        _filename(fn) {
3219      if (!(*_is)) {
3220        delete _is;
3221        throw IoError("Cannot open file", fn);
3222      }
3223    }
3224
3225    /// \brief Constructor
3226    ///
3227    /// Construct a section reader, which reads from the given file.
3228    SectionReader(const char* fn)
3229      : _is(new std::ifstream(fn)), local_is(true),
3230        _filename(fn) {
3231      if (!(*_is)) {
3232        delete _is;
3233        throw IoError("Cannot open file", fn);
3234      }
3235    }
3236
3237    /// \brief Destructor
3238    ~SectionReader() {
3239      for (Sections::iterator it = _sections.begin();
3240           it != _sections.end(); ++it) {
3241        delete it->second;
3242      }
3243
3244      if (local_is) {
3245        delete _is;
3246      }
3247
3248    }
3249
3250  private:
3251
3252    friend SectionReader sectionReader(std::istream& is);
3253    friend SectionReader sectionReader(const std::string& fn);
3254    friend SectionReader sectionReader(const char* fn);
3255
3256    SectionReader(SectionReader& other)
3257      : _is(other._is), local_is(other.local_is) {
3258
3259      other._is = 0;
3260      other.local_is = false;
3261
3262      _sections.swap(other._sections);
3263    }
3264
3265    SectionReader& operator=(const SectionReader&);
3266
3267  public:
3268
3269    /// \name Section Readers
3270    /// @{
3271
3272    /// \brief Add a section processor with line oriented reading
3273    ///
3274    /// The first parameter is the type descriptor of the section, the
3275    /// second is a functor, which takes just one \c std::string
3276    /// parameter. At the reading process, each line of the section
3277    /// will be given to the functor object. However, the empty lines
3278    /// and the comment lines are filtered out, and the leading
3279    /// whitespaces are trimmed from each processed string.
3280    ///
3281    /// For example, let's see a section, which contain several
3282    /// integers, which should be inserted into a vector.
3283    ///\code
3284    ///  @numbers
3285    ///  12 45 23
3286    ///  4
3287    ///  23 6
3288    ///\endcode
3289    ///
3290    /// The functor is implemented as a struct:
3291    ///\code
3292    ///  struct NumberSection {
3293    ///    std::vector<int>& _data;
3294    ///    NumberSection(std::vector<int>& data) : _data(data) {}
3295    ///    void operator()(const std::string& line) {
3296    ///      std::istringstream ls(line);
3297    ///      int value;
3298    ///      while (ls >> value) _data.push_back(value);
3299    ///    }
3300    ///  };
3301    ///
3302    ///  // ...
3303    ///
3304    ///  reader.sectionLines("numbers", NumberSection(vec));
3305    ///\endcode
3306    template <typename Functor>
3307    SectionReader& sectionLines(const std::string& type, Functor functor) {
3308      LEMON_ASSERT(!type.empty(), "Type is empty.");
3309      LEMON_ASSERT(_sections.find(type) == _sections.end(),
3310                   "Multiple reading of section.");
3311      _sections.insert(std::make_pair(type,
3312        new _reader_bits::LineSection<Functor>(functor)));
3313      return *this;
3314    }
3315
3316
3317    /// \brief Add a section processor with stream oriented reading
3318    ///
3319    /// The first parameter is the type of the section, the second is
3320    /// a functor, which takes an \c std::istream& and an \c int&
3321    /// parameter, the latter regard to the line number of stream. The
3322    /// functor can read the input while the section go on, and the
3323    /// line number should be modified accordingly.
3324    template <typename Functor>
3325    SectionReader& sectionStream(const std::string& type, Functor functor) {
3326      LEMON_ASSERT(!type.empty(), "Type is empty.");
3327      LEMON_ASSERT(_sections.find(type) == _sections.end(),
3328                   "Multiple reading of section.");
3329      _sections.insert(std::make_pair(type,
3330         new _reader_bits::StreamSection<Functor>(functor)));
3331      return *this;
3332    }
3333
3334    /// @}
3335
3336  private:
3337
3338    bool readLine() {
3339      std::string str;
3340      while(++line_num, std::getline(*_is, str)) {
3341        line.clear(); line.str(str);
3342        char c;
3343        if (line >> std::ws >> c && c != '#') {
3344          line.putback(c);
3345          return true;
3346        }
3347      }
3348      return false;
3349    }
3350
3351    bool readSuccess() {
3352      return static_cast<bool>(*_is);
3353    }
3354
3355    void skipSection() {
3356      char c;
3357      while (readSuccess() && line >> c && c != '@') {
3358        readLine();
3359      }
3360      if (readSuccess()) {
3361        line.putback(c);
3362      }
3363    }
3364
3365  public:
3366
3367
3368    /// \name Execution of the Reader
3369    /// @{
3370
3371    /// \brief Start the batch processing
3372    ///
3373    /// This function starts the batch processing.
3374    void run() {
3375
3376      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
3377
3378      std::set<std::string> extra_sections;
3379
3380      line_num = 0;
3381      readLine();
3382      skipSection();
3383
3384      while (readSuccess()) {
3385        try {
3386          char c;
3387          std::string section, caption;
3388          line >> c;
3389          _reader_bits::readToken(line, section);
3390          _reader_bits::readToken(line, caption);
3391
3392          if (line >> c)
3393            throw FormatError("Extra character at the end of line");
3394
3395          if (extra_sections.find(section) != extra_sections.end()) {
3396            std::ostringstream msg;
3397            msg << "Multiple occurence of section: " << section;
3398            throw FormatError(msg.str());
3399          }
3400          Sections::iterator it = _sections.find(section);
3401          if (it != _sections.end()) {
3402            extra_sections.insert(section);
3403            it->second->process(*_is, line_num);
3404          }
3405          readLine();
3406          skipSection();
3407        } catch (FormatError& error) {
3408          error.line(line_num);
3409          error.file(_filename);
3410          throw;
3411        }
3412      }
3413      for (Sections::iterator it = _sections.begin();
3414           it != _sections.end(); ++it) {
3415        if (extra_sections.find(it->first) == extra_sections.end()) {
3416          std::ostringstream os;
3417          os << "Cannot find section: " << it->first;
3418          throw FormatError(os.str());
3419        }
3420      }
3421    }
3422
3423    /// @}
3424
3425  };
3426
3427  /// \ingroup lemon_io
3428  ///
3429  /// \brief Return a \ref SectionReader class
3430  ///
3431  /// This function just returns a \ref SectionReader class.
3432  ///
3433  /// Please see SectionReader documentation about the custom section
3434  /// input.
3435  ///
3436  /// \relates SectionReader
3437  /// \sa sectionReader(const std::string& fn)
3438  /// \sa sectionReader(const char *fn)
3439  inline SectionReader sectionReader(std::istream& is) {
3440    SectionReader tmp(is);
3441    return tmp;
3442  }
3443
3444  /// \brief Return a \ref SectionReader class
3445  ///
3446  /// This function just returns a \ref SectionReader class.
3447  /// \relates SectionReader
3448  /// \sa sectionReader(std::istream& is)
3449  inline SectionReader sectionReader(const std::string& fn) {
3450    SectionReader tmp(fn);
3451    return tmp;
3452  }
3453
3454  /// \brief Return a \ref SectionReader class
3455  ///
3456  /// This function just returns a \ref SectionReader class.
3457  /// \relates SectionReader
3458  /// \sa sectionReader(std::istream& is)
3459  inline SectionReader sectionReader(const char* fn) {
3460    SectionReader tmp(fn);
3461    return tmp;
3462  }
3463
3464  /// \ingroup lemon_io
3465  ///
3466  /// \brief Reader for the contents of the \ref lgf-format "LGF" file
3467  ///
3468  /// This class can be used to read the sections, the map names and
3469  /// the attributes from a file. Usually, the LEMON programs know
3470  /// that, which type of graph, which maps and which attributes
3471  /// should be read from a file, but in general tools (like glemon)
3472  /// the contents of an LGF file should be guessed somehow. This class
3473  /// reads the graph and stores the appropriate information for
3474  /// reading the graph.
3475  ///
3476  ///\code
3477  /// LgfContents contents("graph.lgf");
3478  /// contents.run();
3479  ///
3480  /// // Does it contain any node section and arc section?
3481  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
3482  ///   std::cerr << "Failure, cannot find graph." << std::endl;
3483  ///   return -1;
3484  /// }
3485  /// std::cout << "The name of the default node section: "
3486  ///           << contents.nodeSection(0) << std::endl;
3487  /// std::cout << "The number of the arc maps: "
3488  ///           << contents.arcMaps(0).size() << std::endl;
3489  /// std::cout << "The name of second arc map: "
3490  ///           << contents.arcMaps(0)[1] << std::endl;
3491  ///\endcode
3492  class LgfContents {
3493  private:
3494
3495    std::istream* _is;
3496    bool local_is;
3497
3498    std::vector<std::string> _node_sections;
3499    std::vector<std::string> _edge_sections;
3500    std::vector<std::string> _attribute_sections;
3501    std::vector<std::string> _extra_sections;
3502
3503    std::vector<bool> _arc_sections;
3504
3505    std::vector<std::vector<std::string> > _node_maps;
3506    std::vector<std::vector<std::string> > _edge_maps;
3507
3508    std::vector<std::vector<std::string> > _attributes;
3509
3510
3511    int line_num;
3512    std::istringstream line;
3513
3514  public:
3515
3516    /// \brief Constructor
3517    ///
3518    /// Construct an \e LGF contents reader, which reads from the given
3519    /// input stream.
3520    LgfContents(std::istream& is)
3521      : _is(&is), local_is(false) {}
3522
3523    /// \brief Constructor
3524    ///
3525    /// Construct an \e LGF contents reader, which reads from the given
3526    /// file.
3527    LgfContents(const std::string& fn)
3528      : _is(new std::ifstream(fn.c_str())), local_is(true) {
3529      if (!(*_is)) {
3530        delete _is;
3531        throw IoError("Cannot open file", fn);
3532      }
3533    }
3534
3535    /// \brief Constructor
3536    ///
3537    /// Construct an \e LGF contents reader, which reads from the given
3538    /// file.
3539    LgfContents(const char* fn)
3540      : _is(new std::ifstream(fn)), local_is(true) {
3541      if (!(*_is)) {
3542        delete _is;
3543        throw IoError("Cannot open file", fn);
3544      }
3545    }
3546
3547    /// \brief Destructor
3548    ~LgfContents() {
3549      if (local_is) delete _is;
3550    }
3551
3552  private:
3553
3554    LgfContents(const LgfContents&);
3555    LgfContents& operator=(const LgfContents&);
3556
3557  public:
3558
3559
3560    /// \name Node Sections
3561    /// @{
3562
3563    /// \brief Gives back the number of node sections in the file.
3564    ///
3565    /// Gives back the number of node sections in the file.
3566    int nodeSectionNum() const {
3567      return _node_sections.size();
3568    }
3569
3570    /// \brief Returns the node section name at the given position.
3571    ///
3572    /// Returns the node section name at the given position.
3573    const std::string& nodeSection(int i) const {
3574      return _node_sections[i];
3575    }
3576
3577    /// \brief Gives back the node maps for the given section.
3578    ///
3579    /// Gives back the node maps for the given section.
3580    const std::vector<std::string>& nodeMapNames(int i) const {
3581      return _node_maps[i];
3582    }
3583
3584    /// @}
3585
3586    /// \name Arc/Edge Sections
3587    /// @{
3588
3589    /// \brief Gives back the number of arc/edge sections in the file.
3590    ///
3591    /// Gives back the number of arc/edge sections in the file.
3592    /// \note It is synonym of \c edgeSectionNum().
3593    int arcSectionNum() const {
3594      return _edge_sections.size();
3595    }
3596
3597    /// \brief Returns the arc/edge section name at the given position.
3598    ///
3599    /// Returns the arc/edge section name at the given position.
3600    /// \note It is synonym of \c edgeSection().
3601    const std::string& arcSection(int i) const {
3602      return _edge_sections[i];
3603    }
3604
3605    /// \brief Gives back the arc/edge maps for the given section.
3606    ///
3607    /// Gives back the arc/edge maps for the given section.
3608    /// \note It is synonym of \c edgeMapNames().
3609    const std::vector<std::string>& arcMapNames(int i) const {
3610      return _edge_maps[i];
3611    }
3612
3613    /// @}
3614
3615    /// \name Synonyms
3616    /// @{
3617
3618    /// \brief Gives back the number of arc/edge sections in the file.
3619    ///
3620    /// Gives back the number of arc/edge sections in the file.
3621    /// \note It is synonym of \c arcSectionNum().
3622    int edgeSectionNum() const {
3623      return _edge_sections.size();
3624    }
3625
3626    /// \brief Returns the section name at the given position.
3627    ///
3628    /// Returns the section name at the given position.
3629    /// \note It is synonym of \c arcSection().
3630    const std::string& edgeSection(int i) const {
3631      return _edge_sections[i];
3632    }
3633
3634    /// \brief Gives back the edge maps for the given section.
3635    ///
3636    /// Gives back the edge maps for the given section.
3637    /// \note It is synonym of \c arcMapNames().
3638    const std::vector<std::string>& edgeMapNames(int i) const {
3639      return _edge_maps[i];
3640    }
3641
3642    /// @}
3643
3644    /// \name Attribute Sections
3645    /// @{
3646
3647    /// \brief Gives back the number of attribute sections in the file.
3648    ///
3649    /// Gives back the number of attribute sections in the file.
3650    int attributeSectionNum() const {
3651      return _attribute_sections.size();
3652    }
3653
3654    /// \brief Returns the attribute section name at the given position.
3655    ///
3656    /// Returns the attribute section name at the given position.
3657    const std::string& attributeSectionNames(int i) const {
3658      return _attribute_sections[i];
3659    }
3660
3661    /// \brief Gives back the attributes for the given section.
3662    ///
3663    /// Gives back the attributes for the given section.
3664    const std::vector<std::string>& attributes(int i) const {
3665      return _attributes[i];
3666    }
3667
3668    /// @}
3669
3670    /// \name Extra Sections
3671    /// @{
3672
3673    /// \brief Gives back the number of extra sections in the file.
3674    ///
3675    /// Gives back the number of extra sections in the file.
3676    int extraSectionNum() const {
3677      return _extra_sections.size();
3678    }
3679
3680    /// \brief Returns the extra section type at the given position.
3681    ///
3682    /// Returns the section type at the given position.
3683    const std::string& extraSection(int i) const {
3684      return _extra_sections[i];
3685    }
3686
3687    /// @}
3688
3689  private:
3690
3691    bool readLine() {
3692      std::string str;
3693      while(++line_num, std::getline(*_is, str)) {
3694        line.clear(); line.str(str);
3695        char c;
3696        if (line >> std::ws >> c && c != '#') {
3697          line.putback(c);
3698          return true;
3699        }
3700      }
3701      return false;
3702    }
3703
3704    bool readSuccess() {
3705      return static_cast<bool>(*_is);
3706    }
3707
3708    void skipSection() {
3709      char c;
3710      while (readSuccess() && line >> c && c != '@') {
3711        readLine();
3712      }
3713      if (readSuccess()) {
3714        line.putback(c);
3715      }
3716    }
3717
3718    void readMaps(std::vector<std::string>& maps) {
3719      char c;
3720      if (!readLine() || !(line >> c) || c == '@') {
3721        if (readSuccess() && line) line.putback(c);
3722        return;
3723      }
3724      line.putback(c);
3725      std::string map;
3726      while (_reader_bits::readToken(line, map)) {
3727        maps.push_back(map);
3728      }
3729    }
3730
3731    void readAttributes(std::vector<std::string>& attrs) {
3732      readLine();
3733      char c;
3734      while (readSuccess() && line >> c && c != '@') {
3735        line.putback(c);
3736        std::string attr;
3737        _reader_bits::readToken(line, attr);
3738        attrs.push_back(attr);
3739        readLine();
3740      }
3741      line.putback(c);
3742    }
3743
3744  public:
3745
3746    /// \name Execution of the Contents Reader
3747    /// @{
3748
3749    /// \brief Starts the reading
3750    ///
3751    /// This function starts the reading.
3752    void run() {
3753
3754      readLine();
3755      skipSection();
3756
3757      while (readSuccess()) {
3758
3759        char c;
3760        line >> c;
3761
3762        std::string section, caption;
3763        _reader_bits::readToken(line, section);
3764        _reader_bits::readToken(line, caption);
3765
3766        if (section == "nodes") {
3767          _node_sections.push_back(caption);
3768          _node_maps.push_back(std::vector<std::string>());
3769          readMaps(_node_maps.back());
3770          readLine(); skipSection();
3771        } else if (section == "arcs" || section == "edges") {
3772          _edge_sections.push_back(caption);
3773          _arc_sections.push_back(section == "arcs");
3774          _edge_maps.push_back(std::vector<std::string>());
3775          readMaps(_edge_maps.back());
3776          readLine(); skipSection();
3777        } else if (section == "attributes") {
3778          _attribute_sections.push_back(caption);
3779          _attributes.push_back(std::vector<std::string>());
3780          readAttributes(_attributes.back());
3781        } else {
3782          _extra_sections.push_back(section);
3783          readLine(); skipSection();
3784        }
3785      }
3786    }
3787
3788    /// @}
3789
3790  };
3791}
3792
3793#endif
Note: See TracBrowser for help on using the repository browser.