COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/lgf_reader.h @ 516:dab9e610e37d

Last change on this file since 516:dab9e610e37d was 440:88ed40ad0d4f, checked in by Alpar Juttner <alpar@…>, 11 years ago

Happy New Year again

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