Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

graph_reader.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00020 
00021 #include <iostream>
00022 #include <sstream>
00023 
00024 #include <map>
00025 #include <vector>
00026 
00027 #include <memory>
00028 
00029 #include <lemon/error.h>
00030 
00032 
00033 
00034 namespace lemon {
00035 
00036   // Exceptions
00037 
00038   class IOException {
00039   public:
00040     virtual ~IOException() {}
00041     virtual string what() const = 0;
00042   };
00043 
00044   class DataFormatException : public IOException {
00045     std::string message;
00046   public:
00047     DataFormatException(const std::string& _message) 
00048       : message(_message) {}
00049     std::string what() const {
00050       return "DataFormatException: " + message; 
00051     }
00052   };
00053 
00054   template <typename _Exception>
00055   class StreamException : public _Exception {
00056   public:
00057     typedef _Exception Exception;
00058     StreamException(int _line, Exception _exception) 
00059       : Exception(_exception), line_num(_line) {}
00060     virtual int line() const {
00061       return line_num;
00062     }
00063 
00064     virtual ~StreamException() {}
00065 
00066     virtual std::string what() const {
00067       ostringstream os;
00068       os << Exception::what() << " in line " << line();
00069       return os.str();
00070     }
00071   private:
00072     int line_num;
00073   };  
00074 
00075 
00080   struct DefaultReaderTraits {
00081 
00085     template <typename _Value>
00086     struct Reader {
00088       typedef _Value Value;
00092       void read(std::istream& is, Value& value) {
00093         if (!(is >> value)) 
00094           throw DataFormatException("Default Reader format exception");
00095       }
00096     };
00097 
00099     typedef Reader<std::string> DefaultReader;
00100 
00101   };
00102 
00107   class QuotedStringReader {
00108   public:
00109     typedef std::string Value;
00110     
00115     QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
00116     
00120     void read(std::istream& is, std::string& value) {
00121       char c;
00122       value.clear();
00123       is >> ws;
00124       if (!is.get(c) || c != '\"') 
00125         throw DataFormatException("Quoted string format");
00126       while (is.get(c) && c != '\"') {
00127         if (escaped && c == '\\') {
00128           value += readEscape(is);
00129         } else {
00130           value += c;
00131         }
00132       }
00133       if (!is) throw DataFormatException("Quoted string format");
00134     }
00135 
00136   private:
00137     
00138     static char readEscape(std::istream& is) {
00139       char c;
00140       switch (is.get(c), c) {
00141       case '\\':
00142         return '\\';
00143       case '\"':
00144         return '\"';
00145       case '\'':
00146         return '\'';
00147       case '\?':
00148         return '\?';
00149       case 'a':
00150         return '\a';
00151       case 'b':
00152         return '\b';
00153       case 'f':
00154         return '\f';
00155       case 'n':
00156         return '\n';
00157       case 'r':
00158         return '\r';
00159       case 't':
00160         return '\t';
00161       case 'v':
00162         return '\v';
00163       case 'x':
00164         {
00165           int code;
00166           if (!is.get(c) || !isHex(c)) 
00167             throw DataFormatException("Escape format exception");
00168           else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
00169           else code = code * 16 + valueHex(c);
00170           return code;
00171         }
00172       default:
00173         {
00174           int code;
00175           if (!isOct(c)) 
00176             throw DataFormatException("Escape format exception");
00177           else if (code = valueOct(c), !is.get(c) || !isOct(c)) 
00178             is.putback(c);
00179           else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 
00180             is.putback(c);
00181           else code = code * 8 + valueOct(c);
00182           return code;
00183         }             
00184       } 
00185     }
00186 
00187     static bool isOct(char c) {
00188       return '0' <= c && c <='7'; 
00189     }
00190     
00191     static int valueOct(char c) {
00192       return c - '0';
00193     }
00194 
00195    static bool isHex(char c) {
00196       return ('0' <= c && c <= '9') || 
00197         ('a' <= c && c <= 'z') || 
00198         ('A' <= c && c <= 'Z'); 
00199     }
00200     
00201     static int valueHex(char c) {
00202       if ('0' <= c && c <= '9') return c - '0';
00203       if ('a' <= c && c <= 'z') return c - 'a' + 10;
00204       return c - 'A' + 10;
00205     }
00206 
00207     bool escaped;
00208   };
00209 
00215   template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits> 
00216   class GraphReader {
00217   public:
00218     
00219     typedef _Graph Graph;
00220     typedef typename Graph::Node Node;
00221     typedef typename Graph::Edge Edge;
00222 
00223     typedef _ReaderTraits ReaderTraits;
00224     typedef typename ReaderTraits::DefaultReader DefaultReader;
00225 
00231     GraphReader(std::istream& _is, Graph& _graph, 
00232                 const DefaultReader& _reader = DefaultReader()) 
00233       : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
00234 
00238     ~GraphReader() {
00239 
00240       for (typename NodeMapReaders::iterator it = node_map_readers.begin(); 
00241            it != node_map_readers.end(); ++it) {
00242         delete it->second;
00243       }
00244 
00245       for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); 
00246            it != edge_map_readers.end(); ++it) {
00247         delete it->second;
00248       }
00249 
00250     }
00251 
00255     template <typename Map>
00256     GraphReader& addNodeMap(std::string name, Map& map) {
00257       return addNodeMap<typename ReaderTraits::template 
00258         Reader<typename Map::Value>, Map>(name, map);
00259     }
00260 
00264     template <typename Reader, typename Map>
00265     GraphReader& addNodeMap(std::string name, Map& map, 
00266                              const Reader& reader = Reader()) {
00267       if (node_map_readers.find(name) != node_map_readers.end()) {
00268         throw Exception() << "Multiple read rule for node map: " << name;
00269       }
00270       node_map_readers.insert(
00271         make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
00272       return *this;
00273     }
00274 
00278     template <typename Reader>
00279     GraphReader& skipNodeMap(std::string name, 
00280                              const Reader& reader = Reader()) {
00281       if (node_map_readers.find(name) != node_map_readers.end()) {
00282         throw Exception() << "Multiple read rule for node map: " << name;
00283       }
00284       node_map_readers.insert(
00285         make_pair(name, new SkipReader<Node, Reader>(reader)));
00286       return *this;
00287     }
00288 
00292     template <typename Map>
00293     GraphReader& addEdgeMap(std::string name, Map& map) { 
00294       return addEdgeMap<typename ReaderTraits::template
00295         Reader<typename Map::Value>, Map>(name, map);
00296     }
00297 
00298 
00302     template <typename Reader, typename Map>
00303     GraphReader& addEdgeMap(std::string name, Map& map,
00304                              const Reader& reader = Reader()) {
00305       if (edge_map_readers.find(name) != edge_map_readers.end()) {
00306         throw Exception() << "Multiple read rule for edge map: " << name;
00307       }
00308       edge_map_readers.insert(
00309         make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
00310       return *this;
00311     }
00312 
00316     template <typename Reader>
00317     GraphReader& skipEdgeMap(std::string name,
00318                              const Reader& reader = Reader()) {
00319       if (edge_map_readers.find(name) != edge_map_readers.end()) {
00320         throw Exception() << "Multiple read rule for edge map: " << name;
00321       }
00322       edge_map_readers.insert(
00323         make_pair(name, new SkipReader<Edge, Reader>(reader)));
00324       return *this;
00325     }
00326 
00330     GraphReader& addNode(std::string name, Node& node) {
00331       if (node_readers.find(name) != node_readers.end()) {
00332         throw Exception() << "Multiple read rule for node";
00333       }
00334       node_readers.insert(make_pair(name, &node));
00335       return *this;
00336     }
00337 
00341     GraphReader& addEdge(std::string name, Edge& edge) {
00342       if (edge_readers.find(name) != edge_readers.end()) {
00343         throw Exception() << "Multiple read rule for edge";
00344       }
00345       edge_readers.insert(make_pair(name, &edge));
00346       return *this;
00347     }
00348 
00352     void run() {
00353       int line_num = 0;
00354       std::auto_ptr<InverterBase<Node> > nodeInverter;
00355       std::auto_ptr<InverterBase<Edge> > edgeInverter;
00356       try {
00357         std::string line = readNotEmptyLine(is, line_num);
00358         if (line.find("@nodeset") == 0) {
00359           line = readNodeSet(line_num, nodeInverter);
00360         } 
00361         if (line.find("@edgeset") == 0) {
00362           line = readEdgeSet(line_num, edgeInverter, nodeInverter);
00363         }
00364         if (line.find("@nodes") == 0) {
00365           line = readNodes(line_num, nodeInverter);
00366         }
00367         if (line.find("@edges") == 0) {
00368           line = readEdges(line_num, edgeInverter);
00369         }
00370         if (line.find("@end") != 0) {
00371           throw DataFormatException("Invalid control sequence: " + line);
00372         }
00373       } catch (DataFormatException e) {
00374         throw StreamException<DataFormatException>(line_num, e);
00375       }
00376     }
00377 
00378   private:
00379 
00380     template <typename Item> class InverterBase;
00381 
00382     std::string readNodeSet(int& line_num, 
00383                             auto_ptr<InverterBase<Node> > & nodeInverter) {
00384       std::vector<ReaderBase<Node>* > index;
00385       {
00386         std::string line = readNotEmptyLine(is, line_num);    
00387         std::string id;
00388         std::istringstream ls(line);    
00389         while (ls >> id) {
00390           if (id[0] == '#') break;
00391           typename NodeMapReaders::iterator it = node_map_readers.find(id);
00392           if (it != node_map_readers.end()) {
00393             index.push_back(it->second);
00394             node_map_readers.erase(it);
00395           } else {
00396             index.push_back(&nodeSkipper);
00397           }
00398         }
00399       }
00400 
00401       if (index.size() == 0) {
00402         throw DataFormatException("No node map found");
00403       }
00404 
00405       nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
00406       std::string line;
00407       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00408         Node node = graph.addNode();
00409         std::istringstream ls(line);
00410         nodeInverter->read(ls, node);
00411         for (int i = 1; i < (int)index.size(); ++i) {
00412           index[i]->read(ls, node);
00413         }
00414       }
00415       return line;
00416     }
00417 
00418     std::string readEdgeSet(int& line_num, 
00419                             auto_ptr<InverterBase<Edge> > & edgeInverter, 
00420                             auto_ptr<InverterBase<Node> > & nodeInverter) {
00421       std::vector<ReaderBase<Edge>*> index;
00422       {
00423         std::string line = readNotEmptyLine(is, line_num);    
00424         std::string id;
00425         std::istringstream ls(line);    
00426         while (ls >> id) {
00427           if (id[0] == '#') break;
00428           typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
00429           if (it != edge_map_readers.end()) {
00430             index.push_back(it->second);
00431             edge_map_readers.erase(it);
00432           } else {
00433             index.push_back(&edgeSkipper);
00434           }
00435         }
00436       }
00437 
00438       if (index.size() == 0) {
00439         throw DataFormatException("No edge map found");
00440       }
00441 
00442       edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
00443       std::string line;
00444       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
00445         std::istringstream ls(line);
00446         Node source = nodeInverter->read(ls);
00447         Node target = nodeInverter->read(ls);
00448         Edge edge = graph.addEdge(source, target);
00449         edgeInverter->read(ls, edge);
00450         for (int i = 1; i < (int)index.size(); ++i) {
00451           index[i]->read(ls, edge);
00452         }
00453       }      
00454       return line;
00455     }
00456 
00457     std::string readNodes(int& line_num, 
00458                           auto_ptr<InverterBase<Node> >& nodeInverter) {
00459       std::string line;
00460       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00461         std::istringstream ls(line);
00462         std::string name;
00463         ls >> name;
00464         typename NodeReaders::iterator it = node_readers.find(name);
00465         if (it != node_readers.end()) {
00466           *(it -> second) = nodeInverter->read(ls);
00467         } 
00468       }        
00469       return line;
00470     }
00471 
00472     std::string readEdges(int& line_num, 
00473                           auto_ptr<InverterBase<Edge> >& edgeInverter) {
00474       std::string line;
00475       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
00476         std::istringstream ls(line);
00477         std::string name;
00478         ls >> name;
00479         typename EdgeReaders::iterator it = edge_readers.find(name);
00480         if (it != edge_readers.end()) {
00481           *(it -> second) = edgeInverter->read(ls);
00482         } 
00483       }        
00484       return line;    
00485     }
00486 
00487     std::string readNotEmptyLine(std::istream& is, int& line_num) {
00488       std::string line;
00489       while (++line_num, getline(is, line)) {   
00490         int vi = line.find_first_not_of(" \t");
00491         if (vi != (int)string::npos && line[vi] != '#') {
00492           return line.substr(vi);
00493         }
00494       }
00495       throw DataFormatException("End of stream");
00496     }
00497     
00498     // Inverters store and give back the Item from the id,
00499     // and may put the ids into a map.
00500     
00501     template <typename _Item>
00502     class InverterBase {
00503     public:
00504       typedef _Item Item;
00505       virtual void read(std::istream&, const Item&) = 0;
00506       virtual Item read(std::istream&) = 0;
00507     };
00508 
00509     template <typename _Item, typename _Map, typename _Reader>
00510     class MapReaderInverter : public InverterBase<_Item> {
00511     public:
00512       typedef _Item Item;
00513       typedef _Reader Reader;
00514       typedef typename Reader::Value Value;
00515       typedef _Map Map;
00516       typedef std::map<Value, Item> Inverse;
00517 
00518       Map& map;
00519       Reader reader;
00520       Inverse inverse;
00521 
00522       MapReaderInverter(Map& _map, const Reader& _reader) 
00523         : map(_map), reader(_reader) {}
00524 
00525       virtual ~MapReaderInverter() {}
00526 
00527       virtual void read(std::istream& is, const Item& item) {
00528         Value value;
00529         reader.read(is, value);
00530         map.set(item, value);
00531         typename Inverse::iterator it = inverse.find(value);
00532         if (it == inverse.end()) {
00533           inverse.insert(make_pair(value, item));
00534         } else {
00535           throw DataFormatException("Multiple ID occurence");
00536         }
00537       }
00538 
00539       virtual Item read(std::istream& is) {
00540         Value value;
00541         reader.read(is, value); 
00542         typename Inverse::const_iterator it = inverse.find(value);
00543         if (it != inverse.end()) {
00544           return it->second;
00545         } else {
00546           throw DataFormatException("Invalid ID");
00547         }
00548       }      
00549     };
00550 
00551     template <typename _Item, typename _Reader>
00552     class SkipReaderInverter : public InverterBase<_Item> {
00553     public:
00554       typedef _Item Item;
00555       typedef _Reader Reader;
00556       typedef typename Reader::Value Value;
00557       typedef std::map<Value, Item> Inverse;
00558 
00559       Reader reader;
00560 
00561       SkipReaderInverter(const Reader& _reader) 
00562         : reader(_reader) {}
00563 
00564       virtual ~SkipReaderInverter() {}
00565 
00566       virtual void read(std::istream& is, const Item& item) {
00567         Value value;
00568         reader.read(is, value);
00569         typename Inverse::iterator it = inverse.find(value);
00570         if (it == inverse.end()) {
00571           inverse.insert(make_pair(value, item));
00572         } else {
00573           throw DataFormatException("Multiple ID occurence");
00574         }
00575       }
00576 
00577       virtual Item read(std::istream& is) {
00578         Value value;
00579         reader.read(is, value); 
00580         typename Inverse::const_iterator it = inverse.find(value);
00581         if (it != inverse.end()) {
00582           return it->second;
00583         } else {
00584           throw DataFormatException("Invalid ID");
00585         }
00586       }      
00587     private:
00588       Inverse inverse;
00589     };
00590 
00591     // Readers
00592 
00593     template <typename _Item>    
00594     class ReaderBase {
00595     public:
00596       typedef _Item Item;
00597 
00598       //      virtual ~ReaderBase() {}
00599 
00600       virtual void read(std::istream& is, const Item& item) = 0;
00601       virtual InverterBase<_Item>* getInverter() = 0;
00602     };
00603 
00604     template <typename _Item, typename _Map, typename _Reader>
00605     class MapReader : public ReaderBase<_Item> {
00606     public:
00607       typedef _Map Map;
00608       typedef _Reader Reader;
00609       typedef typename Reader::Value Value;
00610       typedef _Item Item;
00611       
00612       Map& map;
00613       Reader reader;
00614 
00615       MapReader(Map& _map, const Reader& _reader) 
00616         : map(_map), reader(_reader) {}
00617 
00618       virtual ~MapReader() {}
00619 
00620       virtual void read(std::istream& is, const Item& item) {
00621         Value value;
00622         reader.read(is, value);
00623         map.set(item, value);
00624       }
00625 
00626       virtual InverterBase<_Item>* getInverter() {
00627         return new MapReaderInverter<Item, Map, Reader>(map, reader);
00628       }
00629     };
00630 
00631 
00632     template <typename _Item, typename _Reader>
00633     class SkipReader : public ReaderBase<_Item> {
00634     public:
00635       typedef _Reader Reader;
00636       typedef typename Reader::Value Value;
00637       typedef _Item Item;
00638 
00639       Reader reader;
00640       SkipReader(const Reader& _reader) : reader(_reader) {}
00641 
00642       virtual ~SkipReader() {}
00643 
00644       virtual void read(std::istream& is, const Item& item) {
00645         Value value;
00646         reader.read(is, value);
00647       }      
00648 
00649       virtual InverterBase<Item>* getInverter() {
00650         return new SkipReaderInverter<Item, Reader>(reader);
00651       }
00652     };
00653 
00654 
00655     typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
00656     NodeMapReaders node_map_readers;
00657 
00658     typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
00659     EdgeMapReaders edge_map_readers;
00660 
00661     typedef std::map<std::string, Node*> NodeReaders;
00662     NodeReaders node_readers;
00663 
00664     typedef std::map<std::string, Edge*> EdgeReaders;
00665     EdgeReaders edge_readers;
00666 
00667     std::istream& is;
00668     Graph& graph;
00669 
00670     SkipReader<Node, DefaultReader> nodeSkipper;
00671     SkipReader<Edge, DefaultReader> edgeSkipper;
00672 
00673   };
00674 
00675 }

Generated on Mon Feb 21 15:02:21 2005 for LEMON by  doxygen 1.4.1