COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 206:4e22275a2b52

Last change on this file since 206:4e22275a2b52 was 190:1e6af6f0843c, checked in by Balazs Dezso <deba@…>, 11 years ago

Move to private copy constrcutors

File size: 71.5 KB
Line 
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
21///\brief 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/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
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    bool isWhiteSpace(char c) {
199      return c == ' ' || c == '\t' || c == '\v' ||
200        c == '\n' || c == '\r' || c == '\f';
201    }
202   
203    bool isOct(char c) {
204      return '0' <= c && c <='7';
205    }
206   
207    int valueOct(char c) {
208      LEMON_ASSERT(isOct(c), "The character is not octal.");
209      return c - '0';
210    }
211
212    bool isHex(char c) {
213      return ('0' <= c && c <= '9') ||
214        ('a' <= c && c <= 'z') ||
215        ('A' <= c && c <= 'Z');
216    }
217   
218    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    bool isIdentifierFirstChar(char c) {
226      return ('a' <= c && c <= 'z') ||
227        ('A' <= c && c <= 'Z') || c == '_';
228    }
229
230    bool isIdentifierChar(char c) {
231      return isIdentifierFirstChar(c) ||
232        ('0' <= c && c <= '9');
233    }
234
235    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    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 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 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  /// is converted to the map's value type. 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 function is multipass reading, which is
441  /// important if two \e \@arcs sections must be read from the
442  /// file. In this example 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. It is impossible read this in
448  /// a single pass, because the arcs are not constructed when the node
449  /// maps are read.
450  template <typename _Digraph>
451  class DigraphReader {
452  public:
453
454    typedef _Digraph Digraph;
455    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
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
489    bool _skip_nodes;
490    bool _skip_arcs;
491
492    int line_num;
493    std::istringstream line;
494
495  public:
496
497    /// \brief Constructor
498    ///
499    /// Construct a directed graph reader, which reads from the given
500    /// input stream.
501    DigraphReader(std::istream& is, Digraph& digraph)
502      : _is(&is), local_is(false), _digraph(digraph),
503        _use_nodes(false), _use_arcs(false),
504        _skip_nodes(false), _skip_arcs(false) {}
505
506    /// \brief Constructor
507    ///
508    /// Construct a directed graph reader, which reads from the given
509    /// file.
510    DigraphReader(const std::string& fn, Digraph& digraph)
511      : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
512        _use_nodes(false), _use_arcs(false),
513        _skip_nodes(false), _skip_arcs(false) {}
514   
515    /// \brief Constructor
516    ///
517    /// Construct a directed graph reader, which reads from the given
518    /// file.
519    DigraphReader(const char* fn, Digraph& digraph)
520      : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
521        _use_nodes(false), _use_arcs(false),
522        _skip_nodes(false), _skip_arcs(false) {}
523
524    /// \brief Destructor
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:
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
577    DigraphReader& operator=(const DigraphReader&);
578
579  public:
580
581    /// \name Reading rules
582    /// @{
583   
584    /// \brief Node map reading rule
585    ///
586    /// Add a node map reading rule to the reader.
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
596    /// \brief Node map reading rule
597    ///
598    /// Add a node map reading rule with specialized converter to the
599    /// reader.
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
610    /// \brief Arc map reading rule
611    ///
612    /// Add an arc map reading rule to the reader.
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
622    /// \brief Arc map reading rule
623    ///
624    /// Add an arc map reading rule with specialized converter to the
625    /// reader.
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
636    /// \brief Attribute reading rule
637    ///
638    /// Add an attribute reading rule to the reader.
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
647    /// \brief Attribute reading rule
648    ///
649    /// Add an attribute reading rule with specialized converter to the
650    /// reader.
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
660    /// \brief Node reading rule
661    ///
662    /// Add a node reading rule to reader.
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
672    /// \brief Arc reading rule
673    ///
674    /// Add an arc reading rule to reader.
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
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
692    DigraphReader& nodes(const std::string& caption) {
693      _nodes_caption = caption;
694      return *this;
695    }
696
697    /// \brief Set \c \@arcs section to be read
698    ///
699    /// Set \c \@arcs section to be read
700    DigraphReader& arcs(const std::string& caption) {
701      _arcs_caption = caption;
702      return *this;
703    }
704
705    /// \brief Set \c \@attributes section to be read
706    ///
707    /// Set \c \@attributes section to be read
708    DigraphReader& attributes(const std::string& caption) {
709      _attributes_caption = caption;
710      return *this;
711    }
712
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.
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
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
738    /// std::string.
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
751    /// \brief Use previously constructed arc set
752    ///
753    /// Use previously constructed arc set, and specify the arc
754    /// label map.
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
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
771    /// std::string.
772    template <typename Map, typename Converter>
773    DigraphReader& useArcs(const Map& map,
774                           const Converter& converter = Converter()) {
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
784    /// \brief Skips the reading of node section
785    ///
786    /// Omit the reading of the node section. This implies that each node
787    /// map reading rule will be abanoned, and the nodes of the graph
788    /// will not be constructed, which usually cause that the arc set
789    /// could not be read due to lack of node name
790    /// resolving. Therefore, the \c skipArcs() should be used too, or
791    /// the useNodes() member function should be used to specify the
792    /// 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 abanoned, 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  /// \relates DigraphReader
1179  template <typename Digraph>
1180  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
1181    DigraphReader<Digraph> tmp(is, digraph);
1182    return tmp;
1183  }
1184
1185  /// \relates DigraphReader
1186  template <typename Digraph>
1187  DigraphReader<Digraph> digraphReader(const std::string& fn,
1188                                       Digraph& digraph) {
1189    DigraphReader<Digraph> tmp(fn, digraph);
1190    return tmp;
1191  }
1192
1193  /// \relates DigraphReader
1194  template <typename Digraph>
1195  DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
1196    DigraphReader<Digraph> tmp(fn, digraph);
1197    return tmp;
1198  }
1199
1200  template <typename Graph>
1201  class GraphReader;
1202
1203  template <typename Graph>
1204  GraphReader<Graph> graphReader(std::istream& is, Graph& graph);   
1205
1206  template <typename Graph>
1207  GraphReader<Graph> graphReader(const std::string& fn, Graph& graph);   
1208
1209  template <typename Graph>
1210  GraphReader<Graph> graphReader(const char *fn, Graph& graph);   
1211
1212  /// \ingroup lemon_io
1213  /// 
1214  /// \brief LGF reader for undirected graphs
1215  ///
1216  /// This utility reads an \ref lgf-format "LGF" file.
1217  template <typename _Graph>
1218  class GraphReader {
1219  public:
1220
1221    typedef _Graph Graph;
1222    TEMPLATE_GRAPH_TYPEDEFS(Graph);
1223   
1224  private:
1225
1226    std::istream* _is;
1227    bool local_is;
1228
1229    Graph& _graph;
1230
1231    std::string _nodes_caption;
1232    std::string _edges_caption;
1233    std::string _attributes_caption;
1234
1235    typedef std::map<std::string, Node> NodeIndex;
1236    NodeIndex _node_index;
1237    typedef std::map<std::string, Edge> EdgeIndex;
1238    EdgeIndex _edge_index;
1239   
1240    typedef std::vector<std::pair<std::string,
1241      _reader_bits::MapStorageBase<Node>*> > NodeMaps;   
1242    NodeMaps _node_maps;
1243
1244    typedef std::vector<std::pair<std::string,
1245      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;
1246    EdgeMaps _edge_maps;
1247
1248    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
1249      Attributes;
1250    Attributes _attributes;
1251
1252    bool _use_nodes;
1253    bool _use_edges;
1254
1255    bool _skip_nodes;
1256    bool _skip_edges;
1257
1258    int line_num;
1259    std::istringstream line;
1260
1261  public:
1262
1263    /// \brief Constructor
1264    ///
1265    /// Construct a undirected graph reader, which reads from the given
1266    /// input stream.
1267    GraphReader(std::istream& is, Graph& graph)
1268      : _is(&is), local_is(false), _graph(graph),
1269        _use_nodes(false), _use_edges(false),
1270        _skip_nodes(false), _skip_edges(false) {}
1271
1272    /// \brief Constructor
1273    ///
1274    /// Construct a undirected graph reader, which reads from the given
1275    /// file.
1276    GraphReader(const std::string& fn, Graph& graph)
1277      : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
1278        _use_nodes(false), _use_edges(false),
1279        _skip_nodes(false), _skip_edges(false) {}
1280   
1281    /// \brief Constructor
1282    ///
1283    /// Construct a undirected graph reader, which reads from the given
1284    /// file.
1285    GraphReader(const char* fn, Graph& graph)
1286      : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
1287        _use_nodes(false), _use_edges(false),
1288        _skip_nodes(false), _skip_edges(false) {}
1289
1290    /// \brief Destructor
1291    ~GraphReader() {
1292      for (typename NodeMaps::iterator it = _node_maps.begin();
1293           it != _node_maps.end(); ++it) {
1294        delete it->second;
1295      }
1296
1297      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1298           it != _edge_maps.end(); ++it) {
1299        delete it->second;
1300      }
1301
1302      for (typename Attributes::iterator it = _attributes.begin();
1303           it != _attributes.end(); ++it) {
1304        delete it->second;
1305      }
1306
1307      if (local_is) {
1308        delete _is;
1309      }
1310
1311    }
1312
1313  private:
1314    friend GraphReader<Graph> graphReader<>(std::istream& is, Graph& graph);   
1315    friend GraphReader<Graph> graphReader<>(const std::string& fn,
1316                                            Graph& graph);   
1317    friend GraphReader<Graph> graphReader<>(const char *fn, Graph& graph);   
1318
1319    GraphReader(GraphReader& other)
1320      : _is(other._is), local_is(other.local_is), _graph(other._graph),
1321        _use_nodes(other._use_nodes), _use_edges(other._use_edges),
1322        _skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {
1323
1324      other._is = 0;
1325      other.local_is = false;
1326     
1327      _node_index.swap(other._node_index);
1328      _edge_index.swap(other._edge_index);
1329
1330      _node_maps.swap(other._node_maps);
1331      _edge_maps.swap(other._edge_maps);
1332      _attributes.swap(other._attributes);
1333
1334      _nodes_caption = other._nodes_caption;
1335      _edges_caption = other._edges_caption;
1336      _attributes_caption = other._attributes_caption;
1337
1338    }
1339
1340    GraphReader& operator=(const GraphReader&);
1341
1342  public:
1343
1344    /// \name Reading rules
1345    /// @{
1346   
1347    /// \brief Node map reading rule
1348    ///
1349    /// Add a node map reading rule to the reader.
1350    template <typename Map>
1351    GraphReader& nodeMap(const std::string& caption, Map& map) {
1352      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1353      _reader_bits::MapStorageBase<Node>* storage =
1354        new _reader_bits::MapStorage<Node, Map>(map);
1355      _node_maps.push_back(std::make_pair(caption, storage));
1356      return *this;
1357    }
1358
1359    /// \brief Node map reading rule
1360    ///
1361    /// Add a node map reading rule with specialized converter to the
1362    /// reader.
1363    template <typename Map, typename Converter>
1364    GraphReader& nodeMap(const std::string& caption, Map& map,
1365                           const Converter& converter = Converter()) {
1366      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1367      _reader_bits::MapStorageBase<Node>* storage =
1368        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1369      _node_maps.push_back(std::make_pair(caption, storage));
1370      return *this;
1371    }
1372
1373    /// \brief Edge map reading rule
1374    ///
1375    /// Add an edge map reading rule to the reader.
1376    template <typename Map>
1377    GraphReader& edgeMap(const std::string& caption, Map& map) {
1378      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1379      _reader_bits::MapStorageBase<Edge>* storage =
1380        new _reader_bits::MapStorage<Edge, Map>(map);
1381      _edge_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 with specialized converter to the
1388    /// reader.
1389    template <typename Map, typename Converter>
1390    GraphReader& edgeMap(const std::string& caption, Map& map,
1391                          const Converter& converter = Converter()) {
1392      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1393      _reader_bits::MapStorageBase<Edge>* storage =
1394        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1395      _edge_maps.push_back(std::make_pair(caption, storage));
1396      return *this;
1397    }
1398
1399    /// \brief Arc map reading rule
1400    ///
1401    /// Add an arc map reading rule to the reader.
1402    template <typename Map>
1403    GraphReader& arcMap(const std::string& caption, Map& map) {
1404      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1405      _reader_bits::MapStorageBase<Edge>* forward_storage =
1406        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1407      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1408      _reader_bits::MapStorageBase<Edge>* backward_storage =
1409        new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1410      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1411      return *this;
1412    }
1413
1414    /// \brief Arc map reading rule
1415    ///
1416    /// Add an arc map reading rule with specialized converter to the
1417    /// reader.
1418    template <typename Map, typename Converter>
1419    GraphReader& arcMap(const std::string& caption, Map& map,
1420                          const Converter& converter = Converter()) {
1421      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1422      _reader_bits::MapStorageBase<Edge>* forward_storage =
1423        new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1424        (_graph, map, converter);
1425      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1426      _reader_bits::MapStorageBase<Edge>* backward_storage =
1427        new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1428        (_graph, map, converter);
1429      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1430      return *this;
1431    }
1432
1433    /// \brief Attribute reading rule
1434    ///
1435    /// Add an attribute reading rule to the reader.
1436    template <typename Value>
1437    GraphReader& attribute(const std::string& caption, Value& value) {
1438      _reader_bits::ValueStorageBase* storage =
1439        new _reader_bits::ValueStorage<Value>(value);
1440      _attributes.insert(std::make_pair(caption, storage));
1441      return *this;
1442    }
1443
1444    /// \brief Attribute reading rule
1445    ///
1446    /// Add an attribute reading rule with specialized converter to the
1447    /// reader.
1448    template <typename Value, typename Converter>
1449    GraphReader& attribute(const std::string& caption, Value& value,
1450                             const Converter& converter = Converter()) {
1451      _reader_bits::ValueStorageBase* storage =
1452        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1453      _attributes.insert(std::make_pair(caption, storage));
1454      return *this;
1455    }
1456
1457    /// \brief Node reading rule
1458    ///
1459    /// Add a node reading rule to reader.
1460    GraphReader& node(const std::string& caption, Node& node) {
1461      typedef _reader_bits::MapLookUpConverter<Node> Converter;
1462      Converter converter(_node_index);
1463      _reader_bits::ValueStorageBase* storage =
1464        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1465      _attributes.insert(std::make_pair(caption, storage));
1466      return *this;
1467    }
1468
1469    /// \brief Edge reading rule
1470    ///
1471    /// Add an edge reading rule to reader.
1472    GraphReader& edge(const std::string& caption, Edge& edge) {
1473      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1474      Converter converter(_edge_index);
1475      _reader_bits::ValueStorageBase* storage =
1476        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1477      _attributes.insert(std::make_pair(caption, storage));
1478      return *this;
1479    }
1480
1481    /// \brief Arc reading rule
1482    ///
1483    /// Add an arc reading rule to reader.
1484    GraphReader& arc(const std::string& caption, Arc& arc) {
1485      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
1486      Converter converter(_graph, _edge_index);
1487      _reader_bits::ValueStorageBase* storage =
1488        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1489      _attributes.insert(std::make_pair(caption, storage));
1490      return *this;
1491    }
1492
1493    /// @}
1494
1495    /// \name Select section by name
1496    /// @{
1497
1498    /// \brief Set \c \@nodes section to be read
1499    ///
1500    /// Set \c \@nodes section to be read
1501    GraphReader& nodes(const std::string& caption) {
1502      _nodes_caption = caption;
1503      return *this;
1504    }
1505
1506    /// \brief Set \c \@edges section to be read
1507    ///
1508    /// Set \c \@edges section to be read
1509    GraphReader& edges(const std::string& caption) {
1510      _edges_caption = caption;
1511      return *this;
1512    }
1513
1514    /// \brief Set \c \@attributes section to be read
1515    ///
1516    /// Set \c \@attributes section to be read
1517    GraphReader& attributes(const std::string& caption) {
1518      _attributes_caption = caption;
1519      return *this;
1520    }
1521
1522    /// @}
1523
1524    /// \name Using previously constructed node or edge set
1525    /// @{
1526
1527    /// \brief Use previously constructed node set
1528    ///
1529    /// Use previously constructed node set, and specify the node
1530    /// label map.
1531    template <typename Map>
1532    GraphReader& useNodes(const Map& map) {
1533      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1534      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1535      _use_nodes = true;
1536      _writer_bits::DefaultConverter<typename Map::Value> converter;
1537      for (NodeIt n(_graph); n != INVALID; ++n) {
1538        _node_index.insert(std::make_pair(converter(map[n]), n));
1539      }
1540      return *this;
1541    }
1542
1543    /// \brief Use previously constructed node set
1544    ///
1545    /// Use previously constructed node set, and specify the node
1546    /// label map and a functor which converts the label map values to
1547    /// std::string.
1548    template <typename Map, typename Converter>
1549    GraphReader& useNodes(const Map& map,
1550                            const Converter& converter = Converter()) {
1551      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1552      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1553      _use_nodes = true;
1554      for (NodeIt n(_graph); n != INVALID; ++n) {
1555        _node_index.insert(std::make_pair(converter(map[n]), n));
1556      }
1557      return *this;
1558    }
1559
1560    /// \brief Use previously constructed edge set
1561    ///
1562    /// Use previously constructed edge set, and specify the edge
1563    /// label map.
1564    template <typename Map>
1565    GraphReader& useEdges(const Map& map) {
1566      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1567      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1568      _use_edges = true;
1569      _writer_bits::DefaultConverter<typename Map::Value> converter;
1570      for (EdgeIt a(_graph); a != INVALID; ++a) {
1571        _edge_index.insert(std::make_pair(converter(map[a]), a));
1572      }
1573      return *this;
1574    }
1575
1576    /// \brief Use previously constructed edge set
1577    ///
1578    /// Use previously constructed edge set, and specify the edge
1579    /// label map and a functor which converts the label map values to
1580    /// std::string.
1581    template <typename Map, typename Converter>
1582    GraphReader& useEdges(const Map& map,
1583                            const Converter& converter = Converter()) {
1584      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1585      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1586      _use_edges = true;
1587      for (EdgeIt a(_graph); a != INVALID; ++a) {
1588        _edge_index.insert(std::make_pair(converter(map[a]), a));
1589      }
1590      return *this;
1591    }
1592
1593    /// \brief Skips the reading of node section
1594    ///
1595    /// Omit the reading of the node section. This implies that each node
1596    /// map reading rule will be abanoned, and the nodes of the graph
1597    /// will not be constructed, which usually cause that the edge set
1598    /// could not be read due to lack of node name
1599    /// resolving. Therefore, the \c skipEdges() should be used too, or
1600    /// the useNodes() member function should be used to specify the
1601    /// label of the nodes.
1602    GraphReader& skipNodes() {
1603      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
1604      _skip_nodes = true;
1605      return *this;
1606    }
1607
1608    /// \brief Skips the reading of edge section
1609    ///
1610    /// Omit the reading of the edge section. This implies that each edge
1611    /// map reading rule will be abanoned, and the edges of the graph
1612    /// will not be constructed.
1613    GraphReader& skipEdges() {
1614      LEMON_ASSERT(!_skip_edges, "Skip edges already set");
1615      _skip_edges = true;
1616      return *this;
1617    }
1618
1619    /// @}
1620
1621  private:
1622
1623    bool readLine() {
1624      std::string str;
1625      while(++line_num, std::getline(*_is, str)) {
1626        line.clear(); line.str(str);
1627        char c;
1628        if (line >> std::ws >> c && c != '#') {
1629          line.putback(c);
1630          return true;
1631        }
1632      }
1633      return false;
1634    }
1635
1636    bool readSuccess() {
1637      return static_cast<bool>(*_is);
1638    }
1639   
1640    void skipSection() {
1641      char c;
1642      while (readSuccess() && line >> c && c != '@') {
1643        readLine();
1644      }
1645      line.putback(c);
1646    }
1647
1648    void readNodes() {
1649
1650      std::vector<int> map_index(_node_maps.size());
1651      int map_num, label_index;
1652
1653      char c;
1654      if (!readLine() || !(line >> c) || c == '@') {
1655        if (readSuccess() && line) line.putback(c);
1656        if (!_node_maps.empty())
1657          throw DataFormatError("Cannot find map names");
1658        return;
1659      }
1660      line.putback(c);
1661     
1662      {
1663        std::map<std::string, int> maps;
1664       
1665        std::string map;
1666        int index = 0;
1667        while (_reader_bits::readToken(line, map)) {
1668          if (maps.find(map) != maps.end()) {
1669            std::ostringstream msg;
1670            msg << "Multiple occurence of node map: " << map;
1671            throw DataFormatError(msg.str().c_str());
1672          }
1673          maps.insert(std::make_pair(map, index));
1674          ++index;
1675        }
1676       
1677        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1678          std::map<std::string, int>::iterator jt =
1679            maps.find(_node_maps[i].first);
1680          if (jt == maps.end()) {
1681            std::ostringstream msg;
1682            msg << "Map not found in file: " << _node_maps[i].first;
1683            throw DataFormatError(msg.str().c_str());
1684          }
1685          map_index[i] = jt->second;
1686        }
1687
1688        {
1689          std::map<std::string, int>::iterator jt = maps.find("label");
1690          if (jt != maps.end()) {
1691            label_index = jt->second;
1692          } else {
1693            label_index = -1;
1694          }
1695        }
1696        map_num = maps.size();
1697      }
1698
1699      while (readLine() && line >> c && c != '@') {
1700        line.putback(c);
1701
1702        std::vector<std::string> tokens(map_num);
1703        for (int i = 0; i < map_num; ++i) {
1704          if (!_reader_bits::readToken(line, tokens[i])) {
1705            std::ostringstream msg;
1706            msg << "Column not found (" << i + 1 << ")";
1707            throw DataFormatError(msg.str().c_str());
1708          }
1709        }
1710        if (line >> std::ws >> c)
1711          throw DataFormatError("Extra character on the end of line");
1712       
1713        Node n;
1714        if (!_use_nodes) {
1715          n = _graph.addNode();
1716          if (label_index != -1)
1717            _node_index.insert(std::make_pair(tokens[label_index], n));
1718        } else {
1719          if (label_index == -1)
1720            throw DataFormatError("Label map not found in file");
1721          typename std::map<std::string, Node>::iterator it =
1722            _node_index.find(tokens[label_index]);
1723          if (it == _node_index.end()) {
1724            std::ostringstream msg;
1725            msg << "Node with label not found: " << tokens[label_index];
1726            throw DataFormatError(msg.str().c_str());       
1727          }
1728          n = it->second;
1729        }
1730
1731        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1732          _node_maps[i].second->set(n, tokens[map_index[i]]);
1733        }
1734
1735      }
1736      if (readSuccess()) {
1737        line.putback(c);
1738      }
1739    }
1740
1741    void readEdges() {
1742
1743      std::vector<int> map_index(_edge_maps.size());
1744      int map_num, label_index;
1745
1746      char c;
1747      if (!readLine() || !(line >> c) || c == '@') {
1748        if (readSuccess() && line) line.putback(c);
1749        if (!_edge_maps.empty())
1750          throw DataFormatError("Cannot find map names");
1751        return;
1752      }
1753      line.putback(c);
1754     
1755      {
1756        std::map<std::string, int> maps;
1757       
1758        std::string map;
1759        int index = 0;
1760        while (_reader_bits::readToken(line, map)) {
1761          if (maps.find(map) != maps.end()) {
1762            std::ostringstream msg;
1763            msg << "Multiple occurence of edge map: " << map;
1764            throw DataFormatError(msg.str().c_str());
1765          }
1766          maps.insert(std::make_pair(map, index));
1767          ++index;
1768        }
1769       
1770        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1771          std::map<std::string, int>::iterator jt =
1772            maps.find(_edge_maps[i].first);
1773          if (jt == maps.end()) {
1774            std::ostringstream msg;
1775            msg << "Map not found in file: " << _edge_maps[i].first;
1776            throw DataFormatError(msg.str().c_str());
1777          }
1778          map_index[i] = jt->second;
1779        }
1780
1781        {
1782          std::map<std::string, int>::iterator jt = maps.find("label");
1783          if (jt != maps.end()) {
1784            label_index = jt->second;
1785          } else {
1786            label_index = -1;
1787          }
1788        }
1789        map_num = maps.size();
1790      }
1791
1792      while (readLine() && line >> c && c != '@') {
1793        line.putback(c);
1794
1795        std::string source_token;
1796        std::string target_token;
1797
1798        if (!_reader_bits::readToken(line, source_token))
1799          throw DataFormatError("Node u not found");
1800
1801        if (!_reader_bits::readToken(line, target_token))
1802          throw DataFormatError("Node v not found");
1803       
1804        std::vector<std::string> tokens(map_num);
1805        for (int i = 0; i < map_num; ++i) {
1806          if (!_reader_bits::readToken(line, tokens[i])) {
1807            std::ostringstream msg;
1808            msg << "Column not found (" << i + 1 << ")";
1809            throw DataFormatError(msg.str().c_str());
1810          }
1811        }
1812        if (line >> std::ws >> c)
1813          throw DataFormatError("Extra character on the end of line");
1814       
1815        Edge e;
1816        if (!_use_edges) {
1817
1818          typename NodeIndex::iterator it;
1819 
1820          it = _node_index.find(source_token);
1821          if (it == _node_index.end()) {
1822            std::ostringstream msg;
1823            msg << "Item not found: " << source_token;
1824            throw DataFormatError(msg.str().c_str());
1825          }
1826          Node source = it->second;
1827
1828          it = _node_index.find(target_token);
1829          if (it == _node_index.end()) {       
1830            std::ostringstream msg;           
1831            msg << "Item not found: " << target_token;
1832            throw DataFormatError(msg.str().c_str());
1833          }                                         
1834          Node target = it->second;                           
1835
1836          e = _graph.addEdge(source, target);
1837          if (label_index != -1)
1838            _edge_index.insert(std::make_pair(tokens[label_index], e));
1839        } else {
1840          if (label_index == -1)
1841            throw DataFormatError("Label map not found in file");
1842          typename std::map<std::string, Edge>::iterator it =
1843            _edge_index.find(tokens[label_index]);
1844          if (it == _edge_index.end()) {
1845            std::ostringstream msg;
1846            msg << "Edge with label not found: " << tokens[label_index];
1847            throw DataFormatError(msg.str().c_str());       
1848          }
1849          e = it->second;
1850        }
1851
1852        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1853          _edge_maps[i].second->set(e, tokens[map_index[i]]);
1854        }
1855
1856      }
1857      if (readSuccess()) {
1858        line.putback(c);
1859      }
1860    }
1861
1862    void readAttributes() {
1863
1864      std::set<std::string> read_attr;
1865
1866      char c;
1867      while (readLine() && line >> c && c != '@') {
1868        line.putback(c);
1869       
1870        std::string attr, token;
1871        if (!_reader_bits::readToken(line, attr))
1872          throw DataFormatError("Attribute name not found");
1873        if (!_reader_bits::readToken(line, token))
1874          throw DataFormatError("Attribute value not found");
1875        if (line >> c)
1876          throw DataFormatError("Extra character on the end of line");   
1877
1878        {
1879          std::set<std::string>::iterator it = read_attr.find(attr);
1880          if (it != read_attr.end()) {
1881            std::ostringstream msg;
1882            msg << "Multiple occurence of attribute " << attr;
1883            throw DataFormatError(msg.str().c_str());
1884          }
1885          read_attr.insert(attr);
1886        }
1887       
1888        {
1889          typename Attributes::iterator it = _attributes.lower_bound(attr);
1890          while (it != _attributes.end() && it->first == attr) {
1891            it->second->set(token);
1892            ++it;
1893          }
1894        }
1895
1896      }
1897      if (readSuccess()) {
1898        line.putback(c);
1899      }
1900      for (typename Attributes::iterator it = _attributes.begin();
1901           it != _attributes.end(); ++it) {
1902        if (read_attr.find(it->first) == read_attr.end()) {
1903          std::ostringstream msg;
1904          msg << "Attribute not found in file: " << it->first;
1905          throw DataFormatError(msg.str().c_str());
1906        }       
1907      }
1908    }
1909
1910  public:
1911
1912    /// \name Execution of the reader   
1913    /// @{
1914
1915    /// \brief Start the batch processing
1916    ///
1917    /// This function starts the batch processing
1918    void run() {
1919     
1920      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1921     
1922      bool nodes_done = _skip_nodes;
1923      bool edges_done = _skip_edges;
1924      bool attributes_done = false;
1925
1926      line_num = 0;     
1927      readLine();
1928      skipSection();
1929
1930      while (readSuccess()) {
1931        try {
1932          char c;
1933          std::string section, caption;
1934          line >> c;
1935          _reader_bits::readToken(line, section);
1936          _reader_bits::readToken(line, caption);
1937
1938          if (line >> c)
1939            throw DataFormatError("Extra character on the end of line");
1940
1941          if (section == "nodes" && !nodes_done) {
1942            if (_nodes_caption.empty() || _nodes_caption == caption) {
1943              readNodes();
1944              nodes_done = true;
1945            }
1946          } else if ((section == "edges" || section == "arcs") &&
1947                     !edges_done) {
1948            if (_edges_caption.empty() || _edges_caption == caption) {
1949              readEdges();
1950              edges_done = true;
1951            }
1952          } else if (section == "attributes" && !attributes_done) {
1953            if (_attributes_caption.empty() || _attributes_caption == caption) {
1954              readAttributes();
1955              attributes_done = true;
1956            }
1957          } else {
1958            readLine();
1959            skipSection();
1960          }
1961        } catch (DataFormatError& error) {
1962          error.line(line_num);
1963          throw;
1964        }       
1965      }
1966
1967      if (!nodes_done) {
1968        throw DataFormatError("Section @nodes not found");
1969      }
1970
1971      if (!edges_done) {
1972        throw DataFormatError("Section @edges not found");
1973      }
1974
1975      if (!attributes_done && !_attributes.empty()) {
1976        throw DataFormatError("Section @attributes not found");
1977      }
1978
1979    }
1980
1981    /// @}
1982   
1983  };
1984
1985  /// \relates GraphReader
1986  template <typename Graph>
1987  GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
1988    GraphReader<Graph> tmp(is, graph);
1989    return tmp;
1990  }
1991
1992  /// \relates GraphReader
1993  template <typename Graph>
1994  GraphReader<Graph> graphReader(const std::string& fn,
1995                                       Graph& graph) {
1996    GraphReader<Graph> tmp(fn, graph);
1997    return tmp;
1998  }
1999
2000  /// \relates GraphReader
2001  template <typename Graph>
2002  GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
2003    GraphReader<Graph> tmp(fn, graph);
2004    return tmp;
2005  }
2006
2007  class SectionReader;
2008
2009  SectionReader sectionReader(std::istream& is);
2010  SectionReader sectionReader(const std::string& fn);
2011  SectionReader sectionReader(const char* fn);
2012 
2013  /// \brief Section reader class
2014  ///
2015  /// In the \e LGF file extra sections can be placed, which contain
2016  /// any data in arbitrary format. Such sections can be read with
2017  /// this class. A reading rule can be added with two different
2018  /// functions, with the \c sectionLines() function a functor can
2019  /// process the section line-by-line. While with the \c
2020  /// sectionStream() member the section can be read from an input
2021  /// stream.
2022  class SectionReader {
2023  private:
2024   
2025    std::istream* _is;
2026    bool local_is;
2027
2028    typedef std::map<std::string, _reader_bits::Section*> Sections;
2029    Sections _sections;
2030
2031    int line_num;
2032    std::istringstream line;
2033
2034  public:
2035
2036    /// \brief Constructor
2037    ///
2038    /// Construct a section reader, which reads from the given input
2039    /// stream.
2040    SectionReader(std::istream& is)
2041      : _is(&is), local_is(false) {}
2042
2043    /// \brief Constructor
2044    ///
2045    /// Construct a section reader, which reads from the given file.
2046    SectionReader(const std::string& fn)
2047      : _is(new std::ifstream(fn.c_str())), local_is(true) {}
2048   
2049    /// \brief Constructor
2050    ///
2051    /// Construct a section reader, which reads from the given file.
2052    SectionReader(const char* fn)
2053      : _is(new std::ifstream(fn)), local_is(true) {}
2054
2055    /// \brief Destructor
2056    ~SectionReader() {
2057      for (Sections::iterator it = _sections.begin();
2058           it != _sections.end(); ++it) {
2059        delete it->second;
2060      }
2061
2062      if (local_is) {
2063        delete _is;
2064      }
2065
2066    }
2067
2068  private:
2069
2070    friend SectionReader sectionReader(std::istream& is);
2071    friend SectionReader sectionReader(const std::string& fn);
2072    friend SectionReader sectionReader(const char* fn);
2073
2074    SectionReader(SectionReader& other)
2075      : _is(other._is), local_is(other.local_is) {
2076
2077      other._is = 0;
2078      other.local_is = false;
2079     
2080      _sections.swap(other._sections);
2081    }
2082   
2083    SectionReader& operator=(const SectionReader&);
2084
2085  public:
2086
2087    /// \name Section readers
2088    /// @{
2089
2090    /// \brief Add a section processor with line oriented reading
2091    ///
2092    /// The first parameter is the type descriptor of the section, the
2093    /// second is a functor, which takes just one \c std::string
2094    /// parameter. At the reading process, each line of the section
2095    /// will be given to the functor object. However, the empty lines
2096    /// and the comment lines are filtered out, and the leading
2097    /// whitespaces are trimmed from each processed string.
2098    ///
2099    /// For example let's see a section, which contain several
2100    /// integers, which should be inserted into a vector.
2101    ///\code
2102    ///  @numbers
2103    ///  12 45 23
2104    ///  4
2105    ///  23 6
2106    ///\endcode
2107    ///
2108    /// The functor is implemented as an struct:
2109    ///\code
2110    ///  struct NumberSection {
2111    ///    std::vector<int>& _data;
2112    ///    NumberSection(std::vector<int>& data) : _data(data) {}
2113    ///    void operator()(const std::string& line) {
2114    ///      std::istringstream ls(line);
2115    ///      int value;
2116    ///      while (ls >> value) _data.push_back(value);
2117    ///    }
2118    ///  };
2119    ///
2120    ///  // ...
2121    ///
2122    ///  reader.sectionLines("numbers", NumberSection(vec)); 
2123    ///\endcode
2124    template <typename Functor>
2125    SectionReader& sectionLines(const std::string& type, Functor functor) {
2126      LEMON_ASSERT(!type.empty(), "Type is not empty.");
2127      LEMON_ASSERT(_sections.find(type) == _sections.end(),
2128                   "Multiple reading of section.");
2129      _sections.insert(std::make_pair(type,
2130        new _reader_bits::LineSection<Functor>(functor)));
2131      return *this;
2132    }
2133
2134
2135    /// \brief Add a section processor with stream oriented reading
2136    ///
2137    /// The first parameter is the type of the section, the second is
2138    /// a functor, which takes an \c std::istream& and an int&
2139    /// parameter, the latter regard to the line number of stream. The
2140    /// functor can read the input while the section go on, and the
2141    /// line number should be modified accordingly.
2142    template <typename Functor>
2143    SectionReader& sectionStream(const std::string& type, Functor functor) {
2144      LEMON_ASSERT(!type.empty(), "Type is not empty.");
2145      LEMON_ASSERT(_sections.find(type) == _sections.end(),
2146                   "Multiple reading of section.");
2147      _sections.insert(std::make_pair(type,
2148         new _reader_bits::StreamSection<Functor>(functor)));
2149      return *this;
2150    }   
2151   
2152    /// @}
2153
2154  private:
2155
2156    bool readLine() {
2157      std::string str;
2158      while(++line_num, std::getline(*_is, str)) {
2159        line.clear(); line.str(str);
2160        char c;
2161        if (line >> std::ws >> c && c != '#') {
2162          line.putback(c);
2163          return true;
2164        }
2165      }
2166      return false;
2167    }
2168
2169    bool readSuccess() {
2170      return static_cast<bool>(*_is);
2171    }
2172   
2173    void skipSection() {
2174      char c;
2175      while (readSuccess() && line >> c && c != '@') {
2176        readLine();
2177      }
2178      line.putback(c);
2179    }
2180
2181  public:
2182
2183
2184    /// \name Execution of the reader   
2185    /// @{
2186
2187    /// \brief Start the batch processing
2188    ///
2189    /// This function starts the batch processing
2190    void run() {
2191     
2192      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
2193     
2194      std::set<std::string> extra_sections;
2195
2196      line_num = 0;     
2197      readLine();
2198      skipSection();
2199
2200      while (readSuccess()) {
2201        try {
2202          char c;
2203          std::string section, caption;
2204          line >> c;
2205          _reader_bits::readToken(line, section);
2206          _reader_bits::readToken(line, caption);
2207
2208          if (line >> c)
2209            throw DataFormatError("Extra character on the end of line");
2210
2211          if (extra_sections.find(section) != extra_sections.end()) {
2212            std::ostringstream msg;
2213            msg << "Multiple occurence of section " << section;
2214            throw DataFormatError(msg.str().c_str());
2215          }
2216          Sections::iterator it = _sections.find(section);
2217          if (it != _sections.end()) {
2218            extra_sections.insert(section);
2219            it->second->process(*_is, line_num);
2220          }
2221          readLine();
2222          skipSection();
2223        } catch (DataFormatError& error) {
2224          error.line(line_num);
2225          throw;
2226        }       
2227      }
2228      for (Sections::iterator it = _sections.begin();
2229           it != _sections.end(); ++it) {
2230        if (extra_sections.find(it->first) == extra_sections.end()) {
2231          std::ostringstream os;
2232          os << "Cannot find section: " << it->first;
2233          throw DataFormatError(os.str().c_str());
2234        }
2235      }
2236    }
2237
2238    /// @}
2239       
2240  };
2241
2242  /// \relates SectionReader
2243  inline SectionReader sectionReader(std::istream& is) {
2244    SectionReader tmp(is);
2245    return tmp;
2246  }
2247
2248  /// \relates SectionReader
2249  inline SectionReader sectionReader(const std::string& fn) {
2250    SectionReader tmp(fn);
2251    return tmp;
2252  }
2253
2254  /// \relates SectionReader
2255  inline SectionReader sectionReader(const char* fn) {
2256    SectionReader tmp(fn);
2257    return tmp;
2258  }
2259
2260  /// \ingroup lemon_io
2261  ///
2262  /// \brief Reader for the contents of the \ref lgf-format "LGF" file
2263  ///
2264  /// This class can be used to read the sections, the map names and
2265  /// the attributes from a file. Usually, the Lemon programs know
2266  /// that, which type of graph, which maps and which attributes
2267  /// should be read from a file, but in general tools (like glemon)
2268  /// the contents of an LGF file should be guessed somehow. This class
2269  /// reads the graph and stores the appropriate information for
2270  /// reading the graph.
2271  ///
2272  ///\code LgfContents contents("graph.lgf");
2273  /// contents.run();
2274  ///
2275  /// // does it contain any node section and arc section
2276  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
2277  ///   std::cerr << "Failure, cannot find graph" << std::endl;
2278  ///   return -1;
2279  /// }
2280  /// std::cout << "The name of the default node section : "
2281  ///           << contents.nodeSection(0) << std::endl;
2282  /// std::cout << "The number of the arc maps : "
2283  ///           << contents.arcMaps(0).size() << std::endl;
2284  /// std::cout << "The name of second arc map : "
2285  ///           << contents.arcMaps(0)[1] << std::endl;
2286  ///\endcode
2287  class LgfContents {   
2288  private:
2289
2290    std::istream* _is;
2291    bool local_is;
2292
2293    std::vector<std::string> _node_sections;
2294    std::vector<std::string> _edge_sections;
2295    std::vector<std::string> _attribute_sections;
2296    std::vector<std::string> _extra_sections;
2297
2298    std::vector<bool> _arc_sections;
2299
2300    std::vector<std::vector<std::string> > _node_maps;
2301    std::vector<std::vector<std::string> > _edge_maps;
2302
2303    std::vector<std::vector<std::string> > _attributes;
2304
2305
2306    int line_num;
2307    std::istringstream line;
2308   
2309  public:
2310
2311    /// \brief Constructor
2312    ///
2313    /// Construct an \e LGF contents reader, which reads from the given
2314    /// input stream.
2315    LgfContents(std::istream& is)
2316      : _is(&is), local_is(false) {}
2317
2318    /// \brief Constructor
2319    ///
2320    /// Construct an \e LGF contents reader, which reads from the given
2321    /// file.
2322    LgfContents(const std::string& fn)
2323      : _is(new std::ifstream(fn.c_str())), local_is(true) {}
2324
2325    /// \brief Constructor
2326    ///
2327    /// Construct an \e LGF contents reader, which reads from the given
2328    /// file.
2329    LgfContents(const char* fn)
2330      : _is(new std::ifstream(fn)), local_is(true) {}
2331   
2332    /// \brief Destructor
2333    ~LgfContents() {
2334      if (local_is) delete _is;
2335    }
2336
2337  private:
2338   
2339    LgfContents(const LgfContents&);
2340    LgfContents& operator=(const LgfContents&);
2341
2342  public:
2343
2344
2345    /// \name Node sections
2346    /// @{
2347
2348    /// \brief Gives back the number of node sections in the file.
2349    ///
2350    /// Gives back the number of node sections in the file.
2351    int nodeSectionNum() const {
2352      return _node_sections.size();
2353    }
2354
2355    /// \brief Returns the section name at the given position.
2356    ///
2357    /// Returns the section name at the given position.
2358    const std::string& nodeSection(int i) const {
2359      return _node_sections[i];
2360    }
2361
2362    /// \brief Gives back the node maps for the given section.
2363    ///
2364    /// Gives back the node maps for the given section.
2365    const std::vector<std::string>& nodeMapNames(int i) const {
2366      return _node_maps[i];
2367    }
2368
2369    /// @}
2370
2371    /// \name Arc/Edge sections
2372    /// @{
2373
2374    /// \brief Gives back the number of arc/edge sections in the file.
2375    ///
2376    /// Gives back the number of arc/edge sections in the file.
2377    /// \note It is synonym of \c edgeSectionNum().
2378    int arcSectionNum() const {
2379      return _edge_sections.size();
2380    }
2381
2382    /// \brief Returns the section name at the given position.
2383    ///
2384    /// Returns the section name at the given position.
2385    /// \note It is synonym of \c edgeSection().
2386    const std::string& arcSection(int i) const {
2387      return _edge_sections[i];
2388    }
2389
2390    /// \brief Gives back the arc/edge maps for the given section.
2391    ///
2392    /// Gives back the arc/edge maps for the given section.
2393    /// \note It is synonym of \c edgeMapNames().
2394    const std::vector<std::string>& arcMapNames(int i) const {
2395      return _edge_maps[i];
2396    }
2397
2398    /// @}
2399
2400    /// \name Synonyms
2401    /// @{
2402
2403    /// \brief Gives back the number of arc/edge sections in the file.
2404    ///
2405    /// Gives back the number of arc/edge sections in the file.
2406    /// \note It is synonym of \c arcSectionNum().
2407    int edgeSectionNum() const {
2408      return _edge_sections.size();
2409    }
2410
2411    /// \brief Returns the section name at the given position.
2412    ///
2413    /// Returns the section name at the given position.
2414    /// \note It is synonym of \c arcSection().
2415    const std::string& edgeSection(int i) const {
2416      return _edge_sections[i];
2417    }
2418
2419    /// \brief Gives back the edge maps for the given section.
2420    ///
2421    /// Gives back the edge maps for the given section.
2422    /// \note It is synonym of \c arcMapNames().
2423    const std::vector<std::string>& edgeMapNames(int i) const {
2424      return _edge_maps[i];
2425    }
2426
2427    /// @}
2428
2429    /// \name Attribute sections   
2430    /// @{
2431
2432    /// \brief Gives back the number of attribute sections in the file.
2433    ///
2434    /// Gives back the number of attribute sections in the file.
2435    int attributeSectionNum() const {
2436      return _attribute_sections.size();
2437    }
2438
2439    /// \brief Returns the section name at the given position.
2440    ///
2441    /// Returns the section name at the given position.
2442    const std::string& attributeSectionNames(int i) const {
2443      return _attribute_sections[i];
2444    }
2445
2446    /// \brief Gives back the attributes for the given section.
2447    ///
2448    /// Gives back the attributes for the given section.
2449    const std::vector<std::string>& attributes(int i) const {
2450      return _attributes[i];
2451    }
2452
2453    /// @}
2454
2455    /// \name Extra sections   
2456    /// @{
2457
2458    /// \brief Gives back the number of extra sections in the file.
2459    ///
2460    /// Gives back the number of extra sections in the file.
2461    int extraSectionNum() const {
2462      return _extra_sections.size();
2463    }
2464
2465    /// \brief Returns the extra section type at the given position.
2466    ///
2467    /// Returns the section type at the given position.
2468    const std::string& extraSection(int i) const {
2469      return _extra_sections[i];
2470    }
2471
2472    /// @}
2473
2474  private:
2475
2476    bool readLine() {
2477      std::string str;
2478      while(++line_num, std::getline(*_is, str)) {
2479        line.clear(); line.str(str);
2480        char c;
2481        if (line >> std::ws >> c && c != '#') {
2482          line.putback(c);
2483          return true;
2484        }
2485      }
2486      return false;
2487    }
2488
2489    bool readSuccess() {
2490      return static_cast<bool>(*_is);
2491    }
2492
2493    void skipSection() {
2494      char c;
2495      while (readSuccess() && line >> c && c != '@') {
2496        readLine();
2497      }
2498      line.putback(c);
2499    }
2500
2501    void readMaps(std::vector<std::string>& maps) {
2502      char c;
2503      if (!readLine() || !(line >> c) || c == '@') {
2504        if (readSuccess() && line) line.putback(c);
2505        return;
2506      }
2507      line.putback(c);
2508      std::string map;
2509      while (_reader_bits::readToken(line, map)) {
2510        maps.push_back(map);
2511      }
2512    }
2513
2514    void readAttributes(std::vector<std::string>& attrs) {
2515      readLine();
2516      char c;
2517      while (readSuccess() && line >> c && c != '@') {
2518        line.putback(c);
2519        std::string attr;
2520        _reader_bits::readToken(line, attr);
2521        attrs.push_back(attr);
2522        readLine();
2523      }
2524      line.putback(c);
2525    }
2526
2527  public:
2528
2529    /// \name Execution of the contents reader   
2530    /// @{
2531
2532    /// \brief Start the reading
2533    ///
2534    /// This function starts the reading
2535    void run() {
2536
2537      readLine();
2538      skipSection();
2539
2540      while (readSuccess()) {
2541
2542        char c;
2543        line >> c;
2544
2545        std::string section, caption;
2546        _reader_bits::readToken(line, section);
2547        _reader_bits::readToken(line, caption);
2548
2549        if (section == "nodes") {
2550          _node_sections.push_back(caption);
2551          _node_maps.push_back(std::vector<std::string>());
2552          readMaps(_node_maps.back());
2553          readLine(); skipSection();
2554        } else if (section == "arcs" || section == "edges") {
2555          _edge_sections.push_back(caption);
2556          _arc_sections.push_back(section == "arcs");
2557          _edge_maps.push_back(std::vector<std::string>());
2558          readMaps(_edge_maps.back());
2559          readLine(); skipSection();
2560        } else if (section == "attributes") {
2561          _attribute_sections.push_back(caption);
2562          _attributes.push_back(std::vector<std::string>());
2563          readAttributes(_attributes.back());
2564        } else {
2565          _extra_sections.push_back(section);
2566          readLine(); skipSection();
2567        }
2568      }
2569    }
2570
2571    /// @}
2572   
2573  };
2574}
2575
2576#endif
Note: See TracBrowser for help on using the repository browser.