src/lemon/graph_reader.h
author athos
Wed, 23 Mar 2005 11:51:40 +0000
changeset 1247 60708e1475ae
parent 1208 f486d30e4e7b
child 1250 30f540067a80
permissions -rw-r--r--
Completions.
     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 
    35 namespace 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& 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