COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/lgf_reader.h @ 171:02f4d5d9bfd7

Last change on this file since 171:02f4d5d9bfd7 was 165:b4c336c27a03, checked in by Balazs Dezso <deba@…>, 16 years ago

Undirected LGF IO

File size: 59.7 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19///\ingroup lemon_io
20///\file
21///\brief Lemon Graph Format reader.
22
23
24#ifndef LEMON_LGF_READER_H
25#define LEMON_LGF_READER_H
26
27#include <iostream>
28#include <fstream>
29#include <sstream>
30
31#include <set>
32#include <map>
33
34#include <lemon/assert.h>
35#include <lemon/graph_utils.h>
36
37#include <lemon/lgf_writer.h>
38
39#include <lemon/concept_check.h>
40#include <lemon/concepts/maps.h>
41
42namespace lemon {
43
44  namespace _reader_bits {
45
46    template <typename Value>
47    struct DefaultConverter {
48      Value operator()(const std::string& str) {
49        std::istringstream is(str);
50        Value value;
51        is >> value;
52
53        char c;
54        if (is >> std::ws >> c) {
55          throw DataFormatError("Remaining characters in token");
56        }
57        return value;
58      }
59    };
60
61    template <>
62    struct DefaultConverter<std::string> {
63      std::string operator()(const std::string& str) {
64        return str;
65      }
66    };
67
68    template <typename _Item>   
69    class MapStorageBase {
70    public:
71      typedef _Item Item;
72
73    public:
74      MapStorageBase() {}
75      virtual ~MapStorageBase() {}
76
77      virtual void set(const Item& item, const std::string& value) = 0;
78
79    };
80
81    template <typename _Item, typename _Map,
82              typename _Converter = DefaultConverter<typename _Map::Value> >
83    class MapStorage : public MapStorageBase<_Item> {
84    public:
85      typedef _Map Map;
86      typedef _Converter Converter;
87      typedef _Item Item;
88     
89    private:
90      Map& _map;
91      Converter _converter;
92
93    public:
94      MapStorage(Map& map, const Converter& converter = Converter())
95        : _map(map), _converter(converter) {}
96      virtual ~MapStorage() {}
97
98      virtual void set(const Item& item ,const std::string& value) {
99        _map.set(item, _converter(value));
100      }
101    };
102
103    template <typename _Graph, bool _dir, typename _Map,
104              typename _Converter = DefaultConverter<typename _Map::Value> >
105    class GraphArcMapStorage : public MapStorageBase<typename _Graph::Edge> {
106    public:
107      typedef _Map Map;
108      typedef _Converter Converter;
109      typedef _Graph Graph;
110      typedef typename Graph::Edge Item;
111      static const bool dir = _dir;
112     
113    private:
114      const Graph& _graph;
115      Map& _map;
116      Converter _converter;
117
118    public:
119      GraphArcMapStorage(const Graph& graph, Map& map,
120                         const Converter& converter = Converter())
121        : _graph(graph), _map(map), _converter(converter) {}
122      virtual ~GraphArcMapStorage() {}
123
124      virtual void set(const Item& item ,const std::string& value) {
125        _map.set(_graph.direct(item, dir), _converter(value));
126      }
127    };
128
129    class ValueStorageBase {
130    public:
131      ValueStorageBase() {}
132      virtual ~ValueStorageBase() {}
133
134      virtual void set(const std::string&) = 0;
135    };
136
137    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
138    class ValueStorage : public ValueStorageBase {
139    public:
140      typedef _Value Value;
141      typedef _Converter Converter;
142
143    private:
144      Value& _value;
145      Converter _converter;
146
147    public:
148      ValueStorage(Value& value, const Converter& converter = Converter())
149        : _value(value), _converter(converter) {}
150
151      virtual void set(const std::string& value) {
152        _value = _converter(value);
153      }
154    };
155
156    template <typename Value>
157    struct MapLookUpConverter {
158      const std::map<std::string, Value>& _map;
159
160      MapLookUpConverter(const std::map<std::string, Value>& map)
161        : _map(map) {}
162
163      Value operator()(const std::string& str) {
164        typename std::map<std::string, Value>::const_iterator it =
165          _map.find(str);
166        if (it == _map.end()) {
167          std::ostringstream msg;
168          msg << "Item not found: " << str;
169          throw DataFormatError(msg.str().c_str());
170        }
171        return it->second;
172      }
173    };
174
175    template <typename Graph>
176    struct GraphArcLookUpConverter {
177      const Graph& _graph;
178      const std::map<std::string, typename Graph::Edge>& _map;
179     
180      GraphArcLookUpConverter(const Graph& graph,
181                              const std::map<std::string,
182                                             typename Graph::Edge>& map)
183        : _graph(graph), _map(map) {}
184     
185      typename Graph::Arc operator()(const std::string& str) {
186        if (str.empty() || (str[0] != '+' && str[0] != '-')) {
187          throw DataFormatError("Item must start with '+' or '-'");
188        }
189        typename std::map<std::string, typename Graph::Edge>
190          ::const_iterator it = _map.find(str.substr(1));
191        if (it == _map.end()) {
192          throw DataFormatError("Item not found");
193        }
194        return _graph.direct(it->second, str[0] == '+');
195      }
196    };
197
198    bool isWhiteSpace(char c) {
199      return c == ' ' || c == '\t' || c == '\v' ||
200        c == '\n' || c == '\r' || c == '\f';
201    }
202   
203    bool isOct(char c) {
204      return '0' <= c && c <='7';
205    }
206   
207    int valueOct(char c) {
208      LEMON_ASSERT(isOct(c), "The character is not octal.");
209      return c - '0';
210    }
211
212    bool isHex(char c) {
213      return ('0' <= c && c <= '9') ||
214        ('a' <= c && c <= 'z') ||
215        ('A' <= c && c <= 'Z');
216    }
217   
218    int valueHex(char c) {
219      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
220      if ('0' <= c && c <= '9') return c - '0';
221      if ('a' <= c && c <= 'z') return c - 'a' + 10;
222      return c - 'A' + 10;
223    }
224
225    bool isIdentifierFirstChar(char c) {
226      return ('a' <= c && c <= 'z') ||
227        ('A' <= c && c <= 'Z') || c == '_';
228    }
229
230    bool isIdentifierChar(char c) {
231      return isIdentifierFirstChar(c) ||
232        ('0' <= c && c <= '9');
233    }
234
235    char readEscape(std::istream& is) {
236      char c;
237      if (!is.get(c))
238        throw DataFormatError("Escape format error");
239
240      switch (c) {
241      case '\\':
242        return '\\';
243      case '\"':
244        return '\"';
245      case '\'':
246        return '\'';
247      case '\?':
248        return '\?';
249      case 'a':
250        return '\a';
251      case 'b':
252        return '\b';
253      case 'f':
254        return '\f';
255      case 'n':
256        return '\n';
257      case 'r':
258        return '\r';
259      case 't':
260        return '\t';
261      case 'v':
262        return '\v';
263      case 'x':
264        {
265          int code;
266          if (!is.get(c) || !isHex(c))
267            throw DataFormatError("Escape format error");
268          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
269          else code = code * 16 + valueHex(c);
270          return code;
271        }
272      default:
273        {
274          int code;
275          if (!isOct(c))
276            throw DataFormatError("Escape format error");
277          else if (code = valueOct(c), !is.get(c) || !isOct(c))
278            is.putback(c);
279          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
280            is.putback(c);
281          else code = code * 8 + valueOct(c);
282          return code;
283        }             
284      }
285    }
286   
287    std::istream& readToken(std::istream& is, std::string& str) {
288      std::ostringstream os;
289
290      char c;
291      is >> std::ws;
292     
293      if (!is.get(c))
294        return is;
295
296      if (c == '\"') {
297        while (is.get(c) && c != '\"') {
298          if (c == '\\')
299            c = readEscape(is);
300          os << c;
301        }
302        if (!is)
303          throw DataFormatError("Quoted format error");
304      } else {
305        is.putback(c);
306        while (is.get(c) && !isWhiteSpace(c)) {
307          if (c == '\\')
308            c = readEscape(is);
309          os << c;
310        }
311        if (!is) {
312          is.clear();
313        } else {
314          is.putback(c);
315        }
316      }
317      str = os.str();
318      return is;
319    }
320
321    class Section {
322    public:
323      virtual ~Section() {}
324      virtual void process(std::istream& is, int& line_num) = 0;
325    };
326
327    template <typename Functor>
328    class LineSection : public Section {
329    private:
330
331      Functor _functor;
332
333    public:
334     
335      LineSection(const Functor& functor) : _functor(functor) {}
336      virtual ~LineSection() {}
337
338      virtual void process(std::istream& is, int& line_num) {
339        char c;
340        std::string line;
341        while (is.get(c) && c != '@') {
342          if (c == '\n') {
343            ++line_num;
344          } else if (c == '#') {
345            getline(is, line);
346            ++line_num;
347          } else if (!isWhiteSpace(c)) {
348            is.putback(c);
349            getline(is, line);
350            _functor(line);
351            ++line_num;
352          }
353        }
354        if (is) is.putback(c);
355        else if (is.eof()) is.clear();
356      }
357    };
358
359    template <typename Functor>
360    class StreamSection : public Section {
361    private:
362
363      Functor _functor;
364
365    public:
366     
367      StreamSection(const Functor& functor) : _functor(functor) {}
368      virtual ~StreamSection() {}
369
370      virtual void process(std::istream& is, int& line_num) {
371        _functor(is, line_num);
372        char c;
373        std::string line;
374        while (is.get(c) && c != '@') {
375          if (c == '\n') {
376            ++line_num;
377          } else if (!isWhiteSpace(c)) {
378            getline(is, line);
379            ++line_num;
380          }
381        }
382        if (is) is.putback(c);
383        else if (is.eof()) is.clear(); 
384      }
385    };
386   
387  }
388
389  /// \ingroup lemon_io
390  /// 
391  /// \brief LGF reader for directed graphs
392  ///
393  /// This utility reads an \ref lgf-format "LGF" file.
394  ///
395  /// The reading method does a batch processing. The user creates a
396  /// reader object, then various reading rules can be added to the
397  /// reader, and eventually the reading is executed with the \c run()
398  /// member function. A map reading rule can be added to the reader
399  /// with the \c nodeMap() or \c arcMap() members. An optional
400  /// converter parameter can also be added as a standard functor
401  /// converting from std::string to the value type of the map. If it
402  /// is set, it will determine how the tokens in the file should be
403  /// is converted to the map's value type. If the functor is not set,
404  /// then a default conversion will be used. One map can be read into
405  /// multiple map objects at the same time. The \c attribute(), \c
406  /// node() and \c arc() functions are used to add attribute reading
407  /// rules.
408  ///
409  ///\code
410  ///     DigraphReader<Digraph>(std::cin, digraph).
411  ///       nodeMap("coordinates", coord_map).
412  ///       arcMap("capacity", cap_map).
413  ///       node("source", src).
414  ///       node("target", trg).
415  ///       attribute("caption", caption).
416  ///       run();
417  ///\endcode
418  ///
419  /// By default the reader uses the first section in the file of the
420  /// proper type. If a section has an optional name, then it can be
421  /// selected for reading by giving an optional name parameter to the
422  /// \c nodes(), \c arcs() or \c attributes() functions. The readers
423  /// also can load extra sections with the \c sectionLines() and
424  /// sectionStream() functions.
425  ///
426  /// The \c useNodes() and \c useArcs() functions are used to tell the reader
427  /// that the nodes or arcs should not be constructed (added to the
428  /// graph) during the reading, but instead the label map of the items
429  /// are given as a parameter of these functions. An
430  /// application of these function is multipass reading, which is
431  /// important if two \e \@arcs sections must be read from the
432  /// file. In this example the first phase would read the node set and one
433  /// of the arc sets, while the second phase would read the second arc
434  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
435  /// The previously read label node map should be passed to the \c
436  /// useNodes() functions. Another application of multipass reading when
437  /// paths are given as a node map or an arc map. It is impossible read this in
438  /// a single pass, because the arcs are not constructed when the node
439  /// maps are read.
440  template <typename _Digraph>
441  class DigraphReader {
442  public:
443
444    typedef _Digraph Digraph;
445    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
446   
447  private:
448
449
450    std::istream* _is;
451    bool local_is;
452
453    Digraph& _digraph;
454
455    std::string _nodes_caption;
456    std::string _arcs_caption;
457    std::string _attributes_caption;
458
459    typedef std::map<std::string, Node> NodeIndex;
460    NodeIndex _node_index;
461    typedef std::map<std::string, Arc> ArcIndex;
462    ArcIndex _arc_index;
463   
464    typedef std::vector<std::pair<std::string,
465      _reader_bits::MapStorageBase<Node>*> > NodeMaps;   
466    NodeMaps _node_maps;
467
468    typedef std::vector<std::pair<std::string,
469      _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
470    ArcMaps _arc_maps;
471
472    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
473      Attributes;
474    Attributes _attributes;
475
476    typedef std::map<std::string, _reader_bits::Section*> Sections;
477    Sections _sections;
478
479    bool _use_nodes;
480    bool _use_arcs;
481
482    int line_num;
483    std::istringstream line;
484
485  public:
486
487    /// \brief Constructor
488    ///
489    /// Construct a directed graph reader, which reads from the given
490    /// input stream.
491    DigraphReader(std::istream& is, Digraph& digraph)
492      : _is(&is), local_is(false), _digraph(digraph),
493        _use_nodes(false), _use_arcs(false) {}
494
495    /// \brief Constructor
496    ///
497    /// Construct a directed graph reader, which reads from the given
498    /// file.
499    DigraphReader(const std::string& fn, Digraph& digraph)
500      : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
501        _use_nodes(false), _use_arcs(false) {}
502   
503    /// \brief Constructor
504    ///
505    /// Construct a directed graph reader, which reads from the given
506    /// file.
507    DigraphReader(const char* fn, Digraph& digraph)
508      : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
509        _use_nodes(false), _use_arcs(false) {}
510
511    /// \brief Copy constructor
512    ///
513    /// The copy constructor transfers all data from the other reader,
514    /// therefore the copied reader will not be usable more.
515    DigraphReader(DigraphReader& other)
516      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
517        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs) {
518
519      other._is = 0;
520      other.local_is = false;
521     
522      _node_index.swap(other._node_index);
523      _arc_index.swap(other._arc_index);
524
525      _node_maps.swap(other._node_maps);
526      _arc_maps.swap(other._arc_maps);
527      _attributes.swap(other._attributes);
528
529      _nodes_caption = other._nodes_caption;
530      _arcs_caption = other._arcs_caption;
531      _attributes_caption = other._attributes_caption;
532
533      _sections.swap(other._sections);
534    }
535
536    /// \brief Destructor
537    ~DigraphReader() {
538      for (typename NodeMaps::iterator it = _node_maps.begin();
539           it != _node_maps.end(); ++it) {
540        delete it->second;
541      }
542
543      for (typename ArcMaps::iterator it = _arc_maps.begin();
544           it != _arc_maps.end(); ++it) {
545        delete it->second;
546      }
547
548      for (typename Attributes::iterator it = _attributes.begin();
549           it != _attributes.end(); ++it) {
550        delete it->second;
551      }
552
553      for (typename Sections::iterator it = _sections.begin();
554           it != _sections.end(); ++it) {
555        delete it->second;
556      }
557
558      if (local_is) {
559        delete _is;
560      }
561
562    }
563
564  private:
565   
566    DigraphReader& operator=(const DigraphReader&);
567
568  public:
569
570    /// \name Reading rules
571    /// @{
572   
573    /// \brief Node map reading rule
574    ///
575    /// Add a node map reading rule to the reader.
576    template <typename Map>
577    DigraphReader& nodeMap(const std::string& caption, Map& map) {
578      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
579      _reader_bits::MapStorageBase<Node>* storage =
580        new _reader_bits::MapStorage<Node, Map>(map);
581      _node_maps.push_back(std::make_pair(caption, storage));
582      return *this;
583    }
584
585    /// \brief Node map reading rule
586    ///
587    /// Add a node map reading rule with specialized converter to the
588    /// reader.
589    template <typename Map, typename Converter>
590    DigraphReader& nodeMap(const std::string& caption, Map& map,
591                           const Converter& converter = Converter()) {
592      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
593      _reader_bits::MapStorageBase<Node>* storage =
594        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
595      _node_maps.push_back(std::make_pair(caption, storage));
596      return *this;
597    }
598
599    /// \brief Arc map reading rule
600    ///
601    /// Add an arc map reading rule to the reader.
602    template <typename Map>
603    DigraphReader& arcMap(const std::string& caption, Map& map) {
604      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
605      _reader_bits::MapStorageBase<Arc>* storage =
606        new _reader_bits::MapStorage<Arc, Map>(map);
607      _arc_maps.push_back(std::make_pair(caption, storage));
608      return *this;
609    }
610
611    /// \brief Arc map reading rule
612    ///
613    /// Add an arc map reading rule with specialized converter to the
614    /// reader.
615    template <typename Map, typename Converter>
616    DigraphReader& arcMap(const std::string& caption, Map& map,
617                          const Converter& converter = Converter()) {
618      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
619      _reader_bits::MapStorageBase<Arc>* storage =
620        new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
621      _arc_maps.push_back(std::make_pair(caption, storage));
622      return *this;
623    }
624
625    /// \brief Attribute reading rule
626    ///
627    /// Add an attribute reading rule to the reader.
628    template <typename Value>
629    DigraphReader& attribute(const std::string& caption, Value& value) {
630      _reader_bits::ValueStorageBase* storage =
631        new _reader_bits::ValueStorage<Value>(value);
632      _attributes.insert(std::make_pair(caption, storage));
633      return *this;
634    }
635
636    /// \brief Attribute reading rule
637    ///
638    /// Add an attribute reading rule with specialized converter to the
639    /// reader.
640    template <typename Value, typename Converter>
641    DigraphReader& attribute(const std::string& caption, Value& value,
642                             const Converter& converter = Converter()) {
643      _reader_bits::ValueStorageBase* storage =
644        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
645      _attributes.insert(std::make_pair(caption, storage));
646      return *this;
647    }
648
649    /// \brief Node reading rule
650    ///
651    /// Add a node reading rule to reader.
652    DigraphReader& node(const std::string& caption, Node& node) {
653      typedef _reader_bits::MapLookUpConverter<Node> Converter;
654      Converter converter(_node_index);
655      _reader_bits::ValueStorageBase* storage =
656        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
657      _attributes.insert(std::make_pair(caption, storage));
658      return *this;
659    }
660
661    /// \brief Arc reading rule
662    ///
663    /// Add an arc reading rule to reader.
664    DigraphReader& arc(const std::string& caption, Arc& arc) {
665      typedef _reader_bits::MapLookUpConverter<Arc> Converter;
666      Converter converter(_arc_index);
667      _reader_bits::ValueStorageBase* storage =
668        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
669      _attributes.insert(std::make_pair(caption, storage));
670      return *this;
671    }
672
673    /// @}
674
675    /// \name Select section by name
676    /// @{
677
678    /// \brief Set \c \@nodes section to be read
679    ///
680    /// Set \c \@nodes section to be read
681    DigraphReader& nodes(const std::string& caption) {
682      _nodes_caption = caption;
683      return *this;
684    }
685
686    /// \brief Set \c \@arcs section to be read
687    ///
688    /// Set \c \@arcs section to be read
689    DigraphReader& arcs(const std::string& caption) {
690      _arcs_caption = caption;
691      return *this;
692    }
693
694    /// \brief Set \c \@attributes section to be read
695    ///
696    /// Set \c \@attributes section to be read
697    DigraphReader& attributes(const std::string& caption) {
698      _attributes_caption = caption;
699      return *this;
700    }
701
702    /// @}
703
704    /// \name Section readers
705    /// @{
706
707    /// \brief Add a section processor with line oriented reading
708    ///
709    /// In the \e LGF file extra sections can be placed, which contain
710    /// any data in arbitrary format. These sections can be read with
711    /// this function line by line. The first parameter is the type
712    /// descriptor of the section, the second is a functor, which
713    /// takes just one \c std::string parameter. At the reading
714    /// process, each line of the section will be given to the functor
715    /// object. However, the empty lines and the comment lines are
716    /// filtered out, and the leading whitespaces are stipped from
717    /// each processed string.
718    ///
719    /// For example let's see a section, which contain several
720    /// integers, which should be inserted into a vector.
721    ///\code
722    ///  @numbers
723    ///  12 45 23
724    ///  4
725    ///  23 6
726    ///\endcode
727    ///
728    /// The functor is implemented as an struct:
729    ///\code
730    ///  struct NumberSection {
731    ///    std::vector<int>& _data;
732    ///    NumberSection(std::vector<int>& data) : _data(data) {}
733    ///    void operator()(const std::string& line) {
734    ///      std::istringstream ls(line);
735    ///      int value;
736    ///      while (ls >> value) _data.push_back(value);
737    ///    }
738    ///  };
739    ///
740    ///  // ...
741    ///
742    ///  reader.sectionLines("numbers", NumberSection(vec)); 
743    ///\endcode
744    template <typename Functor>
745    DigraphReader& sectionLines(const std::string& type, Functor functor) {
746      LEMON_ASSERT(!type.empty(), "Type is not empty.");
747      LEMON_ASSERT(_sections.find(type) == _sections.end(),
748                   "Multiple reading of section.");
749      LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
750                   type != "attributes", "Multiple reading of section.");
751      _sections.insert(std::make_pair(type,
752        new _reader_bits::LineSection<Functor>(functor)));
753      return *this;
754    }
755
756
757    /// \brief Add a section processor with stream oriented reading
758    ///
759    /// In the \e LGF file extra sections can be placed, which contain
760    /// any data in arbitrary format. These sections can be read
761    /// directly with this function. The first parameter is the type
762    /// of the section, the second is a functor, which takes an \c
763    /// std::istream& and an int& parameter, the latter regard to the
764    /// line number of stream. The functor can read the input while
765    /// the section go on, and the line number should be modified
766    /// accordingly.
767    template <typename Functor>
768    DigraphReader& sectionStream(const std::string& type, Functor functor) {
769      LEMON_ASSERT(!type.empty(), "Type is not empty.");
770      LEMON_ASSERT(_sections.find(type) == _sections.end(),
771                   "Multiple reading of section.");
772      LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
773                   type != "attributes", "Multiple reading of section.");
774      _sections.insert(std::make_pair(type,
775         new _reader_bits::StreamSection<Functor>(functor)));
776      return *this;
777    }   
778   
779    /// @}
780
781    /// \name Using previously constructed node or arc set
782    /// @{
783
784    /// \brief Use previously constructed node set
785    ///
786    /// Use previously constructed node set, and specify the node
787    /// label map.
788    template <typename Map>
789    DigraphReader& useNodes(const Map& map) {
790      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
791      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
792      _use_nodes = true;
793      _writer_bits::DefaultConverter<typename Map::Value> converter;
794      for (NodeIt n(_digraph); n != INVALID; ++n) {
795        _node_index.insert(std::make_pair(converter(map[n]), n));
796      }
797      return *this;
798    }
799
800    /// \brief Use previously constructed node set
801    ///
802    /// Use previously constructed node set, and specify the node
803    /// label map and a functor which converts the label map values to
804    /// std::string.
805    template <typename Map, typename Converter>
806    DigraphReader& useNodes(const Map& map,
807                            const Converter& converter = Converter()) {
808      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
809      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
810      _use_nodes = true;
811      for (NodeIt n(_digraph); n != INVALID; ++n) {
812        _node_index.insert(std::make_pair(converter(map[n]), n));
813      }
814      return *this;
815    }
816
817    /// \brief Use previously constructed arc set
818    ///
819    /// Use previously constructed arc set, and specify the arc
820    /// label map.
821    template <typename Map>
822    DigraphReader& useArcs(const Map& map) {
823      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
824      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
825      _use_arcs = true;
826      _writer_bits::DefaultConverter<typename Map::Value> converter;
827      for (ArcIt a(_digraph); a != INVALID; ++a) {
828        _arc_index.insert(std::make_pair(converter(map[a]), a));
829      }
830      return *this;
831    }
832
833    /// \brief Use previously constructed arc set
834    ///
835    /// Use previously constructed arc set, and specify the arc
836    /// label map and a functor which converts the label map values to
837    /// std::string.
838    template <typename Map, typename Converter>
839    DigraphReader& useArcs(const Map& map,
840                            const Converter& converter = Converter()) {
841      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
842      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
843      _use_arcs = true;
844      for (ArcIt a(_digraph); a != INVALID; ++a) {
845        _arc_index.insert(std::make_pair(converter(map[a]), a));
846      }
847      return *this;
848    }
849
850    /// @}
851
852  private:
853
854    bool readLine() {
855      std::string str;
856      while(++line_num, std::getline(*_is, str)) {
857        line.clear(); line.str(str);
858        char c;
859        if (line >> std::ws >> c && c != '#') {
860          line.putback(c);
861          return true;
862        }
863      }
864      return false;
865    }
866
867    bool readSuccess() {
868      return static_cast<bool>(*_is);
869    }
870   
871    void skipSection() {
872      char c;
873      while (readSuccess() && line >> c && c != '@') {
874        readLine();
875      }
876      line.putback(c);
877    }
878
879    void readNodes() {
880
881      std::vector<int> map_index(_node_maps.size());
882      int map_num, label_index;
883
884      if (!readLine())
885        throw DataFormatError("Cannot find map captions");
886     
887      {
888        std::map<std::string, int> maps;
889       
890        std::string map;
891        int index = 0;
892        while (_reader_bits::readToken(line, map)) {
893          if (maps.find(map) != maps.end()) {
894            std::ostringstream msg;
895            msg << "Multiple occurence of node map: " << map;
896            throw DataFormatError(msg.str().c_str());
897          }
898          maps.insert(std::make_pair(map, index));
899          ++index;
900        }
901       
902        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
903          std::map<std::string, int>::iterator jt =
904            maps.find(_node_maps[i].first);
905          if (jt == maps.end()) {
906            std::ostringstream msg;
907            msg << "Map not found in file: " << _node_maps[i].first;
908            throw DataFormatError(msg.str().c_str());
909          }
910          map_index[i] = jt->second;
911        }
912
913        {
914          std::map<std::string, int>::iterator jt = maps.find("label");
915          if (jt == maps.end())
916            throw DataFormatError("Label map not found in file");
917          label_index = jt->second;
918        }
919        map_num = maps.size();
920      }
921
922      char c;
923      while (readLine() && line >> c && c != '@') {
924        line.putback(c);
925
926        std::vector<std::string> tokens(map_num);
927        for (int i = 0; i < map_num; ++i) {
928          if (!_reader_bits::readToken(line, tokens[i])) {
929            std::ostringstream msg;
930            msg << "Column not found (" << i + 1 << ")";
931            throw DataFormatError(msg.str().c_str());
932          }
933        }
934        if (line >> std::ws >> c)
935          throw DataFormatError("Extra character on the end of line");
936       
937        Node n;
938        if (!_use_nodes) {
939          n = _digraph.addNode();
940          _node_index.insert(std::make_pair(tokens[label_index], n));
941        } else {
942          typename std::map<std::string, Node>::iterator it =
943            _node_index.find(tokens[label_index]);
944          if (it == _node_index.end()) {
945            std::ostringstream msg;
946            msg << "Node with label not found: " << tokens[label_index];
947            throw DataFormatError(msg.str().c_str());       
948          }
949          n = it->second;
950        }
951
952        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
953          _node_maps[i].second->set(n, tokens[map_index[i]]);
954        }
955
956      }
957      if (readSuccess()) {
958        line.putback(c);
959      }
960    }
961
962    void readArcs() {
963
964      std::vector<int> map_index(_arc_maps.size());
965      int map_num, label_index;
966
967      if (!readLine())
968        throw DataFormatError("Cannot find map captions");
969     
970      {
971        std::map<std::string, int> maps;
972       
973        std::string map;
974        int index = 0;
975        while (_reader_bits::readToken(line, map)) {
976          if (maps.find(map) != maps.end()) {
977            std::ostringstream msg;
978            msg << "Multiple occurence of arc map: " << map;
979            throw DataFormatError(msg.str().c_str());
980          }
981          maps.insert(std::make_pair(map, index));
982          ++index;
983        }
984       
985        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
986          std::map<std::string, int>::iterator jt =
987            maps.find(_arc_maps[i].first);
988          if (jt == maps.end()) {
989            std::ostringstream msg;
990            msg << "Map not found in file: " << _arc_maps[i].first;
991            throw DataFormatError(msg.str().c_str());
992          }
993          map_index[i] = jt->second;
994        }
995
996        {
997          std::map<std::string, int>::iterator jt = maps.find("label");
998          if (jt == maps.end())
999            throw DataFormatError("Label map not found in file");
1000          label_index = jt->second;
1001        }
1002        map_num = maps.size();
1003      }
1004
1005      char c;
1006      while (readLine() && line >> c && c != '@') {
1007        line.putback(c);
1008
1009        std::string source_token;
1010        std::string target_token;
1011
1012        if (!_reader_bits::readToken(line, source_token))
1013          throw DataFormatError("Source not found");
1014
1015        if (!_reader_bits::readToken(line, target_token))
1016          throw DataFormatError("Source not found");
1017       
1018        std::vector<std::string> tokens(map_num);
1019        for (int i = 0; i < map_num; ++i) {
1020          if (!_reader_bits::readToken(line, tokens[i])) {
1021            std::ostringstream msg;
1022            msg << "Column not found (" << i + 1 << ")";
1023            throw DataFormatError(msg.str().c_str());
1024          }
1025        }
1026        if (line >> std::ws >> c)
1027          throw DataFormatError("Extra character on the end of line");
1028       
1029        Arc a;
1030        if (!_use_arcs) {
1031
1032          typename NodeIndex::iterator it;
1033 
1034          it = _node_index.find(source_token);
1035          if (it == _node_index.end()) {
1036            std::ostringstream msg;
1037            msg << "Item not found: " << source_token;
1038            throw DataFormatError(msg.str().c_str());
1039          }
1040          Node source = it->second;
1041
1042          it = _node_index.find(target_token);
1043          if (it == _node_index.end()) {       
1044            std::ostringstream msg;           
1045            msg << "Item not found: " << target_token;
1046            throw DataFormatError(msg.str().c_str());
1047          }                                         
1048          Node target = it->second;                           
1049
1050          a = _digraph.addArc(source, target);
1051          _arc_index.insert(std::make_pair(tokens[label_index], a));
1052        } else {
1053          typename std::map<std::string, Arc>::iterator it =
1054            _arc_index.find(tokens[label_index]);
1055          if (it == _arc_index.end()) {
1056            std::ostringstream msg;
1057            msg << "Arc with label not found: " << tokens[label_index];
1058            throw DataFormatError(msg.str().c_str());       
1059          }
1060          a = it->second;
1061        }
1062
1063        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
1064          _arc_maps[i].second->set(a, tokens[map_index[i]]);
1065        }
1066
1067      }
1068      if (readSuccess()) {
1069        line.putback(c);
1070      }
1071    }
1072
1073    void readAttributes() {
1074
1075      std::set<std::string> read_attr;
1076
1077      char c;
1078      while (readLine() && line >> c && c != '@') {
1079        line.putback(c);
1080       
1081        std::string attr, token;
1082        if (!_reader_bits::readToken(line, attr))
1083          throw DataFormatError("Attribute name not found");
1084        if (!_reader_bits::readToken(line, token))
1085          throw DataFormatError("Attribute value not found");
1086        if (line >> c)
1087          throw DataFormatError("Extra character on the end of line");   
1088
1089        {
1090          std::set<std::string>::iterator it = read_attr.find(attr);
1091          if (it != read_attr.end()) {
1092            std::ostringstream msg;
1093            msg << "Multiple occurence of attribute " << attr;
1094            throw DataFormatError(msg.str().c_str());
1095          }
1096          read_attr.insert(attr);
1097        }
1098       
1099        {
1100          typename Attributes::iterator it = _attributes.lower_bound(attr);
1101          while (it != _attributes.end() && it->first == attr) {
1102            it->second->set(token);
1103            ++it;
1104          }
1105        }
1106
1107      }
1108      if (readSuccess()) {
1109        line.putback(c);
1110      }
1111      for (typename Attributes::iterator it = _attributes.begin();
1112           it != _attributes.end(); ++it) {
1113        if (read_attr.find(it->first) == read_attr.end()) {
1114          std::ostringstream msg;
1115          msg << "Attribute not found in file: " << it->first;
1116          throw DataFormatError(msg.str().c_str());
1117        }       
1118      }
1119    }
1120
1121  public:
1122
1123    /// \name Execution of the reader   
1124    /// @{
1125
1126    /// \brief Start the batch processing
1127    ///
1128    /// This function starts the batch processing
1129    void run() {
1130      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1131      if (!*_is) {
1132        throw DataFormatError("Cannot find file");
1133      }
1134     
1135      bool nodes_done = false;
1136      bool arcs_done = false;
1137      bool attributes_done = false;
1138      std::set<std::string> extra_sections;
1139
1140      line_num = 0;     
1141      readLine();
1142
1143      while (readSuccess()) {
1144        skipSection();
1145        try {
1146          char c;
1147          std::string section, caption;
1148          line >> c;
1149          _reader_bits::readToken(line, section);
1150          _reader_bits::readToken(line, caption);
1151
1152          if (line >> c)
1153            throw DataFormatError("Extra character on the end of line");
1154
1155          if (section == "nodes" && !nodes_done) {
1156            if (_nodes_caption.empty() || _nodes_caption == caption) {
1157              readNodes();
1158              nodes_done = true;
1159            }
1160          } else if ((section == "arcs" || section == "edges") &&
1161                     !arcs_done) {
1162            if (_arcs_caption.empty() || _arcs_caption == caption) {
1163              readArcs();
1164              arcs_done = true;
1165            }
1166          } else if (section == "attributes" && !attributes_done) {
1167            if (_attributes_caption.empty() || _attributes_caption == caption) {
1168              readAttributes();
1169              attributes_done = true;
1170            }
1171          } else {
1172            if (extra_sections.find(section) != extra_sections.end()) {
1173              std::ostringstream msg;
1174              msg << "Multiple occurence of section " << section;
1175              throw DataFormatError(msg.str().c_str());
1176            }
1177            Sections::iterator it = _sections.find(section);
1178            if (it != _sections.end()) {
1179              extra_sections.insert(section);
1180              it->second->process(*_is, line_num);
1181              readLine();
1182            } else {
1183              readLine();
1184              skipSection();
1185            }
1186          }
1187        } catch (DataFormatError& error) {
1188          error.line(line_num);
1189          throw;
1190        }       
1191      }
1192
1193      if (!nodes_done) {
1194        throw DataFormatError("Section @nodes not found");
1195      }
1196
1197      if (!arcs_done) {
1198        throw DataFormatError("Section @arcs not found");
1199      }
1200
1201      if (!attributes_done && !_attributes.empty()) {
1202        throw DataFormatError("Section @attributes not found");
1203      }
1204
1205    }
1206
1207    /// @}
1208   
1209  };
1210
1211  /// \relates DigraphReader
1212  template <typename Digraph>
1213  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
1214    DigraphReader<Digraph> tmp(is, digraph);
1215    return tmp;
1216  }
1217
1218  /// \relates DigraphReader
1219  template <typename Digraph>
1220  DigraphReader<Digraph> digraphReader(const std::string& fn,
1221                                       Digraph& digraph) {
1222    DigraphReader<Digraph> tmp(fn, digraph);
1223    return tmp;
1224  }
1225
1226  /// \relates DigraphReader
1227  template <typename Digraph>
1228  DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
1229    DigraphReader<Digraph> tmp(fn, digraph);
1230    return tmp;
1231  }
1232
1233  /// \ingroup lemon_io
1234  /// 
1235  /// \brief LGF reader for undirected graphs
1236  ///
1237  /// This utility reads an \ref lgf-format "LGF" file.
1238  template <typename _Graph>
1239  class GraphReader {
1240  public:
1241
1242    typedef _Graph Graph;
1243    TEMPLATE_GRAPH_TYPEDEFS(Graph);
1244   
1245  private:
1246
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    typedef std::map<std::string, _reader_bits::Section*> Sections;
1275    Sections _sections;
1276
1277    bool _use_nodes;
1278    bool _use_edges;
1279
1280    int line_num;
1281    std::istringstream line;
1282
1283  public:
1284
1285    /// \brief Constructor
1286    ///
1287    /// Construct a undirected graph reader, which reads from the given
1288    /// input stream.
1289    GraphReader(std::istream& is, Graph& graph)
1290      : _is(&is), local_is(false), _graph(graph),
1291        _use_nodes(false), _use_edges(false) {}
1292
1293    /// \brief Constructor
1294    ///
1295    /// Construct a undirected graph reader, which reads from the given
1296    /// file.
1297    GraphReader(const std::string& fn, Graph& graph)
1298      : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),
1299        _use_nodes(false), _use_edges(false) {}
1300   
1301    /// \brief Constructor
1302    ///
1303    /// Construct a undirected graph reader, which reads from the given
1304    /// file.
1305    GraphReader(const char* fn, Graph& graph)
1306      : _is(new std::ifstream(fn)), local_is(true), _graph(graph),
1307        _use_nodes(false), _use_edges(false) {}
1308
1309    /// \brief Copy constructor
1310    ///
1311    /// The copy constructor transfers all data from the other reader,
1312    /// therefore the copied reader will not be usable more.
1313    GraphReader(GraphReader& other)
1314      : _is(other._is), local_is(other.local_is), _graph(other._graph),
1315        _use_nodes(other._use_nodes), _use_edges(other._use_edges) {
1316
1317      other._is = 0;
1318      other.local_is = false;
1319     
1320      _node_index.swap(other._node_index);
1321      _edge_index.swap(other._edge_index);
1322
1323      _node_maps.swap(other._node_maps);
1324      _edge_maps.swap(other._edge_maps);
1325      _attributes.swap(other._attributes);
1326
1327      _nodes_caption = other._nodes_caption;
1328      _edges_caption = other._edges_caption;
1329      _attributes_caption = other._attributes_caption;
1330
1331      _sections.swap(other._sections);
1332    }
1333
1334    /// \brief Destructor
1335    ~GraphReader() {
1336      for (typename NodeMaps::iterator it = _node_maps.begin();
1337           it != _node_maps.end(); ++it) {
1338        delete it->second;
1339      }
1340
1341      for (typename EdgeMaps::iterator it = _edge_maps.begin();
1342           it != _edge_maps.end(); ++it) {
1343        delete it->second;
1344      }
1345
1346      for (typename Attributes::iterator it = _attributes.begin();
1347           it != _attributes.end(); ++it) {
1348        delete it->second;
1349      }
1350
1351      for (typename Sections::iterator it = _sections.begin();
1352           it != _sections.end(); ++it) {
1353        delete it->second;
1354      }
1355
1356      if (local_is) {
1357        delete _is;
1358      }
1359
1360    }
1361
1362  private:
1363   
1364    GraphReader& operator=(const GraphReader&);
1365
1366  public:
1367
1368    /// \name Reading rules
1369    /// @{
1370   
1371    /// \brief Node map reading rule
1372    ///
1373    /// Add a node map reading rule to the reader.
1374    template <typename Map>
1375    GraphReader& nodeMap(const std::string& caption, Map& map) {
1376      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1377      _reader_bits::MapStorageBase<Node>* storage =
1378        new _reader_bits::MapStorage<Node, Map>(map);
1379      _node_maps.push_back(std::make_pair(caption, storage));
1380      return *this;
1381    }
1382
1383    /// \brief Node map reading rule
1384    ///
1385    /// Add a node map reading rule with specialized converter to the
1386    /// reader.
1387    template <typename Map, typename Converter>
1388    GraphReader& nodeMap(const std::string& caption, Map& map,
1389                           const Converter& converter = Converter()) {
1390      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
1391      _reader_bits::MapStorageBase<Node>* storage =
1392        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
1393      _node_maps.push_back(std::make_pair(caption, storage));
1394      return *this;
1395    }
1396
1397    /// \brief Edge map reading rule
1398    ///
1399    /// Add an edge map reading rule to the reader.
1400    template <typename Map>
1401    GraphReader& edgeMap(const std::string& caption, Map& map) {
1402      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1403      _reader_bits::MapStorageBase<Edge>* storage =
1404        new _reader_bits::MapStorage<Edge, Map>(map);
1405      _edge_maps.push_back(std::make_pair(caption, storage));
1406      return *this;
1407    }
1408
1409    /// \brief Edge map reading rule
1410    ///
1411    /// Add an edge map reading rule with specialized converter to the
1412    /// reader.
1413    template <typename Map, typename Converter>
1414    GraphReader& edgeMap(const std::string& caption, Map& map,
1415                          const Converter& converter = Converter()) {
1416      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();
1417      _reader_bits::MapStorageBase<Edge>* storage =
1418        new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);
1419      _edge_maps.push_back(std::make_pair(caption, storage));
1420      return *this;
1421    }
1422
1423    /// \brief Arc map reading rule
1424    ///
1425    /// Add an arc map reading rule to the reader.
1426    template <typename Map>
1427    GraphReader& arcMap(const std::string& caption, Map& map) {
1428      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1429      _reader_bits::MapStorageBase<Edge>* forward_storage =
1430        new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);
1431      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1432      _reader_bits::MapStorageBase<Edge>* backward_storage =
1433        new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);
1434      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1435      return *this;
1436    }
1437
1438    /// \brief Arc map reading rule
1439    ///
1440    /// Add an arc map reading rule with specialized converter to the
1441    /// reader.
1442    template <typename Map, typename Converter>
1443    GraphReader& arcMap(const std::string& caption, Map& map,
1444                          const Converter& converter = Converter()) {
1445      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
1446      _reader_bits::MapStorageBase<Edge>* forward_storage =
1447        new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>
1448        (_graph, map, converter);
1449      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));
1450      _reader_bits::MapStorageBase<Edge>* backward_storage =
1451        new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>
1452        (_graph, map, converter);
1453      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));
1454      return *this;
1455    }
1456
1457    /// \brief Attribute reading rule
1458    ///
1459    /// Add an attribute reading rule to the reader.
1460    template <typename Value>
1461    GraphReader& attribute(const std::string& caption, Value& value) {
1462      _reader_bits::ValueStorageBase* storage =
1463        new _reader_bits::ValueStorage<Value>(value);
1464      _attributes.insert(std::make_pair(caption, storage));
1465      return *this;
1466    }
1467
1468    /// \brief Attribute reading rule
1469    ///
1470    /// Add an attribute reading rule with specialized converter to the
1471    /// reader.
1472    template <typename Value, typename Converter>
1473    GraphReader& attribute(const std::string& caption, Value& value,
1474                             const Converter& converter = Converter()) {
1475      _reader_bits::ValueStorageBase* storage =
1476        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
1477      _attributes.insert(std::make_pair(caption, storage));
1478      return *this;
1479    }
1480
1481    /// \brief Node reading rule
1482    ///
1483    /// Add a node reading rule to reader.
1484    GraphReader& node(const std::string& caption, Node& node) {
1485      typedef _reader_bits::MapLookUpConverter<Node> Converter;
1486      Converter converter(_node_index);
1487      _reader_bits::ValueStorageBase* storage =
1488        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
1489      _attributes.insert(std::make_pair(caption, storage));
1490      return *this;
1491    }
1492
1493    /// \brief Edge reading rule
1494    ///
1495    /// Add an edge reading rule to reader.
1496    GraphReader& edge(const std::string& caption, Edge& edge) {
1497      typedef _reader_bits::MapLookUpConverter<Edge> Converter;
1498      Converter converter(_edge_index);
1499      _reader_bits::ValueStorageBase* storage =
1500        new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);
1501      _attributes.insert(std::make_pair(caption, storage));
1502      return *this;
1503    }
1504
1505    /// \brief Arc reading rule
1506    ///
1507    /// Add an arc reading rule to reader.
1508    GraphReader& arc(const std::string& caption, Arc& arc) {
1509      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;
1510      Converter converter(_graph, _edge_index);
1511      _reader_bits::ValueStorageBase* storage =
1512        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
1513      _attributes.insert(std::make_pair(caption, storage));
1514      return *this;
1515    }
1516
1517    /// @}
1518
1519    /// \name Select section by name
1520    /// @{
1521
1522    /// \brief Set \c \@nodes section to be read
1523    ///
1524    /// Set \c \@nodes section to be read
1525    GraphReader& nodes(const std::string& caption) {
1526      _nodes_caption = caption;
1527      return *this;
1528    }
1529
1530    /// \brief Set \c \@edges section to be read
1531    ///
1532    /// Set \c \@edges section to be read
1533    GraphReader& edges(const std::string& caption) {
1534      _edges_caption = caption;
1535      return *this;
1536    }
1537
1538    /// \brief Set \c \@attributes section to be read
1539    ///
1540    /// Set \c \@attributes section to be read
1541    GraphReader& attributes(const std::string& caption) {
1542      _attributes_caption = caption;
1543      return *this;
1544    }
1545
1546    /// @}
1547
1548    /// \name Section readers
1549    /// @{
1550
1551    /// \brief Add a section processor with line oriented reading
1552    ///
1553    /// In the \e LGF file extra sections can be placed, which contain
1554    /// any data in arbitrary format. These sections can be read with
1555    /// this function line by line. The first parameter is the type
1556    /// descriptor of the section, the second is a functor, which
1557    /// takes just one \c std::string parameter. At the reading
1558    /// process, each line of the section will be given to the functor
1559    /// object. However, the empty lines and the comment lines are
1560    /// filtered out, and the leading whitespaces are stipped from
1561    /// each processed string.
1562    ///
1563    /// For example let's see a section, which contain several
1564    /// integers, which should be inserted into a vector.
1565    ///\code
1566    ///  @numbers
1567    ///  12 45 23
1568    ///  4
1569    ///  23 6
1570    ///\endcode
1571    ///
1572    /// The functor is implemented as an struct:
1573    ///\code
1574    ///  struct NumberSection {
1575    ///    std::vector<int>& _data;
1576    ///    NumberSection(std::vector<int>& data) : _data(data) {}
1577    ///    void operator()(const std::string& line) {
1578    ///      std::istringstream ls(line);
1579    ///      int value;
1580    ///      while (ls >> value) _data.push_back(value);
1581    ///    }
1582    ///  };
1583    ///
1584    ///  // ...
1585    ///
1586    ///  reader.sectionLines("numbers", NumberSection(vec)); 
1587    ///\endcode
1588    template <typename Functor>
1589    GraphReader& sectionLines(const std::string& type, Functor functor) {
1590      LEMON_ASSERT(!type.empty(), "Type is not empty.");
1591      LEMON_ASSERT(_sections.find(type) == _sections.end(),
1592                   "Multiple reading of section.");
1593      LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
1594                   type != "attributes", "Multiple reading of section.");
1595      _sections.insert(std::make_pair(type,
1596        new _reader_bits::LineSection<Functor>(functor)));
1597      return *this;
1598    }
1599
1600
1601    /// \brief Add a section processor with stream oriented reading
1602    ///
1603    /// In the \e LGF file extra sections can be placed, which contain
1604    /// any data in arbitrary format. These sections can be read
1605    /// directly with this function. The first parameter is the type
1606    /// of the section, the second is a functor, which takes an \c
1607    /// std::istream& and an int& parameter, the latter regard to the
1608    /// line number of stream. The functor can read the input while
1609    /// the section go on, and the line number should be modified
1610    /// accordingly.
1611    template <typename Functor>
1612    GraphReader& sectionStream(const std::string& type, Functor functor) {
1613      LEMON_ASSERT(!type.empty(), "Type is not empty.");
1614      LEMON_ASSERT(_sections.find(type) == _sections.end(),
1615                   "Multiple reading of section.");
1616      LEMON_ASSERT(type != "nodes" && type != "arcs" && type != "edges" &&
1617                   type != "attributes", "Multiple reading of section.");
1618      _sections.insert(std::make_pair(type,
1619         new _reader_bits::StreamSection<Functor>(functor)));
1620      return *this;
1621    }   
1622   
1623    /// @}
1624
1625    /// \name Using previously constructed node or edge set
1626    /// @{
1627
1628    /// \brief Use previously constructed node set
1629    ///
1630    /// Use previously constructed node set, and specify the node
1631    /// label map.
1632    template <typename Map>
1633    GraphReader& useNodes(const Map& map) {
1634      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1635      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1636      _use_nodes = true;
1637      _writer_bits::DefaultConverter<typename Map::Value> converter;
1638      for (NodeIt n(_graph); n != INVALID; ++n) {
1639        _node_index.insert(std::make_pair(converter(map[n]), n));
1640      }
1641      return *this;
1642    }
1643
1644    /// \brief Use previously constructed node set
1645    ///
1646    /// Use previously constructed node set, and specify the node
1647    /// label map and a functor which converts the label map values to
1648    /// std::string.
1649    template <typename Map, typename Converter>
1650    GraphReader& useNodes(const Map& map,
1651                            const Converter& converter = Converter()) {
1652      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1653      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
1654      _use_nodes = true;
1655      for (NodeIt n(_graph); n != INVALID; ++n) {
1656        _node_index.insert(std::make_pair(converter(map[n]), n));
1657      }
1658      return *this;
1659    }
1660
1661    /// \brief Use previously constructed edge set
1662    ///
1663    /// Use previously constructed edge set, and specify the edge
1664    /// label map.
1665    template <typename Map>
1666    GraphReader& useEdges(const Map& map) {
1667      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1668      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1669      _use_edges = true;
1670      _writer_bits::DefaultConverter<typename Map::Value> converter;
1671      for (EdgeIt a(_graph); a != INVALID; ++a) {
1672        _edge_index.insert(std::make_pair(converter(map[a]), a));
1673      }
1674      return *this;
1675    }
1676
1677    /// \brief Use previously constructed edge set
1678    ///
1679    /// Use previously constructed edge set, and specify the edge
1680    /// label map and a functor which converts the label map values to
1681    /// std::string.
1682    template <typename Map, typename Converter>
1683    GraphReader& useEdges(const Map& map,
1684                            const Converter& converter = Converter()) {
1685      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();
1686      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");
1687      _use_edges = true;
1688      for (EdgeIt a(_graph); a != INVALID; ++a) {
1689        _edge_index.insert(std::make_pair(converter(map[a]), a));
1690      }
1691      return *this;
1692    }
1693
1694    /// @}
1695
1696  private:
1697
1698    bool readLine() {
1699      std::string str;
1700      while(++line_num, std::getline(*_is, str)) {
1701        line.clear(); line.str(str);
1702        char c;
1703        if (line >> std::ws >> c && c != '#') {
1704          line.putback(c);
1705          return true;
1706        }
1707      }
1708      return false;
1709    }
1710
1711    bool readSuccess() {
1712      return static_cast<bool>(*_is);
1713    }
1714   
1715    void skipSection() {
1716      char c;
1717      while (readSuccess() && line >> c && c != '@') {
1718        readLine();
1719      }
1720      line.putback(c);
1721    }
1722
1723    void readNodes() {
1724
1725      std::vector<int> map_index(_node_maps.size());
1726      int map_num, label_index;
1727
1728      if (!readLine())
1729        throw DataFormatError("Cannot find map captions");
1730     
1731      {
1732        std::map<std::string, int> maps;
1733       
1734        std::string map;
1735        int index = 0;
1736        while (_reader_bits::readToken(line, map)) {
1737          if (maps.find(map) != maps.end()) {
1738            std::ostringstream msg;
1739            msg << "Multiple occurence of node map: " << map;
1740            throw DataFormatError(msg.str().c_str());
1741          }
1742          maps.insert(std::make_pair(map, index));
1743          ++index;
1744        }
1745       
1746        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1747          std::map<std::string, int>::iterator jt =
1748            maps.find(_node_maps[i].first);
1749          if (jt == maps.end()) {
1750            std::ostringstream msg;
1751            msg << "Map not found in file: " << _node_maps[i].first;
1752            throw DataFormatError(msg.str().c_str());
1753          }
1754          map_index[i] = jt->second;
1755        }
1756
1757        {
1758          std::map<std::string, int>::iterator jt = maps.find("label");
1759          if (jt == maps.end())
1760            throw DataFormatError("Label map not found in file");
1761          label_index = jt->second;
1762        }
1763        map_num = maps.size();
1764      }
1765
1766      char c;
1767      while (readLine() && line >> c && c != '@') {
1768        line.putback(c);
1769
1770        std::vector<std::string> tokens(map_num);
1771        for (int i = 0; i < map_num; ++i) {
1772          if (!_reader_bits::readToken(line, tokens[i])) {
1773            std::ostringstream msg;
1774            msg << "Column not found (" << i + 1 << ")";
1775            throw DataFormatError(msg.str().c_str());
1776          }
1777        }
1778        if (line >> std::ws >> c)
1779          throw DataFormatError("Extra character on the end of line");
1780       
1781        Node n;
1782        if (!_use_nodes) {
1783          n = _graph.addNode();
1784          _node_index.insert(std::make_pair(tokens[label_index], n));
1785        } else {
1786          typename std::map<std::string, Node>::iterator it =
1787            _node_index.find(tokens[label_index]);
1788          if (it == _node_index.end()) {
1789            std::ostringstream msg;
1790            msg << "Node with label not found: " << tokens[label_index];
1791            throw DataFormatError(msg.str().c_str());       
1792          }
1793          n = it->second;
1794        }
1795
1796        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
1797          _node_maps[i].second->set(n, tokens[map_index[i]]);
1798        }
1799
1800      }
1801      if (readSuccess()) {
1802        line.putback(c);
1803      }
1804    }
1805
1806    void readEdges() {
1807
1808      std::vector<int> map_index(_edge_maps.size());
1809      int map_num, label_index;
1810
1811      if (!readLine())
1812        throw DataFormatError("Cannot find map captions");
1813     
1814      {
1815        std::map<std::string, int> maps;
1816       
1817        std::string map;
1818        int index = 0;
1819        while (_reader_bits::readToken(line, map)) {
1820          if (maps.find(map) != maps.end()) {
1821            std::ostringstream msg;
1822            msg << "Multiple occurence of edge map: " << map;
1823            throw DataFormatError(msg.str().c_str());
1824          }
1825          maps.insert(std::make_pair(map, index));
1826          ++index;
1827        }
1828       
1829        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1830          std::map<std::string, int>::iterator jt =
1831            maps.find(_edge_maps[i].first);
1832          if (jt == maps.end()) {
1833            std::ostringstream msg;
1834            msg << "Map not found in file: " << _edge_maps[i].first;
1835            throw DataFormatError(msg.str().c_str());
1836          }
1837          map_index[i] = jt->second;
1838        }
1839
1840        {
1841          std::map<std::string, int>::iterator jt = maps.find("label");
1842          if (jt == maps.end())
1843            throw DataFormatError("Label map not found in file");
1844          label_index = jt->second;
1845        }
1846        map_num = maps.size();
1847      }
1848
1849      char c;
1850      while (readLine() && line >> c && c != '@') {
1851        line.putback(c);
1852
1853        std::string source_token;
1854        std::string target_token;
1855
1856        if (!_reader_bits::readToken(line, source_token))
1857          throw DataFormatError("Source not found");
1858
1859        if (!_reader_bits::readToken(line, target_token))
1860          throw DataFormatError("Source not found");
1861       
1862        std::vector<std::string> tokens(map_num);
1863        for (int i = 0; i < map_num; ++i) {
1864          if (!_reader_bits::readToken(line, tokens[i])) {
1865            std::ostringstream msg;
1866            msg << "Column not found (" << i + 1 << ")";
1867            throw DataFormatError(msg.str().c_str());
1868          }
1869        }
1870        if (line >> std::ws >> c)
1871          throw DataFormatError("Extra character on the end of line");
1872       
1873        Edge e;
1874        if (!_use_edges) {
1875
1876          typename NodeIndex::iterator it;
1877 
1878          it = _node_index.find(source_token);
1879          if (it == _node_index.end()) {
1880            std::ostringstream msg;
1881            msg << "Item not found: " << source_token;
1882            throw DataFormatError(msg.str().c_str());
1883          }
1884          Node source = it->second;
1885
1886          it = _node_index.find(target_token);
1887          if (it == _node_index.end()) {       
1888            std::ostringstream msg;           
1889            msg << "Item not found: " << target_token;
1890            throw DataFormatError(msg.str().c_str());
1891          }                                         
1892          Node target = it->second;                           
1893
1894          e = _graph.addEdge(source, target);
1895          _edge_index.insert(std::make_pair(tokens[label_index], e));
1896        } else {
1897          typename std::map<std::string, Edge>::iterator it =
1898            _edge_index.find(tokens[label_index]);
1899          if (it == _edge_index.end()) {
1900            std::ostringstream msg;
1901            msg << "Edge with label not found: " << tokens[label_index];
1902            throw DataFormatError(msg.str().c_str());       
1903          }
1904          e = it->second;
1905        }
1906
1907        for (int i = 0; i < static_cast<int>(_edge_maps.size()); ++i) {
1908          _edge_maps[i].second->set(e, tokens[map_index[i]]);
1909        }
1910
1911      }
1912      if (readSuccess()) {
1913        line.putback(c);
1914      }
1915    }
1916
1917    void readAttributes() {
1918
1919      std::set<std::string> read_attr;
1920
1921      char c;
1922      while (readLine() && line >> c && c != '@') {
1923        line.putback(c);
1924       
1925        std::string attr, token;
1926        if (!_reader_bits::readToken(line, attr))
1927          throw DataFormatError("Attribute name not found");
1928        if (!_reader_bits::readToken(line, token))
1929          throw DataFormatError("Attribute value not found");
1930        if (line >> c)
1931          throw DataFormatError("Extra character on the end of line");   
1932
1933        {
1934          std::set<std::string>::iterator it = read_attr.find(attr);
1935          if (it != read_attr.end()) {
1936            std::ostringstream msg;
1937            msg << "Multiple occurence of attribute " << attr;
1938            throw DataFormatError(msg.str().c_str());
1939          }
1940          read_attr.insert(attr);
1941        }
1942       
1943        {
1944          typename Attributes::iterator it = _attributes.lower_bound(attr);
1945          while (it != _attributes.end() && it->first == attr) {
1946            it->second->set(token);
1947            ++it;
1948          }
1949        }
1950
1951      }
1952      if (readSuccess()) {
1953        line.putback(c);
1954      }
1955      for (typename Attributes::iterator it = _attributes.begin();
1956           it != _attributes.end(); ++it) {
1957        if (read_attr.find(it->first) == read_attr.end()) {
1958          std::ostringstream msg;
1959          msg << "Attribute not found in file: " << it->first;
1960          throw DataFormatError(msg.str().c_str());
1961        }       
1962      }
1963    }
1964
1965  public:
1966
1967    /// \name Execution of the reader   
1968    /// @{
1969
1970    /// \brief Start the batch processing
1971    ///
1972    /// This function starts the batch processing
1973    void run() {
1974     
1975      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
1976     
1977      bool nodes_done = false;
1978      bool edges_done = false;
1979      bool attributes_done = false;
1980      std::set<std::string> extra_sections;
1981
1982      line_num = 0;     
1983      readLine();
1984
1985      while (readSuccess()) {
1986        skipSection();
1987        try {
1988          char c;
1989          std::string section, caption;
1990          line >> c;
1991          _reader_bits::readToken(line, section);
1992          _reader_bits::readToken(line, caption);
1993
1994          if (line >> c)
1995            throw DataFormatError("Extra character on the end of line");
1996
1997          if (section == "nodes" && !nodes_done) {
1998            if (_nodes_caption.empty() || _nodes_caption == caption) {
1999              readNodes();
2000              nodes_done = true;
2001            }
2002          } else if ((section == "edges" || section == "arcs") &&
2003                     !edges_done) {
2004            if (_edges_caption.empty() || _edges_caption == caption) {
2005              readEdges();
2006              edges_done = true;
2007            }
2008          } else if (section == "attributes" && !attributes_done) {
2009            if (_attributes_caption.empty() || _attributes_caption == caption) {
2010              readAttributes();
2011              attributes_done = true;
2012            }
2013          } else {
2014            if (extra_sections.find(section) != extra_sections.end()) {
2015              std::ostringstream msg;
2016              msg << "Multiple occurence of section " << section;
2017              throw DataFormatError(msg.str().c_str());
2018            }
2019            Sections::iterator it = _sections.find(section);
2020            if (it != _sections.end()) {
2021              extra_sections.insert(section);
2022              it->second->process(*_is, line_num);
2023              readLine();
2024            } else {
2025              readLine();
2026              skipSection();
2027            }
2028          }
2029        } catch (DataFormatError& error) {
2030          error.line(line_num);
2031          throw;
2032        }       
2033      }
2034
2035      if (!nodes_done) {
2036        throw DataFormatError("Section @nodes not found");
2037      }
2038
2039      if (!edges_done) {
2040        throw DataFormatError("Section @edges not found");
2041      }
2042
2043      if (!attributes_done && !_attributes.empty()) {
2044        throw DataFormatError("Section @attributes not found");
2045      }
2046
2047    }
2048
2049    /// @}
2050   
2051  };
2052
2053  /// \relates GraphReader
2054  template <typename Graph>
2055  GraphReader<Graph> graphReader(std::istream& is, Graph& graph) {
2056    GraphReader<Graph> tmp(is, graph);
2057    return tmp;
2058  }
2059
2060  /// \relates GraphReader
2061  template <typename Graph>
2062  GraphReader<Graph> graphReader(const std::string& fn,
2063                                       Graph& graph) {
2064    GraphReader<Graph> tmp(fn, graph);
2065    return tmp;
2066  }
2067
2068  /// \relates GraphReader
2069  template <typename Graph>
2070  GraphReader<Graph> graphReader(const char* fn, Graph& graph) {
2071    GraphReader<Graph> tmp(fn, graph);
2072    return tmp;
2073  }
2074}
2075
2076#endif
Note: See TracBrowser for help on using the repository browser.