RhodeCode

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

namespace lemon {

/*!

\page lgf-format Lemon Graph Format (LGF)

The \e LGF is a <em>column oriented</em>

file format for storing graphs and associated data like

node and edge maps.

Each line with \c '#' first non-whitespace

character is considered as a comment line.

Otherwise the file consists of sections starting with

a header line. The header lines starts with an \c '@' character followed by the

type of section. The standard section types are \c \@nodes, \c

\@arcs and \c \@edges

and \@attributes. Each header line may also have an optional

\e name, which can be use to distinguish the sections of the same

type.

The standard sections are column oriented, each line consists of

<em>token</em>s separated by whitespaces. A token can be \e plain or

\e quoted. A plain token is just a sequence of non-whitespace characters,

while a quoted token is a

character sequence surrounded by double quotes, and it can also

contain whitespaces and escape sequences. 

The \c \@nodes section describes a set of nodes and associated

maps. The first is a header line, its columns are the names of the

maps appearing in the following lines.

One of the maps must be called \c

"label", which plays special role in the file.

The following

non-empty lines until the next section describes nodes of the

graph. Each line contains the values of the node maps

associated to the current node.

\code

 @nodes

 label   coordinates size    title

 1       (10,20)     10      "First node"

 2       (80,80)     8       "Second node"

 3       (40,10)     10      "Third node"

\endcode

The \c \@arcs section is very similar to the \c \@nodes section,

it again starts with a header line describing the names of the maps,

but the \c "label" map is not obligatory here. The following lines

describe the arcs. The first two tokens of each line are

the source and the target node of the arc, respectively, then come the map

values. The source and target tokens must be node labels.

\code

 @arcs

 	      capacity

 1   2   16

 1   3   12

 2   3   18

\endcode

The \c \@attributes section contains key-value pairs, each line

\code

 @attributes

 source 1

 target 3

 caption "LEMON test digraph"

\endcode

The \e LGF can contain extra sections, but there is no restriction on

the format of such sections.

*/

}

//  LocalWords:  whitespace whitespaces

	if (readSuccess() && line) line.putback(c);

	if (!_node_maps.empty()) 

	  throw DataFormatError("Cannot find map names");

	return;

      }

      line.putback(c);

      {

	std::map<std::string, int> maps;

	std::string map;

	int index = 0;

	while (_reader_bits::readToken(line, map)) {

	  if (maps.find(map) != maps.end()) {

	    std::ostringstream msg;

	    msg << "Multiple occurence of node map: " << map;

	    throw DataFormatError(msg.str().c_str());

	  }

	  maps.insert(std::make_pair(map, index));

	  ++index;

	}

	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {

	  std::map<std::string, int>::iterator jt = 

	    maps.find(_node_maps[i].first);

	  if (jt == maps.end()) {

	    std::ostringstream msg;

	    msg << "Map not found in file: " << _node_maps[i].first;

	    throw DataFormatError(msg.str().c_str());

	  }

	  map_index[i] = jt->second;

	}

	{

	  std::map<std::string, int>::iterator jt = maps.find("label");

	  if (jt != maps.end()) {

	    label_index = jt->second;

	  } else {

	    label_index = -1;

	  }

	}

	map_num = maps.size();

      }

      while (readLine() && line >> c && c != '@') {

	line.putback(c);

	std::vector<std::string> tokens(map_num);

	for (int i = 0; i < map_num; ++i) {

	  if (!_reader_bits::readToken(line, tokens[i])) {

	    std::ostringstream msg;

	    msg << "Column not found (" << i + 1 << ")";

	    throw DataFormatError(msg.str().c_str());

	  }

	}

	if (line >> std::ws >> c)

	  throw DataFormatError("Extra character on the end of line");

	Node n;

	if (!_use_nodes) {

	  n = _digraph.addNode();

	  if (label_index != -1)

	    _node_index.insert(std::make_pair(tokens[label_index], n));

	} else {

	  if (label_index == -1) 

	    throw DataFormatError("Label map not found in file");

	  typename std::map<std::string, Node>::iterator it =

	    _node_index.find(tokens[label_index]);

	  if (it == _node_index.end()) {

	    std::ostringstream msg;

	    msg << "Node with label not found: " << tokens[label_index];

	    throw DataFormatError(msg.str().c_str());	    

	  }

	  n = it->second;

	}

	for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {

	  _node_maps[i].second->set(n, tokens[map_index[i]]);

	}

      }

      if (readSuccess()) {

	line.putback(c);

      }

    }

    void readArcs() {

      std::vector<int> map_index(_arc_maps.size());

      int map_num, label_index;

      char c;

      if (!readLine() || !(line >> c) || c == '@') {

	if (readSuccess() && line) line.putback(c);

	if (!_arc_maps.empty()) 

	  throw DataFormatError("Cannot find map names");

	return;

      }

      line.putback(c);

      {

	std::map<std::string, int> maps;

	std::string map;

	int index = 0;

	while (_reader_bits::readToken(line, map)) {

	  if (maps.find(map) != maps.end()) {

	    std::ostringstream msg;

	    msg << "Multiple occurence of arc map: " << map;

	    throw DataFormatError(msg.str().c_str());

	  }

	  maps.insert(std::make_pair(map, index));

	  ++index;

	}

	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {

	  std::map<std::string, int>::iterator jt = 

	    maps.find(_arc_maps[i].first);

	  if (jt == maps.end()) {

	    std::ostringstream msg;

	    msg << "Map not found in file: " << _arc_maps[i].first;

	    throw DataFormatError(msg.str().c_str());

	  }

	  map_index[i] = jt->second;

	}

	{

	  std::map<std::string, int>::iterator jt = maps.find("label");

	  if (jt != maps.end()) {

	    label_index = jt->second;

	  } else {

	    label_index = -1;

	  }

	}

	map_num = maps.size();

      }

      while (readLine() && line >> c && c != '@') {

	line.putback(c);

	std::string source_token;

	std::string target_token;

	if (!_reader_bits::readToken(line, source_token))

	  throw DataFormatError("Source not found");

	if (!_reader_bits::readToken(line, target_token))

	  throw DataFormatError("Target not found");

	std::vector<std::string> tokens(map_num);

	for (int i = 0; i < map_num; ++i) {

	  if (!_reader_bits::readToken(line, tokens[i])) {

	    std::ostringstream msg;

	    msg << "Column not found (" << i + 1 << ")";

	    throw DataFormatError(msg.str().c_str());

	  }

	}

	if (line >> std::ws >> c)

	  throw DataFormatError("Extra character on the end of line");

	Arc a;

	if (!_use_arcs) {

          typename NodeIndex::iterator it;

          it = _node_index.find(source_token);

          if (it == _node_index.end()) {

            std::ostringstream msg;

            msg << "Item not found: " << source_token;

            throw DataFormatError(msg.str().c_str());

          }

          Node source = it->second;

          it = _node_index.find(target_token);

          if (it == _node_index.end()) {       

            std::ostringstream msg;            

            msg << "Item not found: " << target_token;

            throw DataFormatError(msg.str().c_str());

          }                                          

          Node target = it->second;                            

	  a = _digraph.addArc(source, target);

	  if (label_index != -1) 

	    _arc_index.insert(std::make_pair(tokens[label_index], a));

	} else {

	  if (label_index == -1) 

	    throw DataFormatError("Label map not found in file");

	  typename std::map<std::string, Arc>::iterator it =

	    _arc_index.find(tokens[label_index]);

	  if (it == _arc_index.end()) {

	    std::ostringstream msg;

	    msg << "Arc with label not found: " << tokens[label_index];

	    throw DataFormatError(msg.str().c_str());	    

	  }

	  a = it->second;

	}

	for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {

	  _arc_maps[i].second->set(a, tokens[map_index[i]]);

	}

      }

      if (readSuccess()) {

	line.putback(c);

      }

    }

    void readAttributes() {

      std::set<std::string> read_attr;

      char c;

      while (readLine() && line >> c && c != '@') {

	line.putback(c);

	std::string attr, token;

	if (!_reader_bits::readToken(line, attr))

	  throw DataFormatError("Attribute name not found");

	if (!_reader_bits::readToken(line, token))

	  throw DataFormatError("Attribute value not found");

	if (line >> c)

	  throw DataFormatError("Extra character on the end of line");	  

	{

	  std::set<std::string>::iterator it = read_attr.find(attr);

	  if (it != read_attr.end()) {

	    std::ostringstream msg;

	    msg << "Multiple occurence of attribute " << attr;

	    throw DataFormatError(msg.str().c_str());

	  }

	  read_attr.insert(attr);

	}

	{

	  typename Attributes::iterator it = _attributes.lower_bound(attr);

	  while (it != _attributes.end() && it->first == attr) {

	    it->second->set(token);

	    ++it;

	  }

	}

      }

      if (readSuccess()) {

	line.putback(c);

      }

      for (typename Attributes::iterator it = _attributes.begin();

	   it != _attributes.end(); ++it) {

	if (read_attr.find(it->first) == read_attr.end()) {

	  std::ostringstream msg;

	  msg << "Attribute not found in file: " << it->first;

	  throw DataFormatError(msg.str().c_str());

	}	

      }

    }

  public:

    /// \name Execution of the reader    

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing

    void run() {

      LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");

      if (!*_is) {

	throw DataFormatError("Cannot find file");

      }

      bool nodes_done = _skip_nodes;

      bool arcs_done = _skip_arcs;

      bool attributes_done = false;

      line_num = 0;      

      readLine();

      skipSection();

      while (readSuccess()) {

	try {

	  char c;

	  std::string section, caption;

	  line >> c;

	  _reader_bits::readToken(line, section);

	  _reader_bits::readToken(line, caption);

	  if (line >> c) 

	    throw DataFormatError("Extra character on the end of line");

	  if (section == "nodes" && !nodes_done) {

	    if (_nodes_caption.empty() || _nodes_caption == caption) {

	      readNodes();

	      nodes_done = true;

	    }

	  } else if ((section == "arcs" || section == "edges") && 

		     !arcs_done) {

	    if (_arcs_caption.empty() || _arcs_caption == caption) {

	      readArcs();

	      arcs_done = true;

	    }

	  } else if (section == "attributes" && !attributes_done) {

	    if (_attributes_caption.empty() || _attributes_caption == caption) {

	      readAttributes();

	      attributes_done = true;

	    }

	  } else {

	    readLine();

	    skipSection();

	  }

	} catch (DataFormatError& error) {

	  error.line(line_num);

	  throw;

	}	

      }

      if (!nodes_done) {

	throw DataFormatError("Section @nodes not found");

      }

      if (!arcs_done) {

	throw DataFormatError("Section @arcs not found");

      }

      if (!attributes_done && !_attributes.empty()) {

	throw DataFormatError("Section @attributes not found");

      }

    }

    /// @}

  };

  /// \brief Return a \ref DigraphReader class

  /// 

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {

    DigraphReader<Digraph> tmp(is, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  /// 

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const std::string& fn, 

				       Digraph& digraph) {

    DigraphReader<Digraph> tmp(fn, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphReader class

  /// 

  /// This function just returns a \ref DigraphReader class.

  /// \relates DigraphReader

  template <typename Digraph>

  DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {

    DigraphReader<Digraph> tmp(fn, digraph);

    return tmp;

  }

  template <typename Graph>

  class GraphReader;

  template <typename Graph>

  GraphReader<Graph> graphReader(std::istream& is, Graph& graph);    

  template <typename Graph>

  GraphReader<Graph> graphReader(const std::string& fn, Graph& graph);   

  template <typename Graph>

  GraphReader<Graph> graphReader(const char *fn, Graph& graph);    

  /// \ingroup lemon_io

  ///  

  /// \brief \ref lgf-format "LGF" reader for undirected graphs

  ///

  /// This utility reads an \ref lgf-format "LGF" file.

  ///

  /// It can be used almost the same way as \c DigraphReader.

  /// The only difference is that this class can handle edges and

  /// edge maps as well as arcs and arc maps.

  template <typename _Graph>

  class GraphReader {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    std::istream* _is;

    bool local_is;

    Graph& _graph;

    std::string _nodes_caption;

    std::string _edges_caption;

    std::string _attributes_caption;

    typedef std::map<std::string, Node> NodeIndex;

    NodeIndex _node_index;

    typedef std::map<std::string, Edge> EdgeIndex;

    EdgeIndex _edge_index;

    typedef std::vector<std::pair<std::string, 

      _reader_bits::MapStorageBase<Node>*> > NodeMaps;    

    NodeMaps _node_maps; 

    typedef std::vector<std::pair<std::string,

      _reader_bits::MapStorageBase<Edge>*> > EdgeMaps;

    EdgeMaps _edge_maps;

    typedef std::multimap<std::string, _reader_bits::ValueStorageBase*> 

      Attributes;

    Attributes _attributes;

    bool _use_nodes;

    bool _use_edges;

    bool _skip_nodes;

    bool _skip_edges;

    int line_num;

    std::istringstream line;

  public:

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// input stream.

    GraphReader(std::istream& is, Graph& graph) 

      : _is(&is), local_is(false), _graph(graph),

	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// file.

    GraphReader(const std::string& fn, Graph& graph) 

      : _is(new std::ifstream(fn.c_str())), local_is(true), _graph(graph),

    	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct an undirected graph reader, which reads from the given

    /// file.

    GraphReader(const char* fn, Graph& graph) 

      : _is(new std::ifstream(fn)), local_is(true), _graph(graph),

    	_use_nodes(false), _use_edges(false),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Destructor

    ~GraphReader() {

      for (typename NodeMaps::iterator it = _node_maps.begin(); 

	   it != _node_maps.end(); ++it) {

	delete it->second;

      }

      for (typename EdgeMaps::iterator it = _edge_maps.begin(); 

	   it != _edge_maps.end(); ++it) {

	delete it->second;

      }

      for (typename Attributes::iterator it = _attributes.begin(); 

	   it != _attributes.end(); ++it) {

	delete it->second;

      }

      if (local_is) {

	delete _is;

      }

    }

  private:

    friend GraphReader<Graph> graphReader<>(std::istream& is, Graph& graph);    

    friend GraphReader<Graph> graphReader<>(const std::string& fn, 

					    Graph& graph);   

    friend GraphReader<Graph> graphReader<>(const char *fn, Graph& graph);    

    GraphReader(GraphReader& other) 

      : _is(other._is), local_is(other.local_is), _graph(other._graph),

	_use_nodes(other._use_nodes), _use_edges(other._use_edges),

	_skip_nodes(other._skip_nodes), _skip_edges(other._skip_edges) {

      other._is = 0;

      other.local_is = false;

      _node_index.swap(other._node_index);

      _edge_index.swap(other._edge_index);

      _node_maps.swap(other._node_maps);

      _edge_maps.swap(other._edge_maps);

      _attributes.swap(other._attributes);

      _nodes_caption = other._nodes_caption;

      _edges_caption = other._edges_caption;

      _attributes_caption = other._attributes_caption;

    }

    GraphReader& operator=(const GraphReader&);

  public:

    /// \name Reading rules

    /// @{

    /// \brief Node map reading rule

    ///

    /// Add a node map reading rule to the reader.

    template <typename Map>

    GraphReader& nodeMap(const std::string& caption, Map& map) {

      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();

      _reader_bits::MapStorageBase<Node>* storage = 

	new _reader_bits::MapStorage<Node, Map>(map);

      _node_maps.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Node map reading rule

    ///

    /// Add a node map reading rule with specialized converter to the

    /// reader.

    template <typename Map, typename Converter>

    GraphReader& nodeMap(const std::string& caption, Map& map, 

			   const Converter& converter = Converter()) {

      checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();

      _reader_bits::MapStorageBase<Node>* storage = 

	new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);

      _node_maps.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Edge map reading rule

    ///

    /// Add an edge map reading rule to the reader.

    template <typename Map>

    GraphReader& edgeMap(const std::string& caption, Map& map) {

      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();

      _reader_bits::MapStorageBase<Edge>* storage = 

	new _reader_bits::MapStorage<Edge, Map>(map);

      _edge_maps.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Edge map reading rule

    ///

    /// Add an edge map reading rule with specialized converter to the

    /// reader.

    template <typename Map, typename Converter>

    GraphReader& edgeMap(const std::string& caption, Map& map, 

			  const Converter& converter = Converter()) {

      checkConcept<concepts::WriteMap<Edge, typename Map::Value>, Map>();

      _reader_bits::MapStorageBase<Edge>* storage = 

	new _reader_bits::MapStorage<Edge, Map, Converter>(map, converter);

      _edge_maps.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Arc map reading rule

    ///

    /// Add an arc map reading rule to the reader.

    template <typename Map>

    GraphReader& arcMap(const std::string& caption, Map& map) {

      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();

      _reader_bits::MapStorageBase<Edge>* forward_storage = 

	new _reader_bits::GraphArcMapStorage<Graph, true, Map>(_graph, map);

      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));

      _reader_bits::MapStorageBase<Edge>* backward_storage = 

	new _reader_bits::GraphArcMapStorage<Graph, false, Map>(_graph, map);

      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));

      return *this;

    }

    /// \brief Arc map reading rule

    ///

    /// Add an arc map reading rule with specialized converter to the

    /// reader.

    template <typename Map, typename Converter>

    GraphReader& arcMap(const std::string& caption, Map& map, 

			  const Converter& converter = Converter()) {

      checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();

      _reader_bits::MapStorageBase<Edge>* forward_storage = 

	new _reader_bits::GraphArcMapStorage<Graph, true, Map, Converter>

	(_graph, map, converter);

      _edge_maps.push_back(std::make_pair('+' + caption, forward_storage));

      _reader_bits::MapStorageBase<Edge>* backward_storage = 

	new _reader_bits::GraphArcMapStorage<Graph, false, Map, Converter>

	(_graph, map, converter);

      _edge_maps.push_back(std::make_pair('-' + caption, backward_storage));

      return *this;

    }

    /// \brief Attribute reading rule

    ///

    /// Add an attribute reading rule to the reader.

    template <typename Value>

    GraphReader& attribute(const std::string& caption, Value& value) {

      _reader_bits::ValueStorageBase* storage = 

	new _reader_bits::ValueStorage<Value>(value);

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Attribute reading rule

    ///

    /// Add an attribute reading rule with specialized converter to the

    /// reader.

    template <typename Value, typename Converter>

    GraphReader& attribute(const std::string& caption, Value& value, 

			     const Converter& converter = Converter()) {

      _reader_bits::ValueStorageBase* storage = 

	new _reader_bits::ValueStorage<Value, Converter>(value, converter);

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Node reading rule

    ///

    /// Add a node reading rule to reader.

    GraphReader& node(const std::string& caption, Node& node) {

      typedef _reader_bits::MapLookUpConverter<Node> Converter;

      Converter converter(_node_index);

      _reader_bits::ValueStorageBase* storage = 

	new _reader_bits::ValueStorage<Node, Converter>(node, converter);

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Edge reading rule

    ///

    /// Add an edge reading rule to reader.

    GraphReader& edge(const std::string& caption, Edge& edge) {

      typedef _reader_bits::MapLookUpConverter<Edge> Converter;

      Converter converter(_edge_index);

      _reader_bits::ValueStorageBase* storage = 

	new _reader_bits::ValueStorage<Edge, Converter>(edge, converter);

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Arc reading rule

    ///

    /// Add an arc reading rule to reader.

    GraphReader& arc(const std::string& caption, Arc& arc) {

      typedef _reader_bits::GraphArcLookUpConverter<Graph> Converter;

      Converter converter(_graph, _edge_index);

      _reader_bits::ValueStorageBase* storage = 

	new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);

      _attributes.insert(std::make_pair(caption, storage));

      return *this;

    }

    /// @}

    /// \name Select section by name

    /// @{

    /// \brief Set \c \@nodes section to be read

    ///

    /// Set \c \@nodes section to be read.

    GraphReader& nodes(const std::string& caption) {

      _nodes_caption = caption;

      return *this;

    }

    /// \brief Set \c \@edges section to be read

    ///

    /// Set \c \@edges section to be read.

    GraphReader& edges(const std::string& caption) {

      _edges_caption = caption;

      return *this;

    }

    /// \brief Set \c \@attributes section to be read

    ///

    /// Set \c \@attributes section to be read.

    GraphReader& attributes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// @}

    /// \name Using previously constructed node or edge set

    /// @{

    /// \brief Use previously constructed node set

    ///

    /// Use previously constructed node set, and specify the node

    /// label map.

    template <typename Map>

    GraphReader& useNodes(const Map& map) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 

      _use_nodes = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (NodeIt n(_graph); n != INVALID; ++n) {

	_node_index.insert(std::make_pair(converter(map[n]), n));

      }

      return *this;

    }

    /// \brief Use previously constructed node set

    ///

    /// Use previously constructed node set, and specify the node

    /// label map and a functor which converts the label map values to

    /// \c std::string.

    template <typename Map, typename Converter>

    GraphReader& useNodes(const Map& map, 

			    const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member"); 

      _use_nodes = true;

      for (NodeIt n(_graph); n != INVALID; ++n) {

	_node_index.insert(std::make_pair(converter(map[n]), n));

      }

      return *this;

    }

    /// \brief Use previously constructed edge set

    ///

    /// Use previously constructed edge set, and specify the edge

    /// label map.

    template <typename Map>

    GraphReader& useEdges(const Map& map) {

      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member");

      _use_edges = true;

      _writer_bits::DefaultConverter<typename Map::Value> converter;

      for (EdgeIt a(_graph); a != INVALID; ++a) {

	_edge_index.insert(std::make_pair(converter(map[a]), a));

      }

      return *this;

    }

    /// \brief Use previously constructed edge set

    ///

    /// Use previously constructed edge set, and specify the edge

    /// label map and a functor which converts the label map values to

    /// \c std::string.

    template <typename Map, typename Converter>

    GraphReader& useEdges(const Map& map, 

			    const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Edge, typename Map::Value>, Map>();

      LEMON_ASSERT(!_use_edges, "Multiple usage of useEdges() member"); 

      _use_edges = true;

      for (EdgeIt a(_graph); a != INVALID; ++a) {

	_edge_index.insert(std::make_pair(converter(map[a]), a));

      }

      return *this;

    }

    /// \brief Skip the reading of node section

    ///

    /// Omit the reading of the node section. This implies that each node

    /// map reading rule will be abandoned, and the nodes of the graph

    /// will not be constructed, which usually cause that the edge set

    /// could not be read due to lack of node name

    /// could not be read due to lack of node name resolving.

    /// Therefore \c skipEdges() function should also be used, or

			  const Converter& converter = Converter()) {

      checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();

      _writer_bits::MapStorageBase<Arc>* storage = 

	new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);

      _arc_maps.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Attribute writing rule

    ///

    /// Add an attribute writing rule to the writer.

    template <typename Value>

    DigraphWriter& attribute(const std::string& caption, const Value& value) {

      _writer_bits::ValueStorageBase* storage = 

	new _writer_bits::ValueStorage<Value>(value);

      _attributes.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Attribute writing rule

    ///

    /// Add an attribute writing rule with specialized converter to the

    /// writer.

    template <typename Value, typename Converter>

    DigraphWriter& attribute(const std::string& caption, const Value& value, 

			     const Converter& converter = Converter()) {

      _writer_bits::ValueStorageBase* storage = 

	new _writer_bits::ValueStorage<Value, Converter>(value, converter);

      _attributes.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Node writing rule

    ///

    /// Add a node writing rule to the writer.

    DigraphWriter& node(const std::string& caption, const Node& node) {

      typedef _writer_bits::MapLookUpConverter<Node> Converter;

      Converter converter(_node_index);

      _writer_bits::ValueStorageBase* storage = 

	new _writer_bits::ValueStorage<Node, Converter>(node, converter);

      _attributes.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \brief Arc writing rule

    ///

    /// Add an arc writing rule to writer.

    DigraphWriter& arc(const std::string& caption, const Arc& arc) {

      typedef _writer_bits::MapLookUpConverter<Arc> Converter;

      Converter converter(_arc_index);

      _writer_bits::ValueStorageBase* storage = 

	new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);

      _attributes.push_back(std::make_pair(caption, storage));

      return *this;

    }

    /// \name Section captions

    /// @{

    /// \brief Add an additional caption to the \c \@nodes section

    ///

    /// Add an additional caption to the \c \@nodes section.

    DigraphWriter& nodes(const std::string& caption) {

      _nodes_caption = caption;

      return *this;

    }

    /// \brief Add an additional caption to the \c \@arcs section

    ///

    /// Add an additional caption to the \c \@arcs section.

    DigraphWriter& arcs(const std::string& caption) {

      _arcs_caption = caption;

      return *this;

    }

    /// \brief Add an additional caption to the \c \@attributes section

    ///

    /// Add an additional caption to the \c \@attributes section.

    DigraphWriter& attributes(const std::string& caption) {

      _attributes_caption = caption;

      return *this;

    }

    /// \name Skipping section

    /// @{

    /// \brief Skip writing the node set

    ///

    /// The \c \@nodes section will not be written to the stream.

    DigraphWriter& skipNodes() {

      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");

      _skip_nodes = true;

      return *this;

    }

    /// \brief Skip writing arc set

    ///

    /// The \c \@arcs section will not be written to the stream.

    DigraphWriter& skipArcs() {

      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");

      _skip_arcs = true;

      return *this;

    }

    /// @}

  private:

    void writeNodes() {

      _writer_bits::MapStorageBase<Node>* label = 0;

      for (typename NodeMaps::iterator it = _node_maps.begin();

	   it != _node_maps.end(); ++it) {

        if (it->first == "label") {

	  label = it->second;

	  break;

	}

      }

      *_os << "@nodes";

      if (!_nodes_caption.empty()) {

	_writer_bits::writeToken(*_os << ' ', _nodes_caption);

      }

      *_os << std::endl;

      if (label == 0) {

	*_os << "label" << '\t';

      }

      for (typename NodeMaps::iterator it = _node_maps.begin();

	   it != _node_maps.end(); ++it) {

	_writer_bits::writeToken(*_os, it->first) << '\t';

      }

      *_os << std::endl;

      std::vector<Node> nodes;

      for (NodeIt n(_digraph); n != INVALID; ++n) {

	nodes.push_back(n);

      }

      if (label == 0) {

	IdMap<Digraph, Node> id_map(_digraph);

	_writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);

	std::sort(nodes.begin(), nodes.end(), id_less);

      } else {

	label->sort(nodes);

      }

      for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {

	Node n = nodes[i];

	if (label == 0) {

	  std::ostringstream os;

	  os << _digraph.id(n);

	  _writer_bits::writeToken(*_os, os.str());

	  *_os << '\t';

	  _node_index.insert(std::make_pair(n, os.str()));

	}

	for (typename NodeMaps::iterator it = _node_maps.begin();

	     it != _node_maps.end(); ++it) {

	  std::string value = it->second->get(n);

	  _writer_bits::writeToken(*_os, value);

	  if (it->first == "label") {

	    _node_index.insert(std::make_pair(n, value));

	  }

	  *_os << '\t';

	}

	*_os << std::endl;

      }

    }

    void createNodeIndex() {

      _writer_bits::MapStorageBase<Node>* label = 0;

      for (typename NodeMaps::iterator it = _node_maps.begin();

	   it != _node_maps.end(); ++it) {

        if (it->first == "label") {

	  label = it->second;

	  break;

	}

      }

      if (label == 0) {

	for (NodeIt n(_digraph); n != INVALID; ++n) {

	  std::ostringstream os;

	  os << _digraph.id(n);

	  _node_index.insert(std::make_pair(n, os.str()));	  

	}	

      } else {

	for (NodeIt n(_digraph); n != INVALID; ++n) {

	  std::string value = label->get(n);	  

	  _node_index.insert(std::make_pair(n, value));

	}

      }

    }

    void writeArcs() {

      _writer_bits::MapStorageBase<Arc>* label = 0;

      for (typename ArcMaps::iterator it = _arc_maps.begin();

	   it != _arc_maps.end(); ++it) {

        if (it->first == "label") {

	  label = it->second;

	  break;

	}

      }

      *_os << "@arcs";

      if (!_arcs_caption.empty()) {

	_writer_bits::writeToken(*_os << ' ', _arcs_caption);

      }

      *_os << std::endl;

      *_os << '\t' << '\t';

      if (label == 0) {

	*_os << "label" << '\t';

      }

      for (typename ArcMaps::iterator it = _arc_maps.begin();

	   it != _arc_maps.end(); ++it) {

	_writer_bits::writeToken(*_os, it->first) << '\t';

      }

      *_os << std::endl;

      std::vector<Arc> arcs;

      for (ArcIt n(_digraph); n != INVALID; ++n) {

	arcs.push_back(n);

      }

      if (label == 0) {

	IdMap<Digraph, Arc> id_map(_digraph);