COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_reader.h @ 1311:b810a07248a0

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

Removing sticky using namespace std.
Making up the using of namespaces.

File size: 19.1 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 >> std::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                            std::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 =
383        std::auto_ptr<InverterBase<Node> >(index[0]->getInverter());
384      std::string line;
385      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
386        Node node = graph.addNode();
387        std::istringstream ls(line);
388        nodeInverter->read(ls, node);
389        for (int i = 1; i < (int)index.size(); ++i) {
390          index[i]->read(ls, node);
391        }
392      }
393      return line;
394    }
395
396    std::string readEdgeSet(int& line_num,
397                            std::auto_ptr<InverterBase<Edge> >& edgeInverter,
398                            std::auto_ptr<InverterBase<Node> >& nodeInverter) {
399      std::vector<ReaderBase<Edge>*> index;
400      {
401        std::string line = readNotEmptyLine(is, line_num);   
402        std::string id;
403        std::istringstream ls(line);   
404        while (ls >> id) {
405          if (id[0] == '#') break;
406          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
407          if (it != edge_map_readers.end()) {
408            index.push_back(it->second);
409            edge_map_readers.erase(it);
410          } else {
411            index.push_back(&edgeSkipper);
412          }
413        }
414      }
415
416      if (index.size() == 0) {
417        throw DataFormatError("Cannot find edge id map");
418      }
419
420      edgeInverter =
421        std::auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
422      std::string line;
423      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
424        std::istringstream ls(line);
425        Node source = nodeInverter->read(ls);
426        Node target = nodeInverter->read(ls);
427        Edge edge = graph.addEdge(source, target);
428        edgeInverter->read(ls, edge);
429        for (int i = 1; i < (int)index.size(); ++i) {
430          index[i]->read(ls, edge);
431        }
432      }     
433      return line;
434    }
435
436    std::string readNodes(int& line_num,
437                          std::auto_ptr<InverterBase<Node> >& nodeInverter) {
438      std::string line;
439      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
440        std::istringstream ls(line);
441        std::string name;
442        ls >> name;
443        typename NodeReaders::iterator it = node_readers.find(name);
444        if (it != node_readers.end()) {
445          *(it -> second) = nodeInverter->read(ls);
446        }
447      }       
448      return line;
449    }
450
451    std::string readEdges(int& line_num,
452                          std::auto_ptr<InverterBase<Edge> >& edgeInverter) {
453      std::string line;
454      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
455        std::istringstream ls(line);
456        std::string name;
457        ls >> name;
458        typename EdgeReaders::iterator it = edge_readers.find(name);
459        if (it != edge_readers.end()) {
460          *(it -> second) = edgeInverter->read(ls);
461        }
462      }       
463      return line;   
464    }
465
466    std::string readNotEmptyLine(std::istream& is, int& line_num) {
467      std::string line;
468      while (++line_num, getline(is, line)) {   
469        int vi = line.find_first_not_of(" \t");
470        if (vi != (int)std::string::npos && line[vi] != '#') {
471          return line.substr(vi);
472        }
473      }
474      throw DataFormatError("End of stream error");
475    }
476   
477    // Inverters store and give back the Item from the id,
478    // and may put the ids into a map.
479   
480    template <typename _Item>
481    class InverterBase {
482    public:
483      typedef _Item Item;
484      virtual void read(std::istream&, const Item&) = 0;
485      virtual Item read(std::istream&) = 0;
486    };
487
488    template <typename _Item, typename _Map, typename _Reader>
489    class MapReaderInverter : public InverterBase<_Item> {
490    public:
491      typedef _Item Item;
492      typedef _Reader Reader;
493      typedef typename Reader::Value Value;
494      typedef _Map Map;
495      typedef std::map<Value, Item> Inverse;
496
497      Map& map;
498      Reader reader;
499      Inverse inverse;
500
501      MapReaderInverter(Map& _map, const Reader& _reader)
502        : map(_map), reader(_reader) {}
503
504      virtual ~MapReaderInverter() {}
505
506      virtual void read(std::istream& is, const Item& item) {
507        Value value;
508        reader.read(is, value);
509        map.set(item, value);
510        typename Inverse::iterator it = inverse.find(value);
511        if (it == inverse.end()) {
512          inverse.insert(std::make_pair(value, item));
513        } else {
514          throw DataFormatError("Multiple ID occurence");
515        }
516      }
517
518      virtual Item read(std::istream& is) {
519        Value value;
520        reader.read(is, value);
521        typename Inverse::const_iterator it = inverse.find(value);
522        if (it != inverse.end()) {
523          return it->second;
524        } else {
525          throw DataFormatError("Invalid ID error");
526        }
527      }     
528    };
529
530    template <typename _Item, typename _Reader>
531    class SkipReaderInverter : public InverterBase<_Item> {
532    public:
533      typedef _Item Item;
534      typedef _Reader Reader;
535      typedef typename Reader::Value Value;
536      typedef std::map<Value, Item> Inverse;
537
538      Reader reader;
539
540      SkipReaderInverter(const Reader& _reader)
541        : reader(_reader) {}
542
543      virtual ~SkipReaderInverter() {}
544
545      virtual void read(std::istream& is, const Item& item) {
546        Value value;
547        reader.read(is, value);
548        typename Inverse::iterator it = inverse.find(value);
549        if (it == inverse.end()) {
550          inverse.insert(std::make_pair(value, item));
551        } else {
552          throw DataFormatError("Multiple ID occurence error");
553        }
554      }
555
556      virtual Item read(std::istream& is) {
557        Value value;
558        reader.read(is, value);
559        typename Inverse::const_iterator it = inverse.find(value);
560        if (it != inverse.end()) {
561          return it->second;
562        } else {
563          throw DataFormatError("Invalid ID error");
564        }
565      }     
566    private:
567      Inverse inverse;
568    };
569
570    // Readers
571
572    template <typename _Item>   
573    class ReaderBase {
574    public:
575      typedef _Item Item;
576
577      //      virtual ~ReaderBase() {}
578
579      virtual void read(std::istream& is, const Item& item) = 0;
580      virtual InverterBase<_Item>* getInverter() = 0;
581    };
582
583    template <typename _Item, typename _Map, typename _Reader>
584    class MapReader : public ReaderBase<_Item> {
585    public:
586      typedef _Map Map;
587      typedef _Reader Reader;
588      typedef typename Reader::Value Value;
589      typedef _Item Item;
590     
591      Map& map;
592      Reader reader;
593
594      MapReader(Map& _map, const Reader& _reader)
595        : map(_map), reader(_reader) {}
596
597      virtual ~MapReader() {}
598
599      virtual void read(std::istream& is, const Item& item) {
600        Value value;
601        reader.read(is, value);
602        map.set(item, value);
603      }
604
605      virtual InverterBase<_Item>* getInverter() {
606        return new MapReaderInverter<Item, Map, Reader>(map, reader);
607      }
608    };
609
610
611    template <typename _Item, typename _Reader>
612    class SkipReader : public ReaderBase<_Item> {
613    public:
614      typedef _Reader Reader;
615      typedef typename Reader::Value Value;
616      typedef _Item Item;
617
618      Reader reader;
619      SkipReader(const Reader& _reader) : reader(_reader) {}
620
621      virtual ~SkipReader() {}
622
623      virtual void read(std::istream& is, const Item&) {
624        Value value;
625        reader.read(is, value);
626      }     
627
628      virtual InverterBase<Item>* getInverter() {
629        return new SkipReaderInverter<Item, Reader>(reader);
630      }
631    };
632
633
634    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
635    NodeMapReaders node_map_readers;
636
637    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
638    EdgeMapReaders edge_map_readers;
639
640    typedef std::map<std::string, Node*> NodeReaders;
641    NodeReaders node_readers;
642
643    typedef std::map<std::string, Edge*> EdgeReaders;
644    EdgeReaders edge_readers;
645
646    std::istream& is;
647    Graph& graph;
648
649    SkipReader<Node, DefaultReader> nodeSkipper;
650    SkipReader<Edge, DefaultReader> edgeSkipper;
651
652  };
653
654  /// Ready to use reader function. 
655  template<typename Graph, typename CapacityMap, typename CostMap>
656  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
657                  typename Graph::Node &s, typename Graph::Node &t,
658                  CostMap& cost) {
659    GraphReader<Graph> reader(is, g);
660    reader.addEdgeMap("capacity", capacity);
661    reader.addEdgeMap("cost", cost);
662    reader.addNode("source", s);
663    reader.addNode("target", t);
664    reader.run();
665  }
666
667  template<typename Graph, typename CapacityMap>
668  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
669                  typename Graph::Node &s, typename Graph::Node &t) {
670    GraphReader<Graph> reader(is, g);
671    reader.addEdgeMap("capacity", capacity);
672    reader.addNode("source", s);
673    reader.addNode("target", t);
674    reader.run();
675  }
676
677  template<typename Graph, typename CapacityMap>
678  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity,
679                  typename Graph::Node &s) {
680    GraphReader<Graph> reader(is, g);
681    reader.addEdgeMap("capacity", capacity);
682    reader.addNode("source", s);
683    reader.run();
684  }
685
686  template<typename Graph, typename CapacityMap>
687  void readGraph(std::istream& is, Graph &g, CapacityMap& capacity) {
688    GraphReader<Graph> reader(is, g);
689    reader.addEdgeMap("capacity", capacity);
690    reader.run();
691  }
692
693  template<typename Graph>
694  void readGraph(std::istream& is, Graph &g) {
695    GraphReader<Graph> reader(is, g);
696    reader.run();
697  }
698
699}
700
701#endif
Note: See TracBrowser for help on using the repository browser.