COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/lgf_reader.h @ 260:c691064dfd4f

Last change on this file since 260:c691064dfd4f was 236:da953e387d31, checked in by Akos Ladanyi <ladanyi@…>, 16 years ago

Unify the spelling of LEMON (#103).

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