COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 197:5893bacaa720

Last change on this file since 197:5893bacaa720 was 197:5893bacaa720, checked in by Balazs Dezso <deba@…>, 16 years ago

Set inline functions in header files (ticket #115)

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