COIN-OR::LEMON - Graph Library

Changeset 1037:3eaff8d04171 in lemon-0.x


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

graph_io under construction
This is a working version, but needs more improvments.

todo:

documention + fix the file format
improve the exception system

add some possible asserts

tutorials

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

Legend:

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

    r1036 r1037  
    11#include <lemon/smart_graph.h>
     2
     3#include "map_utils.h"
     4
     5
    26#include "graph_reader.h"
     7#include "graph_writer.h"
    38
    49#include <iostream>
     
    1217  SmartGraph graph;
    1318  GraphReader<SmartGraph> reader(input, graph);
     19
    1420  SmartGraph::NodeMap<int> id(graph);
    1521  reader.readNodeMap("id", id);
     22
    1623  SmartGraph::NodeMap<int> cost(graph);
    1724  reader.readNodeMap("cost", cost);
     25 
    1826  SmartGraph::NodeMap<string> color(graph);
    1927  reader.readNodeMap("color", color);
     28
    2029  SmartGraph::NodeMap<string> description(graph);
    2130  reader.readNodeMap<QuotedStringReader>("description", description);
     31
    2232  SmartGraph::EdgeMap<char> mmap(graph);
    2333  reader.readEdgeMap("mmap", mmap);
     34
    2435  reader.skipEdgeMap<QuotedStringReader>("description");
     36
     37  SmartGraph::Node source;
     38  reader.readNode("source", source);
     39 
     40  SmartGraph::Edge newedge;
     41  reader.readEdge("newedge", newedge);
     42
    2543  try {
    2644    reader.read();
     
    3755    cout << mmap[it] << ' ' << id[graph.source(it)] << ' ' << id[graph.target(it)]  << endl;
    3856  }
     57
     58  cout << id[source] << ' ' << cost[source] << ' ' << color[source] << ' ' << description[source] << endl;
     59  cout << mmap[newedge] << ' ' << id[graph.source(newedge)] << ' ' << id[graph.target(newedge)]  << endl;
     60
     61  ofstream output("copy.lgf");
     62  GraphWriter<SmartGraph> writer(output, graph);
     63 
     64  DescriptorMap<SmartGraph, SmartGraph::Node, SmartGraph::NodeIt, SmartGraph::NodeMap<int> > node_ids(graph);
     65 
     66  writer.writeNodeMap("id", node_ids);
     67  writer.writeNodeMap<QuotedStringWriter>("format", description);
     68
     69  DescriptorMap<SmartGraph, SmartGraph::Edge, SmartGraph::EdgeIt, SmartGraph::EdgeMap<int> > edge_ids(graph);
     70
     71  writer.writeEdgeMap("id", edge_ids);
     72  writer.writeEdgeMap("chars", mmap);
     73 
     74  writer.writeNode("source", node_ids.inverse()[3]);
     75  writer.writeEdge("elek", edge_ids.inverse()[6]);
     76  writer.write();
     77 
    3978  return 0;
    4079}
  • src/work/deba/graph_reader.h

    r1036 r1037  
    2525#include <vector>
    2626
     27#include <memory>
     28
    2729#include <lemon/error.h>
    2830
     
    4951  };
    5052
    51   class StreamException : public IOException {
     53  template <typename _Exception>
     54  class StreamException : public _Exception {
    5255  public:
    53     virtual int line() = 0;
     56    typedef _Exception Exception;
     57    StreamException(int _line, Exception _exception)
     58      : line_num(_line), Exception(_exception) {}
     59    virtual int line() const {
     60      return line_num;
     61    }
     62    virtual std::string what() const {
     63      ostringstream os;
     64      os << Exception::what() << " in line " << line();
     65      return os.str();
     66    }
    5467  private:
    55     IOException* exception;
    5668    int line_num;
    5769  }; 
     
    8597      value.clear();
    8698      is >> ws;
    87       if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format exception");
     99      if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format");
    88100      while (is.get(c) && c != '\"') {
    89101        if (escaped && c == '\\') {
     
    93105        }
    94106      }
    95       if (!is) throw DataFormatException("Quoted string format exception");
     107      if (!is) throw DataFormatException("Quoted string format");
    96108    }
    97109
     
    172184  template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
    173185  class GraphReader {
    174 
    175186  public:
    176187   
     
    182193    typedef typename ReaderTraits::DefaultReader DefaultReader;
    183194
    184     GraphReader(istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader())
     195    GraphReader(std::istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader())
    185196      : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
    186197
     
    188199    ~GraphReader() {
    189200
    190       for (typename NodeReaders::iterator it = node_readers.begin(); it != node_readers.end(); ++it) {
     201      for (typename NodeMapReaders::iterator it = node_map_readers.begin(); it != node_map_readers.end(); ++it) {
    191202        delete it->second;
    192203      }
    193204
    194       for (typename EdgeReaders::iterator it = edge_readers.begin(); it != edge_readers.end(); ++it) {
     205      for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); it != edge_map_readers.end(); ++it) {
    195206        delete it->second;
    196207      }
    197208
    198209    }
     210
     211    // Node map rules
    199212
    200213    template <typename Map>
     
    205218    template <typename Reader, typename Map>
    206219    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       }
    212       node_readers.insert(make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
     220      if (node_map_readers.find(name) != node_map_readers.end()) {
     221        throw Exception() << "Multiple read rule for node map: " << name;
     222      }
     223      node_map_readers.insert(make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
    213224      return *this;
    214225    }
     
    216227    template <typename Reader>
    217228    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)));
     229      if (node_map_readers.find(name) != node_map_readers.end()) {
     230        throw Exception() << "Multiple read rule for node map: " << name;
     231      }
     232      node_map_readers.insert(make_pair(name, new SkipReader<Node, Reader>(reader)));
    224233      return *this;
    225234    }
     235
     236    // Edge map rules
    226237
    227238    template <typename Map>
     
    233244    template <typename Reader, typename Map>
    234245    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       }
    240       edge_readers.insert(make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
     246      if (edge_map_readers.find(name) != edge_map_readers.end()) {
     247        throw Exception() << "Multiple read rule for edge map: " << name;
     248      }
     249      edge_map_readers.insert(make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
    241250      return *this;
    242251    }
     
    244253    template <typename Reader>
    245254    GraphReader& skipEdgeMap(std::string name, const Reader& reader = Reader()) {
     255      if (edge_map_readers.find(name) != edge_map_readers.end()) {
     256        throw Exception() << "Multiple read rule for edge map: " << name;
     257      }
     258      edge_map_readers.insert(make_pair(name, new SkipReader<Edge, Reader>(reader)));
     259      return *this;
     260    }
     261
     262    // Node rules
     263    GraphReader& readNode(std::string name, Node& node) {
     264      if (node_readers.find(name) != node_readers.end()) {
     265        throw Exception() << "Multiple read rule for node";
     266      }
     267      node_readers.insert(make_pair(name, &node));
     268    }
     269
     270    // Edge rules
     271
     272    GraphReader& readEdge(std::string name, Edge& edge) {
    246273      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;
     274        throw Exception() << "Multiple read rule for edge";
     275      }
     276      edge_readers.insert(make_pair(name, &edge));
    253277    }
    254278
    255279    void read() {
    256280      int line_num = 0;
    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         //      }
     281      std::auto_ptr<InverterBase<Node> > nodeInverter;
     282      std::auto_ptr<InverterBase<Edge> > edgeInverter;
     283      try {
     284        std::string line = readNotEmptyLine(is, line_num);
     285        if (line.find("@nodeset") == 0) {
     286          line = readNodeSet(line_num, nodeInverter);
     287        }
     288        if (line.find("@edgeset") == 0) {
     289          line = readEdgeSet(line_num, edgeInverter, nodeInverter);
     290        }
     291        if (line.find("@nodes") == 0) {
     292          line = readNodes(line_num, nodeInverter);
     293        }
     294        if (line.find("@edges") == 0) {
     295          line = readEdges(line_num, edgeInverter);
     296        }
     297        if (line.find("@end") != 0) {
     298          throw DataFormatException("Invalid control sequence: " + line);
     299        }
     300      } catch (DataFormatException e) {
     301        throw StreamException<DataFormatException>(line_num, e);
     302      }
    270303    }
    271304
     
    273306
    274307    template <typename Item> class InverterBase;
    275     //    template <typename Item> class InverterBase;
    276 
    277     void readNodeSet(int& line_num, InverterBase<Node>* & nodeInverter) {
    278       int n = 0;
    279       std::vector<ReaderBase<Node>*> index;
     308
     309    std::string readNodeSet(int& line_num, auto_ptr<InverterBase<Node> > & nodeInverter) {
     310      std::vector<ReaderBase<Node>* > index;
    280311      {
    281312        std::string line = readNotEmptyLine(is, line_num);   
     
    284315        while (ls >> id) {
    285316          if (id[0] == '#') break;
    286           typename NodeReaders::iterator it = node_readers.find(id);
    287           if (it != node_readers.end()) {
     317          typename NodeMapReaders::iterator it = node_map_readers.find(id);
     318          if (it != node_map_readers.end()) {
    288319            index.push_back(it->second);
     320            node_map_readers.erase(it);
    289321          } else {
    290322            index.push_back(&nodeSkipper);
    291323          }
    292           ++n;
    293         }
    294       }
    295 
    296       nodeInverter = index[0]->getInverter();
     324        }
     325      }
     326
     327      if (index.size() == 0) {
     328        throw DataFormatException("No node map found");
     329      }
     330
     331      nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
    297332      std::string line;
    298333      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
     
    300335        std::istringstream ls(line);
    301336        nodeInverter->read(ls, node);
    302         for (int i = 1; i < n; ++i) {
     337        for (int i = 1; i < index.size(); ++i) {
    303338          index[i]->read(ls, node);
    304339        }
    305340      }
    306     }
    307 
    308     void readEdgeSet(int& line_num, InverterBase<Edge>* & edgeInverter, InverterBase<Node>* & nodeInverter) {
    309       int n = 0;
     341      return line;
     342    }
     343
     344    std::string readEdgeSet(int& line_num,
     345                     auto_ptr<InverterBase<Edge> > & edgeInverter, auto_ptr<InverterBase<Node> > & nodeInverter) {
    310346      std::vector<ReaderBase<Edge>*> index;
    311347      {
     
    315351        while (ls >> id) {
    316352          if (id[0] == '#') break;
    317           typename EdgeReaders::iterator it = edge_readers.find(id);
    318           if (it != edge_readers.end()) {
     353          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
     354          if (it != edge_map_readers.end()) {
    319355            index.push_back(it->second);
     356            edge_map_readers.erase(it);
    320357          } else {
    321358            index.push_back(&edgeSkipper);
    322359          }
    323           ++n;
    324         }
    325       }
    326       edgeInverter = index[0]->getInverter();
     360        }
     361      }
     362
     363      if (index.size() == 0) {
     364        throw DataFormatException("No edge map found");
     365      }
     366
     367      edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
    327368      std::string line;
    328369      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
     
    332373        Edge edge = graph.addEdge(source, target);
    333374        edgeInverter->read(ls, edge);
    334         for (int i = 1; i < n; ++i) {
     375        for (int i = 1; i < index.size(); ++i) {
    335376          index[i]->read(ls, edge);
    336377        }
    337378      }     
     379      return line;
     380    }
     381
     382    std::string readNodes(int& line_num, auto_ptr<InverterBase<Node> >& nodeInverter) {
     383      std::string line;
     384      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
     385        std::istringstream ls(line);
     386        std::string name;
     387        ls >> name;
     388        typename NodeReaders::iterator it = node_readers.find(name);
     389        if (it != node_readers.end()) {
     390          *(it -> second) = nodeInverter->read(ls);
     391        }
     392      }       
     393      return line;
     394    }
     395
     396    std::string readEdges(int& line_num, auto_ptr<InverterBase<Edge> >& edgeInverter) {
     397      std::string line;
     398      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
     399        std::istringstream ls(line);
     400        std::string name;
     401        ls >> name;
     402        typename EdgeReaders::iterator it = edge_readers.find(name);
     403        if (it != edge_readers.end()) {
     404          *(it -> second) = edgeInverter->read(ls);
     405        }
     406      }       
     407      return line;   
    338408    }
    339409
     
    346416        }
    347417      }
    348       throw Exception();
    349     }
     418      throw DataFormatException("End of stream");
     419    }
     420   
     421    // Inverters store and give back the Item from the id,
     422    // and may put the ids into a map.
    350423   
    351424    template <typename _Item>
     
    353426    public:
    354427      typedef _Item Item;
    355       virtual void read(istream&, const Item&) = 0;
    356       virtual Item read(istream&) = 0;
     428      virtual void read(std::istream&, const Item&) = 0;
     429      virtual Item read(std::istream&) = 0;
    357430    };
    358431
     
    373446        : map(_map), reader(_reader) {}
    374447
    375       virtual void read(istream& is, const Item& item) {
     448      virtual void read(std::istream& is, const Item& item) {
    376449        Value value;
    377450        reader.read(is, value);
     
    385458      }
    386459
    387       virtual Item read(istream& is) {
     460      virtual Item read(std::istream& is) {
    388461        Value value;
    389462        reader.read(is, value);
     
    410483        : reader(_reader) {}
    411484
    412       virtual void read(istream& is, const Item& item) {
     485      virtual void read(std::istream& is, const Item& item) {
    413486        Value value;
    414487        reader.read(is, value);
     
    421494      }
    422495
    423       virtual Item read(istream& is) {
     496      virtual Item read(std::istream& is) {
    424497        Value value;
    425498        reader.read(is, value);
     
    435508    };
    436509
     510    // Readers
    437511
    438512    template <typename _Item>   
     
    440514    public:
    441515      typedef _Item Item;
    442       virtual void read(istream& is, const Item& item) = 0;
     516
     517      virtual void read(std::istream& is, const Item& item) = 0;
    443518      virtual InverterBase<_Item>* getInverter() = 0;
    444519    };
     
    459534
    460535
    461       virtual void read(istream& is, const Item& item) {
     536      virtual void read(std::istream& is, const Item& item) {
    462537        Value value;
    463538        reader.read(is, value);
     
    481556      SkipReader(const Reader& _reader) : reader(_reader) {}
    482557
    483       virtual void read(istream& is, const Item& item) {
     558      virtual void read(std::istream& is, const Item& item) {
    484559        Value value;
    485560        reader.read(is, value);
     
    492567
    493568
    494     typedef std::map<std::string, ReaderBase<Node>* > NodeReaders;
     569    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
     570    NodeMapReaders node_map_readers;
     571
     572    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
     573    EdgeMapReaders edge_map_readers;
     574
     575    typedef std::map<std::string, Node*> NodeReaders;
    495576    NodeReaders node_readers;
    496577
    497     typedef std::map<std::string, ReaderBase<Edge>* > EdgeReaders;
     578    typedef std::map<std::string, Edge*> EdgeReaders;
    498579    EdgeReaders edge_readers;
    499580
  • src/work/deba/map_utils.h

    r1032 r1037  
    3636  template <
    3737    typename _Graph,
    38     typename _Map,
    39     template <typename, typename> class _InvMap = std::Map
     38    typename _Map
    4039  >
    4140  class InversableMap : protected _Map {
    4241
    4342  public:
     43    typedef _Graph Graph;
    4444
    45     typename _Map Map;
    46     typename _InvMap<Map::Value, Map::Key> InverseMap;
     45    typedef _Map Map;
     46    typedef typename _Map::Key Key;
     47    typedef typename _Map::Value Value;
     48    typedef std::map<Value, Key> InverseMap;
    4749   
    48     typename _Map::Key Key;
    49     typename _Map::Value Value;
    50     typename _Map::ConstReference ConstReference;
     50    typedef typename _Map::ConstReference ConstReference;
    5151
    5252    /// Constructor.
     
    6161    void set(const Key& key, const Value& val) {
    6262      Value oldval = Map::operator[](key);
    63       InverseMap::iterator it = invMap.find(oldval);
    64       if (it != invMap.end() && it->second == key) {
    65         invMap.erase(it);
     63      typename InverseMap::iterator it = inv_map.find(oldval);
     64      if (it != inv_map.end() && it->second == key) {
     65        inv_map.erase(it);
    6666      }     
    67       invMap.insert(make_pair(val, key));
     67      inv_map.insert(make_pair(val, key));
    6868      Map::set(key, val);
    6969    }
     
    7979    virtual void erase(const Key&) {
    8080      Value val = Map::operator[](key);
    81       InverseMap::iterator it = invMap.find(val);
    82       if (it != invMap.end() && it->second == key) {
     81      typename InverseMap::iterator it = inv_map.find(val);
     82      if (it != inv_map.end() && it->second == key) {
    8383        invMap.erase(it);
    8484      }
     
    8787
    8888    const InverseMap& inverse() const {
    89       return invMap;
     89      return inv_map;
    9090    }
    9191
    9292
    9393  private:
    94     InverseMap invMap;   
     94    InverseMap inv_map;   
    9595  };
     96
     97
     98  // unique, continous, mutable
     99
     100  template <
     101    typename _Graph,   
     102    typename _Item,
     103    typename _ItemIt,
     104    typename _Map
     105  >
     106  class DescriptorMap : protected _Map {
     107  public:
     108    typedef _Graph Graph;
     109    typedef _Item Item;
     110    typedef _ItemIt ItemIt;
     111    typedef _Map Map;
     112
     113
     114    typedef typename _Map::Key Key;
     115    typedef typename _Map::Value Value;
     116
     117    typedef vector<Item> InverseMap;
     118
     119    DescriptorMap(const Graph& _graph) : Map(_graph) {
     120      build();
     121    }
     122
     123    virtual void add(const Item& item) {
     124      Map::add(item);
     125      Map::set(item, inv_map.size());
     126      inv_map.push_back(item);
     127    }
     128
     129    virtual void erase(const Item& item) {
     130      Map::set(inv_map.back(), Map::operator[](item));
     131      inv_map[Map::operator[](item)] = inv_map.back();
     132      Map::erase(item);
     133    }
     134
     135    virtual void build() {
     136      Map::build();
     137      for (ItemIt it(*Map::getGraph()); it != INVALID; ++it) {
     138        Map::set(it, inv_map.size());
     139        inv_map.push_back(it); 
     140      }     
     141    }
     142   
     143    virtual void clear() {
     144      inv_map.clear();
     145      Map::clear();
     146    }
     147
     148    int operator[](const Item& item) const {
     149      return Map::operator[](item);
     150    }
     151
     152   
     153    const InverseMap inverse() const {
     154      return inv_map;
     155    }
     156
     157  private:
     158    vector<Item> inv_map;
     159  };
     160
     161  // unique, immutable => IDMap
     162 
     163 
    96164
    97165}
  • src/work/deba/test.lgf

    r1036 r1037  
    20203       4       2       92      "A -> B \t: 10a"        c
    21212       3       6       92      "A -> B \t: 10d"        d
    22 9       5       9       49      "A -> B \t: 10c"        e
     226       5       9       49      "A -> B \t: 10c"        e
    232310      4       3       40      "A -> B \t: 10v"        f
    24241       3       8       84      "A -> B \t: 10g"        g
     25  #
     26 # kajla
    25276       7       4       83      "A -> B \t: 10h"        h
    26288       9       7       37      "A -> B \t: 10j"        i
Note: See TracChangeset for help on using the changeset viewer.