COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_reader.h @ 1208:f486d30e4e7b

Last change on this file since 1208:f486d30e4e7b was 1208:f486d30e4e7b, checked in by Balazs Dezso, 15 years ago

Easy input-output function for common graphs.
Modified Exception handling in graph_reader.

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