COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_reader.h @ 1137:83a48cfd8553

Last change on this file since 1137:83a48cfd8553 was 1137:83a48cfd8553, checked in by Balazs Dezso, 15 years ago

IO moved to lemon.

File size: 18.1 KB
Line 
1/* -*- C++ -*-
2 * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, EGRES).
6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
17///\ingroup gio
18///\file
19///\brief Graph reader.
20
21#include <iostream>
22#include <sstream>
23
24#include <map>
25#include <vector>
26
27#include <memory>
28
29#include <lemon/error.h>
30
31/// \todo fix exceptions
32
33
34namespace lemon {
35
36  // Exceptions
37
38  class IOException {
39  public:
40    virtual ~IOException() {}
41    virtual string what() const = 0;
42  };
43
44  class DataFormatException : public IOException {
45    std::string message;
46  public:
47    DataFormatException(const std::string& _message)
48      : message(_message) {}
49    std::string what() const {
50      return "DataFormatException: " + message;
51    }
52  };
53
54  template <typename _Exception>
55  class StreamException : public _Exception {
56  public:
57    typedef _Exception Exception;
58    StreamException(int _line, Exception _exception)
59      : Exception(_exception), line_num(_line) {}
60    virtual int line() const {
61      return line_num;
62    }
63
64    virtual ~StreamException() {}
65
66    virtual std::string what() const {
67      ostringstream os;
68      os << Exception::what() << " in line " << line();
69      return os.str();
70    }
71  private:
72    int line_num;
73  }; 
74
75
76  /// \brief Standard ReaderTraits for the GraphReader class.
77  ///
78  /// Standard ReaderTraits for the GraphReader class.
79  /// It defines standard reading method for all type of value.
80  struct DefaultReaderTraits {
81
82    /// \brief Template class for reading an value.
83    ///
84    /// Template class for reading an value.
85    template <typename _Value>
86    struct Reader {
87      /// The value type.
88      typedef _Value Value;
89      /// \brief Reads a value from the given stream.
90      ///
91      /// Reads a value from the given stream.
92      void read(std::istream& is, Value& value) {
93        if (!(is >> value))
94          throw DataFormatException("Default Reader format exception");
95      }
96    };
97
98    /// The reader class for the not needed maps.
99    typedef Reader<std::string> DefaultReader;
100
101  };
102
103  /// \brief Reader class for quoted strings.
104  ///
105  /// Reader class for quoted strings. It can process the escape
106  /// sequences in the string.
107  class QuotedStringReader {
108  public:
109    typedef std::string Value;
110   
111    /// \brief Constructor for the reader.
112    ///
113    /// Constructor for the reader. If the given parameter is true
114    /// the reader processes the escape sequences.
115    QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
116   
117    /// \brief Reads a quoted string from the given stream.
118    ///
119    /// Reads a quoted string from the given stream.
120    void read(std::istream& is, std::string& value) {
121      char c;
122      value.clear();
123      is >> ws;
124      if (!is.get(c) || c != '\"')
125        throw DataFormatException("Quoted string format");
126      while (is.get(c) && c != '\"') {
127        if (escaped && c == '\\') {
128          value += readEscape(is);
129        } else {
130          value += c;
131        }
132      }
133      if (!is) throw DataFormatException("Quoted string format");
134    }
135
136  private:
137   
138    static char readEscape(std::istream& is) {
139      char c;
140      switch (is.get(c), c) {
141      case '\\':
142        return '\\';
143      case '\"':
144        return '\"';
145      case '\'':
146        return '\'';
147      case '\?':
148        return '\?';
149      case 'a':
150        return '\a';
151      case 'b':
152        return '\b';
153      case 'f':
154        return '\f';
155      case 'n':
156        return '\n';
157      case 'r':
158        return '\r';
159      case 't':
160        return '\t';
161      case 'v':
162        return '\v';
163      case 'x':
164        {
165          int code;
166          if (!is.get(c) || !isHex(c))
167            throw DataFormatException("Escape format exception");
168          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
169          else code = code * 16 + valueHex(c);
170          return code;
171        }
172      default:
173        {
174          int code;
175          if (!isOct(c))
176            throw DataFormatException("Escape format exception");
177          else if (code = valueOct(c), !is.get(c) || !isOct(c))
178            is.putback(c);
179          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
180            is.putback(c);
181          else code = code * 8 + valueOct(c);
182          return code;
183        }             
184      }
185    }
186
187    static bool isOct(char c) {
188      return '0' <= c && c <='7';
189    }
190   
191    static int valueOct(char c) {
192      return c - '0';
193    }
194
195   static bool isHex(char c) {
196      return ('0' <= c && c <= '9') ||
197        ('a' <= c && c <= 'z') ||
198        ('A' <= c && c <= 'Z');
199    }
200   
201    static int valueHex(char c) {
202      if ('0' <= c && c <= '9') return c - '0';
203      if ('a' <= c && c <= 'z') return c - 'a' + 10;
204      return c - 'A' + 10;
205    }
206
207    bool escaped;
208  };
209
210  /// \brief The graph reader class.
211  ///
212  /// The reader class for the graph input.
213  /// \see graph-io-page
214  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
215  class GraphReader {
216  public:
217   
218    typedef _Graph Graph;
219    typedef typename Graph::Node Node;
220    typedef typename Graph::Edge Edge;
221
222    typedef _ReaderTraits ReaderTraits;
223    typedef typename ReaderTraits::DefaultReader DefaultReader;
224
225    /// \brief Construct a new GraphReader.
226    ///
227    /// Construct a new GraphReader. It reads from the given map,
228    /// it constructs the given map and it use the given reader as the
229    /// default skipper.
230    GraphReader(std::istream& _is, Graph& _graph,
231                const DefaultReader& _reader = DefaultReader())
232      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
233
234    /// \brief Destruct the graph reader.
235    ///
236    /// Destruct the graph reader.
237    ~GraphReader() {
238
239      for (typename NodeMapReaders::iterator it = node_map_readers.begin();
240           it != node_map_readers.end(); ++it) {
241        delete it->second;
242      }
243
244      for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
245           it != edge_map_readers.end(); ++it) {
246        delete it->second;
247      }
248
249    }
250
251    /// \brief Add a new node map reader command for the reader.
252    ///
253    /// Add a new node map reader command for the reader.
254    template <typename Map>
255    GraphReader& addNodeMap(std::string name, Map& map) {
256      return addNodeMap<typename ReaderTraits::template
257        Reader<typename Map::Value>, Map>(name, map);
258    }
259
260    /// \brief Add a new node map reader command for the reader.
261    ///
262    /// Add a new node map reader command for the reader.
263    template <typename Reader, typename Map>
264    GraphReader& addNodeMap(std::string name, Map& map,
265                             const Reader& reader = Reader()) {
266      if (node_map_readers.find(name) != node_map_readers.end()) {
267        throw Exception() << "Multiple read rule for node map: " << name;
268      }
269      node_map_readers.insert(
270        make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
271      return *this;
272    }
273
274    /// \brief Add a new node map skipper command for the reader.
275    ///
276    /// Add a new node map skipper command for the reader.
277    template <typename Reader>
278    GraphReader& skipNodeMap(std::string name,
279                             const Reader& reader = Reader()) {
280      if (node_map_readers.find(name) != node_map_readers.end()) {
281        throw Exception() << "Multiple read rule for node map: " << name;
282      }
283      node_map_readers.insert(
284        make_pair(name, new SkipReader<Node, Reader>(reader)));
285      return *this;
286    }
287
288    /// \brief Add a new edge map reader command for the reader.
289    ///
290    /// Add a new edge map reader command for the reader.
291    template <typename Map>
292    GraphReader& addEdgeMap(std::string name, Map& map) {
293      return addEdgeMap<typename ReaderTraits::template
294        Reader<typename Map::Value>, Map>(name, map);
295    }
296
297
298    /// \brief Add a new edge map reader command for the reader.
299    ///
300    /// Add a new edge map reader command for the reader.
301    template <typename Reader, typename Map>
302    GraphReader& addEdgeMap(std::string name, Map& map,
303                             const Reader& reader = Reader()) {
304      if (edge_map_readers.find(name) != edge_map_readers.end()) {
305        throw Exception() << "Multiple read rule for edge map: " << name;
306      }
307      edge_map_readers.insert(
308        make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
309      return *this;
310    }
311
312    /// \brief Add a new edge map skipper command for the reader.
313    ///
314    /// Add a new edge map skipper command for the reader.
315    template <typename Reader>
316    GraphReader& skipEdgeMap(std::string name,
317                             const Reader& reader = Reader()) {
318      if (edge_map_readers.find(name) != edge_map_readers.end()) {
319        throw Exception() << "Multiple read rule for edge map: " << name;
320      }
321      edge_map_readers.insert(
322        make_pair(name, new SkipReader<Edge, Reader>(reader)));
323      return *this;
324    }
325
326    /// \brief Add a new labeled node reader for the reader.
327    ///
328    /// Add a new labeled node reader for the reader.
329    GraphReader& addNode(std::string name, Node& node) {
330      if (node_readers.find(name) != node_readers.end()) {
331        throw Exception() << "Multiple read rule for node";
332      }
333      node_readers.insert(make_pair(name, &node));
334      return *this;
335    }
336
337    /// \brief Add a new labeled edge reader for the reader.
338    ///
339    /// Add a new labeled edge reader for the reader.
340    GraphReader& addEdge(std::string name, Edge& edge) {
341      if (edge_readers.find(name) != edge_readers.end()) {
342        throw Exception() << "Multiple read rule for edge";
343      }
344      edge_readers.insert(make_pair(name, &edge));
345      return *this;
346    }
347
348    /// \brief Executes the reader commands.
349    ///
350    /// Executes the reader commands.
351    void run() {
352      int line_num = 0;
353      std::auto_ptr<InverterBase<Node> > nodeInverter;
354      std::auto_ptr<InverterBase<Edge> > edgeInverter;
355      try {
356        std::string line = readNotEmptyLine(is, line_num);
357        if (line.find("@nodeset") == 0) {
358          line = readNodeSet(line_num, nodeInverter);
359        }
360        if (line.find("@edgeset") == 0) {
361          line = readEdgeSet(line_num, edgeInverter, nodeInverter);
362        }
363        if (line.find("@nodes") == 0) {
364          line = readNodes(line_num, nodeInverter);
365        }
366        if (line.find("@edges") == 0) {
367          line = readEdges(line_num, edgeInverter);
368        }
369        if (line.find("@end") != 0) {
370          throw DataFormatException("Invalid control sequence: " + line);
371        }
372      } catch (DataFormatException e) {
373        throw StreamException<DataFormatException>(line_num, e);
374      }
375    }
376
377  private:
378
379    template <typename Item> class InverterBase;
380
381    std::string readNodeSet(int& line_num,
382                            auto_ptr<InverterBase<Node> > & nodeInverter) {
383      std::vector<ReaderBase<Node>* > index;
384      {
385        std::string line = readNotEmptyLine(is, line_num);   
386        std::string id;
387        std::istringstream ls(line);   
388        while (ls >> id) {
389          if (id[0] == '#') break;
390          typename NodeMapReaders::iterator it = node_map_readers.find(id);
391          if (it != node_map_readers.end()) {
392            index.push_back(it->second);
393            node_map_readers.erase(it);
394          } else {
395            index.push_back(&nodeSkipper);
396          }
397        }
398      }
399
400      if (index.size() == 0) {
401        throw DataFormatException("No node map found");
402      }
403
404      nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
405      std::string line;
406      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
407        Node node = graph.addNode();
408        std::istringstream ls(line);
409        nodeInverter->read(ls, node);
410        for (int i = 1; i < (int)index.size(); ++i) {
411          index[i]->read(ls, node);
412        }
413      }
414      return line;
415    }
416
417    std::string readEdgeSet(int& line_num,
418                            auto_ptr<InverterBase<Edge> > & edgeInverter,
419                            auto_ptr<InverterBase<Node> > & nodeInverter) {
420      std::vector<ReaderBase<Edge>*> index;
421      {
422        std::string line = readNotEmptyLine(is, line_num);   
423        std::string id;
424        std::istringstream ls(line);   
425        while (ls >> id) {
426          if (id[0] == '#') break;
427          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
428          if (it != edge_map_readers.end()) {
429            index.push_back(it->second);
430            edge_map_readers.erase(it);
431          } else {
432            index.push_back(&edgeSkipper);
433          }
434        }
435      }
436
437      if (index.size() == 0) {
438        throw DataFormatException("No edge map found");
439      }
440
441      edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
442      std::string line;
443      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
444        std::istringstream ls(line);
445        Node source = nodeInverter->read(ls);
446        Node target = nodeInverter->read(ls);
447        Edge edge = graph.addEdge(source, target);
448        edgeInverter->read(ls, edge);
449        for (int i = 1; i < (int)index.size(); ++i) {
450          index[i]->read(ls, edge);
451        }
452      }     
453      return line;
454    }
455
456    std::string readNodes(int& line_num,
457                          auto_ptr<InverterBase<Node> >& nodeInverter) {
458      std::string line;
459      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
460        std::istringstream ls(line);
461        std::string name;
462        ls >> name;
463        typename NodeReaders::iterator it = node_readers.find(name);
464        if (it != node_readers.end()) {
465          *(it -> second) = nodeInverter->read(ls);
466        }
467      }       
468      return line;
469    }
470
471    std::string readEdges(int& line_num,
472                          auto_ptr<InverterBase<Edge> >& edgeInverter) {
473      std::string line;
474      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
475        std::istringstream ls(line);
476        std::string name;
477        ls >> name;
478        typename EdgeReaders::iterator it = edge_readers.find(name);
479        if (it != edge_readers.end()) {
480          *(it -> second) = edgeInverter->read(ls);
481        }
482      }       
483      return line;   
484    }
485
486    std::string readNotEmptyLine(std::istream& is, int& line_num) {
487      std::string line;
488      while (++line_num, getline(is, line)) {   
489        int vi = line.find_first_not_of(" \t");
490        if (vi != (int)string::npos && line[vi] != '#') {
491          return line.substr(vi);
492        }
493      }
494      throw DataFormatException("End of stream");
495    }
496   
497    // Inverters store and give back the Item from the id,
498    // and may put the ids into a map.
499   
500    template <typename _Item>
501    class InverterBase {
502    public:
503      typedef _Item Item;
504      virtual void read(std::istream&, const Item&) = 0;
505      virtual Item read(std::istream&) = 0;
506    };
507
508    template <typename _Item, typename _Map, typename _Reader>
509    class MapReaderInverter : public InverterBase<_Item> {
510    public:
511      typedef _Item Item;
512      typedef _Reader Reader;
513      typedef typename Reader::Value Value;
514      typedef _Map Map;
515      typedef std::map<Value, Item> Inverse;
516
517      Map& map;
518      Reader reader;
519      Inverse inverse;
520
521      MapReaderInverter(Map& _map, const Reader& _reader)
522        : map(_map), reader(_reader) {}
523
524      virtual ~MapReaderInverter() {}
525
526      virtual void read(std::istream& is, const Item& item) {
527        Value value;
528        reader.read(is, value);
529        map.set(item, value);
530        typename Inverse::iterator it = inverse.find(value);
531        if (it == inverse.end()) {
532          inverse.insert(make_pair(value, item));
533        } else {
534          throw DataFormatException("Multiple ID occurence");
535        }
536      }
537
538      virtual Item read(std::istream& is) {
539        Value value;
540        reader.read(is, value);
541        typename Inverse::const_iterator it = inverse.find(value);
542        if (it != inverse.end()) {
543          return it->second;
544        } else {
545          throw DataFormatException("Invalid ID");
546        }
547      }     
548    };
549
550    template <typename _Item, typename _Reader>
551    class SkipReaderInverter : public InverterBase<_Item> {
552    public:
553      typedef _Item Item;
554      typedef _Reader Reader;
555      typedef typename Reader::Value Value;
556      typedef std::map<Value, Item> Inverse;
557
558      Reader reader;
559
560      SkipReaderInverter(const Reader& _reader)
561        : reader(_reader) {}
562
563      virtual ~SkipReaderInverter() {}
564
565      virtual void read(std::istream& is, const Item& item) {
566        Value value;
567        reader.read(is, value);
568        typename Inverse::iterator it = inverse.find(value);
569        if (it == inverse.end()) {
570          inverse.insert(make_pair(value, item));
571        } else {
572          throw DataFormatException("Multiple ID occurence");
573        }
574      }
575
576      virtual Item read(std::istream& is) {
577        Value value;
578        reader.read(is, value);
579        typename Inverse::const_iterator it = inverse.find(value);
580        if (it != inverse.end()) {
581          return it->second;
582        } else {
583          throw DataFormatException("Invalid ID");
584        }
585      }     
586    private:
587      Inverse inverse;
588    };
589
590    // Readers
591
592    template <typename _Item>   
593    class ReaderBase {
594    public:
595      typedef _Item Item;
596
597      //      virtual ~ReaderBase() {}
598
599      virtual void read(std::istream& is, const Item& item) = 0;
600      virtual InverterBase<_Item>* getInverter() = 0;
601    };
602
603    template <typename _Item, typename _Map, typename _Reader>
604    class MapReader : public ReaderBase<_Item> {
605    public:
606      typedef _Map Map;
607      typedef _Reader Reader;
608      typedef typename Reader::Value Value;
609      typedef _Item Item;
610     
611      Map& map;
612      Reader reader;
613
614      MapReader(Map& _map, const Reader& _reader)
615        : map(_map), reader(_reader) {}
616
617      virtual ~MapReader() {}
618
619      virtual void read(std::istream& is, const Item& item) {
620        Value value;
621        reader.read(is, value);
622        map.set(item, value);
623      }
624
625      virtual InverterBase<_Item>* getInverter() {
626        return new MapReaderInverter<Item, Map, Reader>(map, reader);
627      }
628    };
629
630
631    template <typename _Item, typename _Reader>
632    class SkipReader : public ReaderBase<_Item> {
633    public:
634      typedef _Reader Reader;
635      typedef typename Reader::Value Value;
636      typedef _Item Item;
637
638      Reader reader;
639      SkipReader(const Reader& _reader) : reader(_reader) {}
640
641      virtual ~SkipReader() {}
642
643      virtual void read(std::istream& is, const Item& item) {
644        Value value;
645        reader.read(is, value);
646      }     
647
648      virtual InverterBase<Item>* getInverter() {
649        return new SkipReaderInverter<Item, Reader>(reader);
650      }
651    };
652
653
654    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
655    NodeMapReaders node_map_readers;
656
657    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
658    EdgeMapReaders edge_map_readers;
659
660    typedef std::map<std::string, Node*> NodeReaders;
661    NodeReaders node_readers;
662
663    typedef std::map<std::string, Edge*> EdgeReaders;
664    EdgeReaders edge_readers;
665
666    std::istream& is;
667    Graph& graph;
668
669    SkipReader<Node, DefaultReader> nodeSkipper;
670    SkipReader<Edge, DefaultReader> edgeSkipper;
671
672  };
673
674}
Note: See TracBrowser for help on using the repository browser.