COIN-OR::LEMON - Graph Library

Changeset 1036:2f514b5c7122 in lemon-0.x


Ignore:
Timestamp:
12/14/04 20:26:50 (15 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1426
Message:

reader under construction

Location:
src/work/deba
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/deba/graph_io_test.cc

    r1032 r1036  
    11#include <lemon/smart_graph.h>
    2 #include <lemon/graph_reader.h>
     2#include "graph_reader.h"
    33
    44#include <iostream>
     
    1212  SmartGraph graph;
    1313  GraphReader<SmartGraph> reader(input, graph);
     14  SmartGraph::NodeMap<int> id(graph);
     15  reader.readNodeMap("id", id);
    1416  SmartGraph::NodeMap<int> cost(graph);
    1517  reader.readNodeMap("cost", cost);
    1618  SmartGraph::NodeMap<string> color(graph);
    1719  reader.readNodeMap("color", color);
    18   reader.read();
     20  SmartGraph::NodeMap<string> description(graph);
     21  reader.readNodeMap<QuotedStringReader>("description", description);
     22  SmartGraph::EdgeMap<char> mmap(graph);
     23  reader.readEdgeMap("mmap", mmap);
     24  reader.skipEdgeMap<QuotedStringReader>("description");
     25  try {
     26    reader.read();
     27  } catch (IOException& e) {
     28    cerr << e.what() << endl;
     29  } catch (Exception e) {
     30    cerr << e.what() << endl;
     31  }
    1932  for (SmartGraph::NodeIt it(graph); it != INVALID; ++it) {
    20     cout << cost[it] << color[it] << endl;
     33    cout << cost[it] << ' ' << color[it] << ' ' << description[it] << endl;
     34  }
     35
     36  for (SmartGraph::EdgeIt it(graph); it != INVALID; ++it) {
     37    cout << mmap[it] << ' ' << id[graph.source(it)] << ' ' << id[graph.target(it)]  << endl;
    2138  }
    2239  return 0;
  • src/work/deba/graph_reader.h

    r1032 r1036  
    1717///\ingroup gio
    1818///\file
    19 ///\brief Map utilities.
     19///\brief Graph reader.
    2020
    2121#include <iostream>
     
    3131
    3232namespace lemon {
     33
     34  // Exceptions
     35
     36  class IOException {
     37  public:
     38    virtual string what() const = 0;
     39  };
     40
     41  class DataFormatException : public IOException {
     42    std::string message;
     43  public:
     44    DataFormatException(const std::string& _message)
     45      : message(_message) {}
     46    std::string what() const {
     47      return "DataFormatException: " + message;
     48    }
     49  };
     50
     51  class StreamException : public IOException {
     52  public:
     53    virtual int line() = 0;
     54  private:
     55    IOException* exception;
     56    int line_num;
     57  }; 
     58
     59
     60  // Readers and ReaderTraits
    3361 
    3462  struct DefaultReaderTraits {
     
    3866      typedef _Value Value;
    3967      void read(std::istream& is, Value& value) {
    40         is >> value;
    41       }
    42     };
    43 
    44     template <typename _Value>
    45     struct Skipper {
    46       typedef _Value Value;
    47       void read(std::istream& is) {
    48         Value tmp;
    49         is >> tmp;
    50       }     
    51     };
    52 
    53     struct DefaultSkipper {
    54       void read(std::istream& is) {
    55         std::string tmp;
    56         is >> tmp;
    57       }
    58     };
     68        if (!(is >> value))
     69          throw DataFormatException("Default Reader format exception");
     70      }
     71    };
     72
     73    typedef Reader<std::string> DefaultReader;
     74
    5975  };
    6076
    61   class IOException {
    62     virtual string message() = 0;
     77  class QuotedStringReader {
     78  public:
     79    typedef std::string Value;
     80
     81    QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
     82
     83    void read(std::istream& is, std::string& value) {
     84      char c;
     85      value.clear();
     86      is >> ws;
     87      if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format exception");
     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 DataFormatException("Quoted string format exception");
     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)) throw DataFormatException("Escape format exception");
     129          else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
     130          else code = code * 16 + valueHex(c);
     131          return code;
     132        }
     133      default:
     134        {
     135          int code;
     136          if (!isOct(c)) throw DataFormatException("Escape format exception");
     137          else if (code = valueOct(c), !is.get(c) || !isOct(c)) is.putback(c);
     138          else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) is.putback(c);
     139          else code = code * 8 + valueOct(c);
     140          return code;
     141        }             
     142      }
     143    }
     144
     145    static bool isOct(char c) {
     146      return '0' <= c && c <='7';
     147    }
     148   
     149    static int valueOct(char c) {
     150      return c - '0';
     151    }
     152
     153   static bool isHex(char c) {
     154      return ('0' <= c && c <= '9') || ('a' <= c && c <= 'z') || ('A' <= c && c <= 'Z');
     155    }
     156   
     157    static int valueHex(char c) {
     158      if ('0' <= c && c <= '9') return c - '0';
     159      if ('a' <= c && c <= 'z') return c - 'a' + 10;
     160      return c - 'A' + 10;
     161    }
     162
     163    bool escaped;
    63164  };
    64165
    65   class FileReaderException {
    66     virtual int getLine() = 0;   
    67   };
    68 
    69  
     166
     167
     168
     169
     170  // Graph reader
    70171 
    71172  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
     
    79180
    80181    typedef _ReaderTraits ReaderTraits;
    81    
    82 
    83     GraphReader(std::istream& _is, Graph& _graph) : is(_is), graph(_graph) {}
     182    typedef typename ReaderTraits::DefaultReader DefaultReader;
     183
     184    GraphReader(istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader())
     185      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
     186
     187
     188    ~GraphReader() {
     189
     190      for (typename NodeReaders::iterator it = node_readers.begin(); it != node_readers.end(); ++it) {
     191        delete it->second;
     192      }
     193
     194      for (typename EdgeReaders::iterator it = edge_readers.begin(); it != edge_readers.end(); ++it) {
     195        delete it->second;
     196      }
     197
     198    }
    84199
    85200    template <typename Map>
    86     GraphReader& readNodeMap(std::string name, Map& map,
    87                              const typename ReaderTraits::template Reader<typename Map::Value>& reader =
    88                              typename ReaderTraits::template Reader<typename Map::Value>()) {
    89       return readNodeMap<Map, typename ReaderTraits::template Reader<typename Map::Value> >(name, map, reader);
    90     }
    91 
    92     template <typename Map, typename Reader>
     201    GraphReader& readNodeMap(std::string name, Map& map) {
     202      return readNodeMap<typename ReaderTraits::template Reader<typename Map::Value>, Map>(name, map);
     203    }
     204
     205    template <typename Reader, typename Map>
    93206    GraphReader& readNodeMap(std::string name, Map& map, const Reader& reader = Reader()) {
     207      if (node_readers.find(name) != node_readers.end()) {
     208        Exception e;
     209        e << "Multiple read rule for node map: " << name;
     210        throw e;
     211      }
    94212      node_readers.insert(make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
    95213      return *this;
    96214    }
    97215
     216    template <typename Reader>
     217    GraphReader& skipNodeMap(std::string name, const Reader& reader = Reader()) {
     218      if (node_readers.find(name) != node_readers.end()) {
     219        Exception e;
     220        e << "Multiple read rule for node map: " << name;
     221        throw e;
     222      }
     223      node_readers.insert(make_pair(name, new SkipReader<Node, Reader>(reader)));
     224      return *this;
     225    }
     226
    98227    template <typename Map>
    99     GraphReader& readEdgeMap(std::string name, Map& map,
    100                              const typename ReaderTraits::template Reader<typename Map::Value>& reader =
    101                              typename ReaderTraits::template Reader<typename Map::Value>()) {
    102       return readEdgeMap<Map, typename ReaderTraits::template Reader<typename Map::Value> >(name, map, reader);
    103     }
    104 
    105     template <typename Map, typename Reader>
     228    GraphReader& readEdgeMap(std::string name, Map& map) {
     229      return readEdgeMap<typename ReaderTraits::template Reader<typename Map::Value>, Map>(name, map);
     230    }
     231
     232
     233    template <typename Reader, typename Map>
    106234    GraphReader& readEdgeMap(std::string name, Map& map, const Reader& reader = Reader()) {
     235      if (edge_readers.find(name) != edge_readers.end()) {
     236        Exception e;
     237        e << "Multiple read rule for edge map: " << name;
     238        throw e;
     239      }
    107240      edge_readers.insert(make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
    108241      return *this;
    109242    }
    110243
     244    template <typename Reader>
     245    GraphReader& skipEdgeMap(std::string name, const Reader& reader = Reader()) {
     246      if (edge_readers.find(name) != edge_readers.end()) {
     247        Exception e;
     248        e << "Multiple read rule for edge map: " << name;
     249        throw e;
     250      }
     251      edge_readers.insert(make_pair(name, new SkipReader<Edge, Reader>(reader)));
     252      return *this;
     253    }
     254
    111255    void read() {
    112256      int line_num = 0;
    113       readNodeSet(line_num);
    114       readEdgeSet(line_num);
    115       {
    116         std::string line = readNotEmptyLine(is, line_num);
    117       }
     257      InverterBase<Node>* nodeInverter = 0;
     258      InverterBase<Edge>* edgeInverter = 0;
     259      // \todo delete the inverters
     260      //      try {
     261        {
     262          std::string line = readNotEmptyLine(is, line_num);
     263        }
     264        readNodeSet(line_num, nodeInverter);
     265        readEdgeSet(line_num, edgeInverter, nodeInverter);
     266        //      } catch (...){
     267        if (nodeInverter != 0) delete nodeInverter;
     268        if (edgeInverter != 0) delete edgeInverter;
     269        //      }
    118270    }
    119271
    120272  private:
    121273
    122     void readNodeSet(int& line_num) {
     274    template <typename Item> class InverterBase;
     275    //    template <typename Item> class InverterBase;
     276
     277    void readNodeSet(int& line_num, InverterBase<Node>* & nodeInverter) {
    123278      int n = 0;
    124       {
    125         std::string line = readNotEmptyLine(is, line_num);     
    126       }
    127       std::vector<MapReaderBase<Node>*> index;
     279      std::vector<ReaderBase<Node>*> index;
    128280      {
    129281        std::string line = readNotEmptyLine(is, line_num);   
     
    131283        std::istringstream ls(line);   
    132284        while (ls >> id) {
    133           typename map<std::string, MapReaderBase<Node>* >::iterator it = node_readers.find(id);
     285          if (id[0] == '#') break;
     286          typename NodeReaders::iterator it = node_readers.find(id);
    134287          if (it != node_readers.end()) {
    135288            index.push_back(it->second);
    136289          } else {
    137             index.push_back(0);
     290            index.push_back(&nodeSkipper);
    138291          }
    139292          ++n;
    140293        }
    141294      }
     295
     296      nodeInverter = index[0]->getInverter();
    142297      std::string line;
    143298      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
    144299        Node node = graph.addNode();
    145300        std::istringstream ls(line);
    146         for (int i = 0; i < n; ++i) {
    147           if (index[i] != 0) {     
    148             index[i]->read(ls, node);
     301        nodeInverter->read(ls, node);
     302        for (int i = 1; i < n; ++i) {
     303          index[i]->read(ls, node);
     304        }
     305      }
     306    }
     307
     308    void readEdgeSet(int& line_num, InverterBase<Edge>* & edgeInverter, InverterBase<Node>* & nodeInverter) {
     309      int n = 0;
     310      std::vector<ReaderBase<Edge>*> index;
     311      {
     312        std::string line = readNotEmptyLine(is, line_num);   
     313        std::string id;
     314        std::istringstream ls(line);   
     315        while (ls >> id) {
     316          if (id[0] == '#') break;
     317          typename EdgeReaders::iterator it = edge_readers.find(id);
     318          if (it != edge_readers.end()) {
     319            index.push_back(it->second);
    149320          } else {
    150             default_skipper.read(ls);
     321            index.push_back(&edgeSkipper);
    151322          }
    152         }
    153       }
    154     }
    155 
    156     void readEdgeSet(int& line_num) {
    157      
     323          ++n;
     324        }
     325      }
     326      edgeInverter = index[0]->getInverter();
     327      std::string line;
     328      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
     329        std::istringstream ls(line);
     330        Node source = nodeInverter->read(ls);
     331        Node target = nodeInverter->read(ls);
     332        Edge edge = graph.addEdge(source, target);
     333        edgeInverter->read(ls, edge);
     334        for (int i = 1; i < n; ++i) {
     335          index[i]->read(ls, edge);
     336        }
     337      }     
    158338    }
    159339
     
    169349    }
    170350   
    171     istream& is;
    172     Graph& graph;
    173 
    174     typename ReaderTraits::DefaultSkipper default_skipper;
     351    template <typename _Item>
     352    class InverterBase {
     353    public:
     354      typedef _Item Item;
     355      virtual void read(istream&, const Item&) = 0;
     356      virtual Item read(istream&) = 0;
     357    };
     358
     359    template <typename _Item, typename _Map, typename _Reader>
     360    class MapReaderInverter : public InverterBase<_Item> {
     361    public:
     362      typedef _Item Item;
     363      typedef _Reader Reader;
     364      typedef typename Reader::Value Value;
     365      typedef _Map Map;
     366      typedef std::map<Value, Item> Inverse;
     367
     368      Map& map;
     369      Reader reader;
     370      Inverse inverse;
     371
     372      MapReaderInverter(Map& _map, const Reader& _reader)
     373        : map(_map), reader(_reader) {}
     374
     375      virtual void read(istream& is, const Item& item) {
     376        Value value;
     377        reader.read(is, value);
     378        map.set(item, value);
     379        typename Inverse::iterator it = inverse.find(value);
     380        if (it == inverse.end()) {
     381          inverse.insert(make_pair(value, item));
     382        } else {
     383          throw DataFormatException("Multiple ID occurence");
     384        }
     385      }
     386
     387      virtual Item read(istream& is) {
     388        Value value;
     389        reader.read(is, value);
     390        typename Inverse::const_iterator it = inverse.find(value);
     391        if (it != inverse.end()) {
     392          return it->second;
     393        } else {
     394          throw DataFormatException("Invalid ID");
     395        }
     396      }     
     397    };
     398
     399    template <typename _Item, typename _Reader>
     400    class SkipReaderInverter : public InverterBase<_Item> {
     401    public:
     402      typedef _Item Item;
     403      typedef _Reader Reader;
     404      typedef typename Reader::Value Value;
     405      typedef std::map<Value, Item> Inverse;
     406
     407      Reader reader;
     408
     409      SkipReaderInverter(const Reader& _reader)
     410        : reader(_reader) {}
     411
     412      virtual void read(istream& is, const Item& item) {
     413        Value value;
     414        reader.read(is, value);
     415        typename Inverse::iterator it = inverse.find(value);
     416        if (it == inverse.end()) {
     417          inverse.insert(make_pair(value, item));
     418        } else {
     419          throw DataFormatException("Multiple ID occurence");
     420        }
     421      }
     422
     423      virtual Item read(istream& is) {
     424        Value value;
     425        reader.read(is, value);
     426        typename Inverse::const_iterator it = inverse.find(value);
     427        if (it != inverse.end()) {
     428          return it->second;
     429        } else {
     430          throw DataFormatException("Invalid ID");
     431        }
     432      }     
     433    private:
     434      Inverse inverse;
     435    };
     436
    175437
    176438    template <typename _Item>   
    177     class MapReaderBase {
     439    class ReaderBase {
    178440    public:
    179441      typedef _Item Item;
    180442      virtual void read(istream& is, const Item& item) = 0;
    181     };
    182    
     443      virtual InverterBase<_Item>* getInverter() = 0;
     444    };
     445
    183446    template <typename _Item, typename _Map, typename _Reader>
    184     class MapReader : public MapReaderBase<_Item> {
     447    class MapReader : public ReaderBase<_Item> {
    185448    public:
    186449      typedef _Map Map;
    187450      typedef _Reader Reader;
     451      typedef typename Reader::Value Value;
    188452      typedef _Item Item;
    189453     
     
    196460
    197461      virtual void read(istream& is, const Item& item) {
    198         typename Reader::Value value;
     462        Value value;
    199463        reader.read(is, value);
    200464        map.set(item, value);
    201465      }
    202     };
    203 
    204     typedef std::map<std::string, MapReaderBase<Node>* > NodeReaders;
     466
     467      virtual InverterBase<_Item>* getInverter() {
     468        return new MapReaderInverter<Item, Map, Reader>(map, reader);
     469      }
     470    };
     471
     472
     473    template <typename _Item, typename _Reader>
     474    class SkipReader : public ReaderBase<_Item> {
     475    public:
     476      typedef _Reader Reader;
     477      typedef typename Reader::Value Value;
     478      typedef _Item Item;
     479
     480      Reader reader;
     481      SkipReader(const Reader& _reader) : reader(_reader) {}
     482
     483      virtual void read(istream& is, const Item& item) {
     484        Value value;
     485        reader.read(is, value);
     486      }     
     487
     488      virtual InverterBase<Item>* getInverter() {
     489        return new SkipReaderInverter<Item, Reader>(reader);
     490      }
     491    };
     492
     493
     494    typedef std::map<std::string, ReaderBase<Node>* > NodeReaders;
    205495    NodeReaders node_readers;
    206496
    207     typedef std::map<std::string, MapReaderBase<Edge>* > EdgeReaders;
     497    typedef std::map<std::string, ReaderBase<Edge>* > EdgeReaders;
    208498    EdgeReaders edge_readers;
    209499
     500    std::istream& is;
     501    Graph& graph;
     502
     503    SkipReader<Node, DefaultReader> nodeSkipper;
     504    SkipReader<Edge, DefaultReader> edgeSkipper;
     505
    210506  };
    211507
  • src/work/deba/test.lgf

    r1032 r1036  
     1@nodeset
     2id cost color description mmap
     31 1 green "A -> B \t: 10" a
     42 2 blue "A -> B \t: 10" b
     5# hatalom dicsoseg "A -> B \t: 10" c
     63 1 red "A -> B \t: 10" d #adjkhj
     74 2 red "A -> B \t: 10" e
     85 1 green "A -> B \t: 10" f
     910 1 green "A -> B \t: 10" g
     10    # hello - bello csucsok "A -> B \t: 10"
     116 2 blue "A -> B \t: 10" h
     127 1 blue "A -> B \t: 10" i
     138 2 red "A -> B \t: 10" j
     149 1 green "A -> B \t: 10" k
     15
     16@edgeset
     17                id      weight  description             mmap
     181       4       1       10      "A -> B \t: 101"        a
     193       5       5       29      "A -> B \t: 10q"        b
     203       4       2       92      "A -> B \t: 10a"        c
     212       3       6       92      "A -> B \t: 10d"        d
     229       5       9       49      "A -> B \t: 10c"        e
     2310      4       3       40      "A -> B \t: 10v"        f
     241       3       8       84      "A -> B \t: 10g"        g
     256       7       4       83      "A -> B \t: 10h"        h
     268       9       7       37      "A -> B \t: 10j"        i
     277       8       10      12      "A -> B \t: 10g"        j
    128
    229@nodes
     30source 1
     31target 7
    332
    4 id cost color
     33@edges
     34newedge 7
    535
    6 1 1 green
    7 2 2 blue
    8 # hatalom dicsoseg
    9 3 1 red
    10 4 2 red
    11 5 1 green
    12 10 1 green # ez nem egy igazan jo sor
    13     # hello - bello csucsok
    14 6 2 blue
    15 7 1 blue
    16 8 2 red
    17 9 1 green
    18 @edges
    19 source target weight
    20 1 4 10
    21 3 5 29
    22 3 4 92
    23 2 3 92
    24 9 5 49
    25 10 4 40
    26 1 3 84
    27 6 7 83
    28 8 9 37
    29 7 8 89
    3036@end
Note: See TracChangeset for help on using the changeset viewer.