Changeset 1037:3eaff8d04171 in lemon-0.x for src/work

Timestamp:

12/15/04 20:56:55 (20 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:

• graph_io_test.cc (modified) (3 diffs)
• graph_reader.h (modified) (27 diffs)
• graph_writer.h (added)
• map_utils.h (modified) (4 diffs)
• test.lgf (modified) (1 diff)

src/work/deba/graph_io_test.cc

@@ -1 +1 @@
 #include <lemon/smart_graph.h>
+
+#include "map_utils.h"
+
+
 #include "graph_reader.h"
+#include "graph_writer.h"
 
 #include <iostream>
@@ -12 +17 @@
   SmartGraph graph;
   GraphReader<SmartGraph> reader(input, graph);
+
   SmartGraph::NodeMap<int> id(graph);
   reader.readNodeMap("id", id);
+
   SmartGraph::NodeMap<int> cost(graph);
   reader.readNodeMap("cost", cost);
+ 
   SmartGraph::NodeMap<string> color(graph);
   reader.readNodeMap("color", color);
+
   SmartGraph::NodeMap<string> description(graph);
   reader.readNodeMap<QuotedStringReader>("description", description);
+
   SmartGraph::EdgeMap<char> mmap(graph);
   reader.readEdgeMap("mmap", mmap);
+
   reader.skipEdgeMap<QuotedStringReader>("description");
+
+  SmartGraph::Node source;
+  reader.readNode("source", source);
+  
+  SmartGraph::Edge newedge;
+  reader.readEdge("newedge", newedge);
+
   try {
     reader.read();
@@ -37 +55 @@
     cout << mmap[it] << ' ' << id[graph.source(it)] << ' ' << id[graph.target(it)]  << endl;
   }
+
+  cout << id[source] << ' ' << cost[source] << ' ' << color[source] << ' ' << description[source] << endl;
+  cout << mmap[newedge] << ' ' << id[graph.source(newedge)] << ' ' << id[graph.target(newedge)]  << endl;
+
+  ofstream output("copy.lgf");
+  GraphWriter<SmartGraph> writer(output, graph);
+  
+  DescriptorMap<SmartGraph, SmartGraph::Node, SmartGraph::NodeIt, SmartGraph::NodeMap<int> > node_ids(graph);
+  
+  writer.writeNodeMap("id", node_ids);
+  writer.writeNodeMap<QuotedStringWriter>("format", description);
+
+  DescriptorMap<SmartGraph, SmartGraph::Edge, SmartGraph::EdgeIt, SmartGraph::EdgeMap<int> > edge_ids(graph);
+
+  writer.writeEdgeMap("id", edge_ids);
+  writer.writeEdgeMap("chars", mmap);
+  
+  writer.writeNode("source", node_ids.inverse()[3]);
+  writer.writeEdge("elek", edge_ids.inverse()[6]);
+  writer.write();
+  
   return 0;
 }

src/work/deba/graph_reader.h

@@ -25 +25 @@
 #include <vector>
 
+#include <memory>
+
 #include <lemon/error.h>
 
@@ -49 +51 @@
   };
 
-  class StreamException : public IOException {
+  template <typename _Exception>
+  class StreamException : public _Exception {
   public:
-    virtual int line() = 0;
+    typedef _Exception Exception;
+    StreamException(int _line, Exception _exception) 
+      : line_num(_line), Exception(_exception) {}
+    virtual int line() const {
+      return line_num;
+    }
+    virtual std::string what() const {
+      ostringstream os;
+      os << Exception::what() << " in line " << line();
+      return os.str();
+    }
   private:
-    IOException* exception;
     int line_num;
   };  
@@ -85 +97 @@
       value.clear();
       is >> ws;
-      if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format exception");
+      if (!is.get(c) || c != '\"') throw DataFormatException("Quoted string format");
       while (is.get(c) && c != '\"') {
         if (escaped && c == '\\') {
@@ -93 +105 @@
         }
       }
-      if (!is) throw DataFormatException("Quoted string format exception");
+      if (!is) throw DataFormatException("Quoted string format");
     }
 
@@ -172 +184 @@
   template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits> 
   class GraphReader {
-
   public:
     
@@ -182 +193 @@
     typedef typename ReaderTraits::DefaultReader DefaultReader;
 
-    GraphReader(istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader()) 
+    GraphReader(std::istream& _is, Graph& _graph, const DefaultReader& _reader = DefaultReader()) 
       : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
 
@@ -188 +199 @@
     ~GraphReader() {
 
-      for (typename NodeReaders::iterator it = node_readers.begin(); it != node_readers.end(); ++it) {
+      for (typename NodeMapReaders::iterator it = node_map_readers.begin(); it != node_map_readers.end(); ++it) {
         delete it->second;
       }
 
-      for (typename EdgeReaders::iterator it = edge_readers.begin(); it != edge_readers.end(); ++it) {
+      for (typename EdgeMapReaders::iterator it = edge_map_readers.begin(); it != edge_map_readers.end(); ++it) {
         delete it->second;
       }
 
     }
+
+    // Node map rules
 
     template <typename Map>
@@ -205 +218 @@
     template <typename Reader, typename Map>
     GraphReader& readNodeMap(std::string name, Map& map, const Reader& reader = Reader()) {
-      if (node_readers.find(name) != node_readers.end()) {
-        Exception e;
-        e << "Multiple read rule for node map: " << name;
-        throw e;
-      }
-      node_readers.insert(make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
+      if (node_map_readers.find(name) != node_map_readers.end()) {
+        throw Exception() << "Multiple read rule for node map: " << name;
+      }
+      node_map_readers.insert(make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
       return *this;
     }
@@ -216 +227 @@
     template <typename Reader>
     GraphReader& skipNodeMap(std::string name, const Reader& reader = Reader()) {
-      if (node_readers.find(name) != node_readers.end()) {
-        Exception e;
-        e << "Multiple read rule for node map: " << name;
-        throw e;
-      }
-      node_readers.insert(make_pair(name, new SkipReader<Node, Reader>(reader)));
+      if (node_map_readers.find(name) != node_map_readers.end()) {
+        throw Exception() << "Multiple read rule for node map: " << name;
+      }
+      node_map_readers.insert(make_pair(name, new SkipReader<Node, Reader>(reader)));
       return *this;
     }
+
+    // Edge map rules
 
     template <typename Map>
@@ -233 +244 @@
     template <typename Reader, typename Map>
     GraphReader& readEdgeMap(std::string name, Map& map, const Reader& reader = Reader()) {
-      if (edge_readers.find(name) != edge_readers.end()) {
-        Exception e;
-        e << "Multiple read rule for edge map: " << name;
-        throw e;
-      }
-      edge_readers.insert(make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
+      if (edge_map_readers.find(name) != edge_map_readers.end()) {
+        throw Exception() << "Multiple read rule for edge map: " << name;
+      }
+      edge_map_readers.insert(make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
       return *this;
     }
@@ -244 +253 @@
     template <typename Reader>
     GraphReader& skipEdgeMap(std::string name, const Reader& reader = Reader()) {
+      if (edge_map_readers.find(name) != edge_map_readers.end()) {
+        throw Exception() << "Multiple read rule for edge map: " << name;
+      }
+      edge_map_readers.insert(make_pair(name, new SkipReader<Edge, Reader>(reader)));
+      return *this;
+    }
+
+    // Node rules
+    GraphReader& readNode(std::string name, Node& node) {
+      if (node_readers.find(name) != node_readers.end()) {
+        throw Exception() << "Multiple read rule for node";
+      }
+      node_readers.insert(make_pair(name, &node));
+    }
+
+    // Edge rules
+
+    GraphReader& readEdge(std::string name, Edge& edge) {
       if (edge_readers.find(name) != edge_readers.end()) {
-        Exception e;
-        e << "Multiple read rule for edge map: " << name;
-        throw e;
-      }
-      edge_readers.insert(make_pair(name, new SkipReader<Edge, Reader>(reader)));
-      return *this;
+        throw Exception() << "Multiple read rule for edge";
+      }
+      edge_readers.insert(make_pair(name, &edge));
     }
 
     void read() {
       int line_num = 0;
-      InverterBase<Node>* nodeInverter = 0;
-      InverterBase<Edge>* edgeInverter = 0;
-      // \todo delete the inverters
-      //      try {
-        {
-          std::string line = readNotEmptyLine(is, line_num);
-        }
-        readNodeSet(line_num, nodeInverter);
-        readEdgeSet(line_num, edgeInverter, nodeInverter);
-        //      } catch (...){
-        if (nodeInverter != 0) delete nodeInverter;
-        if (edgeInverter != 0) delete edgeInverter;
-        //      }
+      std::auto_ptr<InverterBase<Node> > nodeInverter;
+      std::auto_ptr<InverterBase<Edge> > edgeInverter;
+      try {
+        std::string line = readNotEmptyLine(is, line_num);
+        if (line.find("@nodeset") == 0) {
+          line = readNodeSet(line_num, nodeInverter);
+        } 
+        if (line.find("@edgeset") == 0) {
+          line = readEdgeSet(line_num, edgeInverter, nodeInverter);
+        }
+        if (line.find("@nodes") == 0) {
+          line = readNodes(line_num, nodeInverter);
+        }
+        if (line.find("@edges") == 0) {
+          line = readEdges(line_num, edgeInverter);
+        }
+        if (line.find("@end") != 0) {
+          throw DataFormatException("Invalid control sequence: " + line);
+        }
+      } catch (DataFormatException e) {
+        throw StreamException<DataFormatException>(line_num, e);
+      }
     }
 
@@ -273 +306 @@
 
     template <typename Item> class InverterBase;
-    //    template <typename Item> class InverterBase;
-
-    void readNodeSet(int& line_num, InverterBase<Node>* & nodeInverter) {
-      int n = 0;
-      std::vector<ReaderBase<Node>*> index;
+
+    std::string readNodeSet(int& line_num, auto_ptr<InverterBase<Node> > & nodeInverter) {
+      std::vector<ReaderBase<Node>* > index;
       {
         std::string line = readNotEmptyLine(is, line_num);    
@@ -284 +315 @@
         while (ls >> id) {
           if (id[0] == '#') break;
-          typename NodeReaders::iterator it = node_readers.find(id);
-          if (it != node_readers.end()) {
+          typename NodeMapReaders::iterator it = node_map_readers.find(id);
+          if (it != node_map_readers.end()) {
             index.push_back(it->second);
+            node_map_readers.erase(it);
           } else {
             index.push_back(&nodeSkipper);
           }
-          ++n;
-        }
-      }
-
-      nodeInverter = index[0]->getInverter();
+        }
+      }
+
+      if (index.size() == 0) {
+        throw DataFormatException("No node map found");
+      }
+
+      nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
       std::string line;
       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
@@ -300 +335 @@
         std::istringstream ls(line);
         nodeInverter->read(ls, node);
-        for (int i = 1; i < n; ++i) {
+        for (int i = 1; i < index.size(); ++i) {
           index[i]->read(ls, node);
         }
       }
-    }
-
-    void readEdgeSet(int& line_num, InverterBase<Edge>* & edgeInverter, InverterBase<Node>* & nodeInverter) {
-      int n = 0;
+      return line;
+    }
+
+    std::string readEdgeSet(int& line_num, 
+                     auto_ptr<InverterBase<Edge> > & edgeInverter, auto_ptr<InverterBase<Node> > & nodeInverter) {
       std::vector<ReaderBase<Edge>*> index;
       {
@@ -315 +351 @@
         while (ls >> id) {
           if (id[0] == '#') break;
-          typename EdgeReaders::iterator it = edge_readers.find(id);
-          if (it != edge_readers.end()) {
+          typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
+          if (it != edge_map_readers.end()) {
             index.push_back(it->second);
+            edge_map_readers.erase(it);
           } else {
             index.push_back(&edgeSkipper);
           }
-          ++n;
-        }
-      }
-      edgeInverter = index[0]->getInverter();
+        }
+      }
+
+      if (index.size() == 0) {
+        throw DataFormatException("No edge map found");
+      }
+
+      edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
       std::string line;
       while (line = readNotEmptyLine(is, line_num), line[0] != '@') {   
@@ -332 +373 @@
         Edge edge = graph.addEdge(source, target);
         edgeInverter->read(ls, edge);
-        for (int i = 1; i < n; ++i) {
+        for (int i = 1; i < index.size(); ++i) {
           index[i]->read(ls, edge);
         }
       }      
+      return line;
+    }
+
+    std::string readNodes(int& line_num, auto_ptr<InverterBase<Node> >& nodeInverter) {
+      std::string line;
+      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
+        std::istringstream ls(line);
+        std::string name;
+        ls >> name;
+        typename NodeReaders::iterator it = node_readers.find(name);
+        if (it != node_readers.end()) {
+          *(it -> second) = nodeInverter->read(ls);
+        } 
+      }        
+      return line;
+    }
+
+    std::string readEdges(int& line_num, auto_ptr<InverterBase<Edge> >& edgeInverter) {
+      std::string line;
+      while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
+        std::istringstream ls(line);
+        std::string name;
+        ls >> name;
+        typename EdgeReaders::iterator it = edge_readers.find(name);
+        if (it != edge_readers.end()) {
+          *(it -> second) = edgeInverter->read(ls);
+        } 
+      }        
+      return line;    
     }
 
@@ -346 +416 @@
         }
       }
-      throw Exception();
-    }
+      throw DataFormatException("End of stream");
+    }
+    
+    // Inverters store and give back the Item from the id,
+    // and may put the ids into a map.
     
     template <typename _Item>
@@ -353 +426 @@
     public:
       typedef _Item Item;
-      virtual void read(istream&, const Item&) = 0;
-      virtual Item read(istream&) = 0;
+      virtual void read(std::istream&, const Item&) = 0;
+      virtual Item read(std::istream&) = 0;
     };
 
@@ -373 +446 @@
         : map(_map), reader(_reader) {}
 
-      virtual void read(istream& is, const Item& item) {
+      virtual void read(std::istream& is, const Item& item) {
         Value value;
         reader.read(is, value);
@@ -385 +458 @@
       }
 
-      virtual Item read(istream& is) {
+      virtual Item read(std::istream& is) {
         Value value;
         reader.read(is, value); 
@@ -410 +483 @@
         : reader(_reader) {}
 
-      virtual void read(istream& is, const Item& item) {
+      virtual void read(std::istream& is, const Item& item) {
         Value value;
         reader.read(is, value);
@@ -421 +494 @@
       }
 
-      virtual Item read(istream& is) {
+      virtual Item read(std::istream& is) {
         Value value;
         reader.read(is, value); 
@@ -435 +508 @@
     };
 
+    // Readers
 
     template <typename _Item>    
@@ -440 +514 @@
     public:
       typedef _Item Item;
-      virtual void read(istream& is, const Item& item) = 0;
+
+      virtual void read(std::istream& is, const Item& item) = 0;
       virtual InverterBase<_Item>* getInverter() = 0;
     };
@@ -459 +534 @@
 
 
-      virtual void read(istream& is, const Item& item) {
+      virtual void read(std::istream& is, const Item& item) {
         Value value;
         reader.read(is, value);
@@ -481 +556 @@
       SkipReader(const Reader& _reader) : reader(_reader) {}
 
-      virtual void read(istream& is, const Item& item) {
+      virtual void read(std::istream& is, const Item& item) {
         Value value;
         reader.read(is, value);
@@ -492 +567 @@
 
 
-    typedef std::map<std::string, ReaderBase<Node>* > NodeReaders;
+    typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
+    NodeMapReaders node_map_readers;
+
+    typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
+    EdgeMapReaders edge_map_readers;
+
+    typedef std::map<std::string, Node*> NodeReaders;
     NodeReaders node_readers;
 
-    typedef std::map<std::string, ReaderBase<Edge>* > EdgeReaders;
+    typedef std::map<std::string, Edge*> EdgeReaders;
     EdgeReaders edge_readers;
 

src/work/deba/map_utils.h

@@ -36 +36 @@
   template <
     typename _Graph, 
-    typename _Map, 
-    template <typename, typename> class _InvMap = std::Map
+    typename _Map
   >
   class InversableMap : protected _Map {
 
   public:
+    typedef _Graph Graph;
 
-    typename _Map Map;
-    typename _InvMap<Map::Value, Map::Key> InverseMap;
+    typedef _Map Map;
+    typedef typename _Map::Key Key;
+    typedef typename _Map::Value Value;
+    typedef std::map<Value, Key> InverseMap;
     
-    typename _Map::Key Key;
-    typename _Map::Value Value;
-    typename _Map::ConstReference ConstReference;
+    typedef typename _Map::ConstReference ConstReference;
 
     /// Constructor.
@@ -61 +61 @@
     void set(const Key& key, const Value& val) {
       Value oldval = Map::operator[](key);
-      InverseMap::iterator it = invMap.find(oldval);
-      if (it != invMap.end() && it->second == key) {
-        invMap.erase(it);
+      typename InverseMap::iterator it = inv_map.find(oldval);
+      if (it != inv_map.end() && it->second == key) {
+        inv_map.erase(it);
       }      
-      invMap.insert(make_pair(val, key));
+      inv_map.insert(make_pair(val, key));
       Map::set(key, val);
     }
@@ -79 +79 @@
     virtual void erase(const Key&) {
       Value val = Map::operator[](key);
-      InverseMap::iterator it = invMap.find(val);
-      if (it != invMap.end() && it->second == key) {
+      typename InverseMap::iterator it = inv_map.find(val);
+      if (it != inv_map.end() && it->second == key) {
         invMap.erase(it);
       }
@@ -87 +87 @@
 
     const InverseMap& inverse() const {
-      return invMap;
+      return inv_map;
     } 
 
 
   private:
-    InverseMap invMap;    
+    InverseMap inv_map;    
   };
+
+
+  // unique, continous, mutable
+
+  template <
+    typename _Graph,   
+    typename _Item,
+    typename _ItemIt,
+    typename _Map
+  >
+  class DescriptorMap : protected _Map {
+  public:
+    typedef _Graph Graph;
+    typedef _Item Item;
+    typedef _ItemIt ItemIt;
+    typedef _Map Map;
+
+
+    typedef typename _Map::Key Key;
+    typedef typename _Map::Value Value;
+
+    typedef vector<Item> InverseMap;
+
+    DescriptorMap(const Graph& _graph) : Map(_graph) {
+      build();
+    }
+
+    virtual void add(const Item& item) {
+      Map::add(item);
+      Map::set(item, inv_map.size());
+      inv_map.push_back(item);
+    }
+
+    virtual void erase(const Item& item) {
+      Map::set(inv_map.back(), Map::operator[](item));
+      inv_map[Map::operator[](item)] = inv_map.back();
+      Map::erase(item);
+    }
+
+    virtual void build() {
+      Map::build();
+      for (ItemIt it(*Map::getGraph()); it != INVALID; ++it) {
+        Map::set(it, inv_map.size());
+        inv_map.push_back(it);  
+      }      
+    }
+    
+    virtual void clear() {
+      inv_map.clear();
+      Map::clear();
+    }
+
+    int operator[](const Item& item) const {
+      return Map::operator[](item);
+    }
+
+    
+    const InverseMap inverse() const {
+      return inv_map;
+    }
+
+  private:
+    vector<Item> inv_map;
+  };
+
+  // unique, immutable => IDMap
+  
+  
 
 }

src/work/deba/test.lgf

@@ -20 +20 @@
 3       4       2       92      "A -> B \t: 10a"        c
 2       3       6       92      "A -> B \t: 10d"        d
-9       5       9       49      "A -> B \t: 10c"        e
+6       5       9       49      "A -> B \t: 10c"        e
 10      4       3       40      "A -> B \t: 10v"        f
 1       3       8       84      "A -> B \t: 10g"        g
+  #
+ # kajla
 6       7       4       83      "A -> B \t: 10h"        h
 8       9       7       37      "A -> B \t: 10j"        i