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

	    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 = 

    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);

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

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

      } else {

	label->sort(arcs);

      }

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

	Arc a = arcs[i];

	_writer_bits::writeToken(*_os, _node_index.

				 find(_digraph.source(a))->second);

	*_os << '\t';

	_writer_bits::writeToken(*_os, _node_index.

				 find(_digraph.target(a))->second);

	*_os << '\t';

	if (label == 0) {

	  std::ostringstream os;

	  os << _digraph.id(a);

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

	  *_os << '\t';

	  _arc_index.insert(std::make_pair(a, os.str()));

	}

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

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

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

	  _writer_bits::writeToken(*_os, value);

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

	    _arc_index.insert(std::make_pair(a, value));

	  }

	  *_os << '\t';

	}

	*_os << std::endl;

      }

    }

    void createArcIndex() {

      _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;

	}

      }

      if (label == 0) {

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

	  std::ostringstream os;

	  os << _digraph.id(a);

	  _arc_index.insert(std::make_pair(a, os.str()));	  

	}	

      } else {

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

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

	  _arc_index.insert(std::make_pair(a, value));

	}

      }

    }

    void writeAttributes() {

      if (_attributes.empty()) return;

      *_os << "@attributes";

      if (!_attributes_caption.empty()) {

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

      }

      *_os << std::endl;

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

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

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

	_writer_bits::writeToken(*_os, it->second->get());

	*_os << std::endl;

      }

    }

  public:

    /// \name Execution of the writer    

    /// @{

    /// \brief Start the batch processing

    ///

    /// This function starts the batch processing.

    void run() {

      if (!_skip_nodes) {

	writeNodes();

      } else {

	createNodeIndex();

      }

      if (!_skip_arcs) {      

	writeArcs();

      } else {

	createArcIndex();

      }

      writeAttributes();

    }

    /// \brief Give back the stream of the writer

    ///

    /// Give back the stream of the writer.

    std::ostream& ostream() {

      return *_os;

    }

    /// @}

  };

  /// \brief Return a \ref DigraphWriter class

  /// 

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

  /// \relates DigraphWriter

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(std::ostream& os, 

				       const Digraph& digraph) {

    DigraphWriter<Digraph> tmp(os, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphWriter class

  /// 

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

  /// \relates DigraphWriter

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const std::string& fn, 

				       const Digraph& digraph) {

    DigraphWriter<Digraph> tmp(fn, digraph);

    return tmp;

  }

  /// \brief Return a \ref DigraphWriter class

  /// 

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

  /// \relates DigraphWriter

  template <typename Digraph>

  DigraphWriter<Digraph> digraphWriter(const char* fn, 

				       const Digraph& digraph) {

    DigraphWriter<Digraph> tmp(fn, digraph);

    return tmp;

  }

  template <typename Graph>

  class GraphWriter;

  template <typename Graph>

  GraphWriter<Graph> graphWriter(std::ostream& os, const Graph& graph);    

  template <typename Graph>

  GraphWriter<Graph> graphWriter(const std::string& fn, const Graph& graph);   

  template <typename Graph>

  GraphWriter<Graph> graphWriter(const char *fn, const Graph& graph);    

  /// \ingroup lemon_io

  ///  

  /// \brief \ref lgf-format "LGF" writer for directed graphs

  ///

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

  ///

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

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

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

  template <typename _Graph>

  class GraphWriter {

  public:

    typedef _Graph Graph;

    TEMPLATE_GRAPH_TYPEDEFS(Graph);

  private:

    std::ostream* _os;

    bool local_os;

    Graph& _graph;

    std::string _nodes_caption;

    std::string _edges_caption;

    std::string _attributes_caption;

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

    NodeIndex _node_index;

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

    EdgeIndex _edge_index;

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

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

    NodeMaps _node_maps; 

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

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

    EdgeMaps _edge_maps;

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

      _writer_bits::ValueStorageBase*> > Attributes;

    Attributes _attributes;

    bool _skip_nodes;

    bool _skip_edges;

  public:

    /// \brief Constructor

    ///

    /// Construct a directed graph writer, which writes to the given

    /// output stream.

    GraphWriter(std::ostream& is, const Graph& graph) 

      : _os(&is), local_os(false), _graph(graph),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph writer, which writes to the given

    /// output file.

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

      : _os(new std::ofstream(fn.c_str())), local_os(true), _graph(graph),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Constructor

    ///

    /// Construct a directed graph writer, which writes to the given

    /// output file.

    GraphWriter(const char* fn, const Graph& graph) 

      : _os(new std::ofstream(fn)), local_os(true), _graph(graph),

	_skip_nodes(false), _skip_edges(false) {}

    /// \brief Destructor

    ~GraphWriter() {

      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_os) {

	delete _os;

      }

    }

  private:

    friend GraphWriter<Graph> graphWriter<>(std::ostream& os, 

					    const Graph& graph);    

    friend GraphWriter<Graph> graphWriter<>(const std::string& fn, 

					    const Graph& graph);   

    friend GraphWriter<Graph> graphWriter<>(const char *fn, 

					    const Graph& graph);    

    GraphWriter(GraphWriter& other) 

      : _os(other._os), local_os(other.local_os), _graph(other._graph),

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

      other._os = 0;

      other.local_os = 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;

    }

    GraphWriter& operator=(const GraphWriter&);

  public:

    /// \name Writing rules

    /// @{

    /// \brief Node map writing rule

    ///

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

    template <typename Map>

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

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

      _writer_bits::MapStorageBase<Node>* storage = 

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

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

      return *this;

    }

    /// \brief Node map writing rule

    ///

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

    /// writer.

    template <typename Map, typename Converter>

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

			   const Converter& converter = Converter()) {

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

      _writer_bits::MapStorageBase<Node>* storage = 

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

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

      return *this;

    }

    /// \brief Edge map writing rule

    ///

    /// Add an edge map writing rule to the writer.

    template <typename Map>

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

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

      _writer_bits::MapStorageBase<Edge>* storage = 

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

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

      return *this;

    }

    /// \brief Edge map writing rule

    ///

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

    /// writer.

    template <typename Map, typename Converter>

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

			  const Converter& converter = Converter()) {

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

      _writer_bits::MapStorageBase<Edge>* storage = 

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

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

      return *this;

    }

    /// \brief Arc map writing rule

    ///

    /// Add an arc map writing rule to the writer.

    template <typename Map>

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

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

      _writer_bits::MapStorageBase<Edge>* forward_storage = 

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

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

      _writer_bits::MapStorageBase<Edge>* backward_storage = 

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

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

      return *this;

    }

    /// \brief Arc map writing rule

    ///

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