COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_reader.h @ 1287:984723507b86

Last change on this file since 1287:984723507b86 was 1287:984723507b86, checked in by Alpar Juttner, 15 years ago

New groups called io_group and dimacs_group added

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