deba@127: /* -*- C++ -*-
deba@127:  *
deba@127:  * This file is a part of LEMON, a generic C++ optimization library
deba@127:  *
deba@127:  * Copyright (C) 2003-2008
deba@127:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@127:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@127:  *
deba@127:  * Permission to use, modify and distribute this software is granted
deba@127:  * provided that this copyright notice appears in all copies. For
deba@127:  * precise terms see the accompanying LICENSE file.
deba@127:  *
deba@127:  * This software is provided "AS IS" with no warranty of any kind,
deba@127:  * express or implied, and with no claim as to its suitability for any
deba@127:  * purpose.
deba@127:  *
deba@127:  */
deba@127: 
deba@127: ///\ingroup lemon_io
deba@127: ///\file
deba@127: ///\brief Lemon Graph Format reader.
deba@127: 
deba@127: 
deba@127: #ifndef LEMON_LGF_READER_H
deba@127: #define LEMON_LGF_READER_H
deba@127: 
deba@127: #include <iostream>
deba@127: #include <fstream>
deba@127: #include <sstream>
deba@127: 
deba@127: #include <set>
deba@127: #include <map>
deba@127: 
deba@127: #include <lemon/assert.h>
deba@127: #include <lemon/graph_utils.h>
deba@127: 
deba@127: #include <lemon/lgf_writer.h>
deba@127: 
deba@127: #include <lemon/concept_check.h>
deba@127: #include <lemon/concepts/maps.h>
deba@127: 
deba@127: namespace lemon {
deba@127: 
deba@127:   namespace _reader_bits {
deba@127: 
deba@127:     template <typename Value>
deba@127:     struct DefaultConverter {
deba@127:       Value operator()(const std::string& str) {
deba@127: 	std::istringstream is(str);
deba@127: 	Value value;
deba@127: 	is >> value;
deba@127: 
deba@127: 	char c;
deba@127: 	if (is >> std::ws >> c) {
deba@127: 	  throw DataFormatError("Remaining characters in token");
deba@127: 	}
deba@127: 	return value;
deba@127:       }
deba@127:     };
deba@127: 
deba@127:     template <>
deba@127:     struct DefaultConverter<std::string> {
deba@127:       std::string operator()(const std::string& str) {
deba@127: 	return str;
deba@127:       }
deba@127:     };
deba@127: 
deba@127:     template <typename _Item>    
deba@127:     class MapStorageBase {
deba@127:     public:
deba@127:       typedef _Item Item;
deba@127: 
deba@127:     public:
deba@127:       MapStorageBase() {}
deba@127:       virtual ~MapStorageBase() {}
deba@127: 
deba@127:       virtual void set(const Item& item, const std::string& value) = 0;
deba@127: 
deba@127:     };
deba@127: 
deba@127:     template <typename _Item, typename _Map, 
deba@127: 	      typename _Converter = DefaultConverter<typename _Map::Value> >
deba@127:     class MapStorage : public MapStorageBase<_Item> {
deba@127:     public:
deba@127:       typedef _Map Map;
deba@127:       typedef _Converter Converter;
deba@127:       typedef _Item Item;
deba@127:       
deba@127:     private:
deba@127:       Map& _map;
deba@127:       Converter _converter;
deba@127: 
deba@127:     public:
deba@127:       MapStorage(Map& map, const Converter& converter = Converter()) 
deba@127: 	: _map(map), _converter(converter) {}
deba@127:       virtual ~MapStorage() {}
deba@127: 
deba@127:       virtual void set(const Item& item ,const std::string& value) {
deba@127: 	_map.set(item, _converter(value));
deba@127:       }
deba@127:     };
deba@127: 
deba@127:     class ValueStorageBase {
deba@127:     public:
deba@127:       ValueStorageBase() {}
deba@127:       virtual ~ValueStorageBase() {}
deba@127: 
deba@127:       virtual void set(const std::string&) = 0;
deba@127:     };
deba@127: 
deba@127:     template <typename _Value, typename _Converter = DefaultConverter<_Value> >
deba@127:     class ValueStorage : public ValueStorageBase {
deba@127:     public:
deba@127:       typedef _Value Value;
deba@127:       typedef _Converter Converter;
deba@127: 
deba@127:     private:
deba@127:       Value& _value;
deba@127:       Converter _converter;
deba@127: 
deba@127:     public:
deba@127:       ValueStorage(Value& value, const Converter& converter = Converter())
deba@127:  	: _value(value), _converter(converter) {}
deba@127: 
deba@127:       virtual void set(const std::string& value) {
deba@127: 	_value = _converter(value);
deba@127:       }
deba@127:     };
deba@127: 
deba@127:     template <typename Value>
deba@127:     struct MapLookUpConverter {
deba@127:       const std::map<std::string, Value>& _map;
deba@127: 
deba@127:       MapLookUpConverter(const std::map<std::string, Value>& map)
deba@127:         : _map(map) {}
deba@127: 
deba@127:       Value operator()(const std::string& str) {
deba@127:         typename std::map<std::string, Value>::const_iterator it =
deba@127:           _map.find(str);
deba@127:         if (it == _map.end()) {
deba@127:           std::ostringstream msg;
deba@127:           msg << "Item not found: " << str;
deba@127:           throw DataFormatError(msg.str().c_str());
deba@127:         }
deba@127:         return it->second;
deba@127:       }
deba@127:     };
deba@127: 
deba@127:     bool isWhiteSpace(char c) {
deba@127:       return c == ' ' || c == '\t' || c == '\v' || 
deba@127:         c == '\n' || c == '\r' || c == '\f'; 
deba@127:     }
deba@127:     
deba@127:     bool isOct(char c) {
deba@127:       return '0' <= c && c <='7'; 
deba@127:     }
deba@127:     
deba@127:     int valueOct(char c) {
deba@127:       LEMON_ASSERT(isOct(c), "The character is not octal.");
deba@127:       return c - '0';
deba@127:     }
deba@127: 
deba@127:     bool isHex(char c) {
deba@127:       return ('0' <= c && c <= '9') || 
deba@127: 	('a' <= c && c <= 'z') || 
deba@127: 	('A' <= c && c <= 'Z'); 
deba@127:     }
deba@127:     
deba@127:     int valueHex(char c) {
deba@127:       LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
deba@127:       if ('0' <= c && c <= '9') return c - '0';
deba@127:       if ('a' <= c && c <= 'z') return c - 'a' + 10;
deba@127:       return c - 'A' + 10;
deba@127:     }
deba@127: 
deba@127:     bool isIdentifierFirstChar(char c) {
deba@127:       return ('a' <= c && c <= 'z') ||
deba@127: 	('A' <= c && c <= 'Z') || c == '_';
deba@127:     }
deba@127: 
deba@127:     bool isIdentifierChar(char c) {
deba@127:       return isIdentifierFirstChar(c) ||
deba@127: 	('0' <= c && c <= '9');
deba@127:     }
deba@127: 
deba@127:     char readEscape(std::istream& is) {
deba@127:       char c;
deba@127:       if (!is.get(c))
deba@127: 	throw DataFormatError("Escape format error");
deba@127: 
deba@127:       switch (c) {
deba@127:       case '\\':
deba@127: 	return '\\';
deba@127:       case '\"':
deba@127: 	return '\"';
deba@127:       case '\'':
deba@127: 	return '\'';
deba@127:       case '\?':
deba@127: 	return '\?';
deba@127:       case 'a':
deba@127: 	return '\a';
deba@127:       case 'b':
deba@127: 	return '\b';
deba@127:       case 'f':
deba@127: 	return '\f';
deba@127:       case 'n':
deba@127: 	return '\n';
deba@127:       case 'r':
deba@127: 	return '\r';
deba@127:       case 't':
deba@127: 	return '\t';
deba@127:       case 'v':
deba@127: 	return '\v';
deba@127:       case 'x':
deba@127: 	{
deba@127: 	  int code;
deba@127: 	  if (!is.get(c) || !isHex(c)) 
deba@127: 	    throw DataFormatError("Escape format error");
deba@127: 	  else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
deba@127: 	  else code = code * 16 + valueHex(c);
deba@127: 	  return code;
deba@127: 	}
deba@127:       default:
deba@127: 	{
deba@127: 	  int code;
deba@127: 	  if (!isOct(c)) 
deba@127: 	    throw DataFormatError("Escape format error");
deba@127: 	  else if (code = valueOct(c), !is.get(c) || !isOct(c)) 
deba@127: 	    is.putback(c);
deba@127: 	  else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c)) 
deba@127: 	    is.putback(c);
deba@127: 	  else code = code * 8 + valueOct(c);
deba@127: 	  return code;
deba@127: 	}	      
deba@127:       } 
deba@127:     }
deba@127:     
deba@127:     std::istream& readToken(std::istream& is, std::string& str) {
deba@127:       std::ostringstream os;
deba@127: 
deba@127:       char c;
deba@127:       is >> std::ws;
deba@127:       
deba@127:       if (!is.get(c)) 
deba@127: 	return is;
deba@127: 
deba@127:       if (c == '\"') {
deba@127: 	while (is.get(c) && c != '\"') {
deba@127: 	  if (c == '\\') 
deba@127: 	    c = readEscape(is);
deba@127: 	  os << c;
deba@127: 	}
deba@127: 	if (!is) 
deba@127: 	  throw DataFormatError("Quoted format error");
deba@127:       } else {
deba@127: 	is.putback(c);
deba@127: 	while (is.get(c) && !isWhiteSpace(c)) {
deba@127: 	  if (c == '\\') 
deba@127: 	    c = readEscape(is);
deba@127: 	  os << c;
deba@127: 	}
deba@127: 	if (!is) {
deba@127: 	  is.clear();
deba@127: 	} else {
deba@127: 	  is.putback(c);
deba@127: 	}
deba@127:       }
deba@127:       str = os.str();
deba@127:       return is;
deba@127:     }
deba@127: 
deba@127:     std::istream& readIdentifier(std::istream& is, std::string& str) {
deba@127:       std::ostringstream os;
deba@127: 
deba@127:       char c;
deba@127:       is >> std::ws;
deba@127:       
deba@127:       if (!is.get(c))
deba@127: 	return is;
deba@127: 
deba@127:       if (!isIdentifierFirstChar(c))
deba@127: 	throw DataFormatError("Wrong char in identifier");
deba@127:       
deba@127:       os << c;
deba@127:       
deba@127:       while (is.get(c) && !isWhiteSpace(c)) {
deba@127: 	if (!isIdentifierChar(c)) 
deba@127: 	  throw DataFormatError("Wrong char in identifier");	  
deba@127: 	os << c;
deba@127:       }
deba@127:       if (!is) is.clear();
deba@127:      
deba@127:       str = os.str();
deba@127:       return is;
deba@127:     }
deba@127:     
deba@127:   }
deba@127:   
deba@127:   /// \e
deba@127:   template <typename _Digraph>
deba@127:   class DigraphReader {
deba@127:   public:
deba@127: 
deba@127:     typedef _Digraph Digraph;
deba@139:     DIGRAPH_TYPEDEFS(typename Digraph);
deba@127:     
deba@127:   private:
deba@127: 
deba@127: 
deba@127:     std::istream* _is;
deba@127:     bool local_is;
deba@127: 
deba@127:     Digraph& _digraph;
deba@127: 
deba@127:     std::string _nodes_caption;
deba@127:     std::string _arcs_caption;
deba@127:     std::string _attributes_caption;
deba@127: 
deba@127:     typedef std::map<std::string, Node> NodeIndex;
deba@127:     NodeIndex _node_index;
deba@127:     typedef std::map<std::string, Arc> ArcIndex;
deba@127:     ArcIndex _arc_index;
deba@127:     
deba@127:     typedef std::vector<std::pair<std::string, 
deba@127:       _reader_bits::MapStorageBase<Node>*> > NodeMaps;    
deba@127:     NodeMaps _node_maps; 
deba@127: 
deba@127:     typedef std::vector<std::pair<std::string,
deba@127:       _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
deba@127:     ArcMaps _arc_maps;
deba@127: 
deba@127:     typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 
deba@127:       Attributes;
deba@127:     Attributes _attributes;
deba@127: 
deba@127:     bool _use_nodes;
deba@127:     bool _use_arcs;
deba@127: 
deba@127:     int line_num;
deba@127:     std::istringstream line;
deba@127: 
deba@127:   public:
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader(std::istream& is, Digraph& digraph) 
deba@127:       : _is(&is), local_is(false), _digraph(digraph),
deba@127: 	_use_nodes(false), _use_arcs(false) {}
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader(const std::string& fn, Digraph& digraph) 
deba@127:       : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
deba@127:     	_use_nodes(false), _use_arcs(false) {}
deba@127: 
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader(const char* fn, Digraph& digraph) 
deba@127:       : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
deba@127:     	_use_nodes(false), _use_arcs(false) {}
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader(DigraphReader& other) 
deba@127:       : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
deba@127: 	_use_nodes(other._use_nodes), _use_arcs(other._use_arcs) {
deba@127: 
deba@127:       other.is = 0;
deba@127:       other.local_is = false;
deba@127:       
deba@127:       _node_index.swap(other._node_index);
deba@127:       _arc_index.swap(other._arc_index);
deba@127: 
deba@127:       _node_maps.swap(other._node_maps);
deba@127:       _arc_maps.swap(other._arc_maps);
deba@127:       _attributes.swap(other._attributes);
deba@127: 
deba@127:       _nodes_caption = other._nodes_caption;
deba@127:       _arcs_caption = other._arcs_caption;
deba@127:       _attributes_caption = other._attributes_caption;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     ~DigraphReader() {
deba@127:       for (typename NodeMaps::iterator it = _node_maps.begin(); 
deba@127: 	   it != _node_maps.end(); ++it) {
deba@127: 	delete it->second;
deba@127:       }
deba@127: 
deba@127:       for (typename ArcMaps::iterator it = _arc_maps.begin(); 
deba@127: 	   it != _arc_maps.end(); ++it) {
deba@127: 	delete it->second;
deba@127:       }
deba@127: 
deba@127:       for (typename Attributes::iterator it = _attributes.begin(); 
deba@127: 	   it != _attributes.end(); ++it) {
deba@127: 	delete it->second;
deba@127:       }
deba@127: 
deba@127:       if (local_is) {
deba@127: 	delete _is;
deba@127:       }
deba@127: 
deba@127:     }
deba@127: 
deba@127:   private:
deba@127:     
deba@127:     DigraphReader& operator=(const DigraphReader&);
deba@127: 
deba@127:   public:
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map>
deba@127:     DigraphReader& nodeMap(const std::string& caption, Map& map) {
deba@127:       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
deba@127:       _reader_bits::MapStorageBase<Node>* storage = 
deba@127: 	new _reader_bits::MapStorage<Node, Map>(map);
deba@127:       _node_maps.push_back(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map, typename Converter>
deba@127:     DigraphReader& nodeMap(const std::string& caption, Map& map, 
deba@127: 			   const Converter& converter = Converter()) {
deba@127:       checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
deba@127:       _reader_bits::MapStorageBase<Node>* storage = 
deba@127: 	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
deba@127:       _node_maps.push_back(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map>
deba@127:     DigraphReader& arcMap(const std::string& caption, Map& map) {
deba@127:       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
deba@127:       _reader_bits::MapStorageBase<Arc>* storage = 
deba@127: 	new _reader_bits::MapStorage<Arc, Map>(map);
deba@127:       _arc_maps.push_back(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map, typename Converter>
deba@127:     DigraphReader& arcMap(const std::string& caption, Map& map, 
deba@127: 			  const Converter& converter = Converter()) {
deba@127:       checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
deba@127:       _reader_bits::MapStorageBase<Arc>* storage = 
deba@127: 	new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
deba@127:       _arc_maps.push_back(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Value>
deba@127:     DigraphReader& attribute(const std::string& caption, Value& value) {
deba@127:       _reader_bits::ValueStorageBase* storage = 
deba@127: 	new _reader_bits::ValueStorage<Value>(value);
deba@127:       _attributes.insert(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Value, typename Converter>
deba@127:     DigraphReader& attribute(const std::string& caption, Value& value, 
deba@127: 			     const Converter& converter = Converter()) {
deba@127:       _reader_bits::ValueStorageBase* storage = 
deba@127: 	new _reader_bits::ValueStorage<Value, Converter>(value, converter);
deba@127:       _attributes.insert(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader& node(const std::string& caption, Node& node) {
deba@127:       typedef _reader_bits::MapLookUpConverter<Node> Converter;
deba@127:       Converter converter(_node_index);
deba@127:       _reader_bits::ValueStorageBase* storage = 
deba@127: 	new _reader_bits::ValueStorage<Node, Converter>(node, converter);
deba@127:       _attributes.insert(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader& arc(const std::string& caption, Arc& arc) {
deba@127:       typedef _reader_bits::MapLookUpConverter<Arc> Converter;
deba@127:       Converter converter(_arc_index);
deba@127:       _reader_bits::ValueStorageBase* storage = 
deba@127: 	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
deba@127:       _attributes.insert(std::make_pair(caption, storage));
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader& nodes(const std::string& caption) {
deba@127:       _nodes_caption = caption;
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader& arcs(const std::string& caption) {
deba@127:       _arcs_caption = caption;
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     DigraphReader& attributes(const std::string& caption) {
deba@127:       _attributes_caption = caption;
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map>
deba@127:     DigraphReader& useNodes(const Map& map) {
deba@127:       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
deba@127:       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
deba@127:       _use_nodes = true;
deba@127:       _writer_bits::DefaultConverter<typename Map::Value> converter;
deba@127:       for (NodeIt n(_digraph); n != INVALID; ++n) {
deba@127: 	_node_index.insert(std::make_pair(converter(map[n]), n));
deba@127:       }
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map, typename Converter>
deba@127:     DigraphReader& useNodes(const Map& map, 
deba@127: 			    const Converter& converter = Converter()) {
deba@127:       checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
deba@127:       LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 
deba@127:       _use_nodes = true;
deba@127:       for (NodeIt n(_digraph); n != INVALID; ++n) {
deba@127: 	_node_index.insert(std::make_pair(converter(map[n]), n));
deba@127:       }
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map>
deba@127:     DigraphReader& useArcs(const Map& map) {
deba@127:       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
deba@127:       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
deba@127:       _use_arcs = true;
deba@127:       _writer_bits::DefaultConverter<typename Map::Value> converter;
deba@127:       for (ArcIt a(_digraph); a != INVALID; ++a) {
deba@127: 	_arc_index.insert(std::make_pair(converter(map[a]), a));
deba@127:       }
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:     /// \e
deba@127:     template <typename Map, typename Converter>
deba@127:     DigraphReader& useArcs(const Map& map, 
deba@127: 			    const Converter& converter = Converter()) {
deba@127:       checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
deba@127:       LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member"); 
deba@127:       _use_arcs = true;
deba@127:       for (ArcIt a(_digraph); a != INVALID; ++a) {
deba@127: 	_arc_index.insert(std::make_pair(converter(map[a]), a));
deba@127:       }
deba@127:       return *this;
deba@127:     }
deba@127: 
deba@127:   private:
deba@127: 
deba@127:     bool readLine() {
deba@127:       std::string str;
deba@127:       while(++line_num, std::getline(*_is, str)) {
deba@127: 	line.clear(); line.str(str);
deba@127: 	char c;
deba@127: 	if (line >> std::ws >> c && c != '#') {
deba@127: 	  line.putback(c);
deba@127: 	  return true;
deba@127: 	}
deba@127:       }
deba@127:       return false;
deba@127:     }
deba@127: 
deba@127:     bool readSuccess() {
deba@127:       return static_cast<bool>(*_is);
deba@127:     }
deba@127:     
deba@127:     void skipSection() {
deba@127:       char c;
deba@127:       while (readSuccess() && line >> c && c != '@') {
deba@127: 	readLine();
deba@127:       }
deba@127:       line.putback(c);
deba@127:     }
deba@127: 
deba@127:     void readNodes() {
deba@127: 
deba@127:       std::vector<int> map_index(_node_maps.size());
deba@127:       int map_num, label_index;
deba@127: 
deba@127:       if (!readLine()) 
deba@127: 	throw DataFormatError("Cannot find map captions");
deba@127:       
deba@127:       {
deba@127: 	std::map<std::string, int> maps;
deba@127: 	
deba@127: 	std::string map;
deba@127: 	int index = 0;
deba@127: 	while (_reader_bits::readIdentifier(line, map)) {
deba@127: 	  if (maps.find(map) != maps.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Multiple occurence of node map: " << map;
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	  maps.insert(std::make_pair(map, index));
deba@127: 	  ++index;
deba@127: 	}
deba@127: 	
deba@127: 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
deba@127: 	  std::map<std::string, int>::iterator jt = 
deba@127: 	    maps.find(_node_maps[i].first);
deba@127: 	  if (jt == maps.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Map not found in file: " << _node_maps[i].first;
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	  map_index[i] = jt->second;
deba@127: 	}
deba@127: 
deba@127: 	{
deba@127: 	  std::map<std::string, int>::iterator jt = maps.find("label");
deba@127: 	  if (jt == maps.end())
deba@127: 	    throw DataFormatError("Label map not found in file");
deba@127: 	  label_index = jt->second;
deba@127: 	}
deba@127: 	map_num = maps.size();
deba@127:       }
deba@127: 
deba@127:       char c;
deba@127:       while (readLine() && line >> c && c != '@') {
deba@127: 	line.putback(c);
deba@127: 
deba@127: 	std::vector<std::string> tokens(map_num);
deba@127: 	for (int i = 0; i < map_num; ++i) {
deba@127: 	  if (!_reader_bits::readToken(line, tokens[i])) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Column not found (" << i + 1 << ")";
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	}
deba@127: 	if (line >> std::ws >> c)
deba@127: 	  throw DataFormatError("Extra character on the end of line");
deba@127: 	
deba@127: 	Node n;
deba@127: 	if (!_use_nodes) {
deba@127: 	  n = _digraph.addNode();
deba@127: 	  _node_index.insert(std::make_pair(tokens[label_index], n));
deba@127: 	} else {
deba@127: 	  typename std::map<std::string, Node>::iterator it =
deba@127: 	    _node_index.find(tokens[label_index]);
deba@127: 	  if (it == _node_index.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Node with label not found: " << tokens[label_index];
deba@127: 	    throw DataFormatError(msg.str().c_str());	    
deba@127: 	  }
deba@127: 	  n = it->second;
deba@127: 	}
deba@127: 
deba@127: 	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
deba@127: 	  _node_maps[i].second->set(n, tokens[map_index[i]]);
deba@127: 	}
deba@127: 
deba@127:       }
deba@127:       if (readSuccess()) {
deba@127: 	line.putback(c);
deba@127:       }
deba@127:     }
deba@127: 
deba@127:     void readArcs() {
deba@127: 
deba@127:       std::vector<int> map_index(_arc_maps.size());
deba@127:       int map_num, label_index;
deba@127: 
deba@127:       if (!readLine()) 
deba@127: 	throw DataFormatError("Cannot find map captions");
deba@127:       
deba@127:       {
deba@127: 	std::map<std::string, int> maps;
deba@127: 	
deba@127: 	std::string map;
deba@127: 	int index = 0;
deba@127: 	while (_reader_bits::readIdentifier(line, map)) {
deba@127: 	  if (maps.find(map) != maps.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Multiple occurence of arc map: " << map;
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	  maps.insert(std::make_pair(map, index));
deba@127: 	  ++index;
deba@127: 	}
deba@127: 	
deba@127: 	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
deba@127: 	  std::map<std::string, int>::iterator jt = 
deba@127: 	    maps.find(_arc_maps[i].first);
deba@127: 	  if (jt == maps.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Map not found in file: " << _arc_maps[i].first;
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	  map_index[i] = jt->second;
deba@127: 	}
deba@127: 
deba@127: 	{
deba@127: 	  std::map<std::string, int>::iterator jt = maps.find("label");
deba@127: 	  if (jt == maps.end())
deba@127: 	    throw DataFormatError("Label map not found in file");
deba@127: 	  label_index = jt->second;
deba@127: 	}
deba@127: 	map_num = maps.size();
deba@127:       }
deba@127: 
deba@127:       char c;
deba@127:       while (readLine() && line >> c && c != '@') {
deba@127: 	line.putback(c);
deba@127: 
deba@127: 	std::string source_token;
deba@127: 	std::string target_token;
deba@127: 
deba@127: 	if (!_reader_bits::readToken(line, source_token))
deba@127: 	  throw DataFormatError("Source not found");
deba@127: 
deba@127: 	if (!_reader_bits::readToken(line, target_token))
deba@127: 	  throw DataFormatError("Source not found");
deba@127: 	
deba@127: 	std::vector<std::string> tokens(map_num);
deba@127: 	for (int i = 0; i < map_num; ++i) {
deba@127: 	  if (!_reader_bits::readToken(line, tokens[i])) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Column not found (" << i + 1 << ")";
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	}
deba@127: 	if (line >> std::ws >> c)
deba@127: 	  throw DataFormatError("Extra character on the end of line");
deba@127: 	
deba@127: 	Arc a;
deba@127: 	if (!_use_arcs) {
deba@127: 
deba@127:           typename NodeIndex::iterator it;
deba@127:  
deba@127:           it = _node_index.find(source_token);
deba@127:           if (it == _node_index.end()) {
deba@127:             std::ostringstream msg;
deba@127:             msg << "Item not found: " << source_token;
deba@127:             throw DataFormatError(msg.str().c_str());
deba@127:           }
deba@127:           Node source = it->second;
deba@127: 
deba@127:           it = _node_index.find(target_token);
deba@127:           if (it == _node_index.end()) {       
deba@127:             std::ostringstream msg;            
deba@127:             msg << "Item not found: " << target_token;
deba@127:             throw DataFormatError(msg.str().c_str());
deba@127:           }                                          
deba@127:           Node target = it->second;                            
deba@127: 
deba@127: 	  a = _digraph.addArc(source, target);
deba@127: 	  _arc_index.insert(std::make_pair(tokens[label_index], a));
deba@127: 	} else {
deba@127: 	  typename std::map<std::string, Arc>::iterator it =
deba@127: 	    _arc_index.find(tokens[label_index]);
deba@127: 	  if (it == _arc_index.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Arc with label not found: " << tokens[label_index];
deba@127: 	    throw DataFormatError(msg.str().c_str());	    
deba@127: 	  }
deba@127: 	  a = it->second;
deba@127: 	}
deba@127: 
deba@127: 	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
deba@127: 	  _arc_maps[i].second->set(a, tokens[map_index[i]]);
deba@127: 	}
deba@127: 
deba@127:       }
deba@127:       if (readSuccess()) {
deba@127: 	line.putback(c);
deba@127:       }
deba@127:     }
deba@127: 
deba@127:     void readAttributes() {
deba@127: 
deba@127:       std::set<std::string> read_attr;
deba@127: 
deba@127:       char c;
deba@127:       while (readLine() && line >> c && c != '@') {
deba@127: 	line.putback(c);
deba@127: 	
deba@127: 	std::string attr, token;
deba@127: 	if (!_reader_bits::readIdentifier(line, attr))
deba@127: 	  throw DataFormatError("Attribute name not found");
deba@127: 	if (!_reader_bits::readToken(line, token))
deba@127: 	  throw DataFormatError("Attribute value not found");
deba@127: 	if (line >> c)
deba@127: 	  throw DataFormatError("Extra character on the end of line");	  
deba@127: 
deba@127: 	{
deba@127: 	  std::set<std::string>::iterator it = read_attr.find(attr);
deba@127: 	  if (it != read_attr.end()) {
deba@127: 	    std::ostringstream msg;
deba@127: 	    msg << "Multiple occurence of attribute " << attr;
deba@127: 	    throw DataFormatError(msg.str().c_str());
deba@127: 	  }
deba@127: 	  read_attr.insert(attr);
deba@127: 	}
deba@127: 	
deba@127: 	{
deba@127: 	  typename Attributes::iterator it = _attributes.lower_bound(attr);
deba@127: 	  while (it != _attributes.end() && it->first == attr) {
deba@127: 	    it->second->set(token);
deba@127: 	    ++it;
deba@127: 	  }
deba@127: 	}
deba@127: 
deba@127:       }
deba@127:       if (readSuccess()) {
deba@127: 	line.putback(c);
deba@127:       }
deba@127:       for (typename Attributes::iterator it = _attributes.begin();
deba@127: 	   it != _attributes.end(); ++it) {
deba@127: 	if (read_attr.find(it->first) == read_attr.end()) {
deba@127: 	  std::ostringstream msg;
deba@127: 	  msg << "Attribute not found in file: " << it->first;
deba@127: 	  throw DataFormatError(msg.str().c_str());
deba@127: 	}	
deba@127:       }
deba@127:     }
deba@127: 
deba@127:   public:
deba@127:     
deba@127:     /// \e
deba@127:     void run() {
deba@127:       
deba@127:       LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
deba@127:       
deba@127:       bool nodes_done = false;
deba@127:       bool arcs_done = false;
deba@127:       bool attributes_done = false;
deba@127: 
deba@127:       line_num = 0;      
deba@127:       readLine();
deba@127: 
deba@127:       while (readSuccess()) {
deba@127: 	skipSection();
deba@127: 	try {
deba@127: 	  char c;
deba@127: 	  std::string section, caption;
deba@127: 	  line >> c;
deba@127: 	  _reader_bits::readIdentifier(line, section);
deba@127: 	  _reader_bits::readIdentifier(line, caption);
deba@127: 
deba@127: 	  if (line >> c) 
deba@127: 	    throw DataFormatError("Extra character on the end of line");
deba@127: 
deba@127: 	  if (section == "nodes" && !nodes_done) {
deba@127: 	    if (_nodes_caption.empty() || _nodes_caption == caption) {
deba@127: 	      readNodes();
deba@127: 	      nodes_done = true;
deba@127: 	    }
deba@127: 	  } else if ((section == "arcs" || section == "edges") && 
deba@127: 		     !arcs_done) {
deba@127: 	    if (_arcs_caption.empty() || _arcs_caption == caption) {
deba@127: 	      readArcs();
deba@127: 	      arcs_done = true;
deba@127: 	    }
deba@127: 	  } else if (section == "attributes" && !attributes_done) {
deba@127: 	    if (_attributes_caption.empty() || _attributes_caption == caption) {
deba@127: 	      readAttributes();
deba@127: 	      attributes_done = true;
deba@127: 	    }
deba@127: 	  } else {
deba@127: 	    readLine();
deba@127: 	    skipSection();
deba@127: 	  }
deba@127: 	} catch (DataFormatError& error) {
deba@127: 	  error.line(line_num);
deba@127: 	  throw;
deba@127: 	}	
deba@127:       }
deba@127: 
deba@127:       if (!nodes_done) {
deba@127: 	throw DataFormatError("Section @nodes not found");
deba@127:       }
deba@127: 
deba@127:       if (!arcs_done) {
deba@127: 	throw DataFormatError("Section @arcs not found");
deba@127:       }
deba@127: 
deba@127:       if (!attributes_done && !_attributes.empty()) {
deba@127: 	throw DataFormatError("Section @attributes not found");
deba@127:       }
deba@127: 
deba@127:     }
deba@127:     
deba@127:   };
deba@127: 
deba@127:   template <typename Digraph>
deba@127:   DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
deba@127:     return DigraphReader<Digraph>(is, digraph);
deba@127:   }
deba@127: 
deba@127:   template <typename Digraph>
deba@127:   DigraphReader<Digraph> digraphReader(const std::string& fn, 
deba@127: 				       Digraph& digraph) {
deba@127:     return DigraphReader<Digraph>(fn, digraph);
deba@127:   }
deba@127: 
deba@127:   template <typename Digraph>
deba@127:   DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
deba@127:     return DigraphReader<Digraph>(fn, digraph);
deba@127:   }
deba@127: }
deba@127: 
deba@127: #endif