COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_reader.h @ 1138:f68cb8752d81

Last change on this file since 1138:f68cb8752d81 was 1138:f68cb8752d81, checked in by Alpar Juttner, 15 years ago

Fix wrong reference in the documentation.

File size: 18.2 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 \ref GraphWriter
214  /// \see \ref graph-io-page
215  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
216  class GraphReader {
217  public:
218   
219    typedef _Graph Graph;
220    typedef typename Graph::Node Node;
221    typedef typename Graph::Edge Edge;
222
223    typedef _ReaderTraits ReaderTraits;
224    typedef typename ReaderTraits::DefaultReader DefaultReader;
225
226    /// \brief Construct a new GraphReader.
227    ///
228    /// Construct a new GraphReader. It reads from the given map,
229    /// it constructs the given map and it use the given reader as the
230    /// default skipper.
231    GraphReader(std::istream& _is, Graph& _graph,
232                const DefaultReader& _reader = DefaultReader())
233      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
234
235    /// \brief Destruct the graph reader.
236    ///
237    /// Destruct the graph reader.
238    ~GraphReader() {
239
240      for (typename NodeMapReaders::iterator it = node_map_readers.begin();
241           it != node_map_readers.end(); ++it) {
242        delete it->second;
243      }
244
245      for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
246           it != edge_map_readers.end(); ++it) {
247        delete it->second;
248      }
249
250    }
251
252    /// \brief Add a new node map reader command for the reader.
253    ///
254    /// Add a new node map reader command for the reader.
255    template <typename Map>
256    GraphReader& addNodeMap(std::string name, Map& map) {
257      return addNodeMap<typename ReaderTraits::template
258        Reader<typename Map::Value>, Map>(name, map);
259    }
260
261    /// \brief Add a new node map reader command for the reader.
262    ///
263    /// Add a new node map reader command for the reader.
264    template <typename Reader, typename Map>
265    GraphReader& addNodeMap(std::string name, Map& map,
266                             const Reader& reader = Reader()) {
267      if (node_map_readers.find(name) != node_map_readers.end()) {
268        throw Exception() << "Multiple read rule for node map: " << name;
269      }
270      node_map_readers.insert(
271        make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
272      return *this;
273    }
274
275    /// \brief Add a new node map skipper command for the reader.
276    ///
277    /// Add a new node map skipper command for the reader.
278    template <typename Reader>
279    GraphReader& skipNodeMap(std::string name,
280                             const Reader& reader = Reader()) {
281      if (node_map_readers.find(name) != node_map_readers.end()) {
282        throw Exception() << "Multiple read rule for node map: " << name;
283      }
284      node_map_readers.insert(
285        make_pair(name, new SkipReader<Node, Reader>(reader)));
286      return *this;
287    }
288
289    /// \brief Add a new edge map reader command for the reader.
290    ///
291    /// Add a new edge map reader command for the reader.
292    template <typename Map>
293    GraphReader& addEdgeMap(std::string name, Map& map) {
294      return addEdgeMap<typename ReaderTraits::template
295        Reader<typename Map::Value>, Map>(name, map);
296    }
297
298
299    /// \brief Add a new edge map reader command for the reader.
300    ///
301    /// Add a new edge map reader command for the reader.
302    template <typename Reader, typename Map>
303    GraphReader& addEdgeMap(std::string name, Map& map,
304                             const Reader& reader = Reader()) {
305      if (edge_map_readers.find(name) != edge_map_readers.end()) {
306        throw Exception() << "Multiple read rule for edge map: " << name;
307      }
308      edge_map_readers.insert(
309        make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
310      return *this;
311    }
312
313    /// \brief Add a new edge map skipper command for the reader.
314    ///
315    /// Add a new edge map skipper command for the reader.
316    template <typename Reader>
317    GraphReader& skipEdgeMap(std::string name,
318                             const Reader& reader = Reader()) {
319      if (edge_map_readers.find(name) != edge_map_readers.end()) {
320        throw Exception() << "Multiple read rule for edge map: " << name;
321      }
322      edge_map_readers.insert(
323        make_pair(name, new SkipReader<Edge, Reader>(reader)));
324      return *this;
325    }
326
327    /// \brief Add a new labeled node reader for the reader.
328    ///
329    /// Add a new labeled node reader for the reader.
330    GraphReader& addNode(std::string name, Node& node) {
331      if (node_readers.find(name) != node_readers.end()) {
332        throw Exception() << "Multiple read rule for node";
333      }
334      node_readers.insert(make_pair(name, &node));
335      return *this;
336    }
337
338    /// \brief Add a new labeled edge reader for the reader.
339    ///
340    /// Add a new labeled edge reader for the reader.
341    GraphReader& addEdge(std::string name, Edge& edge) {
342      if (edge_readers.find(name) != edge_readers.end()) {
343        throw Exception() << "Multiple read rule for edge";
344      }
345      edge_readers.insert(make_pair(name, &edge));
346      return *this;
347    }
348
349    /// \brief Executes the reader commands.
350    ///
351    /// Executes the reader commands.
352    void run() {
353      int line_num = 0;
354      std::auto_ptr<InverterBase<Node> > nodeInverter;
355      std::auto_ptr<InverterBase<Edge> > edgeInverter;
356      try {
357        std::string line = readNotEmptyLine(is, line_num);
358        if (line.find("@nodeset") == 0) {
359          line = readNodeSet(line_num, nodeInverter);
360        }
361        if (line.find("@edgeset") == 0) {
362          line = readEdgeSet(line_num, edgeInverter, nodeInverter);
363        }
364        if (line.find("@nodes") == 0) {
365          line = readNodes(line_num, nodeInverter);
366        }
367        if (line.find("@edges") == 0) {
368          line = readEdges(line_num, edgeInverter);
369        }
370        if (line.find("@end") != 0) {
371          throw DataFormatException("Invalid control sequence: " + line);
372        }
373      } catch (DataFormatException e) {
374        throw StreamException<DataFormatException>(line_num, e);
375      }
376    }
377
378  private:
379
380    template <typename Item> class InverterBase;
381
382    std::string readNodeSet(int& line_num,
383                            auto_ptr<InverterBase<Node> > & nodeInverter) {
384      std::vector<ReaderBase<Node>* > index;
385      {
386        std::string line = readNotEmptyLine(is, line_num);   
387        std::string id;
388        std::istringstream ls(line);   
389        while (ls >> id) {
390          if (id[0] == '#') break;
391          typename NodeMapReaders::iterator it = node_map_readers.find(id);
392          if (it != node_map_readers.end()) {
393            index.push_back(it->second);
394            node_map_readers.erase(it);
395          } else {
396            index.push_back(&nodeSkipper);
397          }
398        }
399      }
400
401      if (index.size() == 0) {
402        throw DataFormatException("No node map found");
403      }
404
405      nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
406      std::string line;
407      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
408        Node node = graph.addNode();
409        std::istringstream ls(line);
410        nodeInverter->read(ls, node);
411        for (int i = 1; i < (int)index.size(); ++i) {
412          index[i]->read(ls, node);
413        }
414      }
415      return line;
416    }
417
418    std::string readEdgeSet(int& line_num,
419                            auto_ptr<InverterBase<Edge> > & edgeInverter,
420                            auto_ptr<InverterBase<Node> > & nodeInverter) {
421      std::vector<ReaderBase<Edge>*> index;
422      {
423        std::string line = readNotEmptyLine(is, line_num);   
424        std::string id;
425        std::istringstream ls(line);   
426        while (ls >> id) {
427          if (id[0] == '#') break;
428          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
429          if (it != edge_map_readers.end()) {
430            index.push_back(it->second);
431            edge_map_readers.erase(it);
432          } else {
433            index.push_back(&edgeSkipper);
434          }
435        }
436      }
437
438      if (index.size() == 0) {
439        throw DataFormatException("No edge map found");
440      }
441
442      edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
443      std::string line;
444      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
445        std::istringstream ls(line);
446        Node source = nodeInverter->read(ls);
447        Node target = nodeInverter->read(ls);
448        Edge edge = graph.addEdge(source, target);
449        edgeInverter->read(ls, edge);
450        for (int i = 1; i < (int)index.size(); ++i) {
451          index[i]->read(ls, edge);
452        }
453      }     
454      return line;
455    }
456
457    std::string readNodes(int& line_num,
458                          auto_ptr<InverterBase<Node> >& nodeInverter) {
459      std::string line;
460      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
461        std::istringstream ls(line);
462        std::string name;
463        ls >> name;
464        typename NodeReaders::iterator it = node_readers.find(name);
465        if (it != node_readers.end()) {
466          *(it -> second) = nodeInverter->read(ls);
467        }
468      }       
469      return line;
470    }
471
472    std::string readEdges(int& line_num,
473                          auto_ptr<InverterBase<Edge> >& edgeInverter) {
474      std::string line;
475      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
476        std::istringstream ls(line);
477        std::string name;
478        ls >> name;
479        typename EdgeReaders::iterator it = edge_readers.find(name);
480        if (it != edge_readers.end()) {
481          *(it -> second) = edgeInverter->read(ls);
482        }
483      }       
484      return line;   
485    }
486
487    std::string readNotEmptyLine(std::istream& is, int& line_num) {
488      std::string line;
489      while (++line_num, getline(is, line)) {   
490        int vi = line.find_first_not_of(" \t");
491        if (vi != (int)string::npos && line[vi] != '#') {
492          return line.substr(vi);
493        }
494      }
495      throw DataFormatException("End of stream");
496    }
497   
498    // Inverters store and give back the Item from the id,
499    // and may put the ids into a map.
500   
501    template <typename _Item>
502    class InverterBase {
503    public:
504      typedef _Item Item;
505      virtual void read(std::istream&, const Item&) = 0;
506      virtual Item read(std::istream&) = 0;
507    };
508
509    template <typename _Item, typename _Map, typename _Reader>
510    class MapReaderInverter : public InverterBase<_Item> {
511    public:
512      typedef _Item Item;
513      typedef _Reader Reader;
514      typedef typename Reader::Value Value;
515      typedef _Map Map;
516      typedef std::map<Value, Item> Inverse;
517
518      Map& map;
519      Reader reader;
520      Inverse inverse;
521
522      MapReaderInverter(Map& _map, const Reader& _reader)
523        : map(_map), reader(_reader) {}
524
525      virtual ~MapReaderInverter() {}
526
527      virtual void read(std::istream& is, const Item& item) {
528        Value value;
529        reader.read(is, value);
530        map.set(item, value);
531        typename Inverse::iterator it = inverse.find(value);
532        if (it == inverse.end()) {
533          inverse.insert(make_pair(value, item));
534        } else {
535          throw DataFormatException("Multiple ID occurence");
536        }
537      }
538
539      virtual Item read(std::istream& is) {
540        Value value;
541        reader.read(is, value);
542        typename Inverse::const_iterator it = inverse.find(value);
543        if (it != inverse.end()) {
544          return it->second;
545        } else {
546          throw DataFormatException("Invalid ID");
547        }
548      }     
549    };
550
551    template <typename _Item, typename _Reader>
552    class SkipReaderInverter : public InverterBase<_Item> {
553    public:
554      typedef _Item Item;
555      typedef _Reader Reader;
556      typedef typename Reader::Value Value;
557      typedef std::map<Value, Item> Inverse;
558
559      Reader reader;
560
561      SkipReaderInverter(const Reader& _reader)
562        : reader(_reader) {}
563
564      virtual ~SkipReaderInverter() {}
565
566      virtual void read(std::istream& is, const Item& item) {
567        Value value;
568        reader.read(is, value);
569        typename Inverse::iterator it = inverse.find(value);
570        if (it == inverse.end()) {
571          inverse.insert(make_pair(value, item));
572        } else {
573          throw DataFormatException("Multiple ID occurence");
574        }
575      }
576
577      virtual Item read(std::istream& is) {
578        Value value;
579        reader.read(is, value);
580        typename Inverse::const_iterator it = inverse.find(value);
581        if (it != inverse.end()) {
582          return it->second;
583        } else {
584          throw DataFormatException("Invalid ID");
585        }
586      }     
587    private:
588      Inverse inverse;
589    };
590
591    // Readers
592
593    template <typename _Item>   
594    class ReaderBase {
595    public:
596      typedef _Item Item;
597
598      //      virtual ~ReaderBase() {}
599
600      virtual void read(std::istream& is, const Item& item) = 0;
601      virtual InverterBase<_Item>* getInverter() = 0;
602    };
603
604    template <typename _Item, typename _Map, typename _Reader>
605    class MapReader : public ReaderBase<_Item> {
606    public:
607      typedef _Map Map;
608      typedef _Reader Reader;
609      typedef typename Reader::Value Value;
610      typedef _Item Item;
611     
612      Map& map;
613      Reader reader;
614
615      MapReader(Map& _map, const Reader& _reader)
616        : map(_map), reader(_reader) {}
617
618      virtual ~MapReader() {}
619
620      virtual void read(std::istream& is, const Item& item) {
621        Value value;
622        reader.read(is, value);
623        map.set(item, value);
624      }
625
626      virtual InverterBase<_Item>* getInverter() {
627        return new MapReaderInverter<Item, Map, Reader>(map, reader);
628      }
629    };
630
631
632    template <typename _Item, typename _Reader>
633    class SkipReader : public ReaderBase<_Item> {
634    public:
635      typedef _Reader Reader;
636      typedef typename Reader::Value Value;
637      typedef _Item Item;
638
639      Reader reader;
640      SkipReader(const Reader& _reader) : reader(_reader) {}
641
642      virtual ~SkipReader() {}
643
644      virtual void read(std::istream& is, const Item& item) {
645        Value value;
646        reader.read(is, value);
647      }     
648
649      virtual InverterBase<Item>* getInverter() {
650        return new SkipReaderInverter<Item, Reader>(reader);
651      }
652    };
653
654
655    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
656    NodeMapReaders node_map_readers;
657
658    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
659    EdgeMapReaders edge_map_readers;
660
661    typedef std::map<std::string, Node*> NodeReaders;
662    NodeReaders node_readers;
663
664    typedef std::map<std::string, Edge*> EdgeReaders;
665    EdgeReaders edge_readers;
666
667    std::istream& is;
668    Graph& graph;
669
670    SkipReader<Node, DefaultReader> nodeSkipper;
671    SkipReader<Edge, DefaultReader> edgeSkipper;
672
673  };
674
675}
Note: See TracBrowser for help on using the repository browser.