COIN-OR::LEMON - Graph Library

source: lemon/lemon/lgf_reader.h @ 156:e561aa7675de

Last change on this file since 156:e561aa7675de was 156:e561aa7675de, checked in by Alpar Juttner <alpar@…>, 16 years ago

More flexible header names in .lgf + largely improved doc

File size: 27.8 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    class ValueStorageBase {
104    public:
105      ValueStorageBase() {}
106      virtual ~ValueStorageBase() {}
107
108      virtual void set(const std::string&) = 0;
109    };
110
111    template <typename _Value, typename _Converter = DefaultConverter<_Value> >
112    class ValueStorage : public ValueStorageBase {
113    public:
114      typedef _Value Value;
115      typedef _Converter Converter;
116
117    private:
118      Value& _value;
119      Converter _converter;
120
121    public:
122      ValueStorage(Value& value, const Converter& converter = Converter())
123        : _value(value), _converter(converter) {}
124
125      virtual void set(const std::string& value) {
126        _value = _converter(value);
127      }
128    };
129
130    template <typename Value>
131    struct MapLookUpConverter {
132      const std::map<std::string, Value>& _map;
133
134      MapLookUpConverter(const std::map<std::string, Value>& map)
135        : _map(map) {}
136
137      Value operator()(const std::string& str) {
138        typename std::map<std::string, Value>::const_iterator it =
139          _map.find(str);
140        if (it == _map.end()) {
141          std::ostringstream msg;
142          msg << "Item not found: " << str;
143          throw DataFormatError(msg.str().c_str());
144        }
145        return it->second;
146      }
147    };
148
149    bool isWhiteSpace(char c) {
150      return c == ' ' || c == '\t' || c == '\v' ||
151        c == '\n' || c == '\r' || c == '\f';
152    }
153   
154    bool isOct(char c) {
155      return '0' <= c && c <='7';
156    }
157   
158    int valueOct(char c) {
159      LEMON_ASSERT(isOct(c), "The character is not octal.");
160      return c - '0';
161    }
162
163    bool isHex(char c) {
164      return ('0' <= c && c <= '9') ||
165        ('a' <= c && c <= 'z') ||
166        ('A' <= c && c <= 'Z');
167    }
168   
169    int valueHex(char c) {
170      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
171      if ('0' <= c && c <= '9') return c - '0';
172      if ('a' <= c && c <= 'z') return c - 'a' + 10;
173      return c - 'A' + 10;
174    }
175
176    bool isIdentifierFirstChar(char c) {
177      return ('a' <= c && c <= 'z') ||
178        ('A' <= c && c <= 'Z') || c == '_';
179    }
180
181    bool isIdentifierChar(char c) {
182      return isIdentifierFirstChar(c) ||
183        ('0' <= c && c <= '9');
184    }
185
186    char readEscape(std::istream& is) {
187      char c;
188      if (!is.get(c))
189        throw DataFormatError("Escape format error");
190
191      switch (c) {
192      case '\\':
193        return '\\';
194      case '\"':
195        return '\"';
196      case '\'':
197        return '\'';
198      case '\?':
199        return '\?';
200      case 'a':
201        return '\a';
202      case 'b':
203        return '\b';
204      case 'f':
205        return '\f';
206      case 'n':
207        return '\n';
208      case 'r':
209        return '\r';
210      case 't':
211        return '\t';
212      case 'v':
213        return '\v';
214      case 'x':
215        {
216          int code;
217          if (!is.get(c) || !isHex(c))
218            throw DataFormatError("Escape format error");
219          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
220          else code = code * 16 + valueHex(c);
221          return code;
222        }
223      default:
224        {
225          int code;
226          if (!isOct(c))
227            throw DataFormatError("Escape format error");
228          else if (code = valueOct(c), !is.get(c) || !isOct(c))
229            is.putback(c);
230          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
231            is.putback(c);
232          else code = code * 8 + valueOct(c);
233          return code;
234        }             
235      }
236    }
237   
238    std::istream& readToken(std::istream& is, std::string& str) {
239      std::ostringstream os;
240
241      char c;
242      is >> std::ws;
243     
244      if (!is.get(c))
245        return is;
246
247      if (c == '\"') {
248        while (is.get(c) && c != '\"') {
249          if (c == '\\')
250            c = readEscape(is);
251          os << c;
252        }
253        if (!is)
254          throw DataFormatError("Quoted format error");
255      } else {
256        is.putback(c);
257        while (is.get(c) && !isWhiteSpace(c)) {
258          if (c == '\\')
259            c = readEscape(is);
260          os << c;
261        }
262        if (!is) {
263          is.clear();
264        } else {
265          is.putback(c);
266        }
267      }
268      str = os.str();
269      return is;
270    }
271   
272  }
273
274  /// \ingroup lemon_io
275  /// 
276  /// \brief LGF reader for directed graphs
277  ///
278  /// This utility reads an \ref lgf-format "LGF" file.
279  ///
280  /// The reading method does a batch processing. The user creates a
281  /// reader object, then various reading rules can be added to the
282  /// reader, and eventually the reading is executed with the \c run()
283  /// member function. A map reading rule can be added to the reader
284  /// with the \c nodeMap() or \c arcMap() members. An optional
285  /// converter parameter can also be added as a standard functor converting from
286  /// std::string to the value type of the map. If it is set, it will
287  /// determine how the tokens in the file should be is converted to the map's
288  /// value type. If the functor is not set, then a default conversion
289  /// will be used. One map can be read into multiple map objects at the
290  /// same time. The \c attribute(), \c node() and \c arc() functions
291  /// are used to add attribute reading rules.
292  ///
293  ///\code
294  ///     DigraphReader<Digraph>(std::cin, digraph).
295  ///       nodeMap("coordinates", coord_map).
296  ///       arcMap("capacity", cap_map).
297  ///       node("source", src).
298  ///       node("target", trg).
299  ///       attribute("caption", caption).
300  ///       run();
301  ///\endcode
302  ///
303  /// By default the reader uses the first section in the file of the
304  /// proper type. If a section has an optional name, then it can be
305  /// selected for reading by giving an optional name parameter to
306  /// the \c nodes(), \c arcs() or \c attributes()
307  /// functions.
308  ///
309  /// The \c useNodes() and \c useArcs() functions are used to tell the reader
310  /// that the nodes or arcs should not be constructed (added to the
311  /// graph) during the reading, but instead the label map of the items
312  /// are given as a parameter of these functions. An
313  /// application of these function is multipass reading, which is
314  /// important if two \e \@arcs sections must be read from the
315  /// file. In this example the first phase would read the node set and one
316  /// of the arc sets, while the second phase would read the second arc
317  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
318  /// The previously read label node map should be passed to the \c
319  /// useNodes() functions. Another application of multipass reading when
320  /// paths are given as a node map or an arc map. It is impossible read this in
321  /// a single pass, because the arcs are not constructed when the node
322  /// maps are read.
323  template <typename _Digraph>
324  class DigraphReader {
325  public:
326
327    typedef _Digraph Digraph;
328    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
329   
330  private:
331
332
333    std::istream* _is;
334    bool local_is;
335
336    Digraph& _digraph;
337
338    std::string _nodes_caption;
339    std::string _arcs_caption;
340    std::string _attributes_caption;
341
342    typedef std::map<std::string, Node> NodeIndex;
343    NodeIndex _node_index;
344    typedef std::map<std::string, Arc> ArcIndex;
345    ArcIndex _arc_index;
346   
347    typedef std::vector<std::pair<std::string,
348      _reader_bits::MapStorageBase<Node>*> > NodeMaps;   
349    NodeMaps _node_maps;
350
351    typedef std::vector<std::pair<std::string,
352      _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
353    ArcMaps _arc_maps;
354
355    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
356      Attributes;
357    Attributes _attributes;
358
359    bool _use_nodes;
360    bool _use_arcs;
361
362    int line_num;
363    std::istringstream line;
364
365  public:
366
367    /// \brief Constructor
368    ///
369    /// Construct a directed graph reader, which reads from the given
370    /// input stream.
371    DigraphReader(std::istream& is, Digraph& digraph)
372      : _is(&is), local_is(false), _digraph(digraph),
373        _use_nodes(false), _use_arcs(false) {}
374
375    /// \brief Constructor
376    ///
377    /// Construct a directed graph reader, which reads from the given
378    /// file.
379    DigraphReader(const std::string& fn, Digraph& digraph)
380      : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
381        _use_nodes(false), _use_arcs(false) {}
382   
383    /// \brief Constructor
384    ///
385    /// Construct a directed graph reader, which reads from the given
386    /// file.
387    DigraphReader(const char* fn, Digraph& digraph)
388      : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
389        _use_nodes(false), _use_arcs(false) {}
390
391    /// \brief Copy constructor
392    ///
393    /// The copy constructor transfers all data from the other reader,
394    /// therefore the copied reader will not be usable more.
395    DigraphReader(DigraphReader& other)
396      : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
397        _use_nodes(other._use_nodes), _use_arcs(other._use_arcs) {
398
399      other.is = 0;
400      other.local_is = false;
401     
402      _node_index.swap(other._node_index);
403      _arc_index.swap(other._arc_index);
404
405      _node_maps.swap(other._node_maps);
406      _arc_maps.swap(other._arc_maps);
407      _attributes.swap(other._attributes);
408
409      _nodes_caption = other._nodes_caption;
410      _arcs_caption = other._arcs_caption;
411      _attributes_caption = other._attributes_caption;
412    }
413
414    /// \brief Destructor
415    ~DigraphReader() {
416      for (typename NodeMaps::iterator it = _node_maps.begin();
417           it != _node_maps.end(); ++it) {
418        delete it->second;
419      }
420
421      for (typename ArcMaps::iterator it = _arc_maps.begin();
422           it != _arc_maps.end(); ++it) {
423        delete it->second;
424      }
425
426      for (typename Attributes::iterator it = _attributes.begin();
427           it != _attributes.end(); ++it) {
428        delete it->second;
429      }
430
431      if (local_is) {
432        delete _is;
433      }
434
435    }
436
437  private:
438   
439    DigraphReader& operator=(const DigraphReader&);
440
441  public:
442
443    /// \name Reading rules
444    /// @{
445   
446    /// \brief Node map reading rule
447    ///
448    /// Add a node map reading rule to the reader.
449    template <typename Map>
450    DigraphReader& nodeMap(const std::string& caption, Map& map) {
451      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
452      _reader_bits::MapStorageBase<Node>* storage =
453        new _reader_bits::MapStorage<Node, Map>(map);
454      _node_maps.push_back(std::make_pair(caption, storage));
455      return *this;
456    }
457
458    /// \brief Node map reading rule
459    ///
460    /// Add a node map reading rule with specialized converter to the
461    /// reader.
462    template <typename Map, typename Converter>
463    DigraphReader& nodeMap(const std::string& caption, Map& map,
464                           const Converter& converter = Converter()) {
465      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
466      _reader_bits::MapStorageBase<Node>* storage =
467        new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
468      _node_maps.push_back(std::make_pair(caption, storage));
469      return *this;
470    }
471
472    /// \brief Arc map reading rule
473    ///
474    /// Add an arc map reading rule to the reader.
475    template <typename Map>
476    DigraphReader& arcMap(const std::string& caption, Map& map) {
477      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
478      _reader_bits::MapStorageBase<Arc>* storage =
479        new _reader_bits::MapStorage<Arc, Map>(map);
480      _arc_maps.push_back(std::make_pair(caption, storage));
481      return *this;
482    }
483
484    /// \brief Arc map reading rule
485    ///
486    /// Add an arc map reading rule with specialized converter to the
487    /// reader.
488    template <typename Map, typename Converter>
489    DigraphReader& arcMap(const std::string& caption, Map& map,
490                          const Converter& converter = Converter()) {
491      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
492      _reader_bits::MapStorageBase<Arc>* storage =
493        new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
494      _arc_maps.push_back(std::make_pair(caption, storage));
495      return *this;
496    }
497
498    /// \brief Attribute reading rule
499    ///
500    /// Add an attribute reading rule to the reader.
501    template <typename Value>
502    DigraphReader& attribute(const std::string& caption, Value& value) {
503      _reader_bits::ValueStorageBase* storage =
504        new _reader_bits::ValueStorage<Value>(value);
505      _attributes.insert(std::make_pair(caption, storage));
506      return *this;
507    }
508
509    /// \brief Attribute reading rule
510    ///
511    /// Add an attribute reading rule with specialized converter to the
512    /// reader.
513    template <typename Value, typename Converter>
514    DigraphReader& attribute(const std::string& caption, Value& value,
515                             const Converter& converter = Converter()) {
516      _reader_bits::ValueStorageBase* storage =
517        new _reader_bits::ValueStorage<Value, Converter>(value, converter);
518      _attributes.insert(std::make_pair(caption, storage));
519      return *this;
520    }
521
522    /// \brief Node reading rule
523    ///
524    /// Add a node reading rule to reader.
525    DigraphReader& node(const std::string& caption, Node& node) {
526      typedef _reader_bits::MapLookUpConverter<Node> Converter;
527      Converter converter(_node_index);
528      _reader_bits::ValueStorageBase* storage =
529        new _reader_bits::ValueStorage<Node, Converter>(node, converter);
530      _attributes.insert(std::make_pair(caption, storage));
531      return *this;
532    }
533
534    /// \brief Arc reading rule
535    ///
536    /// Add an arc reading rule to reader.
537    DigraphReader& arc(const std::string& caption, Arc& arc) {
538      typedef _reader_bits::MapLookUpConverter<Arc> Converter;
539      Converter converter(_arc_index);
540      _reader_bits::ValueStorageBase* storage =
541        new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
542      _attributes.insert(std::make_pair(caption, storage));
543      return *this;
544    }
545
546    /// @}
547
548    /// \name Select section by name
549    /// @{
550
551    /// \brief Set \c \@nodes section to be read
552    ///
553    /// Set \c \@nodes section to be read
554    DigraphReader& nodes(const std::string& caption) {
555      _nodes_caption = caption;
556      return *this;
557    }
558
559    /// \brief Set \c \@arcs section to be read
560    ///
561    /// Set \c \@arcs section to be read
562    DigraphReader& arcs(const std::string& caption) {
563      _arcs_caption = caption;
564      return *this;
565    }
566
567    /// \brief Set \c \@attributes section to be read
568    ///
569    /// Set \c \@attributes section to be read
570    DigraphReader& attributes(const std::string& caption) {
571      _attributes_caption = caption;
572      return *this;
573    }
574
575    /// @}
576
577    /// \name Using previously constructed node or arc set
578    /// @{
579
580    /// \brief Use previously constructed node set
581    ///
582    /// Use previously constructed node set, and specify the node
583    /// label map.
584    template <typename Map>
585    DigraphReader& useNodes(const Map& map) {
586      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
587      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
588      _use_nodes = true;
589      _writer_bits::DefaultConverter<typename Map::Value> converter;
590      for (NodeIt n(_digraph); n != INVALID; ++n) {
591        _node_index.insert(std::make_pair(converter(map[n]), n));
592      }
593      return *this;
594    }
595
596    /// \brief Use previously constructed node set
597    ///
598    /// Use previously constructed node set, and specify the node
599    /// label map and a functor which converts the label map values to
600    /// std::string.
601    template <typename Map, typename Converter>
602    DigraphReader& useNodes(const Map& map,
603                            const Converter& converter = Converter()) {
604      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
605      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
606      _use_nodes = true;
607      for (NodeIt n(_digraph); n != INVALID; ++n) {
608        _node_index.insert(std::make_pair(converter(map[n]), n));
609      }
610      return *this;
611    }
612
613    /// \brief Use previously constructed arc set
614    ///
615    /// Use previously constructed arc set, and specify the arc
616    /// label map.
617    template <typename Map>
618    DigraphReader& useArcs(const Map& map) {
619      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
620      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
621      _use_arcs = true;
622      _writer_bits::DefaultConverter<typename Map::Value> converter;
623      for (ArcIt a(_digraph); a != INVALID; ++a) {
624        _arc_index.insert(std::make_pair(converter(map[a]), a));
625      }
626      return *this;
627    }
628
629    /// \brief Use previously constructed arc set
630    ///
631    /// Use previously constructed arc set, and specify the arc
632    /// label map and a functor which converts the label map values to
633    /// std::string.
634    template <typename Map, typename Converter>
635    DigraphReader& useArcs(const Map& map,
636                            const Converter& converter = Converter()) {
637      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
638      LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
639      _use_arcs = true;
640      for (ArcIt a(_digraph); a != INVALID; ++a) {
641        _arc_index.insert(std::make_pair(converter(map[a]), a));
642      }
643      return *this;
644    }
645
646    /// @}
647
648  private:
649
650    bool readLine() {
651      std::string str;
652      while(++line_num, std::getline(*_is, str)) {
653        line.clear(); line.str(str);
654        char c;
655        if (line >> std::ws >> c && c != '#') {
656          line.putback(c);
657          return true;
658        }
659      }
660      return false;
661    }
662
663    bool readSuccess() {
664      return static_cast<bool>(*_is);
665    }
666   
667    void skipSection() {
668      char c;
669      while (readSuccess() && line >> c && c != '@') {
670        readLine();
671      }
672      line.putback(c);
673    }
674
675    void readNodes() {
676
677      std::vector<int> map_index(_node_maps.size());
678      int map_num, label_index;
679
680      if (!readLine())
681        throw DataFormatError("Cannot find map captions");
682     
683      {
684        std::map<std::string, int> maps;
685       
686        std::string map;
687        int index = 0;
688        while (_reader_bits::readToken(line, map)) {
689          if (maps.find(map) != maps.end()) {
690            std::ostringstream msg;
691            msg << "Multiple occurence of node map: " << map;
692            throw DataFormatError(msg.str().c_str());
693          }
694          maps.insert(std::make_pair(map, index));
695          ++index;
696        }
697       
698        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
699          std::map<std::string, int>::iterator jt =
700            maps.find(_node_maps[i].first);
701          if (jt == maps.end()) {
702            std::ostringstream msg;
703            msg << "Map not found in file: " << _node_maps[i].first;
704            throw DataFormatError(msg.str().c_str());
705          }
706          map_index[i] = jt->second;
707        }
708
709        {
710          std::map<std::string, int>::iterator jt = maps.find("label");
711          if (jt == maps.end())
712            throw DataFormatError("Label map not found in file");
713          label_index = jt->second;
714        }
715        map_num = maps.size();
716      }
717
718      char c;
719      while (readLine() && line >> c && c != '@') {
720        line.putback(c);
721
722        std::vector<std::string> tokens(map_num);
723        for (int i = 0; i < map_num; ++i) {
724          if (!_reader_bits::readToken(line, tokens[i])) {
725            std::ostringstream msg;
726            msg << "Column not found (" << i + 1 << ")";
727            throw DataFormatError(msg.str().c_str());
728          }
729        }
730        if (line >> std::ws >> c)
731          throw DataFormatError("Extra character on the end of line");
732       
733        Node n;
734        if (!_use_nodes) {
735          n = _digraph.addNode();
736          _node_index.insert(std::make_pair(tokens[label_index], n));
737        } else {
738          typename std::map<std::string, Node>::iterator it =
739            _node_index.find(tokens[label_index]);
740          if (it == _node_index.end()) {
741            std::ostringstream msg;
742            msg << "Node with label not found: " << tokens[label_index];
743            throw DataFormatError(msg.str().c_str());       
744          }
745          n = it->second;
746        }
747
748        for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
749          _node_maps[i].second->set(n, tokens[map_index[i]]);
750        }
751
752      }
753      if (readSuccess()) {
754        line.putback(c);
755      }
756    }
757
758    void readArcs() {
759
760      std::vector<int> map_index(_arc_maps.size());
761      int map_num, label_index;
762
763      if (!readLine())
764        throw DataFormatError("Cannot find map captions");
765     
766      {
767        std::map<std::string, int> maps;
768       
769        std::string map;
770        int index = 0;
771        while (_reader_bits::readToken(line, map)) {
772          if (maps.find(map) != maps.end()) {
773            std::ostringstream msg;
774            msg << "Multiple occurence of arc map: " << map;
775            throw DataFormatError(msg.str().c_str());
776          }
777          maps.insert(std::make_pair(map, index));
778          ++index;
779        }
780       
781        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
782          std::map<std::string, int>::iterator jt =
783            maps.find(_arc_maps[i].first);
784          if (jt == maps.end()) {
785            std::ostringstream msg;
786            msg << "Map not found in file: " << _arc_maps[i].first;
787            throw DataFormatError(msg.str().c_str());
788          }
789          map_index[i] = jt->second;
790        }
791
792        {
793          std::map<std::string, int>::iterator jt = maps.find("label");
794          if (jt == maps.end())
795            throw DataFormatError("Label map not found in file");
796          label_index = jt->second;
797        }
798        map_num = maps.size();
799      }
800
801      char c;
802      while (readLine() && line >> c && c != '@') {
803        line.putback(c);
804
805        std::string source_token;
806        std::string target_token;
807
808        if (!_reader_bits::readToken(line, source_token))
809          throw DataFormatError("Source not found");
810
811        if (!_reader_bits::readToken(line, target_token))
812          throw DataFormatError("Source not found");
813       
814        std::vector<std::string> tokens(map_num);
815        for (int i = 0; i < map_num; ++i) {
816          if (!_reader_bits::readToken(line, tokens[i])) {
817            std::ostringstream msg;
818            msg << "Column not found (" << i + 1 << ")";
819            throw DataFormatError(msg.str().c_str());
820          }
821        }
822        if (line >> std::ws >> c)
823          throw DataFormatError("Extra character on the end of line");
824       
825        Arc a;
826        if (!_use_arcs) {
827
828          typename NodeIndex::iterator it;
829 
830          it = _node_index.find(source_token);
831          if (it == _node_index.end()) {
832            std::ostringstream msg;
833            msg << "Item not found: " << source_token;
834            throw DataFormatError(msg.str().c_str());
835          }
836          Node source = it->second;
837
838          it = _node_index.find(target_token);
839          if (it == _node_index.end()) {       
840            std::ostringstream msg;           
841            msg << "Item not found: " << target_token;
842            throw DataFormatError(msg.str().c_str());
843          }                                         
844          Node target = it->second;                           
845
846          a = _digraph.addArc(source, target);
847          _arc_index.insert(std::make_pair(tokens[label_index], a));
848        } else {
849          typename std::map<std::string, Arc>::iterator it =
850            _arc_index.find(tokens[label_index]);
851          if (it == _arc_index.end()) {
852            std::ostringstream msg;
853            msg << "Arc with label not found: " << tokens[label_index];
854            throw DataFormatError(msg.str().c_str());       
855          }
856          a = it->second;
857        }
858
859        for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
860          _arc_maps[i].second->set(a, tokens[map_index[i]]);
861        }
862
863      }
864      if (readSuccess()) {
865        line.putback(c);
866      }
867    }
868
869    void readAttributes() {
870
871      std::set<std::string> read_attr;
872
873      char c;
874      while (readLine() && line >> c && c != '@') {
875        line.putback(c);
876       
877        std::string attr, token;
878        if (!_reader_bits::readToken(line, attr))
879          throw DataFormatError("Attribute name not found");
880        if (!_reader_bits::readToken(line, token))
881          throw DataFormatError("Attribute value not found");
882        if (line >> c)
883          throw DataFormatError("Extra character on the end of line");   
884
885        {
886          std::set<std::string>::iterator it = read_attr.find(attr);
887          if (it != read_attr.end()) {
888            std::ostringstream msg;
889            msg << "Multiple occurence of attribute " << attr;
890            throw DataFormatError(msg.str().c_str());
891          }
892          read_attr.insert(attr);
893        }
894       
895        {
896          typename Attributes::iterator it = _attributes.lower_bound(attr);
897          while (it != _attributes.end() && it->first == attr) {
898            it->second->set(token);
899            ++it;
900          }
901        }
902
903      }
904      if (readSuccess()) {
905        line.putback(c);
906      }
907      for (typename Attributes::iterator it = _attributes.begin();
908           it != _attributes.end(); ++it) {
909        if (read_attr.find(it->first) == read_attr.end()) {
910          std::ostringstream msg;
911          msg << "Attribute not found in file: " << it->first;
912          throw DataFormatError(msg.str().c_str());
913        }       
914      }
915    }
916
917  public:
918
919    /// \name Execution of the reader   
920    /// @{
921
922    /// \brief Start the batch processing
923    ///
924    /// This function starts the batch processing
925    void run() {
926     
927      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
928     
929      bool nodes_done = false;
930      bool arcs_done = false;
931      bool attributes_done = false;
932
933      line_num = 0;     
934      readLine();
935
936      while (readSuccess()) {
937        skipSection();
938        try {
939          char c;
940          std::string section, caption;
941          line >> c;
942          _reader_bits::readToken(line, section);
943          _reader_bits::readToken(line, caption);
944
945          if (line >> c)
946            throw DataFormatError("Extra character on the end of line");
947
948          if (section == "nodes" && !nodes_done) {
949            if (_nodes_caption.empty() || _nodes_caption == caption) {
950              readNodes();
951              nodes_done = true;
952            }
953          } else if ((section == "arcs" || section == "edges") &&
954                     !arcs_done) {
955            if (_arcs_caption.empty() || _arcs_caption == caption) {
956              readArcs();
957              arcs_done = true;
958            }
959          } else if (section == "attributes" && !attributes_done) {
960            if (_attributes_caption.empty() || _attributes_caption == caption) {
961              readAttributes();
962              attributes_done = true;
963            }
964          } else {
965            readLine();
966            skipSection();
967          }
968        } catch (DataFormatError& error) {
969          error.line(line_num);
970          throw;
971        }       
972      }
973
974      if (!nodes_done) {
975        throw DataFormatError("Section @nodes not found");
976      }
977
978      if (!arcs_done) {
979        throw DataFormatError("Section @arcs not found");
980      }
981
982      if (!attributes_done && !_attributes.empty()) {
983        throw DataFormatError("Section @attributes not found");
984      }
985
986    }
987
988    /// @}
989   
990  };
991
992  /// \relates DigraphReader
993  template <typename Digraph>
994  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
995    return DigraphReader<Digraph>(is, digraph);
996  }
997
998  /// \relates DigraphReader
999  template <typename Digraph>
1000  DigraphReader<Digraph> digraphReader(const std::string& fn,
1001                                       Digraph& digraph) {
1002    return DigraphReader<Digraph>(fn, digraph);
1003  }
1004
1005  /// \relates DigraphReader
1006  template <typename Digraph>
1007  DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
1008    return DigraphReader<Digraph>(fn, digraph);
1009  }
1010}
1011
1012#endif
Note: See TracBrowser for help on using the repository browser.