/* -*- C++ -*-

  * lemon/lemon_writer.h - Part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2005 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.

  *

  */

 ///\ingroup io_group

 ///\file

 ///\brief Lemon Format writer.

 #ifndef LEMON_LEMON_WRITER_H

 #define LEMON_LEMON_WRITER_H

 #include <iostream>

 #include <fstream>

 #include <string>

 #include <vector>

 #include <algorithm>

 #include <map>

 #include <memory>

 #include <lemon/error.h>

 #include <lemon/invalid.h>

 #include <lemon/graph_utils.h>

 #include <lemon/bits/item_writer.h>

 #include <lemon/utility.h>

 #include <lemon/maps.h>

 #include <lemon/xy.h>

 #include <lemon/concept_check.h>

 #include <lemon/concept/maps.h>

 namespace lemon {

   namespace _writer_bits {

     template <typename Item>

     class ItemIdWriter {

     public:

       bool isIdWriter() { return true; }

       void writeId(std::ostream&, const Item&) {}

       template <class _ItemIdWriter>

       struct Constraints {

 	void constraints() {

 	  bool b = writer.isIdWriter();

 	  ignore_unused_variable_warning(b);

 	  writer.writeId(os, item);

 	}

 	_ItemIdWriter& writer;

 	std::ostream& os;

 	const Item& item;

       };

     };

     template <typename Item>

     class ItemWriter {

     public:

       void write(std::ostream&, const Item&) {}

       template <class _ItemWriter>

       struct Constraints {

 	void constraints() {

 	  writer.write(os, item);

 	}

 	_ItemWriter& writer;

 	std::ostream& os;

 	const Item& item;

       };

     };

     template <typename Map>

     struct Ref { typedef const Map& Type; };

     template <typename Graph, typename Map>

     class ForwardComposeMap {

     public:

       typedef typename Graph::UndirEdge Key;

       typedef typename Map::Value Value;

       ForwardComposeMap(const Graph& _graph, const Map& _map) 

 	: graph(_graph), map(_map) {}

       Value operator[](const Key& key) {

 	return map[graph.direct(key, false)];

       }

     private:

       typename Ref<Map>::Type map;

       const Graph& graph;

     };

     template <typename Graph, typename Map>

     ForwardComposeMap<Graph, Map>

     forwardComposeMap(const Graph& graph, const Map& map) {

       return ForwardComposeMap<Graph, Map>(graph, map);

     }

     template <typename Graph, typename Map>

     class BackwardComposeMap {

     public:

       typedef typename Graph::UndirEdge Key;

       typedef typename Map::Value Value;

       BackwardComposeMap(const Graph& _graph, const Map& _map) 

 	: graph(_graph), map(_map) {}

       Value operator[](const Key& key) {

 	return map[graph.direct(key, false)];

       }

     private:

       typename Ref<Map>::Type map;

       const Graph& graph;

     };

     template <typename Graph, typename Map>

     BackwardComposeMap<Graph, Map>

     backwardComposeMap(const Graph& graph, const Map& map) {

       return BackwardComposeMap<Graph, Map>(graph, map);

     }

     template <typename Graph, typename Map>

     struct Ref<ForwardComposeMap<Graph, Map> > { 

       typedef ForwardComposeMap<Graph, Map> Type;

     };

     template <typename Graph, typename Map>

     struct Ref<BackwardComposeMap<Graph, Map> > { 

       typedef BackwardComposeMap<Graph, Map> Type; 

     };

     template <typename Map>

     struct Ref<XMap<Map> > { 

       typedef XMap<Map> Type;

     };

     template <typename Map>

     struct Ref<ConstXMap<Map> > { 

       typedef ConstXMap<Map> Type;

     };

     template <typename Map>

     struct Ref<YMap<Map> > { 

       typedef YMap<Map> Type;

     };

     template <typename Map>

     struct Ref<ConstYMap<Map> > { 

       typedef ConstYMap<Map> Type;

     };

   }

   /// \ingroup io_group

   /// \brief Lemon Format writer class.

   /// 

   /// The Lemon Format contains several sections. We do not want to

   /// determine what sections are in a lemon file we give only a framework

   /// to write a section oriented format.

   ///

   /// In the Lemon Format each section starts with a line contains a \c \@

   /// character on the first not white space position. This line is the

   /// header line of the section. Each next lines belong to this section

   /// while it does not starts with \c \@ character. This line can start a 

   /// new section or if it can close the file with the \c \@end line.

   /// The file format ignore the empty lines and it may contain comments

   /// started with a \c # character to the end of the line. 

   ///

   /// The framework provides an abstract LemonWriter::SectionWriter class

   /// what defines the interface of a SectionWriter. The SectionWriter

   /// has the \c header() member function what gives back the header of the

   /// section. After that it will be called the \c write() member which

   /// should write the content of the section.

   ///

   /// \relates GraphWriter

   /// \relates NodeSetWriter

   /// \relates EdgeSetWriter

   /// \relates NodesWriter

   /// \relates EdgesWriter

   /// \relates AttributeWriter

   class LemonWriter {

   public:

     /// \brief Abstract base class for writing a section.

     ///

     /// This class has an \c header() member function what gives back

     /// the header line of the section. The \c write() member should

     /// write the content of the section to the stream.

     class SectionWriter {

       friend class LemonWriter;

     protected:

       /// \brief Constructor for SectionWriter.

       ///

       /// Constructor for SectionWriter. It attach this writer to

       /// the given LemonWriter.

       SectionWriter(LemonWriter& writer) {

 	writer.attach(*this);

       }

       virtual ~SectionWriter() {}

       /// \brief The header of section.

       ///

       /// It gives back the header of the section.

       virtual std::string header() = 0;

       /// \brief  Writer function of the section.

       ///

       /// Write the content of the section.

       virtual void write(std::ostream& os) = 0;

     };

     /// \brief Constructor for LemonWriter.

     ///

     /// Constructor for LemonWriter which writes to the given stream.

     LemonWriter(std::ostream& _os) 

       : os(&_os), own_os(false) {}

     /// \brief Constructor for LemonWriter.

     ///

     /// Constructor for LemonWriter which writes to the given file.

     LemonWriter(const std::string& filename) 

       : os(0), own_os(true) {

       os = new std::ofstream(filename.c_str());

     }

     /// \brief Desctructor for LemonWriter.

     ///

     /// Desctructor for LemonWriter.

     ~LemonWriter() {

       if (own_os) {

 	delete os;

       }

     }

   private:

     LemonWriter(const LemonWriter&);

     void operator=(const LemonWriter&);

     void attach(SectionWriter& writer) {

       writers.push_back(&writer);

     }

   public:

     /// \brief Executes the LemonWriter.

     /// 

     /// It executes the LemonWriter.

     void run() {

       SectionWriters::iterator it;

       for (it = writers.begin(); it != writers.end(); ++it) {

 	*os << (*it)->header() << std::endl;

 	(*it)->write(*os);

       }

       *os << "@end" << std::endl;

     }

   private:

     std::ostream* os;

     bool own_os;

     typedef std::vector<SectionWriter*> SectionWriters;

     SectionWriters writers;

   };

   /// \brief Helper class for implementing the common SectionWriters.

   ///

   /// Helper class for implementing the common SectionWriters.

   class CommonSectionWriterBase : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter Parent;

   protected:

     /// \brief Constructor for CommonSectionWriterBase.

     ///

     /// Constructor for CommonSectionWriterBase. It attach this writer to

     /// the given LemonWriter.

     CommonSectionWriterBase(LemonWriter& _writer) 

       : Parent(_writer) {}

     template <typename _Item>    

     class WriterBase {

     public:

       typedef _Item Item;

       virtual ~WriterBase() {}

       virtual void write(std::ostream& os, const Item& item) = 0;

     };

     template <typename _Item, typename _Map, typename _Writer>

     class MapWriter : public WriterBase<_Item> {

     public:

       typedef _Map Map;

       typedef _Writer Writer;

       typedef typename Writer::Value Value;

       typedef _Item Item;

       typename _writer_bits::Ref<Map>::Type map;

       Writer writer;

       MapWriter(const Map& _map, const Writer& _writer) 

 	: map(_map), writer(_writer) {}

       virtual ~MapWriter() {}

       virtual void write(std::ostream& os, const Item& item) {

 	Value value = map[item];

 	writer.write(os, value);

       }

     };

     class ValueWriterBase {

     public:

       virtual ~ValueWriterBase() {}

       virtual void write(std::ostream&) = 0;

     };

     template <typename _Value, typename _Writer>

     class ValueWriter : public ValueWriterBase {

     public:

       typedef _Value Value;

       typedef _Writer Writer;

       ValueWriter(const Value& _value, const Writer& _writer)

  	: value(_value), writer(_writer) {}

       virtual void write(std::ostream& os) {

 	writer.write(os, value);

       }

     private:

       const Value& value;

       Writer writer;

     };

     template <typename _Item>

     class IdWriterBase {

     public:

       typedef _Item Item;

       virtual ~IdWriterBase() {}

       virtual void write(std::ostream&, const Item&) const = 0;

       virtual bool isIdWriter() const = 0;

     };

     template <typename _Item, typename _BoxedIdWriter>

     class IdWriter : public IdWriterBase<_Item> {

     public:

       typedef _Item Item;

       typedef _BoxedIdWriter BoxedIdWriter;

       const BoxedIdWriter& idWriter;

       IdWriter(const BoxedIdWriter& _idWriter) 

 	: idWriter(_idWriter) {}

       virtual void write(std::ostream& os, const Item& item) const {

 	idWriter.writeId(os, item);

       }

       virtual bool isIdWriter() const {

 	return idWriter.isIdWriter();

       }

     };

   };

   /// \ingroup io_group

   /// \brief SectionWriter for writing a graph's nodeset.

   ///

   /// The lemon format can store multiple graph nodesets with several maps.

   /// The nodeset section's header line is \c \@nodeset \c nodeset_id, but the

   /// \c nodeset_id may be empty.

   ///

   /// The first line of the section contains the names of the maps separated

   /// with white spaces. Each next lines describes a node in the nodeset, and

   /// contains the mapped values for each map.

   ///

   /// If the nodeset contains an \c "id" named map then it will be regarded

   /// as id map. This map should contain only unique values and when the 

   /// \c writeId() member will be called with a node it will write it's id.

   /// Otherwise if the \c _forceIdMap constructor parameter is true then

   /// the id map will be the id in the graph.

   ///

   /// \relates LemonWriter

   template <typename _Graph, typename _Traits = DefaultWriterTraits>

   class NodeSetWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

   public:

     typedef _Graph Graph;

     typedef _Traits Traits;

     typedef typename Graph::Node Node;

     /// \brief Constructor.

     ///

     /// Constructor for NodeSetWriter. It creates the NodeSetWriter and

     /// attach it into the given LemonWriter. If the \c _forceIdMap

     /// parameter is true then the writer will write own id map when

     /// the user does not give "id" named map.

     NodeSetWriter(LemonWriter& _writer, const Graph& _graph, 

 		  const std::string& _id = std::string(), 

 		  bool _forceIdMap = true) 

       : Parent(_writer), idMap(0), forceIdMap(_forceIdMap), 

 	graph(_graph), id(_id) {}

     /// \brief Destructor.

     ///

     /// Destructor for NodeSetWriter.

     virtual ~NodeSetWriter() {

       typename MapWriters::iterator it;

       for (it = writers.begin(); it != writers.end(); ++it) {

 	delete it->second;

       }

     }

   private:

     NodeSetWriter(const NodeSetWriter&);

     void operator=(const NodeSetWriter&);

   public:

     /// \brief Add a new node map writer command for the writer.

     ///

     /// Add a new node map writer command for the writer.

     template <typename Map>

     NodeSetWriter& writeNodeMap(std::string name, const Map& map) {

       return writeNodeMap<typename Traits::

 	template Writer<typename Map::Value>, Map>(name, map);

     }

     /// \brief Add a new node map writer command for the writer.

     ///

     /// Add a new node map writer command for the writer.

     template <typename Writer, typename Map>

     NodeSetWriter& writeNodeMap(std::string name, const Map& map, 

 			    const Writer& writer = Writer()) {

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

       checkConcept<_writer_bits::ItemWriter<typename Map::Value>, Writer>();

       writers.push_back(

 	make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));

       return *this;

     }

   protected:

     /// \brief The header of the section.

     ///

     /// It gives back the header of the section.

     virtual std::string header() {

       return "@nodeset " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     virtual void write(std::ostream& os) {

       for (int i = 0; i < (int)writers.size(); ++i) {

 	if (writers[i].first == "id") {

 	  idMap = writers[i].second;

 	  forceIdMap = false;

 	  break;

 	}

       }

       if (forceIdMap) {

 	os << "id\t";

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	os << writers[i].first << '\t';

       }

       os << std::endl;

       for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {

 	if (forceIdMap) {

 	  os << graph.id(it) << '\t';

 	}

 	for (int i = 0; i < (int)writers.size(); ++i) {

 	  writers[i].second->write(os, it);

 	  os << '\t';

 	}

 	os << std::endl;

       }

     }

   public:

     /// \brief Returns true if the nodeset can write the ids of the nodes.

     ///

     /// Returns true if the nodeset can write the ids of the nodes.

     /// It is possible only if an "id" named map was written or the 

     /// \c _forceIdMap constructor parameter was true.

     bool isIdWriter() const {

       return idMap != 0 || forceIdMap;

     }

     /// \brief Write the id of the given node.

     ///

     /// It writes the id of the given node. If there was written an "id"

     /// named map then it will write the map value belongs to the node.

     /// Otherwise if the \c forceId parameter was true it will write

     /// its id in the graph. 

     void writeId(std::ostream& os, const Node& item) const {

       if (forceIdMap) {

 	os << graph.id(item);

       } else {

 	idMap->write(os, item);

       }

     }

   private:

     typedef std::vector<std::pair<std::string, WriterBase<Node>*> > MapWriters;

     MapWriters writers;

     WriterBase<Node>* idMap;

     bool forceIdMap;

     const Graph& graph;   

     std::string id;

   };

   /// \ingroup io_group

   /// \brief SectionWriter for writing a graph's edgesets.

   ///

   /// The lemon format can store multiple graph edgesets with several maps. 

   /// The edgeset section's header line is \c \@edgeset \c edgeset_id, but the

   /// \c edgeset_id may be empty.

   ///

   /// The first line of the section contains the names of the maps separated

   /// with white spaces. Each next lines describes a edge in the edgeset. The

   /// line contains the source and the target nodes' id and the mapped 

   /// values for each map.

   ///

   /// If the edgeset contains an \c "id" named map then it will be regarded

   /// as id map. This map should contain only unique values and when the 

   /// \c writeId() member will be called with an edge it will write it's id.

   /// Otherwise if the \c _forceIdMap constructor parameter is true then

   /// the id map will be the id in the graph.

   ///

   /// The edgeset writer needs a node id writer to identify which nodes

   /// have to be connected. If a NodeSetWriter can write the nodes' id,

   /// it will be able to use with this class.

   ///

   /// \relates LemonWriter

   template <typename _Graph, typename _Traits = DefaultWriterTraits>

   class EdgeSetWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

   public:

     typedef _Graph Graph;

     typedef _Traits Traits;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     /// \brief Constructor.

     ///

     /// Constructor for EdgeSetWriter. It creates the EdgeSetWriter and

     /// attach it into the given LemonWriter. It will write node ids by

     /// the \c _nodeIdWriter. If the \c _forceIdMap parameter is true 

     /// then the writer will write own id map if the user does not give 

     /// "id" named map.

     template <typename NodeIdWriter>

     EdgeSetWriter(LemonWriter& _writer, const Graph& _graph, 

 		  const NodeIdWriter& _nodeIdWriter, 

 		  const std::string& _id = std::string(),

 		  bool _forceIdMap = true)

       : Parent(_writer), idMap(0), forceIdMap(_forceIdMap),

 	graph(_graph), id(_id) {

       checkConcept<_writer_bits::ItemIdWriter<Node>, NodeIdWriter>();

       nodeIdWriter.reset(new IdWriter<Node, NodeIdWriter>(_nodeIdWriter));

     } 

     /// \brief Destructor.

     ///

     /// Destructor for EdgeSetWriter.

     virtual ~EdgeSetWriter() {

       typename MapWriters::iterator it;

       for (it = writers.begin(); it != writers.end(); ++it) {

 	delete it->second;

       }

     }

   private:

     EdgeSetWriter(const EdgeSetWriter&);

     void operator=(const EdgeSetWriter&);

   public:

     /// \brief Add a new edge map writer command for the writer.

     ///

     /// Add a new edge map writer command for the writer.

     template <typename Map>

     EdgeSetWriter& writeEdgeMap(std::string name, const Map& map) {

       return writeEdgeMap<typename Traits::

 	template Writer<typename Map::Value>, Map>(name, map);

     }

     /// \brief Add a new edge map writer command for the writer.

     ///

     /// Add a new edge map writer command for the writer.

     template <typename Writer, typename Map>

     EdgeSetWriter& writeEdgeMap(std::string name, const Map& map, 

 			    const Writer& writer = Writer()) {

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

       checkConcept<_writer_bits::ItemWriter<typename Map::Value>, Writer>();

       writers.push_back(

 	make_pair(name, new MapWriter<Edge, Map, Writer>(map, writer)));

       return *this;

     }

   protected:

     /// \brief The header of the section.

     ///

     /// It gives back the header of the section.

     virtual std::string header() {

       return "@edgeset " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     virtual void write(std::ostream& os) {

       if (!nodeIdWriter->isIdWriter()) {

 	throw DataFormatError("Cannot find nodeset or ID map");

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	if (writers[i].first == "id") {

 	  idMap = writers[i].second;

 	  forceIdMap = false;

 	  break;

 	}

       }

       os << "\t\t";

       if (forceIdMap) {

 	os << "id\t";

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	os << writers[i].first << '\t';

       }

       os << std::endl;

       for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {

 	nodeIdWriter->write(os, graph.source(it));

 	os << '\t';

 	nodeIdWriter->write(os, graph.target(it));

 	os << '\t';

 	if (forceIdMap) {

 	  os << graph.id(it) << '\t';

 	}

 	for (int i = 0; i < (int)writers.size(); ++i) {

 	  writers[i].second->write(os, it);

 	  os << '\t';

 	}

 	os << std::endl;

       }

     }

   public:

     /// \brief Returns true if the edgeset can write the ids of the edges.

     ///

     /// Returns true if the edgeset can write the ids of the edges.

     /// It is possible only if an "id" named map was written or the 

     /// \c _forceIdMap constructor parameter was true.

     bool isIdWriter() const {

       return forceIdMap || idMap != 0;

     }

     /// \brief Write the id of the given edge.

     ///

     /// It writes the id of the given edge. If there was written an "id"

     /// named map then it will write the map value belongs to the edge.

     /// Otherwise if the \c forceId parameter was true it will write

     /// its id in the graph. 

     void writeId(std::ostream& os, const Edge& item) const {

       if (forceIdMap) {

 	os << graph.id(item);

       } else {

 	idMap->write(os, item);

       }

     } 

   private:

     typedef std::vector<std::pair<std::string, WriterBase<Edge>*> > MapWriters;

     MapWriters writers;

     WriterBase<Edge>* idMap;

     bool forceIdMap;

     const Graph& graph;   

     std::string id;

     std::auto_ptr<IdWriterBase<Node> > nodeIdWriter;

   };

   /// \ingroup io_group

   /// \brief SectionWriter for writing a undirected edgeset.

   ///

   /// The lemon format can store multiple undirected edgesets with several 

   /// maps. The undirected edgeset section's header line is \c \@undiredgeset 

   /// \c undiredgeset_id, but the \c undiredgeset_id may be empty.

   ///

   /// The first line of the section contains the names of the maps separated

   /// with white spaces. Each next lines describes an undirected edge in the 

   /// edgeset. The line contains the two connected nodes' id and the mapped 

   /// values for each undirected map.

   ///

   /// The section can handle the directed as a syntactical sugar. Two

   /// undirected edge map describes one directed edge map. This two maps

   /// are the forward map and the backward map and the names of this map

   /// is near the same just with a prefix \c '+' or \c '-' character 

   /// difference.

   ///

   /// If the edgeset contains an \c "id" named map then it will be regarded

   /// as id map. This map should contain only unique values and when the 

   /// \c writeId() member will be called with an undirected edge it will 

   /// write it's id. Otherwise if the \c _forceIdMap constructor parameter

   /// is true then the id map will be the id in the graph.

   ///

   /// The undirected edgeset writer needs a node id writer to identify 

   /// which nodes have to be connected. If a NodeSetWriter can write the 

   /// nodes' id, it will be able to use with this class.

   ///

   /// \relates LemonWriter

   template <typename _Graph, typename _Traits = DefaultWriterTraits>

   class UndirEdgeSetWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

   public:

     typedef _Graph Graph;

     typedef _Traits Traits;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::UndirEdge UndirEdge;

     /// \brief Constructor.

     ///

     /// Constructor for UndirEdgeSetWriter. It creates the UndirEdgeSetWriter

     /// and attach it into the given LemonWriter. It will write node ids by

     /// the \c _nodeIdWriter. If the \c _forceIdMap parameter is true 

     /// then the writer will write own id map if the user does not give 

     /// "id" named map.

     template <typename NodeIdWriter>

     UndirEdgeSetWriter(LemonWriter& _writer, const Graph& _graph, 

 		       const NodeIdWriter& _nodeIdWriter, 

 		       const std::string& _id = std::string(),

 		       bool _forceIdMap = true)

       : Parent(_writer), idMap(0), forceIdMap(_forceIdMap),

 	graph(_graph), id(_id) {

       checkConcept<_writer_bits::ItemIdWriter<Node>, NodeIdWriter>();

       nodeIdWriter.reset(new IdWriter<Node, NodeIdWriter>(_nodeIdWriter));

     } 

     /// \brief Destructor.

     ///

     /// Destructor for UndirEdgeSetWriter.

     virtual ~UndirEdgeSetWriter() {

       typename MapWriters::iterator it;

       for (it = writers.begin(); it != writers.end(); ++it) {

 	delete it->second;

       }

     }

   private:

     UndirEdgeSetWriter(const UndirEdgeSetWriter&);

     void operator=(const UndirEdgeSetWriter&);

   public:

     /// \brief Add a new undirected edge map writer command for the writer.

     ///

     /// Add a new undirected map writer command for the writer.

     template <typename Map>

     UndirEdgeSetWriter& writeUndirEdgeMap(std::string name, const Map& map) {

       return writeUndirEdgeMap<typename Traits::

 	template Writer<typename Map::Value>, Map>(name, map);

     }

     /// \brief Add a new undirected map writer command for the writer.

     ///

     /// Add a new undirected map writer command for the writer.

     template <typename Writer, typename Map>

     UndirEdgeSetWriter& writeUndirEdgeMap(std::string name, const Map& map, 

 					  const Writer& writer = Writer()) {

       checkConcept<concept::ReadMap<UndirEdge, typename Map::Value>, Map>();

       checkConcept<_writer_bits::ItemWriter<typename Map::Value>, Writer>();

       writers.push_back(

 	make_pair(name, new MapWriter<UndirEdge, Map, Writer>(map, writer)));

       return *this;

     }

     /// \brief Add a new directed edge map writer command for the writer.

     ///

     /// Add a new directed map writer command for the writer.

     template <typename Map>

     UndirEdgeSetWriter& writeEdgeMap(std::string name, const Map& map) {

       return writeEdgeMap<typename Traits::

 	template Writer<typename Map::Value>, Map>(name, map);

     }

     /// \brief Add a new directed map writer command for the writer.

     ///

     /// Add a new directed map writer command for the writer.

     template <typename Writer, typename Map>

     UndirEdgeSetWriter& writeEdgeMap(std::string name, const Map& map, 

 				     const Writer& writer = Writer()) {

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

       checkConcept<_writer_bits::ItemWriter<typename Map::Value>, Writer>();

       writeUndirEdge("+" + name, 

 		     _writer_bits::forwardComposeMap(graph, map), writer);

       writeUndirEdge("-" + name, 

 		     _writer_bits::backwardComposeMap(graph, map), writer);

       return *this;

     }

   protected:

     /// \brief The header of the section.

     ///

     /// It gives back the header of the section.

     virtual std::string header() {

       return "@undiredgeset " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     virtual void write(std::ostream& os) {

       if (!nodeIdWriter->isIdWriter()) {

 	throw DataFormatError("Cannot find nodeset or ID map");

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	if (writers[i].first == "id") {

 	  idMap = writers[i].second;

 	  forceIdMap = false;

 	  break;

 	}

       }

       os << "\t\t";

       if (forceIdMap) {

 	os << "id\t";

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	os << writers[i].first << '\t';

       }

       os << std::endl;

       for (typename Graph::UndirEdgeIt it(graph); it != INVALID; ++it) {

 	nodeIdWriter->write(os, graph.source(it));

 	os << '\t';

 	nodeIdWriter->write(os, graph.target(it));

 	os << '\t';

 	if (forceIdMap) {

 	  os << graph.id(it) << '\t';

 	}

 	for (int i = 0; i < (int)writers.size(); ++i) {

 	  writers[i].second->write(os, it);

 	  os << '\t';

 	}

 	os << std::endl;

       }

     }

   public:

     /// \brief Returns true if the undirected edgeset can write the ids of 

     /// the edges.

     ///

     /// Returns true if the undirected edgeset can write the ids of the 

     /// undirected edges. It is possible only if an "id" named map was 

     /// written or the \c _forceIdMap constructor parameter was true.

     bool isIdWriter() const {

       return forceIdMap || idMap != 0;

     }

     /// \brief Write the id of the given undirected edge.

     ///

     /// It writes the id of the given undirected edge. If there was written 

     /// an "id" named map then it will write the map value belongs to the 

     /// undirected edge. Otherwise if the \c forceId parameter was true it 

     /// will write its id in the graph. 

     void writeId(std::ostream& os, const UndirEdge& item) const {

       if (forceIdMap) {

 	os << graph.id(item);

       } else {

 	idMap->write(os, item);

       }

     } 

     /// \brief Write the id of the given edge.

     ///

     /// It writes the id of the given edge. If there was written 

     /// an "id" named map then it will write the map value belongs to the 

     /// edge. Otherwise if the \c forceId parameter was true it 

     /// will write its id in the graph. If the edge is forward map

     /// then its prefix character is \c '+' elsewhere \c '-'.

     void writeId(std::ostream& os, const Edge& item) const {

       if (graph.direction(item)) {

 	os << "+ ";

       } else {

 	os << "- ";

       }

       if (forceIdMap) {

 	os << graph.id(item);

       } else {

 	idMap->write(os, item);

       }

     } 

   private:

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

 				  WriterBase<UndirEdge>*> > MapWriters;

     MapWriters writers;

     WriterBase<UndirEdge>* idMap;

     bool forceIdMap;

     const Graph& graph;   

     std::string id;

     std::auto_ptr<IdWriterBase<Node> > nodeIdWriter;

   };

   /// \ingroup io_group

   /// \brief SectionWriter for writing labeled nodes.

   ///

   /// The nodes section's header line is \c \@nodes \c nodes_id, but the

   /// \c nodes_id may be empty.

   ///

   /// Each line in the section contains the label of the node and 

   /// then the node id. 

   ///

   /// \relates LemonWriter

   template <typename _Graph>

   class NodeWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

     typedef _Graph Graph;

     typedef typename Graph::Node Node;

   public:

     /// \brief Constructor.

     ///

     /// Constructor for NodeWriter. It creates the NodeWriter and

     /// attach it into the given LemonWriter. The given \c _IdWriter

     /// will write the nodes' id what can be a nodeset writer.

     template <typename _IdWriter>

     NodeWriter(LemonWriter& _writer, const _IdWriter& _idWriter, 

 	       const std::string& _id = std::string()) 

       : Parent(_writer), id(_id) {

       checkConcept<_writer_bits::ItemIdWriter<Node>, _IdWriter>();

       idWriter.reset(new IdWriter<Node, _IdWriter>(_idWriter));

     }

     /// \brief Destructor.

     ///

     /// Destructor for NodeWriter.

     virtual ~NodeWriter() {}

   private:

     NodeWriter(const NodeWriter&);

     void operator=(const NodeWriter&);

   public:

     /// \brief Add a node writer command for the NodeWriter.

     ///

     /// Add a node writer command for the NodeWriter.

     void writeNode(const std::string& name, const Node& item) {

       writers.push_back(make_pair(name, &item));

     }

   protected:

     /// \brief Header checking function.

     ///

     /// It gives back true when the header line start with \c \@nodes,

     /// and the header line's id and the writer's id are the same.

     virtual std::string header() {

       return "@nodes " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     virtual void write(std::ostream& os) {

       if (!idWriter->isIdWriter()) {

 	throw DataFormatError("Cannot find nodeset or ID map");

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	os << writers[i].first << ' ';

 	idWriter->write(os, *(writers[i].second));

 	os << std::endl;

       }

     }

   private:

     std::string id;

     typedef std::vector<std::pair<std::string, const Node*> > NodeWriters;

     NodeWriters writers;

     std::auto_ptr<IdWriterBase<Node> > idWriter;

   };

   /// \ingroup io_group

   /// \brief SectionWriter for writing labeled edges.

   ///

   /// The edges section's header line is \c \@edges \c edges_id, but the

   /// \c edges_id may be empty.

   ///

   /// Each line in the section contains the label of the edge and 

   /// then the edge id. 

   ///

   /// \relates LemonWriter

   template <typename _Graph>

   class EdgeWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

     typedef _Graph Graph;

     typedef typename Graph::Edge Edge;

   public:

     /// \brief Constructor.

     ///

     /// Constructor for EdgeWriter. It creates the EdgeWriter and

     /// attach it into the given LemonWriter. The given \c _IdWriter

     /// will write the edges' id what can be a edgeset writer.

     template <typename _IdWriter>

     EdgeWriter(LemonWriter& _writer, const _IdWriter& _idWriter, 

 	       const std::string& _id = std::string()) 

       : Parent(_writer), id(_id) {

       checkConcept<_writer_bits::ItemIdWriter<Edge>, _IdWriter>();

       idWriter.reset(new IdWriter<Edge, _IdWriter>(_idWriter));

     }

     /// \brief Destructor.

     ///

     /// Destructor for EdgeWriter.

     virtual ~EdgeWriter() {}

   private:

     EdgeWriter(const EdgeWriter&);

     void operator=(const EdgeWriter&);

   public:

     /// \brief Add an edge writer command for the EdgeWriter.

     ///

     /// Add an edge writer command for the EdgeWriter.

     void writeEdge(const std::string& name, const Edge& item) {

       writers.push_back(make_pair(name, &item));

     }

   protected:

     /// \brief Header checking function.

     ///

     /// It gives back true when the header line start with \c \@edges,

     /// and the header line's id and the writer's id are the same.

     virtual std::string header() {

       return "@edges " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     virtual void write(std::ostream& os) {

       if (!idWriter->isIdWriter()) {

 	throw DataFormatError("Cannot find edgeset or ID map");

       }

       for (int i = 0; i < (int)writers.size(); ++i) {

 	os << writers[i].first << ' ';

 	idWriter->write(os, *(writers[i].second));

 	os << std::endl;

       }

     }

   private:

     std::string id;

     typedef std::vector<std::pair<std::string, const Edge*> > EdgeWriters;

     EdgeWriters writers;

     std::auto_ptr<IdWriterBase<Edge> > idWriter;

   };

   /// \ingroup io_group

   /// \brief SectionWriter for writing labeled undirected edges.

   ///

   /// The undirected edges section's header line is \c \@undiredges 

   /// \c undiredges_id, but the \c undiredges_id may be empty.

   ///

   /// Each line in the section contains the label of the undirected edge and 

   /// then the undirected edge id. 

   ///

   /// \relates LemonWriter

   template <typename _Graph>

   class UndirEdgeWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

     typedef _Graph Graph;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::UndirEdge UndirEdge;

   public:

     /// \brief Constructor.

     ///

     /// Constructor for UndirEdgeWriter. It creates the UndirEdgeWriter and

     /// attach it into the given LemonWriter. The given \c _IdWriter

     /// will write the undirected edges' id what can be an undirected 

     /// edgeset writer.

     template <typename _IdWriter>

     UndirEdgeWriter(LemonWriter& _writer, const _IdWriter& _idWriter, 

 	       const std::string& _id = std::string()) 

       : Parent(_writer), id(_id) {

       checkConcept<_writer_bits::ItemIdWriter<Edge>, _IdWriter>();

       checkConcept<_writer_bits::ItemIdWriter<UndirEdge>, _IdWriter>();

       undirEdgeIdWriter.reset(new IdWriter<UndirEdge, _IdWriter>(_idWriter));

       edgeIdWriter.reset(new IdWriter<Edge, _IdWriter>(_idWriter));

     }

     /// \brief Destructor.

     ///

     /// Destructor for UndirEdgeWriter.

     virtual ~UndirEdgeWriter() {}

   private:

     UndirEdgeWriter(const UndirEdgeWriter&);

     void operator=(const UndirEdgeWriter&);

   public:

     /// \brief Add an edge writer command for the UndirEdgeWriter.

     ///

     /// Add an edge writer command for the UndirEdgeWriter.

     void writeEdge(const std::string& name, const Edge& item) {

       edgeWriters.push_back(make_pair(name, &item));

     }

     /// \brief Add an undirected edge writer command for the UndirEdgeWriter.

     ///

     /// Add an undirected edge writer command for the UndirEdgeWriter.

     void writeUndirEdge(const std::string& name, const UndirEdge& item) {

       undirEdgeWriters.push_back(make_pair(name, &item));

     }

   protected:

     /// \brief Header checking function.

     ///

     /// It gives back true when the header line start with \c \@undiredges,

     /// and the header line's id and the writer's id are the same.

     virtual std::string header() {

       return "@undiredges " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     virtual void write(std::ostream& os) {

       if (!edgeIdWriter->isIdWriter()) {

 	throw DataFormatError("Cannot find undirected edgeset or ID map");

       }

       if (!undirEdgeIdWriter->isIdWriter()) {

 	throw DataFormatError("Cannot find undirected edgeset or ID map");

       }

       for (int i = 0; i < (int)undirEdgeWriters.size(); ++i) {

 	os << undirEdgeWriters[i].first << ' ';

 	undirEdgeIdWriter->write(os, *(undirEdgeWriters[i].second));

 	os << std::endl;

       }

       for (int i = 0; i < (int)edgeWriters.size(); ++i) {

 	os << edgeWriters[i].first << ' ';

 	edgeIdWriter->write(os, *(edgeWriters[i].second));

 	os << std::endl;

       }

     }

   private:

     std::string id;

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

 				  const UndirEdge*> > UndirEdgeWriters;

     UndirEdgeWriters undirEdgeWriters;

     std::auto_ptr<IdWriterBase<UndirEdge> > undirEdgeIdWriter;

     typedef std::vector<std::pair<std::string, const Edge*> > EdgeWriters;

     EdgeWriters edgeWriters;

     std::auto_ptr<IdWriterBase<Edge> > edgeIdWriter;

   };

   /// \ingroup io_group

   /// \brief SectionWriter for attributes.

   ///

   /// The lemon format can store multiple attribute set. Each set has

   /// the header line \c \@attributes \c attributeset_id, but the 

   /// attributeset_id may be empty.

   ///

   /// The attributeset section contains several lines. Each of them starts

   /// with the name of attribute and then the value.

   ///

   /// \relates LemonWriter

   template <typename _Traits = DefaultWriterTraits>

   class AttributeWriter : public CommonSectionWriterBase {

     typedef CommonSectionWriterBase Parent;

     typedef _Traits Traits; 

   public:

     /// \brief Constructor.

     ///

     /// Constructor for AttributeWriter. It creates the AttributeWriter and

     /// attach it into the given LemonWriter.

     AttributeWriter(LemonWriter& _writer, 

 		    const std::string& _id = std::string()) 

       : Parent(_writer), id(_id) {}

     /// \brief Destructor.

     ///

     /// Destructor for AttributeWriter.

     virtual ~AttributeWriter() {

       typename Writers::iterator it;

       for (it = writers.begin(); it != writers.end(); ++it) {

 	delete it->second;

       }

     }

   private:

     AttributeWriter(const AttributeWriter&);

     void operator=(AttributeWriter&);

   public:

     /// \brief Add an attribute writer command for the writer.

     ///

     /// Add an attribute writer command for the writer.

     template <typename Value>

     AttributeWriter& writeAttribute(const std::string& id, 

 				    const Value& value) {

       return 

 	writeAttribute<typename Traits::template Writer<Value> >(id, value);

     }

     /// \brief Add an attribute writer command for the writer.

     ///

     /// Add an attribute writer command for the writer.

     template <typename Writer, typename Value>

     AttributeWriter& writeAttribute(const std::string& name, 

 				    const Value& value,

 				    const Writer& writer = Writer()) {

       checkConcept<_writer_bits::ItemWriter<Value>, Writer>();

       writers.push_back(make_pair(name, new ValueWriter<Value, Writer>

       			       (value, writer)));

       return *this;

     }

   protected:

     /// \brief The header of section.

     ///

     /// It gives back the header of the section.

     std::string header() {

       return "@attributes " + id;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

     void write(std::ostream& os) {

       typename Writers::iterator it;

       for (it = writers.begin(); it != writers.end(); ++it) {

 	os << it->first << ' ';

 	it->second->write(os);

 	os << std::endl;

       }

     }    

   private:

     std::string id;

     typedef std::vector<std::pair<std::string, ValueWriterBase*> > Writers;

     Writers writers;  

   };

 }

 #endif