COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/lemon/graph_reader.h @ 1266:74d616d081f0

Last change on this file since 1266:74d616d081f0 was 1250:30f540067a80, checked in by Alpar Juttner, 19 years ago

"unused parameter" warning solved

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