COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 293:47fbc814aa31

Last change on this file since 293:47fbc814aa31 was 293:47fbc814aa31, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Change the parameter order in LGF reader and writer tools

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