COIN-OR::LEMON - Graph Library

source: lemon-1.0/lemon/lgf_reader.h @ 322:8c4d380787cf

Last change on this file since 322:8c4d380787cf was 307:a3a69f5bba62, checked in by Akos Ladanyi <ladanyi@…>, 11 years ago

Fix compilation with Visual Studio 2005.

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