COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 1198:4936be66d2f5

Last change on this file since 1198:4936be66d2f5 was 1198:4936be66d2f5, checked in by Balazs Dezso <deba@…>, 7 years ago

Changes in BpGraph? lgf reader and writer (#69)

File size: 116.9 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 DigraphReader class
1234  ///
1235  /// This function just returns a \ref DigraphReader class.
1236  ///
1237  /// With this function a digraph can be read from an
1238  /// \ref lgf-format "LGF" file or input stream with several maps and
1239  /// attributes. For example, there is network flow problem on a
1240  /// digraph, i.e. a digraph with a \e capacity map on the arcs and
1241  /// \e source and \e target nodes. This digraph can be read with the
1242  /// following code:
1243  ///
1244  ///\code
1245  ///ListDigraph digraph;
1246  ///ListDigraph::ArcMap<int> cm(digraph);
1247  ///ListDigraph::Node src, trg;
1248  ///digraphReader(digraph, std::cin).
1249  ///  arcMap("capacity", cap).
1250  ///  node("source", src).
1251  ///  node("target", trg).
1252  ///  run();
1253  ///\endcode
1254  ///
1255  /// For a complete documentation, please see the \ref DigraphReader
1256  /// class documentation.
1257  /// \warning Don't forget to put the \ref DigraphReader::run() "run()"
1258  /// to the end of the parameter list.
1259  /// \relates DigraphReader
1260  /// \sa digraphReader(TDGR& digraph, const std::string& fn)
1261  /// \sa digraphReader(TDGR& digraph, const char* fn)
1262  template <typename TDGR>
1263  DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is) {
1264    DigraphReader<TDGR> tmp(digraph, is);
1265    return tmp;
1266  }
1267
1268  /// \brief Return a \ref DigraphReader class
1269  ///
1270  /// This function just returns a \ref DigraphReader class.
1271  /// \relates DigraphReader
1272  /// \sa digraphReader(TDGR& digraph, std::istream& is)
1273  template <typename TDGR>
1274  DigraphReader<TDGR> digraphReader(TDGR& digraph, const std::string& fn) {
1275    DigraphReader<TDGR> tmp(digraph, fn);
1276    return tmp;
1277  }
1278
1279  /// \brief Return a \ref DigraphReader class
1280  ///
1281  /// This function just returns a \ref DigraphReader class.
1282  /// \relates DigraphReader
1283  /// \sa digraphReader(TDGR& digraph, std::istream& is)
1284  template <typename TDGR>
1285  DigraphReader<TDGR> digraphReader(TDGR& digraph, const char* fn) {
1286    DigraphReader<TDGR> tmp(digraph, fn);
1287    return tmp;
1288  }
1289
1290  template <typename GR>
1291  class GraphReader;
1292
1293  template <typename TGR>
1294  GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin);
1295  template <typename TGR>
1296  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
1297  template <typename TGR>
1298  GraphReader<TGR> graphReader(TGR& graph, const char *fn);
1299
1300  /// \ingroup lemon_io
1301  ///
1302  /// \brief \ref lgf-format "LGF" reader for undirected graphs
1303  ///
1304  /// This utility reads an \ref lgf-format "LGF" file.
1305  ///
1306  /// It can be used almost the same way as \c DigraphReader.
1307  /// The only difference is that this class can handle edges and
1308  /// edge maps as well as arcs and arc maps.
1309  ///
1310  /// The columns in the \c \@edges (or \c \@arcs) section are the
1311  /// edge maps. However, if there are two maps with the same name
1312  /// prefixed with \c '+' and \c '-', then these can be read into an
1313  /// arc map.  Similarly, an attribute can be read into an arc, if
1314  /// it's value is an edge label prefixed with \c '+' or \c '-'.
1315  template <typename GR>
1316  class GraphReader {
1317  public:
1318
1319    typedef GR Graph;
1320
1321  private:
1322
1323    TEMPLATE_GRAPH_TYPEDEFS(GR);
1324
1325    std::istream* _is;
1326    bool local_is;
1327    std::string _filename;
1328
1329    GR& _graph;
1330
1331    std::string _nodes_caption;
1332    std::string _edges_caption;
1333    std::string _attributes_caption;
1334
1335    typedef std::map<std::string, Node> NodeIndex;
1336    NodeIndex _node_index;
1337    typedef std::map<std::string, Edge> EdgeIndex;
1338    EdgeIndex _edge_index;
1339
1340    typedef std::vector<std::pair<std::string,
1341      _reader_bits::MapStorageBase<Node>*> > NodeMaps;
1342    NodeMaps _node_maps;
1343
1344    typedef std::vector<std::pair<std::string,
1345      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1346    EdgeMaps _edge_maps;
1347
1348    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1349      Attributes;
1350    Attributes _attributes;
1351
1352    bool _use_nodes;
1353    bool _use_edges;
1354
1355    bool _skip_nodes;
1356    bool _skip_edges;
1357
1358    int line_num;
1359    std::istringstream line;
1360
1361  public:
1362
1363    /// \brief Constructor
1364    ///
1365    /// Construct an undirected graph reader, which reads from the given
1366    /// input stream.
1367    GraphReader(GR& graph, std::istream& is = std::cin)
1368      : _is(&is), local_is(false), _graph(graph),
1369        _use_nodes(false), _use_edges(false),
1370        _skip_nodes(false), _skip_edges(false) {}
1371
1372    /// \brief Constructor
1373    ///
1374    /// Construct an undirected graph reader, which reads from the given
1375    /// file.
1376    GraphReader(GR& graph, const std::string& fn)
1377      : _is(new std::ifstream(fn.c_str())), local_is(true),
1378        _filename(fn), _graph(graph),
1379        _use_nodes(false), _use_edges(false),
1380        _skip_nodes(false), _skip_edges(false) {
1381      if (!(*_is)) {
1382        delete _is;
1383        throw IoError("Cannot open file", fn);
1384      }
1385    }
1386
1387    /// \brief Constructor
1388    ///
1389    /// Construct an undirected graph reader, which reads from the given
1390    /// file.
1391    GraphReader(GR& graph, const char* fn)
1392      : _is(new std::ifstream(fn)), local_is(true),
1393        _filename(fn), _graph(graph),
1394        _use_nodes(false), _use_edges(false),
1395        _skip_nodes(false), _skip_edges(false) {
1396      if (!(*_is)) {
1397        delete _is;
1398        throw IoError("Cannot open file", fn);
1399      }
1400    }
1401
1402    /// \brief Destructor
1403    ~GraphReader() {
1404      for (typename NodeMaps::iterator it = _node_maps.begin();
1405           it != _node_maps.end(); ++it) {
1406        delete it->second;
1407      }
1408
1409      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1410           it != _edge_maps.end(); ++it) {
1411        delete it->second;
1412      }
1413
1414      for (typename Attributes::iterator it = _attributes.begin();
1415           it != _attributes.end(); ++it) {
1416        delete it->second;
1417      }
1418
1419      if (local_is) {
1420        delete _is;
1421      }
1422
1423    }
1424
1425  private:
1426    template <typename TGR>
1427    friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is);
1428    template <typename TGR>
1429    friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn);
1430    template <typename TGR>
1431    friend GraphReader<TGR> graphReader(TGR& graph, const char *fn);
1432
1433    GraphReader(GraphReader& other)
1434      : _is(other._is), local_is(other.local_is), _graph(other._graph),
1435        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1436        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1437
1438      other._is = 0;
1439      other.local_is = false;
1440
1441      _node_index.swap(other._node_index);
1442      _edge_index.swap(other._edge_index);
1443
1444      _node_maps.swap(other._node_maps);
1445      _edge_maps.swap(other._edge_maps);
1446      _attributes.swap(other._attributes);
1447
1448      _nodes_caption = other._nodes_caption;
1449      _edges_caption = other._edges_caption;
1450      _attributes_caption = other._attributes_caption;
1451
1452    }
1453
1454    GraphReader& operator=(const GraphReader&);
1455
1456  public:
1457
1458    /// \name Reading Rules
1459    /// @{
1460
1461    /// \brief Node map reading rule
1462    ///
1463    /// Add a node map reading rule to the reader.
1464    template <typename Map>
1465    GraphReader& nodeMap(const std::string& caption, Map& map) {
1466      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1467      _reader_bits::MapStorageBase<Node>* storage =
1468        new _reader_bits::MapStorage<Node, Map>(map);
1469      _node_maps.push_back(std::make_pair(caption, storage));
1470      return *this;
1471    }
1472
1473    /// \brief Node map reading rule
1474    ///
1475    /// Add a node map reading rule with specialized converter to the
1476    /// reader.
1477    template <typename Map, typename Converter>
1478    GraphReader& nodeMap(const std::string& caption, Map& map,
1479                           const Converter& converter = Converter()) {
1480      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1481      _reader_bits::MapStorageBase<Node>* storage =
1482        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1483      _node_maps.push_back(std::make_pair(caption, storage));
1484      return *this;
1485    }
1486
1487    /// \brief Edge map reading rule
1488    ///
1489    /// Add an edge map reading rule to the reader.
1490    template <typename Map>
1491    GraphReader& edgeMap(const std::string& caption, Map& map) {
1492      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1493      _reader_bits::MapStorageBase<Edge>* storage =
1494        new _reader_bits::MapStorage<Edge, Map>(map);
1495      _edge_maps.push_back(std::make_pair(caption, storage));
1496      return *this;
1497    }
1498
1499    /// \brief Edge map reading rule
1500    ///
1501    /// Add an edge map reading rule with specialized converter to the
1502    /// reader.
1503    template <typename Map, typename Converter>
1504    GraphReader& edgeMap(const std::string& caption, Map& map,
1505                          const Converter& converter = Converter()) {
1506      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1507      _reader_bits::MapStorageBase<Edge>* storage =
1508        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1509      _edge_maps.push_back(std::make_pair(caption, storage));
1510      return *this;
1511    }
1512
1513    /// \brief Arc map reading rule
1514    ///
1515    /// Add an arc map reading rule to the reader.
1516    template <typename Map>
1517    GraphReader& arcMap(const std::string& caption, Map& map) {
1518      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1519      _reader_bits::MapStorageBase<Edge>* forward_storage =
1520        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1521      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1522      _reader_bits::MapStorageBase<Edge>* backward_storage =
1523        new _reader_bits::GraphArcMapStorage<GR, false, Map>(_graph, map);
1524      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1525      return *this;
1526    }
1527
1528    /// \brief Arc map reading rule
1529    ///
1530    /// Add an arc map reading rule with specialized converter to the
1531    /// reader.
1532    template <typename Map, typename Converter>
1533    GraphReader& arcMap(const std::string& caption, Map& map,
1534                          const Converter& converter = Converter()) {
1535      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1536      _reader_bits::MapStorageBase<Edge>* forward_storage =
1537        new _reader_bits::GraphArcMapStorage<GR, true, Map, Converter>
1538        (_graph, map, converter);
1539      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1540      _reader_bits::MapStorageBase<Edge>* backward_storage =
1541        new _reader_bits::GraphArcMapStorage<GR, false, Map, Converter>
1542        (_graph, map, converter);
1543      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1544      return *this;
1545    }
1546
1547    /// \brief Attribute reading rule
1548    ///
1549    /// Add an attribute reading rule to the reader.
1550    template <typename Value>
1551    GraphReader& attribute(const std::string& caption, Value& value) {
1552      _reader_bits::ValueStorageBase* storage =
1553        new _reader_bits::ValueStorage<Value>(value);
1554      _attributes.insert(std::make_pair(caption, storage));
1555      return *this;
1556    }
1557
1558    /// \brief Attribute reading rule
1559    ///
1560    /// Add an attribute reading rule with specialized converter to the
1561    /// reader.
1562    template <typename Value, typename Converter>
1563    GraphReader& attribute(const std::string& caption, Value& value,
1564                             const Converter& converter = Converter()) {
1565      _reader_bits::ValueStorageBase* storage =
1566        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1567      _attributes.insert(std::make_pair(caption, storage));
1568      return *this;
1569    }
1570
1571    /// \brief Node reading rule
1572    ///
1573    /// Add a node reading rule to reader.
1574    GraphReader& node(const std::string& caption, Node& node) {
1575      typedef _reader_bits::MapLookUpConverter<Node> Converter;
1576      Converter converter(_node_index);
1577      _reader_bits::ValueStorageBase* storage =
1578        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1579      _attributes.insert(std::make_pair(caption, storage));
1580      return *this;
1581    }
1582
1583    /// \brief Edge reading rule
1584    ///
1585    /// Add an edge reading rule to reader.
1586    GraphReader& edge(const std::string& caption, Edge& edge) {
1587      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1588      Converter converter(_edge_index);
1589      _reader_bits::ValueStorageBase* storage =
1590        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1591      _attributes.insert(std::make_pair(caption, storage));
1592      return *this;
1593    }
1594
1595    /// \brief Arc reading rule
1596    ///
1597    /// Add an arc reading rule to reader.
1598    GraphReader& arc(const std::string& caption, Arc& arc) {
1599      typedef _reader_bits::GraphArcLookUpConverter<GR> Converter;
1600      Converter converter(_graph, _edge_index);
1601      _reader_bits::ValueStorageBase* storage =
1602        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1603      _attributes.insert(std::make_pair(caption, storage));
1604      return *this;
1605    }
1606
1607    /// @}
1608
1609    /// \name Select Section by Name
1610    /// @{
1611
1612    /// \brief Set \c \@nodes section to be read
1613    ///
1614    /// Set \c \@nodes section to be read.
1615    GraphReader& nodes(const std::string& caption) {
1616      _nodes_caption = caption;
1617      return *this;
1618    }
1619
1620    /// \brief Set \c \@edges section to be read
1621    ///
1622    /// Set \c \@edges section to be read.
1623    GraphReader& edges(const std::string& caption) {
1624      _edges_caption = caption;
1625      return *this;
1626    }
1627
1628    /// \brief Set \c \@attributes section to be read
1629    ///
1630    /// Set \c \@attributes section to be read.
1631    GraphReader& attributes(const std::string& caption) {
1632      _attributes_caption = caption;
1633      return *this;
1634    }
1635
1636    /// @}
1637
1638    /// \name Using Previously Constructed Node or Edge Set
1639    /// @{
1640
1641    /// \brief Use previously constructed node set
1642    ///
1643    /// Use previously constructed node set, and specify the node
1644    /// label map.
1645    template <typename Map>
1646    GraphReader& useNodes(const Map& map) {
1647      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1648      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1649      _use_nodes = true;
1650      _writer_bits::DefaultConverter<typename Map::Value> converter;
1651      for (NodeIt n(_graph); n != INVALID; ++n) {
1652        _node_index.insert(std::make_pair(converter(map[n]), n));
1653      }
1654      return *this;
1655    }
1656
1657    /// \brief Use previously constructed node set
1658    ///
1659    /// Use previously constructed node set, and specify the node
1660    /// label map and a functor which converts the label map values to
1661    /// \c std::string.
1662    template <typename Map, typename Converter>
1663    GraphReader& useNodes(const Map& map,
1664                            const Converter& converter = Converter()) {
1665      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1666      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1667      _use_nodes = true;
1668      for (NodeIt n(_graph); n != INVALID; ++n) {
1669        _node_index.insert(std::make_pair(converter(map[n]), n));
1670      }
1671      return *this;
1672    }
1673
1674    /// \brief Use previously constructed edge set
1675    ///
1676    /// Use previously constructed edge set, and specify the edge
1677    /// label map.
1678    template <typename Map>
1679    GraphReader& useEdges(const Map& map) {
1680      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1681      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1682      _use_edges = true;
1683      _writer_bits::DefaultConverter<typename Map::Value> converter;
1684      for (EdgeIt a(_graph); a != INVALID; ++a) {
1685        _edge_index.insert(std::make_pair(converter(map[a]), a));
1686      }
1687      return *this;
1688    }
1689
1690    /// \brief Use previously constructed edge set
1691    ///
1692    /// Use previously constructed edge set, and specify the edge
1693    /// label map and a functor which converts the label map values to
1694    /// \c std::string.
1695    template <typename Map, typename Converter>
1696    GraphReader& useEdges(const Map& map,
1697                            const Converter& converter = Converter()) {
1698      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1699      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1700      _use_edges = true;
1701      for (EdgeIt a(_graph); a != INVALID; ++a) {
1702        _edge_index.insert(std::make_pair(converter(map[a]), a));
1703      }
1704      return *this;
1705    }
1706
1707    /// \brief Skip the reading of node section
1708    ///
1709    /// Omit the reading of the node section. This implies that each node
1710    /// map reading rule will be abandoned, and the nodes of the graph
1711    /// will not be constructed, which usually cause that the edge set
1712    /// could not be read due to lack of node name
1713    /// could not be read due to lack of node name resolving.
1714    /// Therefore \c skipEdges() function should also be used, or
1715    /// \c useNodes() should be used to specify the label of the nodes.
1716    GraphReader& skipNodes() {
1717      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1718      _skip_nodes = true;
1719      return *this;
1720    }
1721
1722    /// \brief Skip the reading of edge section
1723    ///
1724    /// Omit the reading of the edge section. This implies that each edge
1725    /// map reading rule will be abandoned, and the edges of the graph
1726    /// will not be constructed.
1727    GraphReader& skipEdges() {
1728      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1729      _skip_edges = true;
1730      return *this;
1731    }
1732
1733    /// @}
1734
1735  private:
1736
1737    bool readLine() {
1738      std::string str;
1739      while(++line_num, std::getline(*_is, str)) {
1740        line.clear(); line.str(str);
1741        char c;
1742        if (line >> std::ws >> c && c != '#') {
1743          line.putback(c);
1744          return true;
1745        }
1746      }
1747      return false;
1748    }
1749
1750    bool readSuccess() {
1751      return static_cast<bool>(*_is);
1752    }
1753
1754    void skipSection() {
1755      char c;
1756      while (readSuccess() && line >> c && c != '@') {
1757        readLine();
1758      }
1759      if (readSuccess()) {
1760        line.putback(c);
1761      }
1762    }
1763
1764    void readNodes() {
1765
1766      std::vector<int> map_index(_node_maps.size());
1767      int map_num, label_index;
1768
1769      char c;
1770      if (!readLine() || !(line >> c) || c == '@') {
1771        if (readSuccess() && line) line.putback(c);
1772        if (!_node_maps.empty())
1773          throw FormatError("Cannot find map names");
1774        return;
1775      }
1776      line.putback(c);
1777
1778      {
1779        std::map<std::string, int> maps;
1780
1781        std::string map;
1782        int index = 0;
1783        while (_reader_bits::readToken(line, map)) {
1784          if (maps.find(map) != maps.end()) {
1785            std::ostringstream msg;
1786            msg << "Multiple occurence of node map: " << map;
1787            throw FormatError(msg.str());
1788          }
1789          maps.insert(std::make_pair(map, index));
1790          ++index;
1791        }
1792
1793        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1794          std::map<std::string, int>::iterator jt =
1795            maps.find(_node_maps[i].first);
1796          if (jt == maps.end()) {
1797            std::ostringstream msg;
1798            msg << "Map not found: " << _node_maps[i].first;
1799            throw FormatError(msg.str());
1800          }
1801          map_index[i] = jt->second;
1802        }
1803
1804        {
1805          std::map<std::string, int>::iterator jt = maps.find("label");
1806          if (jt != maps.end()) {
1807            label_index = jt->second;
1808          } else {
1809            label_index = -1;
1810          }
1811        }
1812        map_num = maps.size();
1813      }
1814
1815      while (readLine() && line >> c && c != '@') {
1816        line.putback(c);
1817
1818        std::vector<std::string> tokens(map_num);
1819        for (int i = 0; i < map_num; ++i) {
1820          if (!_reader_bits::readToken(line, tokens[i])) {
1821            std::ostringstream msg;
1822            msg << "Column not found (" << i + 1 << ")";
1823            throw FormatError(msg.str());
1824          }
1825        }
1826        if (line >> std::ws >> c)
1827          throw FormatError("Extra character at the end of line");
1828
1829        Node n;
1830        if (!_use_nodes) {
1831          n = _graph.addNode();
1832          if (label_index != -1)
1833            _node_index.insert(std::make_pair(tokens[label_index], n));
1834        } else {
1835          if (label_index == -1)
1836            throw FormatError("Label map not found");
1837          typename std::map<std::string, Node>::iterator it =
1838            _node_index.find(tokens[label_index]);
1839          if (it == _node_index.end()) {
1840            std::ostringstream msg;
1841            msg << "Node with label not found: " << tokens[label_index];
1842            throw FormatError(msg.str());
1843          }
1844          n = it->second;
1845        }
1846
1847        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1848          _node_maps[i].second->set(n, tokens[map_index[i]]);
1849        }
1850
1851      }
1852      if (readSuccess()) {
1853        line.putback(c);
1854      }
1855    }
1856
1857    void readEdges() {
1858
1859      std::vector<int> map_index(_edge_maps.size());
1860      int map_num, label_index;
1861
1862      char c;
1863      if (!readLine() || !(line >> c) || c == '@') {
1864        if (readSuccess() && line) line.putback(c);
1865        if (!_edge_maps.empty())
1866          throw FormatError("Cannot find map names");
1867        return;
1868      }
1869      line.putback(c);
1870
1871      {
1872        std::map<std::string, int> maps;
1873
1874        std::string map;
1875        int index = 0;
1876        while (_reader_bits::readToken(line, map)) {
1877          if(map == "-") {
1878              if(index!=0)
1879                throw FormatError("'-' is not allowed as a map name");
1880              else if (line >> std::ws >> c)
1881                throw FormatError("Extra character at the end of line");
1882              else break;
1883            }
1884          if (maps.find(map) != maps.end()) {
1885            std::ostringstream msg;
1886            msg << "Multiple occurence of edge map: " << map;
1887            throw FormatError(msg.str());
1888          }
1889          maps.insert(std::make_pair(map, index));
1890          ++index;
1891        }
1892
1893        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1894          std::map<std::string, int>::iterator jt =
1895            maps.find(_edge_maps[i].first);
1896          if (jt == maps.end()) {
1897            std::ostringstream msg;
1898            msg << "Map not found: " << _edge_maps[i].first;
1899            throw FormatError(msg.str());
1900          }
1901          map_index[i] = jt->second;
1902        }
1903
1904        {
1905          std::map<std::string, int>::iterator jt = maps.find("label");
1906          if (jt != maps.end()) {
1907            label_index = jt->second;
1908          } else {
1909            label_index = -1;
1910          }
1911        }
1912        map_num = maps.size();
1913      }
1914
1915      while (readLine() && line >> c && c != '@') {
1916        line.putback(c);
1917
1918        std::string source_token;
1919        std::string target_token;
1920
1921        if (!_reader_bits::readToken(line, source_token))
1922          throw FormatError("Node u not found");
1923
1924        if (!_reader_bits::readToken(line, target_token))
1925          throw FormatError("Node v not found");
1926
1927        std::vector<std::string> tokens(map_num);
1928        for (int i = 0; i < map_num; ++i) {
1929          if (!_reader_bits::readToken(line, tokens[i])) {
1930            std::ostringstream msg;
1931            msg << "Column not found (" << i + 1 << ")";
1932            throw FormatError(msg.str());
1933          }
1934        }
1935        if (line >> std::ws >> c)
1936          throw FormatError("Extra character at the end of line");
1937
1938        Edge e;
1939        if (!_use_edges) {
1940
1941          typename NodeIndex::iterator it;
1942
1943          it = _node_index.find(source_token);
1944          if (it == _node_index.end()) {
1945            std::ostringstream msg;
1946            msg << "Item not found: " << source_token;
1947            throw FormatError(msg.str());
1948          }
1949          Node source = it->second;
1950
1951          it = _node_index.find(target_token);
1952          if (it == _node_index.end()) {
1953            std::ostringstream msg;
1954            msg << "Item not found: " << target_token;
1955            throw FormatError(msg.str());
1956          }
1957          Node target = it->second;
1958
1959          e = _graph.addEdge(source, target);
1960          if (label_index != -1)
1961            _edge_index.insert(std::make_pair(tokens[label_index], e));
1962        } else {
1963          if (label_index == -1)
1964            throw FormatError("Label map not found");
1965          typename std::map<std::string, Edge>::iterator it =
1966            _edge_index.find(tokens[label_index]);
1967          if (it == _edge_index.end()) {
1968            std::ostringstream msg;
1969            msg << "Edge with label not found: " << tokens[label_index];
1970            throw FormatError(msg.str());
1971          }
1972          e = it->second;
1973        }
1974
1975        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1976          _edge_maps[i].second->set(e, tokens[map_index[i]]);
1977        }
1978
1979      }
1980      if (readSuccess()) {
1981        line.putback(c);
1982      }
1983    }
1984
1985    void readAttributes() {
1986
1987      std::set<std::string> read_attr;
1988
1989      char c;
1990      while (readLine() && line >> c && c != '@') {
1991        line.putback(c);
1992
1993        std::string attr, token;
1994        if (!_reader_bits::readToken(line, attr))
1995          throw FormatError("Attribute name not found");
1996        if (!_reader_bits::readToken(line, token))
1997          throw FormatError("Attribute value not found");
1998        if (line >> c)
1999          throw FormatError("Extra character at the end of line");
2000
2001        {
2002          std::set<std::string>::iterator it = read_attr.find(attr);
2003          if (it != read_attr.end()) {
2004            std::ostringstream msg;
2005            msg << "Multiple occurence of attribute: " << attr;
2006            throw FormatError(msg.str());
2007          }
2008          read_attr.insert(attr);
2009        }
2010
2011        {
2012          typename Attributes::iterator it = _attributes.lower_bound(attr);
2013          while (it != _attributes.end() && it->first == attr) {
2014            it->second->set(token);
2015            ++it;
2016          }
2017        }
2018
2019      }
2020      if (readSuccess()) {
2021        line.putback(c);
2022      }
2023      for (typename Attributes::iterator it = _attributes.begin();
2024           it != _attributes.end(); ++it) {
2025        if (read_attr.find(it->first) == read_attr.end()) {
2026          std::ostringstream msg;
2027          msg << "Attribute not found: " << it->first;
2028          throw FormatError(msg.str());
2029        }
2030      }
2031    }
2032
2033  public:
2034
2035    /// \name Execution of the Reader
2036    /// @{
2037
2038    /// \brief Start the batch processing
2039    ///
2040    /// This function starts the batch processing
2041    void run() {
2042
2043      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2044
2045      bool nodes_done = _skip_nodes;
2046      bool edges_done = _skip_edges;
2047      bool attributes_done = false;
2048
2049      line_num = 0;
2050      readLine();
2051      skipSection();
2052
2053      while (readSuccess()) {
2054        try {
2055          char c;
2056          std::string section, caption;
2057          line >> c;
2058          _reader_bits::readToken(line, section);
2059          _reader_bits::readToken(line, caption);
2060
2061          if (line >> c)
2062            throw FormatError("Extra character at the end of line");
2063
2064          if (section == "nodes" && !nodes_done) {
2065            if (_nodes_caption.empty() || _nodes_caption == caption) {
2066              readNodes();
2067              nodes_done = true;
2068            }
2069          } else if ((section == "edges" || section == "arcs") &&
2070                     !edges_done) {
2071            if (_edges_caption.empty() || _edges_caption == caption) {
2072              readEdges();
2073              edges_done = true;
2074            }
2075          } else if (section == "attributes" && !attributes_done) {
2076            if (_attributes_caption.empty() || _attributes_caption == caption) {
2077              readAttributes();
2078              attributes_done = true;
2079            }
2080          } else {
2081            readLine();
2082            skipSection();
2083          }
2084        } catch (FormatError& error) {
2085          error.line(line_num);
2086          error.file(_filename);
2087          throw;
2088        }
2089      }
2090
2091      if (!nodes_done) {
2092        throw FormatError("Section @nodes not found");
2093      }
2094
2095      if (!edges_done) {
2096        throw FormatError("Section @edges not found");
2097      }
2098
2099      if (!attributes_done && !_attributes.empty()) {
2100        throw FormatError("Section @attributes not found");
2101      }
2102
2103    }
2104
2105    /// @}
2106
2107  };
2108
2109  /// \ingroup lemon_io
2110  ///
2111  /// \brief Return a \ref GraphReader class
2112  ///
2113  /// This function just returns a \ref GraphReader class.
2114  ///
2115  /// With this function a graph can be read from an
2116  /// \ref lgf-format "LGF" file or input stream with several maps and
2117  /// attributes. For example, there is weighted matching problem on a
2118  /// graph, i.e. a graph with a \e weight map on the edges. This
2119  /// graph can be read with the following code:
2120  ///
2121  ///\code
2122  ///ListGraph graph;
2123  ///ListGraph::EdgeMap<int> weight(graph);
2124  ///graphReader(graph, std::cin).
2125  ///  edgeMap("weight", weight).
2126  ///  run();
2127  ///\endcode
2128  ///
2129  /// For a complete documentation, please see the \ref GraphReader
2130  /// class documentation.
2131  /// \warning Don't forget to put the \ref GraphReader::run() "run()"
2132  /// to the end of the parameter list.
2133  /// \relates GraphReader
2134  /// \sa graphReader(TGR& graph, const std::string& fn)
2135  /// \sa graphReader(TGR& graph, const char* fn)
2136  template <typename TGR>
2137  GraphReader<TGR> graphReader(TGR& graph, std::istream& is) {
2138    GraphReader<TGR> tmp(graph, is);
2139    return tmp;
2140  }
2141
2142  /// \brief Return a \ref GraphReader class
2143  ///
2144  /// This function just returns a \ref GraphReader class.
2145  /// \relates GraphReader
2146  /// \sa graphReader(TGR& graph, std::istream& is)
2147  template <typename TGR>
2148  GraphReader<TGR> graphReader(TGR& graph, const std::string& fn) {
2149    GraphReader<TGR> tmp(graph, fn);
2150    return tmp;
2151  }
2152
2153  /// \brief Return a \ref GraphReader class
2154  ///
2155  /// This function just returns a \ref GraphReader class.
2156  /// \relates GraphReader
2157  /// \sa graphReader(TGR& graph, std::istream& is)
2158  template <typename TGR>
2159  GraphReader<TGR> graphReader(TGR& graph, const char* fn) {
2160    GraphReader<TGR> tmp(graph, fn);
2161    return tmp;
2162  }
2163
2164  template <typename BGR>
2165  class BpGraphReader;
2166
2167  template <typename TBGR>
2168  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is = std::cin);
2169  template <typename TBGR>
2170  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn);
2171  template <typename TBGR>
2172  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
2173
2174  /// \ingroup lemon_io
2175  ///
2176  /// \brief \ref lgf-format "LGF" reader for bipartite graphs
2177  ///
2178  /// This utility reads an \ref lgf-format "LGF" file.
2179  ///
2180  /// It can be used almost the same way as \c GraphReader, but it
2181  /// reads the red and blue nodes from separate sections, and these
2182  /// sections can contain different set of maps.
2183  ///
2184  /// The red and blue node maps are read from the corresponding
2185  /// sections. If a map is defined with the same name in both of
2186  /// these sections, then it can be read as a node map.
2187  template <typename BGR>
2188  class BpGraphReader {
2189  public:
2190
2191    typedef BGR Graph;
2192
2193  private:
2194
2195    TEMPLATE_BPGRAPH_TYPEDEFS(BGR);
2196
2197    std::istream* _is;
2198    bool local_is;
2199    std::string _filename;
2200
2201    BGR& _graph;
2202
2203    std::string _nodes_caption;
2204    std::string _edges_caption;
2205    std::string _attributes_caption;
2206
2207    typedef std::map<std::string, RedNode> RedNodeIndex;
2208    RedNodeIndex _red_node_index;
2209    typedef std::map<std::string, BlueNode> BlueNodeIndex;
2210    BlueNodeIndex _blue_node_index;
2211    typedef std::map<std::string, Edge> EdgeIndex;
2212    EdgeIndex _edge_index;
2213
2214    typedef std::vector<std::pair<std::string,
2215      _reader_bits::MapStorageBase<RedNode>*> > RedNodeMaps;
2216    RedNodeMaps _red_node_maps;
2217    typedef std::vector<std::pair<std::string,
2218      _reader_bits::MapStorageBase<BlueNode>*> > BlueNodeMaps;
2219    BlueNodeMaps _blue_node_maps;
2220
2221    typedef std::vector<std::pair<std::string,
2222      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
2223    EdgeMaps _edge_maps;
2224
2225    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
2226      Attributes;
2227    Attributes _attributes;
2228
2229    bool _use_nodes;
2230    bool _use_edges;
2231
2232    bool _skip_nodes;
2233    bool _skip_edges;
2234
2235    int line_num;
2236    std::istringstream line;
2237
2238  public:
2239
2240    /// \brief Constructor
2241    ///
2242    /// Construct an undirected graph reader, which reads from the given
2243    /// input stream.
2244    BpGraphReader(BGR& graph, std::istream& is = std::cin)
2245      : _is(&is), local_is(false), _graph(graph),
2246        _use_nodes(false), _use_edges(false),
2247        _skip_nodes(false), _skip_edges(false) {}
2248
2249    /// \brief Constructor
2250    ///
2251    /// Construct an undirected graph reader, which reads from the given
2252    /// file.
2253    BpGraphReader(BGR& graph, const std::string& fn)
2254      : _is(new std::ifstream(fn.c_str())), local_is(true),
2255        _filename(fn), _graph(graph),
2256        _use_nodes(false), _use_edges(false),
2257        _skip_nodes(false), _skip_edges(false) {
2258      if (!(*_is)) {
2259        delete _is;
2260        throw IoError("Cannot open file", fn);
2261      }
2262    }
2263
2264    /// \brief Constructor
2265    ///
2266    /// Construct an undirected graph reader, which reads from the given
2267    /// file.
2268    BpGraphReader(BGR& graph, const char* fn)
2269      : _is(new std::ifstream(fn)), local_is(true),
2270        _filename(fn), _graph(graph),
2271        _use_nodes(false), _use_edges(false),
2272        _skip_nodes(false), _skip_edges(false) {
2273      if (!(*_is)) {
2274        delete _is;
2275        throw IoError("Cannot open file", fn);
2276      }
2277    }
2278
2279    /// \brief Destructor
2280    ~BpGraphReader() {
2281      for (typename RedNodeMaps::iterator it = _red_node_maps.begin();
2282           it != _red_node_maps.end(); ++it) {
2283        delete it->second;
2284      }
2285
2286      for (typename BlueNodeMaps::iterator it = _blue_node_maps.begin();
2287           it != _blue_node_maps.end(); ++it) {
2288        delete it->second;
2289      }
2290
2291      for (typename EdgeMaps::iterator it = _edge_maps.begin();
2292           it != _edge_maps.end(); ++it) {
2293        delete it->second;
2294      }
2295
2296      for (typename Attributes::iterator it = _attributes.begin();
2297           it != _attributes.end(); ++it) {
2298        delete it->second;
2299      }
2300
2301      if (local_is) {
2302        delete _is;
2303      }
2304
2305    }
2306
2307  private:
2308    template <typename TBGR>
2309    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is);
2310    template <typename TBGR>
2311    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph,
2312                                             const std::string& fn);
2313    template <typename TBGR>
2314    friend BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char *fn);
2315
2316    BpGraphReader(BpGraphReader& other)
2317      : _is(other._is), local_is(other.local_is), _graph(other._graph),
2318        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
2319        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
2320
2321      other._is = 0;
2322      other.local_is = false;
2323
2324      _red_node_index.swap(other._red_node_index);
2325      _blue_node_index.swap(other._blue_node_index);
2326      _edge_index.swap(other._edge_index);
2327
2328      _red_node_maps.swap(other._red_node_maps);
2329      _blue_node_maps.swap(other._blue_node_maps);
2330      _edge_maps.swap(other._edge_maps);
2331      _attributes.swap(other._attributes);
2332
2333      _nodes_caption = other._nodes_caption;
2334      _edges_caption = other._edges_caption;
2335      _attributes_caption = other._attributes_caption;
2336
2337    }
2338
2339    BpGraphReader& operator=(const BpGraphReader&);
2340
2341  public:
2342
2343    /// \name Reading Rules
2344    /// @{
2345
2346    /// \brief Node map reading rule
2347    ///
2348    /// Add a node map reading rule to the reader.
2349    template <typename Map>
2350    BpGraphReader& nodeMap(const std::string& caption, Map& map) {
2351      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2352      _reader_bits::MapStorageBase<RedNode>* red_storage =
2353        new _reader_bits::MapStorage<RedNode, Map>(map);
2354      _red_node_maps.push_back(std::make_pair(caption, red_storage));
2355      _reader_bits::MapStorageBase<BlueNode>* blue_storage =
2356        new _reader_bits::MapStorage<BlueNode, Map>(map);
2357      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
2358      return *this;
2359    }
2360
2361    /// \brief Node map reading rule
2362    ///
2363    /// Add a node map reading rule with specialized converter to the
2364    /// reader.
2365    template <typename Map, typename Converter>
2366    BpGraphReader& nodeMap(const std::string& caption, Map& map,
2367                           const Converter& converter = Converter()) {
2368      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
2369      _reader_bits::MapStorageBase<RedNode>* red_storage =
2370        new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter);
2371      _red_node_maps.push_back(std::make_pair(caption, red_storage));
2372      _reader_bits::MapStorageBase<BlueNode>* blue_storage =
2373        new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
2374      _blue_node_maps.push_back(std::make_pair(caption, blue_storage));
2375      return *this;
2376    }
2377
2378    /// Add a red node map reading rule to the reader.
2379    template <typename Map>
2380    BpGraphReader& redNodeMap(const std::string& caption, Map& map) {
2381      checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>();
2382      _reader_bits::MapStorageBase<RedNode>* storage =
2383        new _reader_bits::MapStorage<RedNode, Map>(map);
2384      _red_node_maps.push_back(std::make_pair(caption, storage));
2385      return *this;
2386    }
2387
2388    /// \brief Red node map reading rule
2389    ///
2390    /// Add a red node map node reading rule with specialized converter to
2391    /// the reader.
2392    template <typename Map, typename Converter>
2393    BpGraphReader& redNodeMap(const std::string& caption, Map& map,
2394                              const Converter& converter = Converter()) {
2395      checkConcept<concepts::WriteMap<RedNode, typename Map::Value>, Map>();
2396      _reader_bits::MapStorageBase<RedNode>* storage =
2397        new _reader_bits::MapStorage<RedNode, Map, Converter>(map, converter);
2398      _red_node_maps.push_back(std::make_pair(caption, storage));
2399      return *this;
2400    }
2401
2402    /// Add a blue node map reading rule to the reader.
2403    template <typename Map>
2404    BpGraphReader& blueNodeMap(const std::string& caption, Map& map) {
2405      checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>();
2406      _reader_bits::MapStorageBase<BlueNode>* storage =
2407        new _reader_bits::MapStorage<BlueNode, Map>(map);
2408      _blue_node_maps.push_back(std::make_pair(caption, storage));
2409      return *this;
2410    }
2411
2412    /// \brief Blue node map reading rule
2413    ///
2414    /// Add a blue node map reading rule with specialized converter to
2415    /// the reader.
2416    template <typename Map, typename Converter>
2417    BpGraphReader& blueNodeMap(const std::string& caption, Map& map,
2418                               const Converter& converter = Converter()) {
2419      checkConcept<concepts::WriteMap<BlueNode, typename Map::Value>, Map>();
2420      _reader_bits::MapStorageBase<BlueNode>* storage =
2421        new _reader_bits::MapStorage<BlueNode, Map, Converter>(map, converter);
2422      _blue_node_maps.push_back(std::make_pair(caption, storage));
2423      return *this;
2424    }
2425
2426    /// \brief Edge map reading rule
2427    ///
2428    /// Add an edge map reading rule to the reader.
2429    template <typename Map>
2430    BpGraphReader& edgeMap(const std::string& caption, Map& map) {
2431      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
2432      _reader_bits::MapStorageBase<Edge>* storage =
2433        new _reader_bits::MapStorage<Edge, Map>(map);
2434      _edge_maps.push_back(std::make_pair(caption, storage));
2435      return *this;
2436    }
2437
2438    /// \brief Edge map reading rule
2439    ///
2440    /// Add an edge map reading rule with specialized converter to the
2441    /// reader.
2442    template <typename Map, typename Converter>
2443    BpGraphReader& edgeMap(const std::string& caption, Map& map,
2444                          const Converter& converter = Converter()) {
2445      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
2446      _reader_bits::MapStorageBase<Edge>* storage =
2447        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
2448      _edge_maps.push_back(std::make_pair(caption, storage));
2449      return *this;
2450    }
2451
2452    /// \brief Arc map reading rule
2453    ///
2454    /// Add an arc map reading rule to the reader.
2455    template <typename Map>
2456    BpGraphReader& arcMap(const std::string& caption, Map& map) {
2457      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
2458      _reader_bits::MapStorageBase<Edge>* forward_storage =
2459        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
2460      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
2461      _reader_bits::MapStorageBase<Edge>* backward_storage =
2462        new _reader_bits::GraphArcMapStorage<BGR, false, Map>(_graph, map);
2463      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
2464      return *this;
2465    }
2466
2467    /// \brief Arc map reading rule
2468    ///
2469    /// Add an arc map reading rule with specialized converter to the
2470    /// reader.
2471    template <typename Map, typename Converter>
2472    BpGraphReader& arcMap(const std::string& caption, Map& map,
2473                          const Converter& converter = Converter()) {
2474      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
2475      _reader_bits::MapStorageBase<Edge>* forward_storage =
2476        new _reader_bits::GraphArcMapStorage<BGR, true, Map, Converter>
2477        (_graph, map, converter);
2478      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
2479      _reader_bits::MapStorageBase<Edge>* backward_storage =
2480        new _reader_bits::GraphArcMapStorage<BGR, false, Map, Converter>
2481        (_graph, map, converter);
2482      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
2483      return *this;
2484    }
2485
2486    /// \brief Attribute reading rule
2487    ///
2488    /// Add an attribute reading rule to the reader.
2489    template <typename Value>
2490    BpGraphReader& attribute(const std::string& caption, Value& value) {
2491      _reader_bits::ValueStorageBase* storage =
2492        new _reader_bits::ValueStorage<Value>(value);
2493      _attributes.insert(std::make_pair(caption, storage));
2494      return *this;
2495    }
2496
2497    /// \brief Attribute reading rule
2498    ///
2499    /// Add an attribute reading rule with specialized converter to the
2500    /// reader.
2501    template <typename Value, typename Converter>
2502    BpGraphReader& attribute(const std::string& caption, Value& value,
2503                             const Converter& converter = Converter()) {
2504      _reader_bits::ValueStorageBase* storage =
2505        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
2506      _attributes.insert(std::make_pair(caption, storage));
2507      return *this;
2508    }
2509
2510    /// \brief Node reading rule
2511    ///
2512    /// Add a node reading rule to reader.
2513    BpGraphReader& node(const std::string& caption, Node& node) {
2514      typedef _reader_bits::DoubleMapLookUpConverter<
2515        Node, RedNodeIndex, BlueNodeIndex> Converter;
2516      Converter converter(_red_node_index, _blue_node_index);
2517      _reader_bits::ValueStorageBase* storage =
2518        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
2519      _attributes.insert(std::make_pair(caption, storage));
2520      return *this;
2521    }
2522
2523    /// \brief Red node reading rule
2524    ///
2525    /// Add a red node reading rule to reader.
2526    BpGraphReader& redNode(const std::string& caption, RedNode& node) {
2527      typedef _reader_bits::MapLookUpConverter<RedNode> Converter;
2528      Converter converter(_red_node_index);
2529      _reader_bits::ValueStorageBase* storage =
2530        new _reader_bits::ValueStorage<RedNode, Converter>(node, converter);
2531      _attributes.insert(std::make_pair(caption, storage));
2532      return *this;
2533    }
2534
2535    /// \brief Blue node reading rule
2536    ///
2537    /// Add a blue node reading rule to reader.
2538    BpGraphReader& blueNode(const std::string& caption, BlueNode& node) {
2539      typedef _reader_bits::MapLookUpConverter<BlueNode> Converter;
2540      Converter converter(_blue_node_index);
2541      _reader_bits::ValueStorageBase* storage =
2542        new _reader_bits::ValueStorage<BlueNode, Converter>(node, converter);
2543      _attributes.insert(std::make_pair(caption, storage));
2544      return *this;
2545    }
2546
2547    /// \brief Edge reading rule
2548    ///
2549    /// Add an edge reading rule to reader.
2550    BpGraphReader& edge(const std::string& caption, Edge& edge) {
2551      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
2552      Converter converter(_edge_index);
2553      _reader_bits::ValueStorageBase* storage =
2554        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
2555      _attributes.insert(std::make_pair(caption, storage));
2556      return *this;
2557    }
2558
2559    /// \brief Arc reading rule
2560    ///
2561    /// Add an arc reading rule to reader.
2562    BpGraphReader& arc(const std::string& caption, Arc& arc) {
2563      typedef _reader_bits::GraphArcLookUpConverter<BGR> Converter;
2564      Converter converter(_graph, _edge_index);
2565      _reader_bits::ValueStorageBase* storage =
2566        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
2567      _attributes.insert(std::make_pair(caption, storage));
2568      return *this;
2569    }
2570
2571    /// @}
2572
2573    /// \name Select Section by Name
2574    /// @{
2575
2576    /// \brief Set \c \@nodes section to be read
2577    ///
2578    /// Set \c \@nodes section to be read.
2579    BpGraphReader& nodes(const std::string& caption) {
2580      _nodes_caption = caption;
2581      return *this;
2582    }
2583
2584    /// \brief Set \c \@edges section to be read
2585    ///
2586    /// Set \c \@edges section to be read.
2587    BpGraphReader& edges(const std::string& caption) {
2588      _edges_caption = caption;
2589      return *this;
2590    }
2591
2592    /// \brief Set \c \@attributes section to be read
2593    ///
2594    /// Set \c \@attributes section to be read.
2595    BpGraphReader& attributes(const std::string& caption) {
2596      _attributes_caption = caption;
2597      return *this;
2598    }
2599
2600    /// @}
2601
2602    /// \name Using Previously Constructed Node or Edge Set
2603    /// @{
2604
2605    /// \brief Use previously constructed node set
2606    ///
2607    /// Use previously constructed node set, and specify the node
2608    /// label map.
2609    template <typename Map>
2610    BpGraphReader& useNodes(const Map& map) {
2611      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
2612      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
2613      _use_nodes = true;
2614      _writer_bits::DefaultConverter<typename Map::Value> converter;
2615      for (RedNodeIt n(_graph); n != INVALID; ++n) {
2616        _red_node_index.insert(std::make_pair(converter(map[n]), n));
2617      }
2618      for (BlueNodeIt n(_graph); n != INVALID; ++n) {
2619        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
2620      }
2621      return *this;
2622    }
2623
2624    /// \brief Use previously constructed node set
2625    ///
2626    /// Use previously constructed node set, and specify the node
2627    /// label map and a functor which converts the label map values to
2628    /// \c std::string.
2629    template <typename Map, typename Converter>
2630    BpGraphReader& useNodes(const Map& map,
2631                            const Converter& converter = Converter()) {
2632      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
2633      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
2634      _use_nodes = true;
2635      for (RedNodeIt n(_graph); n != INVALID; ++n) {
2636        _red_node_index.insert(std::make_pair(converter(map[n]), n));
2637      }
2638      for (BlueNodeIt n(_graph); n != INVALID; ++n) {     
2639        _blue_node_index.insert(std::make_pair(converter(map[n]), n));
2640      }
2641      return *this;
2642    }
2643
2644    /// \brief Use previously constructed edge set
2645    ///
2646    /// Use previously constructed edge set, and specify the edge
2647    /// label map.
2648    template <typename Map>
2649    BpGraphReader& useEdges(const Map& map) {
2650      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
2651      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
2652      _use_edges = true;
2653      _writer_bits::DefaultConverter<typename Map::Value> converter;
2654      for (EdgeIt a(_graph); a != INVALID; ++a) {
2655        _edge_index.insert(std::make_pair(converter(map[a]), a));
2656      }
2657      return *this;
2658    }
2659
2660    /// \brief Use previously constructed edge set
2661    ///
2662    /// Use previously constructed edge set, and specify the edge
2663    /// label map and a functor which converts the label map values to
2664    /// \c std::string.
2665    template <typename Map, typename Converter>
2666    BpGraphReader& useEdges(const Map& map,
2667                            const Converter& converter = Converter()) {
2668      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
2669      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
2670      _use_edges = true;
2671      for (EdgeIt a(_graph); a != INVALID; ++a) {
2672        _edge_index.insert(std::make_pair(converter(map[a]), a));
2673      }
2674      return *this;
2675    }
2676
2677    /// \brief Skip the reading of node section
2678    ///
2679    /// Omit the reading of the node section. This implies that each node
2680    /// map reading rule will be abandoned, and the nodes of the graph
2681    /// will not be constructed, which usually cause that the edge set
2682    /// could not be read due to lack of node name
2683    /// could not be read due to lack of node name resolving.
2684    /// Therefore \c skipEdges() function should also be used, or
2685    /// \c useNodes() should be used to specify the label of the nodes.
2686    BpGraphReader& skipNodes() {
2687      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
2688      _skip_nodes = true;
2689      return *this;
2690    }
2691
2692    /// \brief Skip the reading of edge section
2693    ///
2694    /// Omit the reading of the edge section. This implies that each edge
2695    /// map reading rule will be abandoned, and the edges of the graph
2696    /// will not be constructed.
2697    BpGraphReader& skipEdges() {
2698      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
2699      _skip_edges = true;
2700      return *this;
2701    }
2702
2703    /// @}
2704
2705  private:
2706
2707    bool readLine() {
2708      std::string str;
2709      while(++line_num, std::getline(*_is, str)) {
2710        line.clear(); line.str(str);
2711        char c;
2712        if (line >> std::ws >> c && c != '#') {
2713          line.putback(c);
2714          return true;
2715        }
2716      }
2717      return false;
2718    }
2719
2720    bool readSuccess() {
2721      return static_cast<bool>(*_is);
2722    }
2723
2724    void skipSection() {
2725      char c;
2726      while (readSuccess() && line >> c && c != '@') {
2727        readLine();
2728      }
2729      if (readSuccess()) {
2730        line.putback(c);
2731      }
2732    }
2733
2734    void readRedNodes() {
2735
2736      std::vector<int> map_index(_red_node_maps.size());
2737      int map_num, label_index;
2738
2739      char c;
2740      if (!readLine() || !(line >> c) || c == '@') {
2741        if (readSuccess() && line) line.putback(c);
2742        if (!_red_node_maps.empty())
2743          throw FormatError("Cannot find map names");
2744        return;
2745      }
2746      line.putback(c);
2747
2748      {
2749        std::map<std::string, int> maps;
2750
2751        std::string map;
2752        int index = 0;
2753        while (_reader_bits::readToken(line, map)) {
2754          if (maps.find(map) != maps.end()) {
2755            std::ostringstream msg;
2756            msg << "Multiple occurence of red node map: " << map;
2757            throw FormatError(msg.str());
2758          }
2759          maps.insert(std::make_pair(map, index));
2760          ++index;
2761        }
2762
2763        for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) {
2764          std::map<std::string, int>::iterator jt =
2765            maps.find(_red_node_maps[i].first);
2766          if (jt == maps.end()) {
2767            std::ostringstream msg;
2768            msg << "Map not found: " << _red_node_maps[i].first;
2769            throw FormatError(msg.str());
2770          }
2771          map_index[i] = jt->second;
2772        }
2773
2774        {
2775          std::map<std::string, int>::iterator jt = maps.find("label");
2776          if (jt != maps.end()) {
2777            label_index = jt->second;
2778          } else {
2779            label_index = -1;
2780          }
2781        }
2782        map_num = maps.size();
2783      }
2784
2785      while (readLine() && line >> c && c != '@') {
2786        line.putback(c);
2787
2788        std::vector<std::string> tokens(map_num);
2789        for (int i = 0; i < map_num; ++i) {
2790          if (!_reader_bits::readToken(line, tokens[i])) {
2791            std::ostringstream msg;
2792            msg << "Column not found (" << i + 1 << ")";
2793            throw FormatError(msg.str());
2794          }
2795        }
2796        if (line >> std::ws >> c)
2797          throw FormatError("Extra character at the end of line");
2798
2799        RedNode n;
2800        if (!_use_nodes) {
2801          n = _graph.addRedNode();
2802          if (label_index != -1)
2803            _red_node_index.insert(std::make_pair(tokens[label_index], n));
2804        } else {
2805          if (label_index == -1)
2806            throw FormatError("Label map not found");
2807          typename std::map<std::string, RedNode>::iterator it =
2808            _red_node_index.find(tokens[label_index]);
2809          if (it == _red_node_index.end()) {
2810            std::ostringstream msg;
2811            msg << "Node with label not found: " << tokens[label_index];
2812            throw FormatError(msg.str());
2813          }
2814          n = it->second;
2815        }
2816
2817        for (int i = 0; i < static_cast<int>(_red_node_maps.size()); ++i) {
2818          _red_node_maps[i].second->set(n, tokens[map_index[i]]);
2819        }
2820
2821      }
2822      if (readSuccess()) {
2823        line.putback(c);
2824      }
2825    }
2826
2827    void readBlueNodes() {
2828
2829      std::vector<int> map_index(_blue_node_maps.size());
2830      int map_num, label_index;
2831
2832      char c;
2833      if (!readLine() || !(line >> c) || c == '@') {
2834        if (readSuccess() && line) line.putback(c);
2835        if (!_blue_node_maps.empty())
2836          throw FormatError("Cannot find map names");
2837        return;
2838      }
2839      line.putback(c);
2840
2841      {
2842        std::map<std::string, int> maps;
2843
2844        std::string map;
2845        int index = 0;
2846        while (_reader_bits::readToken(line, map)) {
2847          if (maps.find(map) != maps.end()) {
2848            std::ostringstream msg;
2849            msg << "Multiple occurence of blue node map: " << map;
2850            throw FormatError(msg.str());
2851          }
2852          maps.insert(std::make_pair(map, index));
2853          ++index;
2854        }
2855
2856        for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) {
2857          std::map<std::string, int>::iterator jt =
2858            maps.find(_blue_node_maps[i].first);
2859          if (jt == maps.end()) {
2860            std::ostringstream msg;
2861            msg << "Map not found: " << _blue_node_maps[i].first;
2862            throw FormatError(msg.str());
2863          }
2864          map_index[i] = jt->second;
2865        }
2866
2867        {
2868          std::map<std::string, int>::iterator jt = maps.find("label");
2869          if (jt != maps.end()) {
2870            label_index = jt->second;
2871          } else {
2872            label_index = -1;
2873          }
2874        }
2875        map_num = maps.size();
2876      }
2877
2878      while (readLine() && line >> c && c != '@') {
2879        line.putback(c);
2880
2881        std::vector<std::string> tokens(map_num);
2882        for (int i = 0; i < map_num; ++i) {
2883          if (!_reader_bits::readToken(line, tokens[i])) {
2884            std::ostringstream msg;
2885            msg << "Column not found (" << i + 1 << ")";
2886            throw FormatError(msg.str());
2887          }
2888        }
2889        if (line >> std::ws >> c)
2890          throw FormatError("Extra character at the end of line");
2891
2892        BlueNode n;
2893        if (!_use_nodes) {
2894          n = _graph.addBlueNode();
2895          if (label_index != -1)
2896            _blue_node_index.insert(std::make_pair(tokens[label_index], n));
2897        } else {
2898          if (label_index == -1)
2899            throw FormatError("Label map not found");
2900          typename std::map<std::string, BlueNode>::iterator it =
2901            _blue_node_index.find(tokens[label_index]);
2902          if (it == _blue_node_index.end()) {
2903            std::ostringstream msg;
2904            msg << "Node with label not found: " << tokens[label_index];
2905            throw FormatError(msg.str());
2906          }
2907          n = it->second;
2908        }
2909
2910        for (int i = 0; i < static_cast<int>(_blue_node_maps.size()); ++i) {
2911          _blue_node_maps[i].second->set(n, tokens[map_index[i]]);
2912        }
2913
2914      }
2915      if (readSuccess()) {
2916        line.putback(c);
2917      }
2918    }
2919
2920    void readEdges() {
2921
2922      std::vector<int> map_index(_edge_maps.size());
2923      int map_num, label_index;
2924
2925      char c;
2926      if (!readLine() || !(line >> c) || c == '@') {
2927        if (readSuccess() && line) line.putback(c);
2928        if (!_edge_maps.empty())
2929          throw FormatError("Cannot find map names");
2930        return;
2931      }
2932      line.putback(c);
2933
2934      {
2935        std::map<std::string, int> maps;
2936
2937        std::string map;
2938        int index = 0;
2939        while (_reader_bits::readToken(line, map)) {
2940          if (maps.find(map) != maps.end()) {
2941            std::ostringstream msg;
2942            msg << "Multiple occurence of edge map: " << map;
2943            throw FormatError(msg.str());
2944          }
2945          maps.insert(std::make_pair(map, index));
2946          ++index;
2947        }
2948
2949        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
2950          std::map<std::string, int>::iterator jt =
2951            maps.find(_edge_maps[i].first);
2952          if (jt == maps.end()) {
2953            std::ostringstream msg;
2954            msg << "Map not found: " << _edge_maps[i].first;
2955            throw FormatError(msg.str());
2956          }
2957          map_index[i] = jt->second;
2958        }
2959
2960        {
2961          std::map<std::string, int>::iterator jt = maps.find("label");
2962          if (jt != maps.end()) {
2963            label_index = jt->second;
2964          } else {
2965            label_index = -1;
2966          }
2967        }
2968        map_num = maps.size();
2969      }
2970
2971      while (readLine() && line >> c && c != '@') {
2972        line.putback(c);
2973
2974        std::string source_token;
2975        std::string target_token;
2976
2977        if (!_reader_bits::readToken(line, source_token))
2978          throw FormatError("Red node not found");
2979
2980        if (!_reader_bits::readToken(line, target_token))
2981          throw FormatError("Blue node not found");
2982
2983        std::vector<std::string> tokens(map_num);
2984        for (int i = 0; i < map_num; ++i) {
2985          if (!_reader_bits::readToken(line, tokens[i])) {
2986            std::ostringstream msg;
2987            msg << "Column not found (" << i + 1 << ")";
2988            throw FormatError(msg.str());
2989          }
2990        }
2991        if (line >> std::ws >> c)
2992          throw FormatError("Extra character at the end of line");
2993
2994        Edge e;
2995        if (!_use_edges) {
2996          typename RedNodeIndex::iterator rit =
2997            _red_node_index.find(source_token);
2998          if (rit == _red_node_index.end()) {
2999            std::ostringstream msg;
3000            msg << "Item not found: " << source_token;
3001            throw FormatError(msg.str());
3002          }
3003          RedNode source = rit->second;
3004          typename BlueNodeIndex::iterator it =
3005            _blue_node_index.find(target_token);
3006          if (it == _blue_node_index.end()) {
3007            std::ostringstream msg;
3008            msg << "Item not found: " << target_token;
3009            throw FormatError(msg.str());
3010          }
3011          BlueNode target = it->second;
3012
3013          // It is checked that source is red and
3014          // target is blue, so this should be safe:
3015          e = _graph.addEdge(source, target);
3016          if (label_index != -1)
3017            _edge_index.insert(std::make_pair(tokens[label_index], e));
3018        } else {
3019          if (label_index == -1)
3020            throw FormatError("Label map not found");
3021          typename std::map<std::string, Edge>::iterator it =
3022            _edge_index.find(tokens[label_index]);
3023          if (it == _edge_index.end()) {
3024            std::ostringstream msg;
3025            msg << "Edge with label not found: " << tokens[label_index];
3026            throw FormatError(msg.str());
3027          }
3028          e = it->second;
3029        }
3030
3031        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
3032          _edge_maps[i].second->set(e, tokens[map_index[i]]);
3033        }
3034
3035      }
3036      if (readSuccess()) {
3037        line.putback(c);
3038      }
3039    }
3040
3041    void readAttributes() {
3042
3043      std::set<std::string> read_attr;
3044
3045      char c;
3046      while (readLine() && line >> c && c != '@') {
3047        line.putback(c);
3048
3049        std::string attr, token;
3050        if (!_reader_bits::readToken(line, attr))
3051          throw FormatError("Attribute name not found");
3052        if (!_reader_bits::readToken(line, token))
3053          throw FormatError("Attribute value not found");
3054        if (line >> c)
3055          throw FormatError("Extra character at the end of line");
3056
3057        {
3058          std::set<std::string>::iterator it = read_attr.find(attr);
3059          if (it != read_attr.end()) {
3060            std::ostringstream msg;
3061            msg << "Multiple occurence of attribute: " << attr;
3062            throw FormatError(msg.str());
3063          }
3064          read_attr.insert(attr);
3065        }
3066
3067        {
3068          typename Attributes::iterator it = _attributes.lower_bound(attr);
3069          while (it != _attributes.end() && it->first == attr) {
3070            it->second->set(token);
3071            ++it;
3072          }
3073        }
3074
3075      }
3076      if (readSuccess()) {
3077        line.putback(c);
3078      }
3079      for (typename Attributes::iterator it = _attributes.begin();
3080           it != _attributes.end(); ++it) {
3081        if (read_attr.find(it->first) == read_attr.end()) {
3082          std::ostringstream msg;
3083          msg << "Attribute not found: " << it->first;
3084          throw FormatError(msg.str());
3085        }
3086      }
3087    }
3088
3089  public:
3090
3091    /// \name Execution of the Reader
3092    /// @{
3093
3094    /// \brief Start the batch processing
3095    ///
3096    /// This function starts the batch processing
3097    void run() {
3098
3099      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
3100
3101      bool red_nodes_done = _skip_nodes;
3102      bool blue_nodes_done = _skip_nodes;
3103      bool edges_done = _skip_edges;
3104      bool attributes_done = false;
3105
3106      line_num = 0;
3107      readLine();
3108      skipSection();
3109
3110      while (readSuccess()) {
3111        try {
3112          char c;
3113          std::string section, caption;
3114          line >> c;
3115          _reader_bits::readToken(line, section);
3116          _reader_bits::readToken(line, caption);
3117
3118          if (line >> c)
3119            throw FormatError("Extra character at the end of line");
3120
3121          if (section == "red_nodes" && !red_nodes_done) {
3122            if (_nodes_caption.empty() || _nodes_caption == caption) {
3123              readRedNodes();
3124              red_nodes_done = true;
3125            }
3126          } else if (section == "blue_nodes" && !blue_nodes_done) {
3127            if (_nodes_caption.empty() || _nodes_caption == caption) {
3128              readBlueNodes();
3129              blue_nodes_done = true;
3130            }
3131          } else if ((section == "edges" || section == "arcs") &&
3132                     !edges_done) {
3133            if (_edges_caption.empty() || _edges_caption == caption) {
3134              readEdges();
3135              edges_done = true;
3136            }
3137          } else if (section == "attributes" && !attributes_done) {
3138            if (_attributes_caption.empty() || _attributes_caption == caption) {
3139              readAttributes();
3140              attributes_done = true;
3141            }
3142          } else {
3143            readLine();
3144            skipSection();
3145          }
3146        } catch (FormatError& error) {
3147          error.line(line_num);
3148          error.file(_filename);
3149          throw;
3150        }
3151      }
3152
3153      if (!red_nodes_done) {
3154        throw FormatError("Section @red_nodes not found");
3155      }
3156
3157      if (!blue_nodes_done) {
3158        throw FormatError("Section @blue_nodes not found");
3159      }
3160
3161      if (!edges_done) {
3162        throw FormatError("Section @edges not found");
3163      }
3164
3165      if (!attributes_done && !_attributes.empty()) {
3166        throw FormatError("Section @attributes not found");
3167      }
3168
3169    }
3170
3171    /// @}
3172
3173  };
3174
3175  /// \ingroup lemon_io
3176  ///
3177  /// \brief Return a \ref BpGraphReader class
3178  ///
3179  /// This function just returns a \ref BpGraphReader class.
3180  ///
3181  /// With this function a graph can be read from an
3182  /// \ref lgf-format "LGF" file or input stream with several maps and
3183  /// attributes. For example, there is bipartite weighted matching problem
3184  /// on a graph, i.e. a graph with a \e weight map on the edges. This
3185  /// graph can be read with the following code:
3186  ///
3187  ///\code
3188  ///ListBpGraph graph;
3189  ///ListBpGraph::EdgeMap<int> weight(graph);
3190  ///bpGraphReader(graph, std::cin).
3191  ///  edgeMap("weight", weight).
3192  ///  run();
3193  ///\endcode
3194  ///
3195  /// For a complete documentation, please see the \ref BpGraphReader
3196  /// class documentation.
3197  /// \warning Don't forget to put the \ref BpGraphReader::run() "run()"
3198  /// to the end of the parameter list.
3199  /// \relates BpGraphReader
3200  /// \sa bpGraphReader(TBGR& graph, const std::string& fn)
3201  /// \sa bpGraphReader(TBGR& graph, const char* fn)
3202  template <typename TBGR>
3203  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, std::istream& is) {
3204    BpGraphReader<TBGR> tmp(graph, is);
3205    return tmp;
3206  }
3207
3208  /// \brief Return a \ref BpGraphReader class
3209  ///
3210  /// This function just returns a \ref BpGraphReader class.
3211  /// \relates BpGraphReader
3212  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
3213  template <typename TBGR>
3214  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const std::string& fn) {
3215    BpGraphReader<TBGR> tmp(graph, fn);
3216    return tmp;
3217  }
3218
3219  /// \brief Return a \ref BpGraphReader class
3220  ///
3221  /// This function just returns a \ref BpGraphReader class.
3222  /// \relates BpGraphReader
3223  /// \sa bpGraphReader(TBGR& graph, std::istream& is)
3224  template <typename TBGR>
3225  BpGraphReader<TBGR> bpGraphReader(TBGR& graph, const char* fn) {
3226    BpGraphReader<TBGR> tmp(graph, fn);
3227    return tmp;
3228  }
3229
3230  class SectionReader;
3231
3232  SectionReader sectionReader(std::istream& is);
3233  SectionReader sectionReader(const std::string& fn);
3234  SectionReader sectionReader(const char* fn);
3235
3236  /// \ingroup lemon_io
3237  ///
3238  /// \brief Section reader class
3239  ///
3240  /// In the \ref lgf-format "LGF" file extra sections can be placed,
3241  /// which contain any data in arbitrary format. Such sections can be
3242  /// read with this class. A reading rule can be added to the class
3243  /// with two different functions. With the \c sectionLines() function a
3244  /// functor can process the section line-by-line, while with the \c
3245  /// sectionStream() member the section can be read from an input
3246  /// stream.
3247  class SectionReader {
3248  private:
3249
3250    std::istream* _is;
3251    bool local_is;
3252    std::string _filename;
3253
3254    typedef std::map<std::string, _reader_bits::Section*> Sections;
3255    Sections _sections;
3256
3257    int line_num;
3258    std::istringstream line;
3259
3260  public:
3261
3262    /// \brief Constructor
3263    ///
3264    /// Construct a section reader, which reads from the given input
3265    /// stream.
3266    SectionReader(std::istream& is)
3267      : _is(&is), local_is(false) {}
3268
3269    /// \brief Constructor
3270    ///
3271    /// Construct a section reader, which reads from the given file.
3272    SectionReader(const std::string& fn)
3273      : _is(new std::ifstream(fn.c_str())), local_is(true),
3274        _filename(fn) {
3275      if (!(*_is)) {
3276        delete _is;
3277        throw IoError("Cannot open file", fn);
3278      }
3279    }
3280
3281    /// \brief Constructor
3282    ///
3283    /// Construct a section reader, which reads from the given file.
3284    SectionReader(const char* fn)
3285      : _is(new std::ifstream(fn)), local_is(true),
3286        _filename(fn) {
3287      if (!(*_is)) {
3288        delete _is;
3289        throw IoError("Cannot open file", fn);
3290      }
3291    }
3292
3293    /// \brief Destructor
3294    ~SectionReader() {
3295      for (Sections::iterator it = _sections.begin();
3296           it != _sections.end(); ++it) {
3297        delete it->second;
3298      }
3299
3300      if (local_is) {
3301        delete _is;
3302      }
3303
3304    }
3305
3306  private:
3307
3308    friend SectionReader sectionReader(std::istream& is);
3309    friend SectionReader sectionReader(const std::string& fn);
3310    friend SectionReader sectionReader(const char* fn);
3311
3312    SectionReader(SectionReader& other)
3313      : _is(other._is), local_is(other.local_is) {
3314
3315      other._is = 0;
3316      other.local_is = false;
3317
3318      _sections.swap(other._sections);
3319    }
3320
3321    SectionReader& operator=(const SectionReader&);
3322
3323  public:
3324
3325    /// \name Section Readers
3326    /// @{
3327
3328    /// \brief Add a section processor with line oriented reading
3329    ///
3330    /// The first parameter is the type descriptor of the section, the
3331    /// second is a functor, which takes just one \c std::string
3332    /// parameter. At the reading process, each line of the section
3333    /// will be given to the functor object. However, the empty lines
3334    /// and the comment lines are filtered out, and the leading
3335    /// whitespaces are trimmed from each processed string.
3336    ///
3337    /// For example, let's see a section, which contain several
3338    /// integers, which should be inserted into a vector.
3339    ///\code
3340    ///  @numbers
3341    ///  12 45 23
3342    ///  4
3343    ///  23 6
3344    ///\endcode
3345    ///
3346    /// The functor is implemented as a struct:
3347    ///\code
3348    ///  struct NumberSection {
3349    ///    std::vector<int>& _data;
3350    ///    NumberSection(std::vector<int>& data) : _data(data) {}
3351    ///    void operator()(const std::string& line) {
3352    ///      std::istringstream ls(line);
3353    ///      int value;
3354    ///      while (ls >> value) _data.push_back(value);
3355    ///    }
3356    ///  };
3357    ///
3358    ///  // ...
3359    ///
3360    ///  reader.sectionLines("numbers", NumberSection(vec));
3361    ///\endcode
3362    template <typename Functor>
3363    SectionReader& sectionLines(const std::string& type, Functor functor) {
3364      LEMON_ASSERT(!type.empty(), "Type is empty.");
3365      LEMON_ASSERT(_sections.find(type) == _sections.end(),
3366                   "Multiple reading of section.");
3367      _sections.insert(std::make_pair(type,
3368        new _reader_bits::LineSection<Functor>(functor)));
3369      return *this;
3370    }
3371
3372
3373    /// \brief Add a section processor with stream oriented reading
3374    ///
3375    /// The first parameter is the type of the section, the second is
3376    /// a functor, which takes an \c std::istream& and an \c int&
3377    /// parameter, the latter regard to the line number of stream. The
3378    /// functor can read the input while the section go on, and the
3379    /// line number should be modified accordingly.
3380    template <typename Functor>
3381    SectionReader& sectionStream(const std::string& type, Functor functor) {
3382      LEMON_ASSERT(!type.empty(), "Type is empty.");
3383      LEMON_ASSERT(_sections.find(type) == _sections.end(),
3384                   "Multiple reading of section.");
3385      _sections.insert(std::make_pair(type,
3386         new _reader_bits::StreamSection<Functor>(functor)));
3387      return *this;
3388    }
3389
3390    /// @}
3391
3392  private:
3393
3394    bool readLine() {
3395      std::string str;
3396      while(++line_num, std::getline(*_is, str)) {
3397        line.clear(); line.str(str);
3398        char c;
3399        if (line >> std::ws >> c && c != '#') {
3400          line.putback(c);
3401          return true;
3402        }
3403      }
3404      return false;
3405    }
3406
3407    bool readSuccess() {
3408      return static_cast<bool>(*_is);
3409    }
3410
3411    void skipSection() {
3412      char c;
3413      while (readSuccess() && line >> c && c != '@') {
3414        readLine();
3415      }
3416      if (readSuccess()) {
3417        line.putback(c);
3418      }
3419    }
3420
3421  public:
3422
3423
3424    /// \name Execution of the Reader
3425    /// @{
3426
3427    /// \brief Start the batch processing
3428    ///
3429    /// This function starts the batch processing.
3430    void run() {
3431
3432      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
3433
3434      std::set<std::string> extra_sections;
3435
3436      line_num = 0;
3437      readLine();
3438      skipSection();
3439
3440      while (readSuccess()) {
3441        try {
3442          char c;
3443          std::string section, caption;
3444          line >> c;
3445          _reader_bits::readToken(line, section);
3446          _reader_bits::readToken(line, caption);
3447
3448          if (line >> c)
3449            throw FormatError("Extra character at the end of line");
3450
3451          if (extra_sections.find(section) != extra_sections.end()) {
3452            std::ostringstream msg;
3453            msg << "Multiple occurence of section: " << section;
3454            throw FormatError(msg.str());
3455          }
3456          Sections::iterator it = _sections.find(section);
3457          if (it != _sections.end()) {
3458            extra_sections.insert(section);
3459            it->second->process(*_is, line_num);
3460          }
3461          readLine();
3462          skipSection();
3463        } catch (FormatError& error) {
3464          error.line(line_num);
3465          error.file(_filename);
3466          throw;
3467        }
3468      }
3469      for (Sections::iterator it = _sections.begin();
3470           it != _sections.end(); ++it) {
3471        if (extra_sections.find(it->first) == extra_sections.end()) {
3472          std::ostringstream os;
3473          os << "Cannot find section: " << it->first;
3474          throw FormatError(os.str());
3475        }
3476      }
3477    }
3478
3479    /// @}
3480
3481  };
3482
3483  /// \ingroup lemon_io
3484  ///
3485  /// \brief Return a \ref SectionReader class
3486  ///
3487  /// This function just returns a \ref SectionReader class.
3488  ///
3489  /// Please see SectionReader documentation about the custom section
3490  /// input.
3491  ///
3492  /// \relates SectionReader
3493  /// \sa sectionReader(const std::string& fn)
3494  /// \sa sectionReader(const char *fn)
3495  inline SectionReader sectionReader(std::istream& is) {
3496    SectionReader tmp(is);
3497    return tmp;
3498  }
3499
3500  /// \brief Return a \ref SectionReader class
3501  ///
3502  /// This function just returns a \ref SectionReader class.
3503  /// \relates SectionReader
3504  /// \sa sectionReader(std::istream& is)
3505  inline SectionReader sectionReader(const std::string& fn) {
3506    SectionReader tmp(fn);
3507    return tmp;
3508  }
3509
3510  /// \brief Return a \ref SectionReader class
3511  ///
3512  /// This function just returns a \ref SectionReader class.
3513  /// \relates SectionReader
3514  /// \sa sectionReader(std::istream& is)
3515  inline SectionReader sectionReader(const char* fn) {
3516    SectionReader tmp(fn);
3517    return tmp;
3518  }
3519
3520  /// \ingroup lemon_io
3521  ///
3522  /// \brief Reader for the contents of the \ref lgf-format "LGF" file
3523  ///
3524  /// This class can be used to read the sections, the map names and
3525  /// the attributes from a file. Usually, the LEMON programs know
3526  /// that, which type of graph, which maps and which attributes
3527  /// should be read from a file, but in general tools (like glemon)
3528  /// the contents of an LGF file should be guessed somehow. This class
3529  /// reads the graph and stores the appropriate information for
3530  /// reading the graph.
3531  ///
3532  ///\code
3533  /// LgfContents contents("graph.lgf");
3534  /// contents.run();
3535  ///
3536  /// // Does it contain any node section and arc section?
3537  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
3538  ///   std::cerr << "Failure, cannot find graph." << std::endl;
3539  ///   return -1;
3540  /// }
3541  /// std::cout << "The name of the default node section: "
3542  ///           << contents.nodeSection(0) << std::endl;
3543  /// std::cout << "The number of the arc maps: "
3544  ///           << contents.arcMaps(0).size() << std::endl;
3545  /// std::cout << "The name of second arc map: "
3546  ///           << contents.arcMaps(0)[1] << std::endl;
3547  ///\endcode
3548  class LgfContents {
3549  private:
3550
3551    std::istream* _is;
3552    bool local_is;
3553
3554    std::vector<std::string> _node_sections;
3555    std::vector<std::string> _edge_sections;
3556    std::vector<std::string> _attribute_sections;
3557    std::vector<std::string> _extra_sections;
3558
3559    std::vector<bool> _arc_sections;
3560
3561    std::vector<std::vector<std::string> > _node_maps;
3562    std::vector<std::vector<std::string> > _edge_maps;
3563
3564    std::vector<std::vector<std::string> > _attributes;
3565
3566
3567    int line_num;
3568    std::istringstream line;
3569
3570  public:
3571
3572    /// \brief Constructor
3573    ///
3574    /// Construct an \e LGF contents reader, which reads from the given
3575    /// input stream.
3576    LgfContents(std::istream& is)
3577      : _is(&is), local_is(false) {}
3578
3579    /// \brief Constructor
3580    ///
3581    /// Construct an \e LGF contents reader, which reads from the given
3582    /// file.
3583    LgfContents(const std::string& fn)
3584      : _is(new std::ifstream(fn.c_str())), local_is(true) {
3585      if (!(*_is)) {
3586        delete _is;
3587        throw IoError("Cannot open file", fn);
3588      }
3589    }
3590
3591    /// \brief Constructor
3592    ///
3593    /// Construct an \e LGF contents reader, which reads from the given
3594    /// file.
3595    LgfContents(const char* fn)
3596      : _is(new std::ifstream(fn)), local_is(true) {
3597      if (!(*_is)) {
3598        delete _is;
3599        throw IoError("Cannot open file", fn);
3600      }
3601    }
3602
3603    /// \brief Destructor
3604    ~LgfContents() {
3605      if (local_is) delete _is;
3606    }
3607
3608  private:
3609
3610    LgfContents(const LgfContents&);
3611    LgfContents& operator=(const LgfContents&);
3612
3613  public:
3614
3615
3616    /// \name Node Sections
3617    /// @{
3618
3619    /// \brief Gives back the number of node sections in the file.
3620    ///
3621    /// Gives back the number of node sections in the file.
3622    int nodeSectionNum() const {
3623      return _node_sections.size();
3624    }
3625
3626    /// \brief Returns the node section name at the given position.
3627    ///
3628    /// Returns the node section name at the given position.
3629    const std::string& nodeSection(int i) const {
3630      return _node_sections[i];
3631    }
3632
3633    /// \brief Gives back the node maps for the given section.
3634    ///
3635    /// Gives back the node maps for the given section.
3636    const std::vector<std::string>& nodeMapNames(int i) const {
3637      return _node_maps[i];
3638    }
3639
3640    /// @}
3641
3642    /// \name Arc/Edge Sections
3643    /// @{
3644
3645    /// \brief Gives back the number of arc/edge sections in the file.
3646    ///
3647    /// Gives back the number of arc/edge sections in the file.
3648    /// \note It is synonym of \c edgeSectionNum().
3649    int arcSectionNum() const {
3650      return _edge_sections.size();
3651    }
3652
3653    /// \brief Returns the arc/edge section name at the given position.
3654    ///
3655    /// Returns the arc/edge section name at the given position.
3656    /// \note It is synonym of \c edgeSection().
3657    const std::string& arcSection(int i) const {
3658      return _edge_sections[i];
3659    }
3660
3661    /// \brief Gives back the arc/edge maps for the given section.
3662    ///
3663    /// Gives back the arc/edge maps for the given section.
3664    /// \note It is synonym of \c edgeMapNames().
3665    const std::vector<std::string>& arcMapNames(int i) const {
3666      return _edge_maps[i];
3667    }
3668
3669    /// @}
3670
3671    /// \name Synonyms
3672    /// @{
3673
3674    /// \brief Gives back the number of arc/edge sections in the file.
3675    ///
3676    /// Gives back the number of arc/edge sections in the file.
3677    /// \note It is synonym of \c arcSectionNum().
3678    int edgeSectionNum() const {
3679      return _edge_sections.size();
3680    }
3681
3682    /// \brief Returns the section name at the given position.
3683    ///
3684    /// Returns the section name at the given position.
3685    /// \note It is synonym of \c arcSection().
3686    const std::string& edgeSection(int i) const {
3687      return _edge_sections[i];
3688    }
3689
3690    /// \brief Gives back the edge maps for the given section.
3691    ///
3692    /// Gives back the edge maps for the given section.
3693    /// \note It is synonym of \c arcMapNames().
3694    const std::vector<std::string>& edgeMapNames(int i) const {
3695      return _edge_maps[i];
3696    }
3697
3698    /// @}
3699
3700    /// \name Attribute Sections
3701    /// @{
3702
3703    /// \brief Gives back the number of attribute sections in the file.
3704    ///
3705    /// Gives back the number of attribute sections in the file.
3706    int attributeSectionNum() const {
3707      return _attribute_sections.size();
3708    }
3709
3710    /// \brief Returns the attribute section name at the given position.
3711    ///
3712    /// Returns the attribute section name at the given position.
3713    const std::string& attributeSectionNames(int i) const {
3714      return _attribute_sections[i];
3715    }
3716
3717    /// \brief Gives back the attributes for the given section.
3718    ///
3719    /// Gives back the attributes for the given section.
3720    const std::vector<std::string>& attributes(int i) const {
3721      return _attributes[i];
3722    }
3723
3724    /// @}
3725
3726    /// \name Extra Sections
3727    /// @{
3728
3729    /// \brief Gives back the number of extra sections in the file.
3730    ///
3731    /// Gives back the number of extra sections in the file.
3732    int extraSectionNum() const {
3733      return _extra_sections.size();
3734    }
3735
3736    /// \brief Returns the extra section type at the given position.
3737    ///
3738    /// Returns the section type at the given position.
3739    const std::string& extraSection(int i) const {
3740      return _extra_sections[i];
3741    }
3742
3743    /// @}
3744
3745  private:
3746
3747    bool readLine() {
3748      std::string str;
3749      while(++line_num, std::getline(*_is, str)) {
3750        line.clear(); line.str(str);
3751        char c;
3752        if (line >> std::ws >> c && c != '#') {
3753          line.putback(c);
3754          return true;
3755        }
3756      }
3757      return false;
3758    }
3759
3760    bool readSuccess() {
3761      return static_cast<bool>(*_is);
3762    }
3763
3764    void skipSection() {
3765      char c;
3766      while (readSuccess() && line >> c && c != '@') {
3767        readLine();
3768      }
3769      if (readSuccess()) {
3770        line.putback(c);
3771      }
3772    }
3773
3774    void readMaps(std::vector<std::string>& maps) {
3775      char c;
3776      if (!readLine() || !(line >> c) || c == '@') {
3777        if (readSuccess() && line) line.putback(c);
3778        return;
3779      }
3780      line.putback(c);
3781      std::string map;
3782      while (_reader_bits::readToken(line, map)) {
3783        maps.push_back(map);
3784      }
3785    }
3786
3787    void readAttributes(std::vector<std::string>& attrs) {
3788      readLine();
3789      char c;
3790      while (readSuccess() && line >> c && c != '@') {
3791        line.putback(c);
3792        std::string attr;
3793        _reader_bits::readToken(line, attr);
3794        attrs.push_back(attr);
3795        readLine();
3796      }
3797      line.putback(c);
3798    }
3799
3800  public:
3801
3802    /// \name Execution of the Contents Reader
3803    /// @{
3804
3805    /// \brief Starts the reading
3806    ///
3807    /// This function starts the reading.
3808    void run() {
3809
3810      readLine();
3811      skipSection();
3812
3813      while (readSuccess()) {
3814
3815        char c;
3816        line >> c;
3817
3818        std::string section, caption;
3819        _reader_bits::readToken(line, section);
3820        _reader_bits::readToken(line, caption);
3821
3822        if (section == "nodes") {
3823          _node_sections.push_back(caption);
3824          _node_maps.push_back(std::vector<std::string>());
3825          readMaps(_node_maps.back());
3826          readLine(); skipSection();
3827        } else if (section == "arcs" || section == "edges") {
3828          _edge_sections.push_back(caption);
3829          _arc_sections.push_back(section == "arcs");
3830          _edge_maps.push_back(std::vector<std::string>());
3831          readMaps(_edge_maps.back());
3832          readLine(); skipSection();
3833        } else if (section == "attributes") {
3834          _attribute_sections.push_back(caption);
3835          _attributes.push_back(std::vector<std::string>());
3836          readAttributes(_attributes.back());
3837        } else {
3838          _extra_sections.push_back(section);
3839          readLine(); skipSection();
3840        }
3841      }
3842    }
3843
3844    /// @}
3845
3846  };
3847}
3848
3849#endif
Note: See TracBrowser for help on using the repository browser.