COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 1269:9eac00ea588f

Last change on this file since 1269:9eac00ea588f was 1250:97d978243703, checked in by Alpar Juttner <alpar@…>, 6 years ago

Fix unresolved doc references (#459)

File size: 117.2 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              typename Map = std::map<std::string, Value> >
159    struct MapLookUpConverter {
160      const Map& _map;
161
162      MapLookUpConverter(const Map& map)
163        : _map(map) {}
164
165      Value operator()(const std::string& str) {
166        typename Map::const_iterator it = _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 Value,
177              typename Map1 = std::map<std::string, Value>,
178              typename Map2 = std::map<std::string, Value> >
179    struct DoubleMapLookUpConverter {
180      const Map1& _map1;
181      const Map2& _map2;
182
183      DoubleMapLookUpConverter(const Map1& map1, const Map2& map2)
184        : _map1(map1), _map2(map2) {}
185
186      Value operator()(const std::string& str) {
187        typename Map1::const_iterator it1 = _map1.find(str);
188        typename Map2::const_iterator it2 = _map2.find(str);
189        if (it1 == _map1.end()) {
190          if (it2 == _map2.end()) {
191            std::ostringstream msg;
192            msg << "Item not found: " << str;
193            throw FormatError(msg.str());
194          } else {
195            return it2->second;
196          }
197        } else {
198          if (it2 == _map2.end()) {
199            return it1->second;
200          } else {
201            std::ostringstream msg;
202            msg << "Item is ambigous: " << str;
203            throw FormatError(msg.str());
204          }
205        }
206      }
207    };
208
209    template <typename GR>
210    struct GraphArcLookUpConverter {
211      const GR& _graph;
212      const std::map<std::string, typename GR::Edge>& _map;
213
214      GraphArcLookUpConverter(const GR& graph,
215                              const std::map<std::string,
216                                             typename GR::Edge>& map)
217        : _graph(graph), _map(map) {}
218
219      typename GR::Arc operator()(const std::string& str) {
220        if (str.empty() || (str[0] != '+' && str[0] != '-')) {
221          throw FormatError("Item must start with '+' or '-'");
222        }
223        typename std::map<std::string, typename GR::Edge>
224          ::const_iterator it = _map.find(str.substr(1));
225        if (it == _map.end()) {
226          throw FormatError("Item not found");
227        }
228        return _graph.direct(it->second, str[0] == '+');
229      }
230    };
231
232    inline bool isWhiteSpace(char c) {
233      return c == ' ' || c == '\t' || c == '\v' ||
234        c == '\n' || c == '\r' || c == '\f';
235    }
236
237    inline bool isOct(char c) {
238      return '0' <= c && c <='7';
239    }
240
241    inline int valueOct(char c) {
242      LEMON_ASSERT(isOct(c), "The character is not octal.");
243      return c - '0';
244    }
245
246    inline bool isHex(char c) {
247      return ('0' <= c && c <= '9') ||
248        ('a' <= c && c <= 'z') ||
249        ('A' <= c && c <= 'Z');
250    }
251
252    inline int valueHex(char c) {
253      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
254      if ('0' <= c && c <= '9') return c - '0';
255      if ('a' <= c && c <= 'z') return c - 'a' + 10;
256      return c - 'A' + 10;
257    }
258
259    inline bool isIdentifierFirstChar(char c) {
260      return ('a' <= c && c <= 'z') ||
261        ('A' <= c && c <= 'Z') || c == '_';
262    }
263
264    inline bool isIdentifierChar(char c) {
265      return isIdentifierFirstChar(c) ||
266        ('0' <= c && c <= '9');
267    }
268
269    inline char readEscape(std::istream& is) {
270      char c;
271      if (!is.get(c))
272        throw FormatError("Escape format error");
273
274      switch (c) {
275      case '\\':
276        return '\\';
277      case '\"':
278        return '\"';
279      case '\'':
280        return '\'';
281      case '\?':
282        return '\?';
283      case 'a':
284        return '\a';
285      case 'b':
286        return '\b';
287      case 'f':
288        return '\f';
289      case 'n':
290        return '\n';
291      case 'r':
292        return '\r';
293      case 't':
294        return '\t';
295      case 'v':
296        return '\v';
297      case 'x':
298        {
299          int code;
300          if (!is.get(c) || !isHex(c))
301            throw FormatError("Escape format error");
302          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
303          else code = code * 16 + valueHex(c);
304          return code;
305        }
306      default:
307        {
308          int code;
309          if (!isOct(c))
310            throw FormatError("Escape format error");
311          else if (code = valueOct(c), !is.get(c) || !isOct(c))
312            is.putback(c);
313          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
314            is.putback(c);
315          else code = code * 8 + valueOct(c);
316          return code;
317        }
318      }
319    }
320
321    inline std::istream& readToken(std::istream& is, std::string& str) {
322      std::ostringstream os;
323
324      char c;
325      is >> std::ws;
326
327      if (!is.get(c))
328        return is;
329
330      if (c == '\"') {
331        while (is.get(c) && c != '\"') {
332          if (c == '\\')
333            c = readEscape(is);
334          os << c;
335        }
336        if (!is)
337          throw FormatError("Quoted format error");
338      } else {
339        is.putback(c);
340        while (is.get(c) && !isWhiteSpace(c)) {
341          if (c == '\\')
342            c = readEscape(is);
343          os << c;
344        }
345        if (!is) {
346          is.clear();
347        } else {
348          is.putback(c);
349        }
350      }
351      str = os.str();
352      return is;
353    }
354
355    class Section {
356    public:
357      virtual ~Section() {}
358      virtual void process(std::istream& is, int& line_num) = 0;
359    };
360
361    template <typename Functor>
362    class LineSection : public Section {
363    private:
364
365      Functor _functor;
366
367    public:
368
369      LineSection(const Functor& functor) : _functor(functor) {}
370      virtual ~LineSection() {}
371
372      virtual void process(std::istream& is, int& 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 (c == '#') {
379            getline(is, line);
380            ++line_num;
381          } else if (!isWhiteSpace(c)) {
382            is.putback(c);
383            getline(is, line);
384            _functor(line);
385            ++line_num;
386          }
387        }
388        if (is) is.putback(c);
389        else if (is.eof()) is.clear();
390      }
391    };
392
393    template <typename Functor>
394    class StreamSection : public Section {
395    private:
396
397      Functor _functor;
398
399    public:
400
401      StreamSection(const Functor& functor) : _functor(functor) {}
402      virtual ~StreamSection() {}
403
404      virtual void process(std::istream& is, int& line_num) {
405        _functor(is, line_num);
406        char c;
407        std::string line;
408        while (is.get(c) && c != '@') {
409          if (c == '\n') {
410            ++line_num;
411          } else if (!isWhiteSpace(c)) {
412            getline(is, line);
413            ++line_num;
414          }
415        }
416        if (is) is.putback(c);
417        else if (is.eof()) is.clear();
418      }
419    };
420
421  }
422
423  template <typename DGR>
424  class DigraphReader;
425
426  template <typename TDGR>
427  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is = std::cin);
428  template <typename TDGR>
429  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn);
430  template <typename TDGR>
431  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
432
433  /// \ingroup lemon_io
434  ///
435  /// \brief \ref lgf-format "LGF" reader for directed graphs
436  ///
437  /// This utility reads an \ref lgf-format "LGF" file.
438  ///
439  /// The reading method does a batch processing. The user creates a
440  /// reader object, then various reading rules can be added to the
441  /// reader, and eventually the reading is executed with the \c run()
442  /// member function. A map reading rule can be added to the reader
443  /// with the \c nodeMap() or \c arcMap() members. An optional
444  /// converter parameter can also be added as a standard functor
445  /// converting from \c std::string to the value type of the map. If it
446  /// is set, it will determine how the tokens in the file should be
447  /// converted to the value type of the map. If the functor is not set,
448  /// then a default conversion will be used. One map can be read into
449  /// multiple map objects at the same time. The \c attribute(), \c
450  /// node() and \c arc() functions are used to add attribute reading
451  /// rules.
452  ///
453  ///\code
454  /// DigraphReader<DGR>(digraph, std::cin).
455  ///   nodeMap("coordinates", coord_map).
456  ///   arcMap("capacity", cap_map).
457  ///   node("source", src).
458  ///   node("target", trg).
459  ///   attribute("caption", caption).
460  ///   run();
461  ///\endcode
462  ///
463  /// By default, the reader uses the first section in the file of the
464  /// proper type. If a section has an optional name, then it can be
465  /// selected for reading by giving an optional name parameter to the
466  /// \c nodes(), \c arcs() or \c attributes() functions.
467  ///
468  /// The \c useNodes() and \c useArcs() functions are used to tell the reader
469  /// that the nodes or arcs should not be constructed (added to the
470  /// graph) during the reading, but instead the label map of the items
471  /// are given as a parameter of these functions. An
472  /// application of these functions is multipass reading, which is
473  /// important if two \c \@arcs sections must be read from the
474  /// file. In this case the first phase would read the node set and one
475  /// of the arc sets, while the second phase would read the second arc
476  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
477  /// The previously read label node map should be passed to the \c
478  /// useNodes() functions. Another application of multipass reading when
479  /// paths are given as a node map or an arc map.
480  /// It is impossible to read this in
481  /// a single pass, because the arcs are not constructed when the node
482  /// maps are read.
483  template <typename DGR>
484  class DigraphReader {
485  public:
486
487    typedef DGR Digraph;
488
489  private:
490
491    TEMPLATE_DIGRAPH_TYPEDEFS(DGR);
492
493    std::istream* _is;
494    bool local_is;
495    std::string _filename;
496
497    DGR& _digraph;
498
499    std::string _nodes_caption;
500    std::string _arcs_caption;
501    std::string _attributes_caption;
502
503    typedef std::map<std::string, Node> NodeIndex;
504    NodeIndex _node_index;
505    typedef std::map<std::string, Arc> ArcIndex;
506    ArcIndex _arc_index;
507
508    typedef std::vector<std::pair<std::string,
509      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
510    NodeMaps _node_maps;
511
512    typedef std::vector<std::pair<std::string,
513      _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
514    ArcMaps _arc_maps;
515
516    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
517      Attributes;
518    Attributes _attributes;
519
520    bool _use_nodes;
521    bool _use_arcs;
522
523    bool _skip_nodes;
524    bool _skip_arcs;
525
526    int line_num;
527    std::istringstream line;
528
529  public:
530
531    /// \brief Constructor
532    ///
533    /// Construct a directed graph reader, which reads from the given
534    /// input stream.
535    DigraphReader(DGR& digraph, std::istream& is = std::cin)
536      : _is(&is), local_is(false), _digraph(digraph),
537        _use_nodes(false), _use_arcs(false),
538        _skip_nodes(false), _skip_arcs(false) {}
539
540    /// \brief Constructor
541    ///
542    /// Construct a directed graph reader, which reads from the given
543    /// file.
544    DigraphReader(DGR& digraph, const std::string& fn)
545      : _is(new std::ifstream(fn.c_str())), local_is(true),
546        _filename(fn), _digraph(digraph),
547        _use_nodes(false), _use_arcs(false),
548        _skip_nodes(false), _skip_arcs(false) {
549      if (!(*_is)) {
550        delete _is;
551        throw IoError("Cannot open file", fn);
552      }
553    }
554
555    /// \brief Constructor
556    ///
557    /// Construct a directed graph reader, which reads from the given
558    /// file.
559    DigraphReader(DGR& digraph, const char* fn)
560      : _is(new std::ifstream(fn)), local_is(true),
561        _filename(fn), _digraph(digraph),
562        _use_nodes(false), _use_arcs(false),
563        _skip_nodes(false), _skip_arcs(false) {
564      if (!(*_is)) {
565        delete _is;
566        throw IoError("Cannot open file", fn);
567      }
568    }
569
570    /// \brief Destructor
571    ~DigraphReader() {
572      for (typename NodeMaps::iterator it = _node_maps.begin();
573           it != _node_maps.end(); ++it) {
574        delete it->second;
575      }
576
577      for (typename ArcMaps::iterator it = _arc_maps.begin();
578           it != _arc_maps.end(); ++it) {
579        delete it->second;
580      }
581
582      for (typename Attributes::iterator it = _attributes.begin();
583           it != _attributes.end(); ++it) {
584        delete it->second;
585      }
586
587      if (local_is) {
588        delete _is;
589      }
590
591    }
592
593  private:
594
595    template <typename TDGR>
596    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is);
597    template <typename TDGR>
598    friend DigraphReader<TDGR> digraphReader(TDGR& digraph,
599                                             const std::string& fn);
600    template <typename TDGR>
601    friend DigraphReader<TDGR> digraphReader(TDGR& digraph, const char *fn);
602
603    DigraphReader(DigraphReader& other)
604      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
605        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs),
606        _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
607
608      other._is = 0;
609      other.local_is = false;
610
611      _node_index.swap(other._node_index);
612      _arc_index.swap(other._arc_index);
613
614      _node_maps.swap(other._node_maps);
615      _arc_maps.swap(other._arc_maps);
616      _attributes.swap(other._attributes);
617
618      _nodes_caption = other._nodes_caption;
619      _arcs_caption = other._arcs_caption;
620      _attributes_caption = other._attributes_caption;
621
622    }
623
624    DigraphReader& operator=(const DigraphReader&);
625
626  public:
627
628    /// \name Reading Rules
629    /// @{
630
631    /// \brief Node map reading rule
632    ///
633    /// Add a node map reading rule to the reader.
634    template <typename Map>
635    DigraphReader& nodeMap(const std::string& caption, Map& map) {
636      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
637      _reader_bits::MapStorageBase<Node>* storage =
638        new _reader_bits::MapStorage<Node, Map>(map);
639      _node_maps.push_back(std::make_pair(caption, storage));
640      return *this;
641    }
642
643    /// \brief Node map reading rule
644    ///
645    /// Add a node map reading rule with specialized converter to the
646    /// reader.
647    template <typename Map, typename Converter>
648    DigraphReader& nodeMap(const std::string& caption, Map& map,
649                           const Converter& converter = Converter()) {
650      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
651      _reader_bits::MapStorageBase<Node>* storage =
652        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
653      _node_maps.push_back(std::make_pair(caption, storage));
654      return *this;
655    }
656
657    /// \brief Arc map reading rule
658    ///
659    /// Add an arc map reading rule to the reader.
660    template <typename Map>
661    DigraphReader& arcMap(const std::string& caption, Map& map) {
662      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
663      _reader_bits::MapStorageBase<Arc>* storage =
664        new _reader_bits::MapStorage<Arc, Map>(map);
665      _arc_maps.push_back(std::make_pair(caption, storage));
666      return *this;
667    }
668
669    /// \brief Arc map reading rule
670    ///
671    /// Add an arc map reading rule with specialized converter to the
672    /// reader.
673    template <typename Map, typename Converter>
674    DigraphReader& arcMap(const std::string& caption, Map& map,
675                          const Converter& converter = Converter()) {
676      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
677      _reader_bits::MapStorageBase<Arc>* storage =
678        new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
679      _arc_maps.push_back(std::make_pair(caption, storage));
680      return *this;
681    }
682
683    /// \brief Attribute reading rule
684    ///
685    /// Add an attribute reading rule to the reader.
686    template <typename Value>
687    DigraphReader& attribute(const std::string& caption, Value& value) {
688      _reader_bits::ValueStorageBase* storage =
689        new _reader_bits::ValueStorage<Value>(value);
690      _attributes.insert(std::make_pair(caption, storage));
691      return *this;
692    }
693
694    /// \brief Attribute reading rule
695    ///
696    /// Add an attribute reading rule with specialized converter to the
697    /// reader.
698    template <typename Value, typename Converter>
699    DigraphReader& attribute(const std::string& caption, Value& value,
700                             const Converter& converter = Converter()) {
701      _reader_bits::ValueStorageBase* storage =
702        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
703      _attributes.insert(std::make_pair(caption, storage));
704      return *this;
705    }
706
707    /// \brief Node reading rule
708    ///
709    /// Add a node reading rule to reader.
710    DigraphReader& node(const std::string& caption, Node& node) {
711      typedef _reader_bits::MapLookUpConverter<Node> Converter;
712      Converter converter(_node_index);
713      _reader_bits::ValueStorageBase* storage =
714        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
715      _attributes.insert(std::make_pair(caption, storage));
716      return *this;
717    }
718
719    /// \brief Arc reading rule
720    ///
721    /// Add an arc reading rule to reader.
722    DigraphReader& arc(const std::string& caption, Arc& arc) {
723      typedef _reader_bits::MapLookUpConverter<Arc> Converter;
724      Converter converter(_arc_index);
725      _reader_bits::ValueStorageBase* storage =
726        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
727      _attributes.insert(std::make_pair(caption, storage));
728      return *this;
729    }
730
731    /// @}
732
733    /// \name Select Section by Name
734    /// @{
735
736    /// \brief Set \c \@nodes section to be read
737    ///
738    /// Set \c \@nodes section to be read
739    DigraphReader& nodes(const std::string& caption) {
740      _nodes_caption = caption;
741      return *this;
742    }
743
744    /// \brief Set \c \@arcs section to be read
745    ///
746    /// Set \c \@arcs section to be read
747    DigraphReader& arcs(const std::string& caption) {
748      _arcs_caption = caption;
749      return *this;
750    }
751
752    /// \brief Set \c \@attributes section to be read
753    ///
754    /// Set \c \@attributes section to be read
755    DigraphReader& attributes(const std::string& caption) {
756      _attributes_caption = caption;
757      return *this;
758    }
759
760    /// @}
761
762    /// \name Using Previously Constructed Node or Arc Set
763    /// @{
764
765    /// \brief Use previously constructed node set
766    ///
767    /// Use previously constructed node set, and specify the node
768    /// label map.
769    template <typename Map>
770    DigraphReader& useNodes(const Map& map) {
771      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
772      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
773      _use_nodes = true;
774      _writer_bits::DefaultConverter<typename Map::Value> converter;
775      for (NodeIt n(_digraph); n != INVALID; ++n) {
776        _node_index.insert(std::make_pair(converter(map[n]), n));
777      }
778      return *this;
779    }
780
781    /// \brief Use previously constructed node set
782    ///
783    /// Use previously constructed node set, and specify the node
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& useNodes(const Map& map,
788                            const Converter& converter = Converter()) {
789      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
790      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
791      _use_nodes = true;
792      for (NodeIt n(_digraph); n != INVALID; ++n) {
793        _node_index.insert(std::make_pair(converter(map[n]), n));
794      }
795      return *this;
796    }
797
798    /// \brief Use previously constructed arc set
799    ///
800    /// Use previously constructed arc set, and specify the arc
801    /// label map.
802    template <typename Map>
803    DigraphReader& useArcs(const Map& map) {
804      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
805      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
806      _use_arcs = true;
807      _writer_bits::DefaultConverter<typename Map::Value> converter;
808      for (ArcIt a(_digraph); a != INVALID; ++a) {
809        _arc_index.insert(std::make_pair(converter(map[a]), a));
810      }
811      return *this;
812    }
813
814    /// \brief Use previously constructed arc set
815    ///
816    /// Use previously constructed arc set, and specify the arc
817    /// label map and a functor which converts the label map values to
818    /// \c std::string.
819    template <typename Map, typename Converter>
820    DigraphReader& useArcs(const Map& map,
821                           const Converter& converter = Converter()) {
822      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
823      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
824      _use_arcs = true;
825      for (ArcIt a(_digraph); a != INVALID; ++a) {
826        _arc_index.insert(std::make_pair(converter(map[a]), a));
827      }
828      return *this;
829    }
830
831    /// \brief Skips the reading of node section
832    ///
833    /// Omit the reading of the node section. This implies that each node
834    /// map reading rule will be abandoned, and the nodes of the graph
835    /// will not be constructed, which usually cause that the arc set
836    /// could not be read due to lack of node name resolving.
837    /// Therefore \c skipArcs() function should also be used, or
838    /// \c useNodes() should be used to specify the label of the nodes.
839    DigraphReader& skipNodes() {
840      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
841      _skip_nodes = true;
842      return *this;
843    }
844
845    /// \brief Skips the reading of arc section
846    ///
847    /// Omit the reading of the arc section. This implies that each arc
848    /// map reading rule will be abandoned, and the arcs of the graph
849    /// will not be constructed.
850    DigraphReader& skipArcs() {
851      LEMON_ASSERT(!_skip_arcs, "Skip arcs already set");
852      _skip_arcs = true;
853      return *this;
854    }
855
856    /// @}
857
858  private:
859
860    bool readLine() {
861      std::string str;
862      while(++line_num, std::getline(*_is, str)) {
863        line.clear(); line.str(str);
864        char c;
865        if (line >> std::ws >> c && c != '#') {
866          line.putback(c);
867          return true;
868        }
869      }
870      return false;
871    }
872
873    bool readSuccess() {
874      return static_cast<bool>(*_is);
875    }
876
877    void skipSection() {
878      char c;
879      while (readSuccess() && line >> c && c != '@') {
880        readLine();
881      }
882      if (readSuccess()) {
883        line.putback(c);
884      }
885    }
886
887    void readNodes() {
888
889      std::vector<int> map_index(_node_maps.size());
890      int map_num, label_index;
891
892      char c;
893      if (!readLine() || !(line >> c) || c == '@') {
894        if (readSuccess() && line) line.putback(c);
895        if (!_node_maps.empty())
896          throw FormatError("Cannot find map names");
897        return;
898      }
899      line.putback(c);
900
901      {
902        std::map<std::string, int> maps;
903
904        std::string map;
905        int index = 0;
906        while (_reader_bits::readToken(line, map)) {
907          if (maps.find(map) != maps.end()) {
908            std::ostringstream msg;
909            msg << "Multiple occurence of node map: " << map;
910            throw FormatError(msg.str());
911          }
912          maps.insert(std::make_pair(map, index));
913          ++index;
914        }
915
916        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
917          std::map<std::string, int>::iterator jt =
918            maps.find(_node_maps[i].first);
919          if (jt == maps.end()) {
920            std::ostringstream msg;
921            msg << "Map not found: " << _node_maps[i].first;
922            throw FormatError(msg.str());
923          }
924          map_index[i] = jt->second;
925        }
926
927        {
928          std::map<std::string, int>::iterator jt = maps.find("label");
929          if (jt != maps.end()) {
930            label_index = jt->second;
931          } else {
932            label_index = -1;
933          }
934        }
935        map_num = maps.size();
936      }
937
938      while (readLine() && line >> c && c != '@') {
939        line.putback(c);
940
941        std::vector<std::string> tokens(map_num);
942        for (int i = 0; i < map_num; ++i) {
943          if (!_reader_bits::readToken(line, tokens[i])) {
944            std::ostringstream msg;
945            msg << "Column not found (" << i + 1 << ")";
946            throw FormatError(msg.str());
947          }
948        }
949        if (line >> std::ws >> c)
950          throw FormatError("Extra character at the end of line");
951
952        Node n;
953        if (!_use_nodes) {
954          n = _digraph.addNode();
955          if (label_index != -1)
956            _node_index.insert(std::make_pair(tokens[label_index], n));
957        } else {
958          if (label_index == -1)
959            throw FormatError("Label map not found");
960          typename std::map<std::string, Node>::iterator it =
961            _node_index.find(tokens[label_index]);
962          if (it == _node_index.end()) {
963            std::ostringstream msg;
964            msg << "Node with label not found: " << tokens[label_index];
965            throw FormatError(msg.str());
966          }
967          n = it->second;
968        }
969
970        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
971          _node_maps[i].second->set(n, tokens[map_index[i]]);
972        }
973
974      }
975      if (readSuccess()) {
976        line.putback(c);
977      }
978    }
979
980    void readArcs() {
981
982      std::vector<int> map_index(_arc_maps.size());
983      int map_num, label_index;
984
985      char c;
986      if (!readLine() || !(line >> c) || c == '@') {
987        if (readSuccess() && line) line.putback(c);
988        if (!_arc_maps.empty())
989          throw FormatError("Cannot find map names");
990        return;
991      }
992      line.putback(c);
993
994      {
995        std::map<std::string, int> maps;
996
997        std::string map;
998        int index = 0;
999        while (_reader_bits::readToken(line, map)) {
1000          if(map == "-") {
1001              if(index!=0)
1002                throw FormatError("'-' is not allowed as a map name");
1003              else if (line >> std::ws >> c)
1004                throw FormatError("Extra character at the end of line");
1005              else break;
1006            }
1007          if (maps.find(map) != maps.end()) {
1008            std::ostringstream msg;
1009            msg << "Multiple occurence of arc map: " << map;
1010            throw FormatError(msg.str());
1011          }
1012          maps.insert(std::make_pair(map, index));
1013          ++index;
1014        }
1015
1016        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1017          std::map<std::string, int>::iterator jt =
1018            maps.find(_arc_maps[i].first);
1019          if (jt == maps.end()) {
1020            std::ostringstream msg;
1021            msg << "Map not found: " << _arc_maps[i].first;
1022            throw FormatError(msg.str());
1023          }
1024          map_index[i] = jt->second;
1025        }
1026
1027        {
1028          std::map<std::string, int>::iterator jt = maps.find("label");
1029          if (jt != maps.end()) {
1030            label_index = jt->second;
1031          } else {
1032            label_index = -1;
1033          }
1034        }
1035        map_num = maps.size();
1036      }
1037
1038      while (readLine() && line >> c && c != '@') {
1039        line.putback(c);
1040
1041        std::string source_token;
1042        std::string target_token;
1043
1044        if (!_reader_bits::readToken(line, source_token))
1045          throw FormatError("Source not found");
1046
1047        if (!_reader_bits::readToken(line, target_token))
1048          throw FormatError("Target not found");
1049
1050        std::vector<std::string> tokens(map_num);
1051        for (int i = 0; i < map_num; ++i) {
1052          if (!_reader_bits::readToken(line, tokens[i])) {
1053            std::ostringstream msg;
1054            msg << "Column not found (" << i + 1 << ")";
1055            throw FormatError(msg.str());
1056          }
1057        }
1058        if (line >> std::ws >> c)
1059          throw FormatError("Extra character at the end of line");
1060
1061        Arc a;
1062        if (!_use_arcs) {
1063
1064          typename NodeIndex::iterator it;
1065
1066          it = _node_index.find(source_token);
1067          if (it == _node_index.end()) {
1068            std::ostringstream msg;
1069            msg << "Item not found: " << source_token;
1070            throw FormatError(msg.str());
1071          }
1072          Node source = it->second;
1073
1074          it = _node_index.find(target_token);
1075          if (it == _node_index.end()) {
1076            std::ostringstream msg;
1077            msg << "Item not found: " << target_token;
1078            throw FormatError(msg.str());
1079          }
1080          Node target = it->second;
1081
1082          a = _digraph.addArc(source, target);
1083          if (label_index != -1)
1084            _arc_index.insert(std::make_pair(tokens[label_index], a));
1085        } else {
1086          if (label_index == -1)
1087            throw FormatError("Label map not found");
1088          typename std::map<std::string, Arc>::iterator it =
1089            _arc_index.find(tokens[label_index]);
1090          if (it == _arc_index.end()) {
1091            std::ostringstream msg;
1092            msg << "Arc with label not found: " << tokens[label_index];
1093            throw FormatError(msg.str());
1094          }
1095          a = it->second;
1096        }
1097
1098        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1099          _arc_maps[i].second->set(a, tokens[map_index[i]]);
1100        }
1101
1102      }
1103      if (readSuccess()) {
1104        line.putback(c);
1105      }
1106    }
1107
1108    void readAttributes() {
1109
1110      std::set<std::string> read_attr;
1111
1112      char c;
1113      while (readLine() && line >> c && c != '@') {
1114        line.putback(c);
1115
1116        std::string attr, token;
1117        if (!_reader_bits::readToken(line, attr))
1118          throw FormatError("Attribute name not found");
1119        if (!_reader_bits::readToken(line, token))
1120          throw FormatError("Attribute value not found");
1121        if (line >> c)
1122          throw FormatError("Extra character at the end of line");
1123
1124        {
1125          std::set<std::string>::iterator it = read_attr.find(attr);
1126          if (it != read_attr.end()) {
1127            std::ostringstream msg;
1128            msg << "Multiple occurence of attribute: " << attr;
1129            throw FormatError(msg.str());
1130          }
1131          read_attr.insert(attr);
1132        }
1133
1134        {
1135          typename Attributes::iterator it = _attributes.lower_bound(attr);
1136          while (it != _attributes.end() && it->first == attr) {
1137            it->second->set(token);
1138            ++it;
1139          }
1140        }
1141
1142      }
1143      if (readSuccess()) {
1144        line.putback(c);
1145      }
1146      for (typename Attributes::iterator it = _attributes.begin();
1147           it != _attributes.end(); ++it) {
1148        if (read_attr.find(it->first) == read_attr.end()) {
1149          std::ostringstream msg;
1150          msg << "Attribute not found: " << it->first;
1151          throw FormatError(msg.str());
1152        }
1153      }
1154    }
1155
1156  public:
1157
1158    /// \name Execution of the Reader
1159    /// @{
1160
1161    /// \brief Start the batch processing
1162    ///
1163    /// This function starts the batch processing
1164    void run() {
1165      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1166
1167      bool nodes_done = _skip_nodes;
1168      bool arcs_done = _skip_arcs;
1169      bool attributes_done = false;
1170
1171      line_num = 0;
1172      readLine();
1173      skipSection();
1174
1175      while (readSuccess()) {
1176        try {
1177          char c;
1178          std::string section, caption;
1179          line >> c;
1180          _reader_bits::readToken(line, section);
1181          _reader_bits::readToken(line, caption);
1182
1183          if (line >> c)
1184            throw FormatError("Extra character at the end of line");
1185
1186          if (section == "nodes" && !nodes_done) {
1187            if (_nodes_caption.empty() || _nodes_caption == caption) {
1188              readNodes();
1189              nodes_done = true;
1190            }
1191          } else if ((section == "arcs" || section == "edges") &&
1192                     !arcs_done) {
1193            if (_arcs_caption.empty() || _arcs_caption == caption) {
1194              readArcs();
1195              arcs_done = true;
1196            }
1197          } else if (section == "attributes" && !attributes_done) {
1198            if (_attributes_caption.empty() || _attributes_caption == caption) {
1199              readAttributes();
1200              attributes_done = true;
1201            }
1202          } else {
1203            readLine();
1204            skipSection();
1205          }
1206        } catch (FormatError& error) {
1207          error.line(line_num);
1208          error.file(_filename);
1209          throw;
1210        }
1211      }
1212
1213      if (!nodes_done) {
1214        throw FormatError("Section @nodes not found");
1215      }
1216
1217      if (!arcs_done) {
1218        throw FormatError("Section @arcs not found");
1219      }
1220
1221      if (!attributes_done && !_attributes.empty()) {
1222        throw FormatError("Section @attributes not found");
1223      }
1224
1225    }
1226
1227    /// @}
1228
1229  };
1230
1231  /// \ingroup lemon_io
1232  ///
1233  /// \brief Return a \ref lemon::DigraphReader "DigraphReader" class
1234  ///
1235  /// This function just returns a \ref lemon::DigraphReader
1236  /// "DigraphReader" class.
1237  ///
1238  /// With this function a digraph can be read from an
1239  /// \ref lgf-format "LGF" file or input stream with several maps and
1240  /// attributes. For example, there is network flow problem on a
1241  /// digraph, i.e. a digraph with a \e capacity map on the arcs and
1242  /// \e source and \e target nodes. This digraph can be read with the
1243  /// following code:
1244  ///
1245  ///\code
1246  ///ListDigraph digraph;
1247  ///ListDigraph::ArcMap<int> cm(digraph);
1248  ///ListDigraph::Node src, trg;
1249  ///digraphReader(digraph, std::cin).
1250  ///  arcMap("capacity", cap).
1251  ///  node("source", src).
1252  ///  node("target", trg).
1253  ///  run();
1254  ///\endcode
1255  ///
1256  /// For a complete documentation, please see the
1257  /// \ref lemon::DigraphReader "DigraphReader"
1258  /// class documentation.
1259  /// \warning Don't forget to put the \ref lemon::DigraphReader::run() "run()"
1260  /// to the end of the parameter list.
1261  /// \relates DigraphReader
1262  /// \sa digraphReader(TDGR& digraph, const std::string& fn)
1263  /// \sa digraphReader(TDGR& digraph, const char* fn)
1264  template <typename TDGR>
1265  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) {
1266    DigraphReader<TDGR> tmp(digraph, is);
1267    return tmp;
1268  }
1269
1270  /// \brief Return a \ref DigraphReader class
1271  ///
1272  /// This function just returns a \ref DigraphReader class.
1273  /// \relates DigraphReader
1274  /// \sa digraphReader(TDGR& digraph, std::istream& is)
1275  template <typename TDGR>
1276  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) {
1277    DigraphReader<TDGR> tmp(digraph, fn);
1278    return tmp;
1279  }
1280
1281  /// \brief Return a \ref DigraphReader class
1282  ///
1283  /// This function just returns a \ref DigraphReader class.
1284  /// \relates DigraphReader
1285  /// \sa digraphReader(TDGR& digraph, std::istream& is)
1286  template <typename TDGR>
1287  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
1288    DigraphReader<TDGR> tmp(digraph, fn);
1289    return tmp;
1290  }
1291
1292  template <typename GR>
1293  class GraphReader;
1294
1295  template <typename TGR>
1296  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
1297  template <typename TGR>
1298  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
1299  template <typename TGR>
1300  GraphReader<TGR> graphReader(TGR& graph, const char *fn);
1301
1302  /// \ingroup lemon_io
1303  ///
1304  /// \brief \ref lgf-format "LGF" reader for undirected graphs
1305  ///
1306  /// This utility reads an \ref lgf-format "LGF" file.
1307  ///
1308  /// It can be used almost the same way as \c DigraphReader.
1309  /// The only difference is that this class can handle edges and
1310  /// edge maps as well as arcs and arc maps.
1311  ///
1312  /// The columns in the \c \@edges (or \c \@arcs) section are the
1313  /// edge maps. However, if there are two maps with the same name
1314  /// prefixed with \c '+' and \c '-', then these can be read into an
1315  /// arc map.  Similarly, an attribute can be read into an arc, if
1316  /// it's value is an edge label prefixed with \c '+' or \c '-'.
1317  template <typename GR>
1318  class GraphReader {
1319  public:
1320
1321    typedef GR Graph;
1322
1323  private:
1324
1325    TEMPLATE_GRAPH_TYPEDEFS(GR);
1326
1327    std::istream* _is;
1328    bool local_is;
1329    std::string _filename;
1330
1331    GR& _graph;
1332
1333    std::string _nodes_caption;
1334    std::string _edges_caption;
1335    std::string _attributes_caption;
1336
1337    typedef std::map<std::string, Node> NodeIndex;
1338    NodeIndex _node_index;
1339    typedef std::map<std::string, Edge> EdgeIndex;
1340    EdgeIndex _edge_index;
1341
1342    typedef std::vector<std::pair<std::string,
1343      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
1344    NodeMaps _node_maps;
1345
1346    typedef std::vector<std::pair<std::string,
1347      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1348    EdgeMaps _edge_maps;
1349
1350    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1351      Attributes;
1352    Attributes _attributes;
1353
1354    bool _use_nodes;
1355    bool _use_edges;
1356
1357    bool _skip_nodes;
1358    bool _skip_edges;
1359
1360    int line_num;
1361    std::istringstream line;
1362
1363  public:
1364
1365    /// \brief Constructor
1366    ///
1367    /// Construct an undirected graph reader, which reads from the given
1368    /// input stream.
1369    GraphReader(GR& graph, std::istream& is = std::cin)
1370      : _is(&is), local_is(false), _graph(graph),
1371        _use_nodes(false), _use_edges(false),
1372        _skip_nodes(false), _skip_edges(false) {}
1373
1374    /// \brief Constructor
1375    ///
1376    /// Construct an undirected graph reader, which reads from the given
1377    /// file.
1378    GraphReader(GR& graph, const std::string& fn)
1379      : _is(new std::ifstream(fn.c_str())), local_is(true),
1380        _filename(fn), _graph(graph),
1381        _use_nodes(false), _use_edges(false),
1382        _skip_nodes(false), _skip_edges(false) {
1383      if (!(*_is)) {
1384        delete _is;
1385        throw IoError("Cannot open file", fn);
1386      }
1387    }
1388
1389    /// \brief Constructor
1390    ///
1391    /// Construct an undirected graph reader, which reads from the given
1392    /// file.
1393    GraphReader(GR& graph, const char* fn)
1394      : _is(new std::ifstream(fn)), local_is(true),
1395        _filename(fn), _graph(graph),
1396        _use_nodes(false), _use_edges(false),
1397        _skip_nodes(false), _skip_edges(false) {
1398      if (!(*_is)) {
1399        delete _is;
1400        throw IoError("Cannot open file", fn);
1401      }
1402    }
1403
1404    /// \brief Destructor
1405    ~GraphReader() {
1406      for (typename NodeMaps::iterator it = _node_maps.begin();
1407           it != _node_maps.end(); ++it) {
1408        delete it->second;
1409      }
1410
1411      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1412           it != _edge_maps.end(); ++it) {
1413        delete it->second;
1414      }
1415
1416      for (typename Attributes::iterator it = _attributes.begin();
1417           it != _attributes.end(); ++it) {
1418        delete it->second;
1419      }
1420
1421      if (local_is) {
1422        delete _is;
1423      }
1424
1425    }
1426
1427  private:
1428    template <typename TGR>
1429    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
1430    template <typename TGR>
1431    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
1432    template <typename TGR>
1433    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
1434
1435    GraphReader(GraphReader& other)
1436      : _is(other._is), local_is(other.local_is), _graph(other._graph),
1437        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1438        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1439
1440      other._is = 0;
1441      other.local_is = false;
1442
1443      _node_index.swap(other._node_index);
1444      _edge_index.swap(other._edge_index);
1445
1446      _node_maps.swap(other._node_maps);
1447      _edge_maps.swap(other._edge_maps);
1448      _attributes.swap(other._attributes);
1449
1450      _nodes_caption = other._nodes_caption;
1451      _edges_caption = other._edges_caption;
1452      _attributes_caption = other._attributes_caption;
1453
1454    }
1455
1456    GraphReader& operator=(const GraphReader&);
1457
1458  public:
1459
1460    /// \name Reading Rules
1461    /// @{
1462
1463    /// \brief Node map reading rule
1464    ///
1465    /// Add a node map reading rule to the reader.
1466    template <typename Map>
1467    GraphReader& nodeMap(const std::string& caption, Map& map) {
1468      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1469      _reader_bits::MapStorageBase<Node>* storage =
1470        new _reader_bits::MapStorage<Node, Map>(map);
1471      _node_maps.push_back(std::make_pair(caption, storage));
1472      return *this;
1473    }
1474
1475    /// \brief Node map reading rule
1476    ///
1477    /// Add a node map reading rule with specialized converter to the
1478    /// reader.
1479    template <typename Map, typename Converter>
1480    GraphReader& nodeMap(const std::string& caption, Map& map,
1481                           const Converter& converter = Converter()) {
1482      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1483      _reader_bits::MapStorageBase<Node>* storage =
1484        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1485      _node_maps.push_back(std::make_pair(caption, storage));
1486      return *this;
1487    }
1488
1489    /// \brief Edge map reading rule
1490    ///
1491    /// Add an edge map reading rule to the reader.
1492    template <typename Map>
1493    GraphReader& edgeMap(const std::string& caption, Map& map) {
1494      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1495      _reader_bits::MapStorageBase<Edge>* storage =
1496        new _reader_bits::MapStorage<Edge, Map>(map);
1497      _edge_maps.push_back(std::make_pair(caption, storage));
1498      return *this;
1499    }
1500
1501    /// \brief Edge map reading rule
1502    ///
1503    /// Add an edge map reading rule with specialized converter to the
1504    /// reader.
1505    template <typename Map, typename Converter>
1506    GraphReader& edgeMap(const std::string& caption, Map& map,
1507                          const Converter& converter = Converter()) {
1508      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1509      _reader_bits::MapStorageBase<Edge>* storage =
1510        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1511      _edge_maps.push_back(std::make_pair(caption, storage));
1512      return *this;
1513    }
1514
1515    /// \brief Arc map reading rule
1516    ///
1517    /// Add an arc map reading rule to the reader.
1518    template <typename Map>
1519    GraphReader& arcMap(const std::string& caption, Map& map) {
1520      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1521      _reader_bits::MapStorageBase<Edge>* forward_storage =
1522        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1523      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1524      _reader_bits::MapStorageBase<Edge>* backward_storage =
1525        new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
1526      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1527      return *this;
1528    }
1529
1530    /// \brief Arc map reading rule
1531    ///
1532    /// Add an arc map reading rule with specialized converter to the
1533    /// reader.
1534    template <typename Map, typename Converter>
1535    GraphReader& arcMap(const std::string& caption, Map& map,
1536                          const Converter& converter = Converter()) {
1537      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1538      _reader_bits::MapStorageBase<Edge>* forward_storage =
1539        new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter>
1540        (_graph, map, converter);
1541      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1542      _reader_bits::MapStorageBase<Edge>* backward_storage =
1543        new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter>
1544        (_graph, map, converter);
1545      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1546      return *this;
1547    }
1548
1549    /// \brief Attribute reading rule
1550    ///
1551    /// Add an attribute reading rule to the reader.
1552    template <typename Value>
1553    GraphReader& attribute(const std::string& caption, Value& value) {
1554      _reader_bits::ValueStorageBase* storage =
1555        new _reader_bits::ValueStorage<Value>(value);
1556      _attributes.insert(std::make_pair(caption, storage));
1557      return *this;
1558    }
1559
1560    /// \brief Attribute reading rule
1561    ///
1562    /// Add an attribute reading rule with specialized converter to the
1563    /// reader.
1564    template <typename Value, typename Converter>
1565    GraphReader& attribute(const std::string& caption, Value& value,
1566                             const Converter& converter = Converter()) {
1567      _reader_bits::ValueStorageBase* storage =
1568        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1569      _attributes.insert(std::make_pair(caption, storage));
1570      return *this;
1571    }
1572
1573    /// \brief Node reading rule
1574    ///
1575    /// Add a node reading rule to reader.
1576    GraphReader& node(const std::string& caption, Node& node) {
1577      typedef _reader_bits::MapLookUpConverter<Node> Converter;
1578      Converter converter(_node_index);
1579      _reader_bits::ValueStorageBase* storage =
1580        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1581      _attributes.insert(std::make_pair(caption, storage));
1582      return *this;
1583    }
1584
1585    /// \brief Edge reading rule
1586    ///
1587    /// Add an edge reading rule to reader.
1588    GraphReader& edge(const std::string& caption, Edge& edge) {
1589      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1590      Converter converter(_edge_index);
1591      _reader_bits::ValueStorageBase* storage =
1592        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1593      _attributes.insert(std::make_pair(caption, storage));
1594      return *this;
1595    }
1596
1597    /// \brief Arc reading rule
1598    ///
1599    /// Add an arc reading rule to reader.
1600    GraphReader& arc(const std::string& caption, Arc& arc) {
1601      typedef _reader_bits::GraphArcLookUpConverter<GR> Converter;
1602      Converter converter(_graph, _edge_index);
1603      _reader_bits::ValueStorageBase* storage =
1604        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1605      _attributes.insert(std::make_pair(caption, storage));
1606      return *this;
1607    }
1608
1609    /// @}
1610
1611    /// \name Select Section by Name
1612    /// @{
1613
1614    /// \brief Set \c \@nodes section to be read
1615    ///
1616    /// Set \c \@nodes section to be read.
1617    GraphReader& nodes(const std::string& caption) {
1618      _nodes_caption = caption;
1619      return *this;
1620    }
1621
1622    /// \brief Set \c \@edges section to be read
1623    ///
1624    /// Set \c \@edges section to be read.
1625    GraphReader& edges(const std::string& caption) {
1626      _edges_caption = caption;
1627      return *this;
1628    }
1629
1630    /// \brief Set \c \@attributes section to be read
1631    ///
1632    /// Set \c \@attributes section to be read.
1633    GraphReader& attributes(const std::string& caption) {
1634      _attributes_caption = caption;
1635      return *this;
1636    }
1637
1638    /// @}
1639
1640    /// \name Using Previously Constructed Node or Edge Set
1641    /// @{
1642
1643    /// \brief Use previously constructed node set
1644    ///
1645    /// Use previously constructed node set, and specify the node
1646    /// label map.
1647    template <typename Map>
1648    GraphReader& useNodes(const Map& map) {
1649      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1650      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1651      _use_nodes = true;
1652      _writer_bits::DefaultConverter<typename Map::Value> converter;
1653      for (NodeIt n(_graph); n != INVALID; ++n) {
1654        _node_index.insert(std::make_pair(converter(map[n]), n));
1655      }
1656      return *this;
1657    }
1658
1659    /// \brief Use previously constructed node set
1660    ///
1661    /// Use previously constructed node set, and specify the node
1662    /// label map and a functor which converts the label map values to
1663    /// \c std::string.
1664    template <typename Map, typename Converter>
1665    GraphReader& useNodes(const Map& map,
1666                            const Converter& converter = Converter()) {
1667      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1668      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1669      _use_nodes = true;
1670      for (NodeIt n(_graph); n != INVALID; ++n) {
1671        _node_index.insert(std::make_pair(converter(map[n]), n));
1672      }
1673      return *this;
1674    }
1675
1676    /// \brief Use previously constructed edge set
1677    ///
1678    /// Use previously constructed edge set, and specify the edge
1679    /// label map.
1680    template <typename Map>
1681    GraphReader& useEdges(const Map& map) {
1682      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1683      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1684      _use_edges = true;
1685      _writer_bits::DefaultConverter<typename Map::Value> converter;
1686      for (EdgeIt a(_graph); a != INVALID; ++a) {
1687        _edge_index.insert(std::make_pair(converter(map[a]), a));
1688      }
1689      return *this;
1690    }
1691
1692    /// \brief Use previously constructed edge set
1693    ///
1694    /// Use previously constructed edge set, and specify the edge
1695    /// label map and a functor which converts the label map values to
1696    /// \c std::string.
1697    template <typename Map, typename Converter>
1698    GraphReader& useEdges(const Map& map,
1699                            const Converter& converter = Converter()) {
1700      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1701      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1702      _use_edges = true;
1703      for (EdgeIt a(_graph); a != INVALID; ++a) {
1704        _edge_index.insert(std::make_pair(converter(map[a]), a));
1705      }
1706      return *this;
1707    }
1708
1709    /// \brief Skip the reading of node section
1710    ///
1711    /// Omit the reading of the node section. This implies that each node
1712    /// map reading rule will be abandoned, and the nodes of the graph
1713    /// will not be constructed, which usually cause that the edge set
1714    /// could not be read due to lack of node name
1715    /// could not be read due to lack of node name resolving.
1716    /// Therefore \c skipEdges() function should also be used, or
1717    /// \c useNodes() should be used to specify the label of the nodes.
1718    GraphReader& skipNodes() {
1719      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1720      _skip_nodes = true;
1721      return *this;
1722    }
1723
1724    /// \brief Skip the reading of edge section
1725    ///
1726    /// Omit the reading of the edge section. This implies that each edge
1727    /// map reading rule will be abandoned, and the edges of the graph
1728    /// will not be constructed.
1729    GraphReader& skipEdges() {
1730      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1731      _skip_edges = true;
1732      return *this;
1733    }
1734
1735    /// @}
1736
1737  private:
1738
1739    bool readLine() {
1740      std::string str;
1741      while(++line_num, std::getline(*_is, str)) {
1742        line.clear(); line.str(str);
1743        char c;
1744        if (line >> std::ws >> c && c != '#') {
1745          line.putback(c);
1746          return true;
1747        }
1748      }
1749      return false;
1750    }
1751
1752    bool readSuccess() {
1753      return static_cast<bool>(*_is);
1754    }
1755
1756    void skipSection() {
1757      char c;
1758      while (readSuccess() && line >> c && c != '@') {
1759        readLine();
1760      }
1761      if (readSuccess()) {
1762        line.putback(c);
1763      }
1764    }
1765
1766    void readNodes() {
1767
1768      std::vector<int> map_index(_node_maps.size());
1769      int map_num, label_index;
1770
1771      char c;
1772      if (!readLine() || !(line >> c) || c == '@') {
1773        if (readSuccess() && line) line.putback(c);
1774        if (!_node_maps.empty())
1775          throw FormatError("Cannot find map names");
1776        return;
1777      }
1778      line.putback(c);
1779
1780      {
1781        std::map<std::string, int> maps;
1782
1783        std::string map;
1784        int index = 0;
1785        while (_reader_bits::readToken(line, map)) {
1786          if (maps.find(map) != maps.end()) {
1787            std::ostringstream msg;
1788            msg << "Multiple occurence of node map: " << map;
1789            throw FormatError(msg.str());
1790          }
1791          maps.insert(std::make_pair(map, index));
1792          ++index;
1793        }
1794
1795        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1796          std::map<std::string, int>::iterator jt =
1797            maps.find(_node_maps[i].first);
1798          if (jt == maps.end()) {
1799            std::ostringstream msg;
1800            msg << "Map not found: " << _node_maps[i].first;
1801            throw FormatError(msg.str());
1802          }
1803          map_index[i] = jt->second;
1804        }
1805
1806        {
1807          std::map<std::string, int>::iterator jt = maps.find("label");
1808          if (jt != maps.end()) {
1809            label_index = jt->second;
1810          } else {
1811            label_index = -1;
1812          }
1813        }
1814        map_num = maps.size();
1815      }
1816
1817      while (readLine() && line >> c && c != '@') {
1818        line.putback(c);
1819
1820        std::vector<std::string> tokens(map_num);
1821        for (int i = 0; i < map_num; ++i) {
1822          if (!_reader_bits::readToken(line, tokens[i])) {
1823            std::ostringstream msg;
1824            msg << "Column not found (" << i + 1 << ")";
1825            throw FormatError(msg.str());
1826          }
1827        }
1828        if (line >> std::ws >> c)
1829          throw FormatError("Extra character at the end of line");
1830
1831        Node n;
1832        if (!_use_nodes) {
1833          n = _graph.addNode();
1834          if (label_index != -1)
1835            _node_index.insert(std::make_pair(tokens[label_index], n));
1836        } else {
1837          if (label_index == -1)
1838            throw FormatError("Label map not found");
1839          typename std::map<std::string, Node>::iterator it =
1840            _node_index.find(tokens[label_index]);
1841          if (it == _node_index.end()) {
1842            std::ostringstream msg;
1843            msg << "Node with label not found: " << tokens[label_index];
1844            throw FormatError(msg.str());
1845          }
1846          n = it->second;
1847        }
1848
1849        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1850          _node_maps[i].second->set(n, tokens[map_index[i]]);
1851        }
1852
1853      }
1854      if (readSuccess()) {
1855        line.putback(c);
1856      }
1857    }
1858
1859    void readEdges() {
1860
1861      std::vector<int> map_index(_edge_maps.size());
1862      int map_num, label_index;
1863
1864      char c;
1865      if (!readLine() || !(line >> c) || c == '@') {
1866        if (readSuccess() && line) line.putback(c);
1867        if (!_edge_maps.empty())
1868          throw FormatError("Cannot find map names");
1869        return;
1870      }
1871      line.putback(c);
1872
1873      {
1874        std::map<std::string, int> maps;
1875
1876        std::string map;
1877        int index = 0;
1878        while (_reader_bits::readToken(line, map)) {
1879          if(map == "-") {
1880              if(index!=0)
1881                throw FormatError("'-' is not allowed as a map name");
1882              else if (line >> std::ws >> c)
1883                throw FormatError("Extra character at the end of line");
1884              else break;
1885            }
1886          if (maps.find(map) != maps.end()) {
1887            std::ostringstream msg;
1888            msg << "Multiple occurence of edge map: " << map;
1889            throw FormatError(msg.str());
1890          }
1891          maps.insert(std::make_pair(map, index));
1892          ++index;
1893        }
1894
1895        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1896          std::map<std::string, int>::iterator jt =
1897            maps.find(_edge_maps[i].first);
1898          if (jt == maps.end()) {
1899            std::ostringstream msg;
1900            msg << "Map not found: " << _edge_maps[i].first;
1901            throw FormatError(msg.str());
1902          }
1903          map_index[i] = jt->second;
1904        }
1905
1906        {
1907          std::map<std::string, int>::iterator jt = maps.find("label");
1908          if (jt != maps.end()) {
1909            label_index = jt->second;
1910          } else {
1911            label_index = -1;
1912          }
1913        }
1914        map_num = maps.size();
1915      }
1916
1917      while (readLine() && line >> c && c != '@') {
1918        line.putback(c);
1919
1920        std::string source_token;
1921        std::string target_token;
1922
1923        if (!_reader_bits::readToken(line, source_token))
1924          throw FormatError("Node u not found");
1925
1926        if (!_reader_bits::readToken(line, target_token))
1927          throw FormatError("Node v not found");
1928
1929        std::vector<std::string> tokens(map_num);
1930        for (int i = 0; i < map_num; ++i) {
1931          if (!_reader_bits::readToken(line, tokens[i])) {
1932            std::ostringstream msg;
1933            msg << "Column not found (" << i + 1 << ")";
1934            throw FormatError(msg.str());
1935          }
1936        }
1937        if (line >> std::ws >> c)
1938          throw FormatError("Extra character at the end of line");
1939
1940        Edge e;
1941        if (!_use_edges) {
1942
1943          typename NodeIndex::iterator it;
1944
1945          it = _node_index.find(source_token);
1946          if (it == _node_index.end()) {
1947            std::ostringstream msg;
1948            msg << "Item not found: " << source_token;
1949            throw FormatError(msg.str());
1950          }
1951          Node source = it->second;
1952
1953          it = _node_index.find(target_token);
1954          if (it == _node_index.end()) {
1955            std::ostringstream msg;
1956            msg << "Item not found: " << target_token;
1957            throw FormatError(msg.str());
1958          }
1959          Node target = it->second;
1960
1961          e = _graph.addEdge(source, target);
1962          if (label_index != -1)
1963            _edge_index.insert(std::make_pair(tokens[label_index], e));
1964        } else {
1965          if (label_index == -1)
1966            throw FormatError("Label map not found");
1967          typename std::map<std::string, Edge>::iterator it =
1968            _edge_index.find(tokens[label_index]);
1969          if (it == _edge_index.end()) {
1970            std::ostringstream msg;
1971            msg << "Edge with label not found: " << tokens[label_index];
1972            throw FormatError(msg.str());
1973          }
1974          e = it->second;
1975        }
1976
1977        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1978          _edge_maps[i].second->set(e, tokens[map_index[i]]);
1979        }
1980
1981      }
1982      if (readSuccess()) {
1983        line.putback(c);
1984      }
1985    }
1986
1987    void readAttributes() {
1988
1989      std::set<std::string> read_attr;
1990
1991      char c;
1992      while (readLine() && line >> c && c != '@') {
1993        line.putback(c);
1994
1995        std::string attr, token;
1996        if (!_reader_bits::readToken(line, attr))
1997          throw FormatError("Attribute name not found");
1998        if (!_reader_bits::readToken(line, token))
1999          throw FormatError("Attribute value not found");
2000        if (line >> c)
2001          throw FormatError("Extra character at the end of line");
2002
2003        {
2004          std::set<std::string>::iterator it = read_attr.find(attr);
2005          if (it != read_attr.end()) {
2006            std::ostringstream msg;
2007            msg << "Multiple occurence of attribute: " << attr;
2008            throw FormatError(msg.str());
2009          }
2010          read_attr.insert(attr);
2011        }
2012
2013        {
2014          typename Attributes::iterator it = _attributes.lower_bound(attr);
2015          while (it != _attributes.end() && it->first == attr) {
2016            it->second->set(token);
2017            ++it;
2018          }
2019        }
2020
2021      }
2022      if (readSuccess()) {
2023        line.putback(c);
2024      }
2025      for (typename Attributes::iterator it = _attributes.begin();
2026           it != _attributes.end(); ++it) {
2027        if (read_attr.find(it->first) == read_attr.end()) {
2028          std::ostringstream msg;
2029          msg << "Attribute not found: " << it->first;
2030          throw FormatError(msg.str());
2031        }
2032      }
2033    }
2034
2035  public:
2036
2037    /// \name Execution of the Reader
2038    /// @{
2039
2040    /// \brief Start the batch processing
2041    ///
2042    /// This function starts the batch processing
2043    void run() {
2044
2045      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2046
2047      bool nodes_done = _skip_nodes;
2048      bool edges_done = _skip_edges;
2049      bool attributes_done = false;
2050
2051      line_num = 0;
2052      readLine();
2053      skipSection();
2054
2055      while (readSuccess()) {
2056        try {
2057          char c;
2058          std::string section, caption;
2059          line >> c;
2060          _reader_bits::readToken(line, section);
2061          _reader_bits::readToken(line, caption);
2062
2063          if (line >> c)
2064            throw FormatError("Extra character at the end of line");
2065
2066          if (section == "nodes" && !nodes_done) {
2067            if (_nodes_caption.empty() || _nodes_caption == caption) {
2068              readNodes();
2069              nodes_done = true;
2070            }
2071          } else if ((section == "edges" || section == "arcs") &&
2072                     !edges_done) {
2073            if (_edges_caption.empty() || _edges_caption == caption) {
2074              readEdges();
2075              edges_done = true;
2076            }
2077          } else if (section == "attributes" && !attributes_done) {
2078            if (_attributes_caption.empty() || _attributes_caption == caption) {
2079              readAttributes();
2080              attributes_done = true;
2081            }
2082          } else {
2083            readLine();
2084            skipSection();
2085          }
2086        } catch (FormatError& error) {
2087          error.line(line_num);
2088          error.file(_filename);
2089          throw;
2090        }
2091      }
2092
2093      if (!nodes_done) {
2094        throw FormatError("Section @nodes not found");
2095      }
2096
2097      if (!edges_done) {
2098        throw FormatError("Section @edges not found");
2099      }
2100
2101      if (!attributes_done && !_attributes.empty()) {
2102        throw FormatError("Section @attributes not found");
2103      }
2104
2105    }
2106
2107    /// @}
2108
2109  };
2110
2111  /// \ingroup lemon_io
2112  ///
2113  /// \brief Return a \ref lemon::GraphReader "GraphReader" class
2114  ///
2115  /// This function just returns a \ref lemon::GraphReader "GraphReader" class.
2116  ///
2117  /// With this function a graph can be read from an
2118  /// \ref lgf-format "LGF" file or input stream with several maps and
2119  /// attributes. For example, there is weighted matching problem on a
2120  /// graph, i.e. a graph with a \e weight map on the edges. This
2121  /// graph can be read with the following code:
2122  ///
2123  ///\code
2124  ///ListGraph graph;
2125  ///ListGraph::EdgeMap<int> weight(graph);
2126  ///graphReader(graph, std::cin).
2127  ///  edgeMap("weight", weight).
2128  ///  run();
2129  ///\endcode
2130  ///
2131  /// For a complete documentation, please see the
2132  /// \ref lemon::GraphReader "GraphReader"
2133  /// class documentation.
2134  /// \warning Don't forget to put the \ref lemon::GraphReader::run() "run()"
2135  /// to the end of the parameter list.
2136  /// \relates GraphReader
2137  /// \sa graphReader(TGR& graph, const std::string& fn)
2138  /// \sa graphReader(TGR& graph, const char* fn)
2139  template <typename TGR>
2140  GraphReader<TGR> graphReader(TGR& graph, std::istream& is) {
2141    GraphReader<TGR> tmp(graph, is);
2142    return tmp;
2143  }
2144
2145  /// \brief Return a \ref GraphReader class
2146  ///
2147  /// This function just returns a \ref GraphReader class.
2148  /// \relates GraphReader
2149  /// \sa graphReader(TGR& graph, std::istream& is)
2150  template <typename TGR>
2151  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) {
2152    GraphReader<TGR> tmp(graph, fn);
2153    return tmp;
2154  }
2155
2156  /// \brief Return a \ref GraphReader class
2157  ///
2158  /// This function just returns a \ref GraphReader class.
2159  /// \relates GraphReader
2160  /// \sa graphReader(TGR& graph, std::istream& is)
2161  template <typename TGR>
2162  GraphReader<TGR> graphReader(TGR& graph, const char* fn) {
2163    GraphReader<TGR> tmp(graph, fn);
2164    return tmp;
2165  }
2166
2167  template <typename BGR>
2168  class BpGraphReader;
2169
2170  template <typename TBGR>
2171  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin);
2172  template <typename TBGR>
2173  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn);
2174  template <typename TBGR>
2175  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
2176
2177  /// \ingroup lemon_io
2178  ///
2179  /// \brief \ref lgf-format "LGF" reader for bipartite graphs
2180  ///
2181  /// This utility reads an \ref lgf-format "LGF" file.
2182  ///
2183  /// It can be used almost the same way as \c GraphReader, but it
2184  /// reads the red and blue nodes from separate sections, and these
2185  /// sections can contain different set of maps.
2186  ///
2187  /// The red and blue node maps are read from the corresponding
2188  /// sections. If a map is defined with the same name in both of
2189  /// these sections, then it can be read as a node map.
2190  template <typename BGR>
2191  class BpGraphReader {
2192  public:
2193
2194    typedef BGR Graph;
2195
2196  private:
2197
2198    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
2199
2200    std::istream* _is;
2201    bool local_is;
2202    std::string _filename;
2203
2204    BGR& _graph;
2205
2206    std::string _nodes_caption;
2207    std::string _edges_caption;
2208    std::string _attributes_caption;
2209
2210    typedef std::map<std::string, RedNode> RedNodeIndex;
2211    RedNodeIndex _red_node_index;
2212    typedef std::map<std::string, BlueNode> BlueNodeIndex;
2213    BlueNodeIndex _blue_node_index;
2214    typedef std::map<std::string, Edge> EdgeIndex;
2215    EdgeIndex _edge_index;
2216
2217    typedef std::vector<std::pair<std::string,
2218      _reader_bits::MapStorageBase<RedNode>*> > RedNodeMaps;
2219    RedNodeMaps _red_node_maps;
2220    typedef std::vector<std::pair<std::string,
2221      _reader_bits::MapStorageBase<BlueNode>*> > BlueNodeMaps;
2222    BlueNodeMaps _blue_node_maps;
2223
2224    typedef std::vector<std::pair<std::string,
2225      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
2226    EdgeMaps _edge_maps;
2227
2228    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
2229      Attributes;
2230    Attributes _attributes;
2231
2232    bool _use_nodes;
2233    bool _use_edges;
2234
2235    bool _skip_nodes;
2236    bool _skip_edges;
2237
2238    int line_num;
2239    std::istringstream line;
2240
2241  public:
2242
2243    /// \brief Constructor
2244    ///
2245    /// Construct an undirected graph reader, which reads from the given
2246    /// input stream.
2247    BpGraphReader(BGR& graph, std::istream& is = std::cin)
2248      : _is(&is), local_is(false), _graph(graph),
2249        _use_nodes(false), _use_edges(false),
2250        _skip_nodes(false), _skip_edges(false) {}
2251
2252    /// \brief Constructor
2253    ///
2254    /// Construct an undirected graph reader, which reads from the given
2255    /// file.
2256    BpGraphReader(BGR& graph, const std::string& fn)
2257      : _is(new std::ifstream(fn.c_str())), local_is(true),
2258        _filename(fn), _graph(graph),
2259        _use_nodes(false), _use_edges(false),
2260        _skip_nodes(false), _skip_edges(false) {
2261      if (!(*_is)) {
2262        delete _is;
2263        throw IoError("Cannot open file", fn);
2264      }
2265    }
2266
2267    /// \brief Constructor
2268    ///
2269    /// Construct an undirected graph reader, which reads from the given
2270    /// file.
2271    BpGraphReader(BGR& graph, const char* fn)
2272      : _is(new std::ifstream(fn)), local_is(true),
2273        _filename(fn), _graph(graph),
2274        _use_nodes(false), _use_edges(false),
2275        _skip_nodes(false), _skip_edges(false) {
2276      if (!(*_is)) {
2277        delete _is;
2278        throw IoError("Cannot open file", fn);
2279      }
2280    }
2281
2282    /// \brief Destructor
2283    ~BpGraphReader() {
2284      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2285           it != _red_node_maps.end(); ++it) {
2286        delete it->second;
2287      }
2288
2289      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2290           it != _blue_node_maps.end(); ++it) {
2291        delete it->second;
2292      }
2293
2294      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2295           it != _edge_maps.end(); ++it) {
2296        delete it->second;
2297      }
2298
2299      for (typename Attributes::iterator it = _attributes.begin();
2300           it != _attributes.end(); ++it) {
2301        delete it->second;
2302      }
2303
2304      if (local_is) {
2305        delete _is;
2306      }
2307
2308    }
2309
2310  private:
2311    template <typename TBGR>
2312    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is);
2313    template <typename TBGR>
2314    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph,
2315                                             const std::string& fn);
2316    template <typename TBGR>
2317    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
2318
2319    BpGraphReader(BpGraphReader& other)
2320      : _is(other._is), local_is(other.local_is), _graph(other._graph),
2321        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
2322        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
2323
2324      other._is = 0;
2325      other.local_is = false;
2326
2327      _red_node_index.swap(other._red_node_index);
2328      _blue_node_index.swap(other._blue_node_index);
2329      _edge_index.swap(other._edge_index);
2330
2331      _red_node_maps.swap(other._red_node_maps);
2332      _blue_node_maps.swap(other._blue_node_maps);
2333      _edge_maps.swap(other._edge_maps);
2334      _attributes.swap(other._attributes);
2335
2336      _nodes_caption = other._nodes_caption;
2337      _edges_caption = other._edges_caption;
2338      _attributes_caption = other._attributes_caption;
2339
2340    }
2341
2342    BpGraphReader& operator=(const BpGraphReader&);
2343
2344  public:
2345
2346    /// \name Reading Rules
2347    /// @{
2348
2349    /// \brief Node map reading rule
2350    ///
2351    /// Add a node map reading rule to the reader.
2352    template <typename Map>
2353    BpGraphReader& nodeMap(const std::string& caption, Map& map) {
2354      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2355      _reader_bits::MapStorageBase<RedNode>* red_storage =
2356        new _reader_bits::MapStorage<RedNode, Map>(map);
2357      _red_node_maps.push_back(std::make_pair(caption, red_storage));
2358      _reader_bits::MapStorageBase<BlueNode>* blue_storage =
2359        new _reader_bits::MapStorage<BlueNode, Map>(map);
2360      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
2361      return *this;
2362    }
2363
2364    /// \brief Node map reading rule
2365    ///
2366    /// Add a node map reading rule with specialized converter to the
2367    /// reader.
2368    template <typename Map, typename Converter>
2369    BpGraphReader& nodeMap(const std::string& caption, Map& map,
2370                           const Converter& converter = Converter()) {
2371      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2372      _reader_bits::MapStorageBase<RedNode>* red_storage =
2373        new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter);
2374      _red_node_maps.push_back(std::make_pair(caption, red_storage));
2375      _reader_bits::MapStorageBase<BlueNode>* blue_storage =
2376        new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
2377      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
2378      return *this;
2379    }
2380
2381    /// Add a red node map reading rule to the reader.
2382    template <typename Map>
2383    BpGraphReader& redNodeMap(const std::string& caption, Map& map) {
2384      checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>();
2385      _reader_bits::MapStorageBase<RedNode>* storage =
2386        new _reader_bits::MapStorage<RedNode, Map>(map);
2387      _red_node_maps.push_back(std::make_pair(caption, storage));
2388      return *this;
2389    }
2390
2391    /// \brief Red node map reading rule
2392    ///
2393    /// Add a red node map node reading rule with specialized converter to
2394    /// the reader.
2395    template <typename Map, typename Converter>
2396    BpGraphReader& redNodeMap(const std::string& caption, Map& map,
2397                              const Converter& converter = Converter()) {
2398      checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>();
2399      _reader_bits::MapStorageBase<RedNode>* storage =
2400        new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter);
2401      _red_node_maps.push_back(std::make_pair(caption, storage));
2402      return *this;
2403    }
2404
2405    /// Add a blue node map reading rule to the reader.
2406    template <typename Map>
2407    BpGraphReader& blueNodeMap(const std::string& caption, Map& map) {
2408      checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>();
2409      _reader_bits::MapStorageBase<BlueNode>* storage =
2410        new _reader_bits::MapStorage<BlueNode, Map>(map);
2411      _blue_node_maps.push_back(std::make_pair(caption, storage));
2412      return *this;
2413    }
2414
2415    /// \brief Blue node map reading rule
2416    ///
2417    /// Add a blue node map reading rule with specialized converter to
2418    /// the reader.
2419    template <typename Map, typename Converter>
2420    BpGraphReader& blueNodeMap(const std::string& caption, Map& map,
2421                               const Converter& converter = Converter()) {
2422      checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>();
2423      _reader_bits::MapStorageBase<BlueNode>* storage =
2424        new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
2425      _blue_node_maps.push_back(std::make_pair(caption, storage));
2426      return *this;
2427    }
2428
2429    /// \brief Edge map reading rule
2430    ///
2431    /// Add an edge map reading rule to the reader.
2432    template <typename Map>
2433    BpGraphReader& edgeMap(const std::string& caption, Map& map) {
2434      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
2435      _reader_bits::MapStorageBase<Edge>* storage =
2436        new _reader_bits::MapStorage<Edge, Map>(map);
2437      _edge_maps.push_back(std::make_pair(caption, storage));
2438      return *this;
2439    }
2440
2441    /// \brief Edge map reading rule
2442    ///
2443    /// Add an edge map reading rule with specialized converter to the
2444    /// reader.
2445    template <typename Map, typename Converter>
2446    BpGraphReader& edgeMap(const std::string& caption, Map& map,
2447                          const Converter& converter = Converter()) {
2448      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
2449      _reader_bits::MapStorageBase<Edge>* storage =
2450        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
2451      _edge_maps.push_back(std::make_pair(caption, storage));
2452      return *this;
2453    }
2454
2455    /// \brief Arc map reading rule
2456    ///
2457    /// Add an arc map reading rule to the reader.
2458    template <typename Map>
2459    BpGraphReader& arcMap(const std::string& caption, Map& map) {
2460      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
2461      _reader_bits::MapStorageBase<Edge>* forward_storage =
2462        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
2463      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
2464      _reader_bits::MapStorageBase<Edge>* backward_storage =
2465        new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
2466      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
2467      return *this;
2468    }
2469
2470    /// \brief Arc map reading rule
2471    ///
2472    /// Add an arc map reading rule with specialized converter to the
2473    /// reader.
2474    template <typename Map, typename Converter>
2475    BpGraphReader& arcMap(const std::string& caption, Map& map,
2476                          const Converter& converter = Converter()) {
2477      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
2478      _reader_bits::MapStorageBase<Edge>* forward_storage =
2479        new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter>
2480        (_graph, map, converter);
2481      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
2482      _reader_bits::MapStorageBase<Edge>* backward_storage =
2483        new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter>
2484        (_graph, map, converter);
2485      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
2486      return *this;
2487    }
2488
2489    /// \brief Attribute reading rule
2490    ///
2491    /// Add an attribute reading rule to the reader.
2492    template <typename Value>
2493    BpGraphReader& attribute(const std::string& caption, Value& value) {
2494      _reader_bits::ValueStorageBase* storage =
2495        new _reader_bits::ValueStorage<Value>(value);
2496      _attributes.insert(std::make_pair(caption, storage));
2497      return *this;
2498    }
2499
2500    /// \brief Attribute reading rule
2501    ///
2502    /// Add an attribute reading rule with specialized converter to the
2503    /// reader.
2504    template <typename Value, typename Converter>
2505    BpGraphReader& attribute(const std::string& caption, Value& value,
2506                             const Converter& converter = Converter()) {
2507      _reader_bits::ValueStorageBase* storage =
2508        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
2509      _attributes.insert(std::make_pair(caption, storage));
2510      return *this;
2511    }
2512
2513    /// \brief Node reading rule
2514    ///
2515    /// Add a node reading rule to reader.
2516    BpGraphReader& node(const std::string& caption, Node& node) {
2517      typedef _reader_bits::DoubleMapLookUpConverter<
2518        Node, RedNodeIndex, BlueNodeIndex> Converter;
2519      Converter converter(_red_node_index, _blue_node_index);
2520      _reader_bits::ValueStorageBase* storage =
2521        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
2522      _attributes.insert(std::make_pair(caption, storage));
2523      return *this;
2524    }
2525
2526    /// \brief Red node reading rule
2527    ///
2528    /// Add a red node reading rule to reader.
2529    BpGraphReader& redNode(const std::string& caption, RedNode& node) {
2530      typedef _reader_bits::MapLookUpConverter<RedNode> Converter;
2531      Converter converter(_red_node_index);
2532      _reader_bits::ValueStorageBase* storage =
2533        new _reader_bits::ValueStorage<RedNode, Converter>(node, converter);
2534      _attributes.insert(std::make_pair(caption, storage));
2535      return *this;
2536    }
2537
2538    /// \brief Blue node reading rule
2539    ///
2540    /// Add a blue node reading rule to reader.
2541    BpGraphReader& blueNode(const std::string& caption, BlueNode& node) {
2542      typedef _reader_bits::MapLookUpConverter<BlueNode> Converter;
2543      Converter converter(_blue_node_index);
2544      _reader_bits::ValueStorageBase* storage =
2545        new _reader_bits::ValueStorage<BlueNode, Converter>(node, converter);
2546      _attributes.insert(std::make_pair(caption, storage));
2547      return *this;
2548    }
2549
2550    /// \brief Edge reading rule
2551    ///
2552    /// Add an edge reading rule to reader.
2553    BpGraphReader& edge(const std::string& caption, Edge& edge) {
2554      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
2555      Converter converter(_edge_index);
2556      _reader_bits::ValueStorageBase* storage =
2557        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
2558      _attributes.insert(std::make_pair(caption, storage));
2559      return *this;
2560    }
2561
2562    /// \brief Arc reading rule
2563    ///
2564    /// Add an arc reading rule to reader.
2565    BpGraphReader& arc(const std::string& caption, Arc& arc) {
2566      typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter;
2567      Converter converter(_graph, _edge_index);
2568      _reader_bits::ValueStorageBase* storage =
2569        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
2570      _attributes.insert(std::make_pair(caption, storage));
2571      return *this;
2572    }
2573
2574    /// @}
2575
2576    /// \name Select Section by Name
2577    /// @{
2578
2579    /// \brief Set \c \@nodes section to be read
2580    ///
2581    /// Set \c \@nodes section to be read.
2582    BpGraphReader& nodes(const std::string& caption) {
2583      _nodes_caption = caption;
2584      return *this;
2585    }
2586
2587    /// \brief Set \c \@edges section to be read
2588    ///
2589    /// Set \c \@edges section to be read.
2590    BpGraphReader& edges(const std::string& caption) {
2591      _edges_caption = caption;
2592      return *this;
2593    }
2594
2595    /// \brief Set \c \@attributes section to be read
2596    ///
2597    /// Set \c \@attributes section to be read.
2598    BpGraphReader& attributes(const std::string& caption) {
2599      _attributes_caption = caption;
2600      return *this;
2601    }
2602
2603    /// @}
2604
2605    /// \name Using Previously Constructed Node or Edge Set
2606    /// @{
2607
2608    /// \brief Use previously constructed node set
2609    ///
2610    /// Use previously constructed node set, and specify the node
2611    /// label map.
2612    template <typename Map>
2613    BpGraphReader& useNodes(const Map& map) {
2614      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
2615      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
2616      _use_nodes = true;
2617      _writer_bits::DefaultConverter<typename Map::Value> converter;
2618      for (RedNodeIt n(_graph); n != INVALID; ++n) {
2619        _red_node_index.insert(std::make_pair(converter(map[n]), n));
2620      }
2621      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2622        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
2623      }
2624      return *this;
2625    }
2626
2627    /// \brief Use previously constructed node set
2628    ///
2629    /// Use previously constructed node set, and specify the node
2630    /// label map and a functor which converts the label map values to
2631    /// \c std::string.
2632    template <typename Map, typename Converter>
2633    BpGraphReader& useNodes(const Map& map,
2634                            const Converter& converter = Converter()) {
2635      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
2636      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
2637      _use_nodes = true;
2638      for (RedNodeIt n(_graph); n != INVALID; ++n) {
2639        _red_node_index.insert(std::make_pair(converter(map[n]), n));
2640      }
2641      for (BlueNodeIt n(_graph); n != INVALID; ++n) {     
2642        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
2643      }
2644      return *this;
2645    }
2646
2647    /// \brief Use previously constructed edge set
2648    ///
2649    /// Use previously constructed edge set, and specify the edge
2650    /// label map.
2651    template <typename Map>
2652    BpGraphReader& useEdges(const Map& map) {
2653      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
2654      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
2655      _use_edges = true;
2656      _writer_bits::DefaultConverter<typename Map::Value> converter;
2657      for (EdgeIt a(_graph); a != INVALID; ++a) {
2658        _edge_index.insert(std::make_pair(converter(map[a]), a));
2659      }
2660      return *this;
2661    }
2662
2663    /// \brief Use previously constructed edge set
2664    ///
2665    /// Use previously constructed edge set, and specify the edge
2666    /// label map and a functor which converts the label map values to
2667    /// \c std::string.
2668    template <typename Map, typename Converter>
2669    BpGraphReader& useEdges(const Map& map,
2670                            const Converter& converter = Converter()) {
2671      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
2672      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
2673      _use_edges = true;
2674      for (EdgeIt a(_graph); a != INVALID; ++a) {
2675        _edge_index.insert(std::make_pair(converter(map[a]), a));
2676      }
2677      return *this;
2678    }
2679
2680    /// \brief Skip the reading of node section
2681    ///
2682    /// Omit the reading of the node section. This implies that each node
2683    /// map reading rule will be abandoned, and the nodes of the graph
2684    /// will not be constructed, which usually cause that the edge set
2685    /// could not be read due to lack of node name
2686    /// could not be read due to lack of node name resolving.
2687    /// Therefore \c skipEdges() function should also be used, or
2688    /// \c useNodes() should be used to specify the label of the nodes.
2689    BpGraphReader& skipNodes() {
2690      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
2691      _skip_nodes = true;
2692      return *this;
2693    }
2694
2695    /// \brief Skip the reading of edge section
2696    ///
2697    /// Omit the reading of the edge section. This implies that each edge
2698    /// map reading rule will be abandoned, and the edges of the graph
2699    /// will not be constructed.
2700    BpGraphReader& skipEdges() {
2701      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
2702      _skip_edges = true;
2703      return *this;
2704    }
2705
2706    /// @}
2707
2708  private:
2709
2710    bool readLine() {
2711      std::string str;
2712      while(++line_num, std::getline(*_is, str)) {
2713        line.clear(); line.str(str);
2714        char c;
2715        if (line >> std::ws >> c && c != '#') {
2716          line.putback(c);
2717          return true;
2718        }
2719      }
2720      return false;
2721    }
2722
2723    bool readSuccess() {
2724      return static_cast<bool>(*_is);
2725    }
2726
2727    void skipSection() {
2728      char c;
2729      while (readSuccess() && line >> c && c != '@') {
2730        readLine();
2731      }
2732      if (readSuccess()) {
2733        line.putback(c);
2734      }
2735    }
2736
2737    void readRedNodes() {
2738
2739      std::vector<int> map_index(_red_node_maps.size());
2740      int map_num, label_index;
2741
2742      char c;
2743      if (!readLine() || !(line >> c) || c == '@') {
2744        if (readSuccess() && line) line.putback(c);
2745        if (!_red_node_maps.empty())
2746          throw FormatError("Cannot find map names");
2747        return;
2748      }
2749      line.putback(c);
2750
2751      {
2752        std::map<std::string, int> maps;
2753
2754        std::string map;
2755        int index = 0;
2756        while (_reader_bits::readToken(line, map)) {
2757          if (maps.find(map) != maps.end()) {
2758            std::ostringstream msg;
2759            msg << "Multiple occurence of red node map: " << map;
2760            throw FormatError(msg.str());
2761          }
2762          maps.insert(std::make_pair(map, index));
2763          ++index;
2764        }
2765
2766        for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) {
2767          std::map<std::string, int>::iterator jt =
2768            maps.find(_red_node_maps[i].first);
2769          if (jt == maps.end()) {
2770            std::ostringstream msg;
2771            msg << "Map not found: " << _red_node_maps[i].first;
2772            throw FormatError(msg.str());
2773          }
2774          map_index[i] = jt->second;
2775        }
2776
2777        {
2778          std::map<std::string, int>::iterator jt = maps.find("label");
2779          if (jt != maps.end()) {
2780            label_index = jt->second;
2781          } else {
2782            label_index = -1;
2783          }
2784        }
2785        map_num = maps.size();
2786      }
2787
2788      while (readLine() && line >> c && c != '@') {
2789        line.putback(c);
2790
2791        std::vector<std::string> tokens(map_num);
2792        for (int i = 0; i < map_num; ++i) {
2793          if (!_reader_bits::readToken(line, tokens[i])) {
2794            std::ostringstream msg;
2795            msg << "Column not found (" << i + 1 << ")";
2796            throw FormatError(msg.str());
2797          }
2798        }
2799        if (line >> std::ws >> c)
2800          throw FormatError("Extra character at the end of line");
2801
2802        RedNode n;
2803        if (!_use_nodes) {
2804          n = _graph.addRedNode();
2805          if (label_index != -1)
2806            _red_node_index.insert(std::make_pair(tokens[label_index], n));
2807        } else {
2808          if (label_index == -1)
2809            throw FormatError("Label map not found");
2810          typename std::map<std::string, RedNode>::iterator it =
2811            _red_node_index.find(tokens[label_index]);
2812          if (it == _red_node_index.end()) {
2813            std::ostringstream msg;
2814            msg << "Node with label not found: " << tokens[label_index];
2815            throw FormatError(msg.str());
2816          }
2817          n = it->second;
2818        }
2819
2820        for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) {
2821          _red_node_maps[i].second->set(n, tokens[map_index[i]]);
2822        }
2823
2824      }
2825      if (readSuccess()) {
2826        line.putback(c);
2827      }
2828    }
2829
2830    void readBlueNodes() {
2831
2832      std::vector<int> map_index(_blue_node_maps.size());
2833      int map_num, label_index;
2834
2835      char c;
2836      if (!readLine() || !(line >> c) || c == '@') {
2837        if (readSuccess() && line) line.putback(c);
2838        if (!_blue_node_maps.empty())
2839          throw FormatError("Cannot find map names");
2840        return;
2841      }
2842      line.putback(c);
2843
2844      {
2845        std::map<std::string, int> maps;
2846
2847        std::string map;
2848        int index = 0;
2849        while (_reader_bits::readToken(line, map)) {
2850          if (maps.find(map) != maps.end()) {
2851            std::ostringstream msg;
2852            msg << "Multiple occurence of blue node map: " << map;
2853            throw FormatError(msg.str());
2854          }
2855          maps.insert(std::make_pair(map, index));
2856          ++index;
2857        }
2858
2859        for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) {
2860          std::map<std::string, int>::iterator jt =
2861            maps.find(_blue_node_maps[i].first);
2862          if (jt == maps.end()) {
2863            std::ostringstream msg;
2864            msg << "Map not found: " << _blue_node_maps[i].first;
2865            throw FormatError(msg.str());
2866          }
2867          map_index[i] = jt->second;
2868        }
2869
2870        {
2871          std::map<std::string, int>::iterator jt = maps.find("label");
2872          if (jt != maps.end()) {
2873            label_index = jt->second;
2874          } else {
2875            label_index = -1;
2876          }
2877        }
2878        map_num = maps.size();
2879      }
2880
2881      while (readLine() && line >> c && c != '@') {
2882        line.putback(c);
2883
2884        std::vector<std::string> tokens(map_num);
2885        for (int i = 0; i < map_num; ++i) {
2886          if (!_reader_bits::readToken(line, tokens[i])) {
2887            std::ostringstream msg;
2888            msg << "Column not found (" << i + 1 << ")";
2889            throw FormatError(msg.str());
2890          }
2891        }
2892        if (line >> std::ws >> c)
2893          throw FormatError("Extra character at the end of line");
2894
2895        BlueNode n;
2896        if (!_use_nodes) {
2897          n = _graph.addBlueNode();
2898          if (label_index != -1)
2899            _blue_node_index.insert(std::make_pair(tokens[label_index], n));
2900        } else {
2901          if (label_index == -1)
2902            throw FormatError("Label map not found");
2903          typename std::map<std::string, BlueNode>::iterator it =
2904            _blue_node_index.find(tokens[label_index]);
2905          if (it == _blue_node_index.end()) {
2906            std::ostringstream msg;
2907            msg << "Node with label not found: " << tokens[label_index];
2908            throw FormatError(msg.str());
2909          }
2910          n = it->second;
2911        }
2912
2913        for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) {
2914          _blue_node_maps[i].second->set(n, tokens[map_index[i]]);
2915        }
2916
2917      }
2918      if (readSuccess()) {
2919        line.putback(c);
2920      }
2921    }
2922
2923    void readEdges() {
2924
2925      std::vector<int> map_index(_edge_maps.size());
2926      int map_num, label_index;
2927
2928      char c;
2929      if (!readLine() || !(line >> c) || c == '@') {
2930        if (readSuccess() && line) line.putback(c);
2931        if (!_edge_maps.empty())
2932          throw FormatError("Cannot find map names");
2933        return;
2934      }
2935      line.putback(c);
2936
2937      {
2938        std::map<std::string, int> maps;
2939
2940        std::string map;
2941        int index = 0;
2942        while (_reader_bits::readToken(line, map)) {
2943          if (maps.find(map) != maps.end()) {
2944            std::ostringstream msg;
2945            msg << "Multiple occurence of edge map: " << map;
2946            throw FormatError(msg.str());
2947          }
2948          maps.insert(std::make_pair(map, index));
2949          ++index;
2950        }
2951
2952        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
2953          std::map<std::string, int>::iterator jt =
2954            maps.find(_edge_maps[i].first);
2955          if (jt == maps.end()) {
2956            std::ostringstream msg;
2957            msg << "Map not found: " << _edge_maps[i].first;
2958            throw FormatError(msg.str());
2959          }
2960          map_index[i] = jt->second;
2961        }
2962
2963        {
2964          std::map<std::string, int>::iterator jt = maps.find("label");
2965          if (jt != maps.end()) {
2966            label_index = jt->second;
2967          } else {
2968            label_index = -1;
2969          }
2970        }
2971        map_num = maps.size();
2972      }
2973
2974      while (readLine() && line >> c && c != '@') {
2975        line.putback(c);
2976
2977        std::string source_token;
2978        std::string target_token;
2979
2980        if (!_reader_bits::readToken(line, source_token))
2981          throw FormatError("Red node not found");
2982
2983        if (!_reader_bits::readToken(line, target_token))
2984          throw FormatError("Blue node not found");
2985
2986        std::vector<std::string> tokens(map_num);
2987        for (int i = 0; i < map_num; ++i) {
2988          if (!_reader_bits::readToken(line, tokens[i])) {
2989            std::ostringstream msg;
2990            msg << "Column not found (" << i + 1 << ")";
2991            throw FormatError(msg.str());
2992          }
2993        }
2994        if (line >> std::ws >> c)
2995          throw FormatError("Extra character at the end of line");
2996
2997        Edge e;
2998        if (!_use_edges) {
2999          typename RedNodeIndex::iterator rit =
3000            _red_node_index.find(source_token);
3001          if (rit == _red_node_index.end()) {
3002            std::ostringstream msg;
3003            msg << "Item not found: " << source_token;
3004            throw FormatError(msg.str());
3005          }
3006          RedNode source = rit->second;
3007          typename BlueNodeIndex::iterator it =
3008            _blue_node_index.find(target_token);
3009          if (it == _blue_node_index.end()) {
3010            std::ostringstream msg;
3011            msg << "Item not found: " << target_token;
3012            throw FormatError(msg.str());
3013          }
3014          BlueNode target = it->second;
3015
3016          // It is checked that source is red and
3017          // target is blue, so this should be safe:
3018          e = _graph.addEdge(source, target);
3019          if (label_index != -1)
3020            _edge_index.insert(std::make_pair(tokens[label_index], e));
3021        } else {
3022          if (label_index == -1)
3023            throw FormatError("Label map not found");
3024          typename std::map<std::string, Edge>::iterator it =
3025            _edge_index.find(tokens[label_index]);
3026          if (it == _edge_index.end()) {
3027            std::ostringstream msg;
3028            msg << "Edge with label not found: " << tokens[label_index];
3029            throw FormatError(msg.str());
3030          }
3031          e = it->second;
3032        }
3033
3034        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
3035          _edge_maps[i].second->set(e, tokens[map_index[i]]);
3036        }
3037
3038      }
3039      if (readSuccess()) {
3040        line.putback(c);
3041      }
3042    }
3043
3044    void readAttributes() {
3045
3046      std::set<std::string> read_attr;
3047
3048      char c;
3049      while (readLine() && line >> c && c != '@') {
3050        line.putback(c);
3051
3052        std::string attr, token;
3053        if (!_reader_bits::readToken(line, attr))
3054          throw FormatError("Attribute name not found");
3055        if (!_reader_bits::readToken(line, token))
3056          throw FormatError("Attribute value not found");
3057        if (line >> c)
3058          throw FormatError("Extra character at the end of line");
3059
3060        {
3061          std::set<std::string>::iterator it = read_attr.find(attr);
3062          if (it != read_attr.end()) {
3063            std::ostringstream msg;
3064            msg << "Multiple occurence of attribute: " << attr;
3065            throw FormatError(msg.str());
3066          }
3067          read_attr.insert(attr);
3068        }
3069
3070        {
3071          typename Attributes::iterator it = _attributes.lower_bound(attr);
3072          while (it != _attributes.end() && it->first == attr) {
3073            it->second->set(token);
3074            ++it;
3075          }
3076        }
3077
3078      }
3079      if (readSuccess()) {
3080        line.putback(c);
3081      }
3082      for (typename Attributes::iterator it = _attributes.begin();
3083           it != _attributes.end(); ++it) {
3084        if (read_attr.find(it->first) == read_attr.end()) {
3085          std::ostringstream msg;
3086          msg << "Attribute not found: " << it->first;
3087          throw FormatError(msg.str());
3088        }
3089      }
3090    }
3091
3092  public:
3093
3094    /// \name Execution of the Reader
3095    /// @{
3096
3097    /// \brief Start the batch processing
3098    ///
3099    /// This function starts the batch processing
3100    void run() {
3101
3102      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
3103
3104      bool red_nodes_done = _skip_nodes;
3105      bool blue_nodes_done = _skip_nodes;
3106      bool edges_done = _skip_edges;
3107      bool attributes_done = false;
3108
3109      line_num = 0;
3110      readLine();
3111      skipSection();
3112
3113      while (readSuccess()) {
3114        try {
3115          char c;
3116          std::string section, caption;
3117          line >> c;
3118          _reader_bits::readToken(line, section);
3119          _reader_bits::readToken(line, caption);
3120
3121          if (line >> c)
3122            throw FormatError("Extra character at the end of line");
3123
3124          if (section == "red_nodes" && !red_nodes_done) {
3125            if (_nodes_caption.empty() || _nodes_caption == caption) {
3126              readRedNodes();
3127              red_nodes_done = true;
3128            }
3129          } else if (section == "blue_nodes" && !blue_nodes_done) {
3130            if (_nodes_caption.empty() || _nodes_caption == caption) {
3131              readBlueNodes();
3132              blue_nodes_done = true;
3133            }
3134          } else if ((section == "edges" || section == "arcs") &&
3135                     !edges_done) {
3136            if (_edges_caption.empty() || _edges_caption == caption) {
3137              readEdges();
3138              edges_done = true;
3139            }
3140          } else if (section == "attributes" && !attributes_done) {
3141            if (_attributes_caption.empty() || _attributes_caption == caption) {
3142              readAttributes();
3143              attributes_done = true;
3144            }
3145          } else {
3146            readLine();
3147            skipSection();
3148          }
3149        } catch (FormatError& error) {
3150          error.line(line_num);
3151          error.file(_filename);
3152          throw;
3153        }
3154      }
3155
3156      if (!red_nodes_done) {
3157        throw FormatError("Section @red_nodes not found");
3158      }
3159
3160      if (!blue_nodes_done) {
3161        throw FormatError("Section @blue_nodes not found");
3162      }
3163
3164      if (!edges_done) {
3165        throw FormatError("Section @edges not found");
3166      }
3167
3168      if (!attributes_done && !_attributes.empty()) {
3169        throw FormatError("Section @attributes not found");
3170      }
3171
3172    }
3173
3174    /// @}
3175
3176  };
3177
3178  /// \ingroup lemon_io
3179  ///
3180  /// \brief Return a \ref lemon::BpGraphReader "BpGraphReader" class
3181  ///
3182  /// This function just returns a \ref lemon::BpGraphReader
3183  /// "BpGraphReader" class.
3184  ///
3185  /// With this function a graph can be read from an
3186  /// \ref lgf-format "LGF" file or input stream with several maps and
3187  /// attributes. For example, there is bipartite weighted matching problem
3188  /// on a graph, i.e. a graph with a \e weight map on the edges. This
3189  /// graph can be read with the following code:
3190  ///
3191  ///\code
3192  ///ListBpGraph graph;
3193  ///ListBpGraph::EdgeMap<int> weight(graph);
3194  ///bpGraphReader(graph, std::cin).
3195  ///  edgeMap("weight", weight).
3196  ///  run();
3197  ///\endcode
3198  ///
3199  /// For a complete documentation, please see the
3200  /// \ref lemon::BpGraphReader "BpGraphReader"
3201  /// class documentation.
3202  /// \warning Don't forget to put the \ref lemon::BpGraphReader::run() "run()"
3203  /// to the end of the parameter list.
3204  /// \relates BpGraphReader
3205  /// \sa bpGraphReader(TBGR& graph, const std::string& fn)
3206  /// \sa bpGraphReader(TBGR& graph, const char* fn)
3207  template <typename TBGR>
3208  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) {
3209    BpGraphReader<TBGR> tmp(graph, is);
3210    return tmp;
3211  }
3212
3213  /// \brief Return a \ref BpGraphReader class
3214  ///
3215  /// This function just returns a \ref BpGraphReader class.
3216  /// \relates BpGraphReader
3217  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
3218  template <typename TBGR>
3219  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) {
3220    BpGraphReader<TBGR> tmp(graph, fn);
3221    return tmp;
3222  }
3223
3224  /// \brief Return a \ref BpGraphReader class
3225  ///
3226  /// This function just returns a \ref BpGraphReader class.
3227  /// \relates BpGraphReader
3228  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
3229  template <typename TBGR>
3230  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) {
3231    BpGraphReader<TBGR> tmp(graph, fn);
3232    return tmp;
3233  }
3234
3235  class SectionReader;
3236
3237  SectionReader sectionReader(std::istream& is);
3238  SectionReader sectionReader(const std::string& fn);
3239  SectionReader sectionReader(const char* fn);
3240
3241  /// \ingroup lemon_io
3242  ///
3243  /// \brief Section reader class
3244  ///
3245  /// In the \ref lgf-format "LGF" file extra sections can be placed,
3246  /// which contain any data in arbitrary format. Such sections can be
3247  /// read with this class. A reading rule can be added to the class
3248  /// with two different functions. With the \c sectionLines() function a
3249  /// functor can process the section line-by-line, while with the \c
3250  /// sectionStream() member the section can be read from an input
3251  /// stream.
3252  class SectionReader {
3253  private:
3254
3255    std::istream* _is;
3256    bool local_is;
3257    std::string _filename;
3258
3259    typedef std::map<std::string, _reader_bits::Section*> Sections;
3260    Sections _sections;
3261
3262    int line_num;
3263    std::istringstream line;
3264
3265  public:
3266
3267    /// \brief Constructor
3268    ///
3269    /// Construct a section reader, which reads from the given input
3270    /// stream.
3271    SectionReader(std::istream& is)
3272      : _is(&is), local_is(false) {}
3273
3274    /// \brief Constructor
3275    ///
3276    /// Construct a section reader, which reads from the given file.
3277    SectionReader(const std::string& fn)
3278      : _is(new std::ifstream(fn.c_str())), local_is(true),
3279        _filename(fn) {
3280      if (!(*_is)) {
3281        delete _is;
3282        throw IoError("Cannot open file", fn);
3283      }
3284    }
3285
3286    /// \brief Constructor
3287    ///
3288    /// Construct a section reader, which reads from the given file.
3289    SectionReader(const char* fn)
3290      : _is(new std::ifstream(fn)), local_is(true),
3291        _filename(fn) {
3292      if (!(*_is)) {
3293        delete _is;
3294        throw IoError("Cannot open file", fn);
3295      }
3296    }
3297
3298    /// \brief Destructor
3299    ~SectionReader() {
3300      for (Sections::iterator it = _sections.begin();
3301           it != _sections.end(); ++it) {
3302        delete it->second;
3303      }
3304
3305      if (local_is) {
3306        delete _is;
3307      }
3308
3309    }
3310
3311  private:
3312
3313    friend SectionReader sectionReader(std::istream& is);
3314    friend SectionReader sectionReader(const std::string& fn);
3315    friend SectionReader sectionReader(const char* fn);
3316
3317    SectionReader(SectionReader& other)
3318      : _is(other._is), local_is(other.local_is) {
3319
3320      other._is = 0;
3321      other.local_is = false;
3322
3323      _sections.swap(other._sections);
3324    }
3325
3326    SectionReader& operator=(const SectionReader&);
3327
3328  public:
3329
3330    /// \name Section Readers
3331    /// @{
3332
3333    /// \brief Add a section processor with line oriented reading
3334    ///
3335    /// The first parameter is the type descriptor of the section, the
3336    /// second is a functor, which takes just one \c std::string
3337    /// parameter. At the reading process, each line of the section
3338    /// will be given to the functor object. However, the empty lines
3339    /// and the comment lines are filtered out, and the leading
3340    /// whitespaces are trimmed from each processed string.
3341    ///
3342    /// For example, let's see a section, which contain several
3343    /// integers, which should be inserted into a vector.
3344    ///\code
3345    ///  @numbers
3346    ///  12 45 23
3347    ///  4
3348    ///  23 6
3349    ///\endcode
3350    ///
3351    /// The functor is implemented as a struct:
3352    ///\code
3353    ///  struct NumberSection {
3354    ///    std::vector<int>& _data;
3355    ///    NumberSection(std::vector<int>& data) : _data(data) {}
3356    ///    void operator()(const std::string& line) {
3357    ///      std::istringstream ls(line);
3358    ///      int value;
3359    ///      while (ls >> value) _data.push_back(value);
3360    ///    }
3361    ///  };
3362    ///
3363    ///  // ...
3364    ///
3365    ///  reader.sectionLines("numbers", NumberSection(vec));
3366    ///\endcode
3367    template <typename Functor>
3368    SectionReader& sectionLines(const std::string& type, Functor functor) {
3369      LEMON_ASSERT(!type.empty(), "Type is empty.");
3370      LEMON_ASSERT(_sections.find(type) == _sections.end(),
3371                   "Multiple reading of section.");
3372      _sections.insert(std::make_pair(type,
3373        new _reader_bits::LineSection<Functor>(functor)));
3374      return *this;
3375    }
3376
3377
3378    /// \brief Add a section processor with stream oriented reading
3379    ///
3380    /// The first parameter is the type of the section, the second is
3381    /// a functor, which takes an \c std::istream& and an \c int&
3382    /// parameter, the latter regard to the line number of stream. The
3383    /// functor can read the input while the section go on, and the
3384    /// line number should be modified accordingly.
3385    template <typename Functor>
3386    SectionReader& sectionStream(const std::string& type, Functor functor) {
3387      LEMON_ASSERT(!type.empty(), "Type is empty.");
3388      LEMON_ASSERT(_sections.find(type) == _sections.end(),
3389                   "Multiple reading of section.");
3390      _sections.insert(std::make_pair(type,
3391         new _reader_bits::StreamSection<Functor>(functor)));
3392      return *this;
3393    }
3394
3395    /// @}
3396
3397  private:
3398
3399    bool readLine() {
3400      std::string str;
3401      while(++line_num, std::getline(*_is, str)) {
3402        line.clear(); line.str(str);
3403        char c;
3404        if (line >> std::ws >> c && c != '#') {
3405          line.putback(c);
3406          return true;
3407        }
3408      }
3409      return false;
3410    }
3411
3412    bool readSuccess() {
3413      return static_cast<bool>(*_is);
3414    }
3415
3416    void skipSection() {
3417      char c;
3418      while (readSuccess() && line >> c && c != '@') {
3419        readLine();
3420      }
3421      if (readSuccess()) {
3422        line.putback(c);
3423      }
3424    }
3425
3426  public:
3427
3428
3429    /// \name Execution of the Reader
3430    /// @{
3431
3432    /// \brief Start the batch processing
3433    ///
3434    /// This function starts the batch processing.
3435    void run() {
3436
3437      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
3438
3439      std::set<std::string> extra_sections;
3440
3441      line_num = 0;
3442      readLine();
3443      skipSection();
3444
3445      while (readSuccess()) {
3446        try {
3447          char c;
3448          std::string section, caption;
3449          line >> c;
3450          _reader_bits::readToken(line, section);
3451          _reader_bits::readToken(line, caption);
3452
3453          if (line >> c)
3454            throw FormatError("Extra character at the end of line");
3455
3456          if (extra_sections.find(section) != extra_sections.end()) {
3457            std::ostringstream msg;
3458            msg << "Multiple occurence of section: " << section;
3459            throw FormatError(msg.str());
3460          }
3461          Sections::iterator it = _sections.find(section);
3462          if (it != _sections.end()) {
3463            extra_sections.insert(section);
3464            it->second->process(*_is, line_num);
3465          }
3466          readLine();
3467          skipSection();
3468        } catch (FormatError& error) {
3469          error.line(line_num);
3470          error.file(_filename);
3471          throw;
3472        }
3473      }
3474      for (Sections::iterator it = _sections.begin();
3475           it != _sections.end(); ++it) {
3476        if (extra_sections.find(it->first) == extra_sections.end()) {
3477          std::ostringstream os;
3478          os << "Cannot find section: " << it->first;
3479          throw FormatError(os.str());
3480        }
3481      }
3482    }
3483
3484    /// @}
3485
3486  };
3487
3488  /// \ingroup lemon_io
3489  ///
3490  /// \brief Return a \ref SectionReader class
3491  ///
3492  /// This function just returns a \ref SectionReader class.
3493  ///
3494  /// Please see SectionReader documentation about the custom section
3495  /// input.
3496  ///
3497  /// \relates SectionReader
3498  /// \sa sectionReader(const std::string& fn)
3499  /// \sa sectionReader(const char *fn)
3500  inline SectionReader sectionReader(std::istream& is) {
3501    SectionReader tmp(is);
3502    return tmp;
3503  }
3504
3505  /// \brief Return a \ref SectionReader class
3506  ///
3507  /// This function just returns a \ref SectionReader class.
3508  /// \relates SectionReader
3509  /// \sa sectionReader(std::istream& is)
3510  inline SectionReader sectionReader(const std::string& fn) {
3511    SectionReader tmp(fn);
3512    return tmp;
3513  }
3514
3515  /// \brief Return a \ref SectionReader class
3516  ///
3517  /// This function just returns a \ref SectionReader class.
3518  /// \relates SectionReader
3519  /// \sa sectionReader(std::istream& is)
3520  inline SectionReader sectionReader(const char* fn) {
3521    SectionReader tmp(fn);
3522    return tmp;
3523  }
3524
3525  /// \ingroup lemon_io
3526  ///
3527  /// \brief Reader for the contents of the \ref lgf-format "LGF" file
3528  ///
3529  /// This class can be used to read the sections, the map names and
3530  /// the attributes from a file. Usually, the LEMON programs know
3531  /// that, which type of graph, which maps and which attributes
3532  /// should be read from a file, but in general tools (like glemon)
3533  /// the contents of an LGF file should be guessed somehow. This class
3534  /// reads the graph and stores the appropriate information for
3535  /// reading the graph.
3536  ///
3537  ///\code
3538  /// LgfContents contents("graph.lgf");
3539  /// contents.run();
3540  ///
3541  /// // Does it contain any node section and arc section?
3542  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
3543  ///   std::cerr << "Failure, cannot find graph." << std::endl;
3544  ///   return -1;
3545  /// }
3546  /// std::cout << "The name of the default node section: "
3547  ///           << contents.nodeSection(0) << std::endl;
3548  /// std::cout << "The number of the arc maps: "
3549  ///           << contents.arcMaps(0).size() << std::endl;
3550  /// std::cout << "The name of second arc map: "
3551  ///           << contents.arcMaps(0)[1] << std::endl;
3552  ///\endcode
3553  class LgfContents {
3554  private:
3555
3556    std::istream* _is;
3557    bool local_is;
3558
3559    std::vector<std::string> _node_sections;
3560    std::vector<std::string> _edge_sections;
3561    std::vector<std::string> _attribute_sections;
3562    std::vector<std::string> _extra_sections;
3563
3564    std::vector<bool> _arc_sections;
3565
3566    std::vector<std::vector<std::string> > _node_maps;
3567    std::vector<std::vector<std::string> > _edge_maps;
3568
3569    std::vector<std::vector<std::string> > _attributes;
3570
3571
3572    int line_num;
3573    std::istringstream line;
3574
3575  public:
3576
3577    /// \brief Constructor
3578    ///
3579    /// Construct an \e LGF contents reader, which reads from the given
3580    /// input stream.
3581    LgfContents(std::istream& is)
3582      : _is(&is), local_is(false) {}
3583
3584    /// \brief Constructor
3585    ///
3586    /// Construct an \e LGF contents reader, which reads from the given
3587    /// file.
3588    LgfContents(const std::string& fn)
3589      : _is(new std::ifstream(fn.c_str())), local_is(true) {
3590      if (!(*_is)) {
3591        delete _is;
3592        throw IoError("Cannot open file", fn);
3593      }
3594    }
3595
3596    /// \brief Constructor
3597    ///
3598    /// Construct an \e LGF contents reader, which reads from the given
3599    /// file.
3600    LgfContents(const char* fn)
3601      : _is(new std::ifstream(fn)), local_is(true) {
3602      if (!(*_is)) {
3603        delete _is;
3604        throw IoError("Cannot open file", fn);
3605      }
3606    }
3607
3608    /// \brief Destructor
3609    ~LgfContents() {
3610      if (local_is) delete _is;
3611    }
3612
3613  private:
3614
3615    LgfContents(const LgfContents&);
3616    LgfContents& operator=(const LgfContents&);
3617
3618  public:
3619
3620
3621    /// \name Node Sections
3622    /// @{
3623
3624    /// \brief Gives back the number of node sections in the file.
3625    ///
3626    /// Gives back the number of node sections in the file.
3627    int nodeSectionNum() const {
3628      return _node_sections.size();
3629    }
3630
3631    /// \brief Returns the node section name at the given position.
3632    ///
3633    /// Returns the node section name at the given position.
3634    const std::string& nodeSection(int i) const {
3635      return _node_sections[i];
3636    }
3637
3638    /// \brief Gives back the node maps for the given section.
3639    ///
3640    /// Gives back the node maps for the given section.
3641    const std::vector<std::string>& nodeMapNames(int i) const {
3642      return _node_maps[i];
3643    }
3644
3645    /// @}
3646
3647    /// \name Arc/Edge Sections
3648    /// @{
3649
3650    /// \brief Gives back the number of arc/edge sections in the file.
3651    ///
3652    /// Gives back the number of arc/edge sections in the file.
3653    /// \note It is synonym of \c edgeSectionNum().
3654    int arcSectionNum() const {
3655      return _edge_sections.size();
3656    }
3657
3658    /// \brief Returns the arc/edge section name at the given position.
3659    ///
3660    /// Returns the arc/edge section name at the given position.
3661    /// \note It is synonym of \c edgeSection().
3662    const std::string& arcSection(int i) const {
3663      return _edge_sections[i];
3664    }
3665
3666    /// \brief Gives back the arc/edge maps for the given section.
3667    ///
3668    /// Gives back the arc/edge maps for the given section.
3669    /// \note It is synonym of \c edgeMapNames().
3670    const std::vector<std::string>& arcMapNames(int i) const {
3671      return _edge_maps[i];
3672    }
3673
3674    /// @}
3675
3676    /// \name Synonyms
3677    /// @{
3678
3679    /// \brief Gives back the number of arc/edge sections in the file.
3680    ///
3681    /// Gives back the number of arc/edge sections in the file.
3682    /// \note It is synonym of \c arcSectionNum().
3683    int edgeSectionNum() const {
3684      return _edge_sections.size();
3685    }
3686
3687    /// \brief Returns the section name at the given position.
3688    ///
3689    /// Returns the section name at the given position.
3690    /// \note It is synonym of \c arcSection().
3691    const std::string& edgeSection(int i) const {
3692      return _edge_sections[i];
3693    }
3694
3695    /// \brief Gives back the edge maps for the given section.
3696    ///
3697    /// Gives back the edge maps for the given section.
3698    /// \note It is synonym of \c arcMapNames().
3699    const std::vector<std::string>& edgeMapNames(int i) const {
3700      return _edge_maps[i];
3701    }
3702
3703    /// @}
3704
3705    /// \name Attribute Sections
3706    /// @{
3707
3708    /// \brief Gives back the number of attribute sections in the file.
3709    ///
3710    /// Gives back the number of attribute sections in the file.
3711    int attributeSectionNum() const {
3712      return _attribute_sections.size();
3713    }
3714
3715    /// \brief Returns the attribute section name at the given position.
3716    ///
3717    /// Returns the attribute section name at the given position.
3718    const std::string& attributeSectionNames(int i) const {
3719      return _attribute_sections[i];
3720    }
3721
3722    /// \brief Gives back the attributes for the given section.
3723    ///
3724    /// Gives back the attributes for the given section.
3725    const std::vector<std::string>& attributes(int i) const {
3726      return _attributes[i];
3727    }
3728
3729    /// @}
3730
3731    /// \name Extra Sections
3732    /// @{
3733
3734    /// \brief Gives back the number of extra sections in the file.
3735    ///
3736    /// Gives back the number of extra sections in the file.
3737    int extraSectionNum() const {
3738      return _extra_sections.size();
3739    }
3740
3741    /// \brief Returns the extra section type at the given position.
3742    ///
3743    /// Returns the section type at the given position.
3744    const std::string& extraSection(int i) const {
3745      return _extra_sections[i];
3746    }
3747
3748    /// @}
3749
3750  private:
3751
3752    bool readLine() {
3753      std::string str;
3754      while(++line_num, std::getline(*_is, str)) {
3755        line.clear(); line.str(str);
3756        char c;
3757        if (line >> std::ws >> c && c != '#') {
3758          line.putback(c);
3759          return true;
3760        }
3761      }
3762      return false;
3763    }
3764
3765    bool readSuccess() {
3766      return static_cast<bool>(*_is);
3767    }
3768
3769    void skipSection() {
3770      char c;
3771      while (readSuccess() && line >> c && c != '@') {
3772        readLine();
3773      }
3774      if (readSuccess()) {
3775        line.putback(c);
3776      }
3777    }
3778
3779    void readMaps(std::vector<std::string>& maps) {
3780      char c;
3781      if (!readLine() || !(line >> c) || c == '@') {
3782        if (readSuccess() && line) line.putback(c);
3783        return;
3784      }
3785      line.putback(c);
3786      std::string map;
3787      while (_reader_bits::readToken(line, map)) {
3788        maps.push_back(map);
3789      }
3790    }
3791
3792    void readAttributes(std::vector<std::string>& attrs) {
3793      readLine();
3794      char c;
3795      while (readSuccess() && line >> c && c != '@') {
3796        line.putback(c);
3797        std::string attr;
3798        _reader_bits::readToken(line, attr);
3799        attrs.push_back(attr);
3800        readLine();
3801      }
3802      line.putback(c);
3803    }
3804
3805  public:
3806
3807    /// \name Execution of the Contents Reader
3808    /// @{
3809
3810    /// \brief Starts the reading
3811    ///
3812    /// This function starts the reading.
3813    void run() {
3814
3815      readLine();
3816      skipSection();
3817
3818      while (readSuccess()) {
3819
3820        char c;
3821        line >> c;
3822
3823        std::string section, caption;
3824        _reader_bits::readToken(line, section);
3825        _reader_bits::readToken(line, caption);
3826
3827        if (section == "nodes") {
3828          _node_sections.push_back(caption);
3829          _node_maps.push_back(std::vector<std::string>());
3830          readMaps(_node_maps.back());
3831          readLine(); skipSection();
3832        } else if (section == "arcs" || section == "edges") {
3833          _edge_sections.push_back(caption);
3834          _arc_sections.push_back(section == "arcs");
3835          _edge_maps.push_back(std::vector<std::string>());
3836          readMaps(_edge_maps.back());
3837          readLine(); skipSection();
3838        } else if (section == "attributes") {
3839          _attribute_sections.push_back(caption);
3840          _attributes.push_back(std::vector<std::string>());
3841          readAttributes(_attributes.back());
3842        } else {
3843          _extra_sections.push_back(section);
3844          readLine(); skipSection();
3845        }
3846      }
3847    }
3848
3849    /// @}
3850
3851  };
3852}
3853
3854#endif
Note: See TracBrowser for help on using the repository browser.