/* -*- C++ -*-

  *

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

  *

  * Copyright (C) 2003-2006

  * 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 lemon_io

 ///\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/bits/invalid.h>

 #include <lemon/graph_utils.h>

 #include <lemon/bits/item_writer.h>

 #include <lemon/bits/utility.h>

 #include <lemon/maps.h>

 #include <lemon/dim2.h>

 #include <lemon/concept_check.h>

 #include <lemon/concepts/maps.h>

 namespace lemon {

   namespace _writer_bits {

     template <typename T>

     bool operator<(T, T) {

       throw DataFormatError("Label is not comparable");

     }

     template <typename T>

     struct Less {

       bool operator()(const T& p, const T& q) const {

 	return p < q;

       }

     };

     template <typename Map>

     struct ComposeLess {

       ComposeLess(const Map& _map) : map(_map), less() {}

       bool operator()(const typename Map::Key& p, 

                       const typename Map::Key& q) const {

 	return less(map[p], map[q]);

       }

       const Map& map;

       Less<typename Map::Value> less;

     };

     template <typename Item>

     class ItemLabelWriter {

     public:

       bool isLabelWriter() { return true; }

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

       template <class _ItemLabelWriter>

       struct Constraints {

 	void constraints() {

 	  bool b = writer.isLabelWriter();

 	  ignore_unused_variable_warning(b);

 	  writer.writeLabel(os, item);

 	}

 	_ItemLabelWriter& 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::UEdge 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::UEdge 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<dim2::XMap<Map> > { 

       typedef dim2::XMap<Map> Type;

     };

     template <typename Map>

     struct Ref<dim2::ConstXMap<Map> > { 

       typedef dim2::ConstXMap<Map> Type;

     };

     template <typename Map>

     struct Ref<dim2::YMap<Map> > { 

       typedef dim2::YMap<Map> Type;

     };

     template <typename Map>

     struct Ref<dim2::ConstYMap<Map> > { 

       typedef dim2::ConstYMap<Map> Type;

     };

     template <typename _Item>    

     class MapWriterBase {

     public:

       typedef _Item Item;

       virtual ~MapWriterBase() {}

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

       virtual void sortByMap(std::vector<Item>&) const = 0;

     };

     template <typename _Item, typename _Map, typename _Writer>

     class MapWriter : public MapWriterBase<_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) const {

 	Value value = map[item];

 	writer.write(os, value);

       }

       virtual void sortByMap(std::vector<Item>& items) const {

         ComposeLess<Map> less(map);

         std::sort(items.begin(), items.end(), less);

       }

     };

     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 LabelWriterBase {

     public:

       typedef _Item Item;

       virtual ~LabelWriterBase() {}

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

       virtual bool isLabelWriter() const = 0;

     };

     template <typename _Item, typename _BoxedLabelWriter>

     class LabelWriter : public LabelWriterBase<_Item> {

     public:

       typedef _Item Item;

       typedef _BoxedLabelWriter BoxedLabelWriter;

       const BoxedLabelWriter& labelWriter;

       LabelWriter(const BoxedLabelWriter& _labelWriter) 

 	: labelWriter(_labelWriter) {}

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

 	labelWriter.writeLabel(os, item);

       }

       virtual bool isLabelWriter() const {

 	return labelWriter.isLabelWriter();

       }

     };

   }

   /// \ingroup lemon_io

   /// \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 Gives back true when the section should be written.

       ///

       /// Gives back true when the section should be written.

       virtual bool valid() { return true; }

     };

     /// \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) {

         if ((*it)->valid()) {

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

   };

   /// \ingroup section_io

   /// \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_name, but 

   /// the \c nodeset_name 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 "label" named map then it will be regarded

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

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

   /// label. Otherwise if the \c _forceLabelMap constructor parameter is true 

   /// then the label map will be the id in the graph. In addition if the

   /// the \c _sortByLabel is true then the writer will write the edges

   /// sorted by the labels.

   ///

   /// \relates LemonWriter

   template <typename _Graph, typename _Traits = DefaultWriterTraits>

   class NodeSetWriter : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter 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 _forceLabelMap

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

     /// the user does not give "label" named map. In addition if the

     /// the \c _sortByLabel is true then the writer will write the edges

     /// sorted by the labels.

     NodeSetWriter(LemonWriter& _writer, const Graph& _graph, 

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

 		  bool _forceLabelMap = true, bool _sortByLabel = true) 

       : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap), 

 	sortByLabel(_sortByLabel), graph(_graph), name(_name) {}

     /// \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 label, const Map& map) {

       return writeNodeMap<typename Traits::

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

     }

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

     ///

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

     template <typename ItemWriter, typename Map>

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

 			    const ItemWriter& iw = ItemWriter()) {

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

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

       writers.push_back(

 	make_pair(label, new _writer_bits::

 		  MapWriter<Node, Map, ItemWriter>(map, iw)));

       return *this;

     }

   protected:

     /// \brief The header of the section.

     ///

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

     virtual std::string header() {

       return "@nodeset " + name;

     }

     /// \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 == "label") {

 	  labelMap = writers[i].second;

 	  forceLabelMap = false;

 	  break;

 	}

       }

       std::vector<Node> items;

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

         items.push_back(it);

       }

       if (sortByLabel) {

         if (labelMap) {

           labelMap->sortByMap(items);

         } else {

           typedef IdMap<Graph, Node> Map;

           Map map(graph);

           _writer_bits::ComposeLess<Map> less(map);

           std::sort(items.begin(), items.end(), less);

         }

       }

       if (forceLabelMap) {

 	os << "label\t";

       }

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

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

       }

       os << std::endl;

       for (typename std::vector<Node>::iterator it = items.begin();

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

 	if (forceLabelMap) {

 	  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 labels of the nodes.

     ///

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

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

     /// \c _forceLabelMap constructor parameter was true.

     bool isLabelWriter() const {

       return labelMap != 0 || forceLabelMap;

     }

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

     ///

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

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

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

     /// its label in the graph. 

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

       if (forceLabelMap) {

 	os << graph.id(item);

       } else {

 	labelMap->write(os, item);

       }

     }

   private:

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

 				  MapWriterBase<Node>*> > MapWriters;

     MapWriters writers;

     _writer_bits::MapWriterBase<Node>* labelMap;

     bool forceLabelMap;

     bool sortByLabel;

     const Graph& graph;   

     std::string name;

   };

   /// \ingroup section_io

   /// \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_name, but 

   /// the \c edgeset_name 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' label and the mapped 

   /// values for each map.

   ///

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

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

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

   /// label. Otherwise if the \c _forceLabelMap constructor parameter is true 

   /// then the label map will be the id in the graph. In addition if the

   /// the \c _sortByLabel is true then the writer will write the edges

   /// sorted by the labels.

   ///

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

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

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

   ///

   /// \relates LemonWriter

   template <typename _Graph, typename _Traits = DefaultWriterTraits>

   class EdgeSetWriter : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter 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

     /// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap

     /// parameter is true then the writer will write own label map if

     /// the user does not give "label" named map. In addition if the

     /// the \c _sortByLabel is true then the writer will write the

     /// edges sorted by the labels.

     template <typename NodeLabelWriter>

     EdgeSetWriter(LemonWriter& _writer, const Graph& _graph, 

 		  const NodeLabelWriter& _nodeLabelWriter, 

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

 		  bool _forceLabelMap = true, bool _sortByLabel = true)

       : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),

 	sortByLabel(_sortByLabel), graph(_graph), name(_name) {

       checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();

       nodeLabelWriter.reset(new _writer_bits::

 			 LabelWriter<Node, NodeLabelWriter>(_nodeLabelWriter));

     } 

     /// \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 label, const Map& map) {

       return writeEdgeMap<typename Traits::

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

     }

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

     ///

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

     template <typename ItemWriter, typename Map>

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

 			    const ItemWriter& iw = ItemWriter()) {

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

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

       writers.push_back(

 	make_pair(label, new _writer_bits::

 		  MapWriter<Edge, Map, ItemWriter>(map, iw)));

       return *this;

     }

   protected:

     /// \brief The header of the section.

     ///

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

     virtual std::string header() {

       return "@edgeset " + name;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

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

       if (!nodeLabelWriter->isLabelWriter()) {

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

       }

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

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

 	  labelMap = writers[i].second;

 	  forceLabelMap = false;

 	  break;

 	}

       }

       std::vector<Edge> items;

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

         items.push_back(it);

       }

       if (sortByLabel) {

         if (labelMap) {

           labelMap->sortByMap(items);

         } else {

           typedef IdMap<Graph, Edge> Map;

           Map map(graph);

           _writer_bits::ComposeLess<Map> less(map);

           std::sort(items.begin(), items.end(), less);

         }

       }

       os << "\t\t";

       if (forceLabelMap) {

 	os << "label\t";

       }

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

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

       }

       os << std::endl;

       for (typename std::vector<Edge>::iterator it = items.begin();

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

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

 	os << '\t';

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

 	os << '\t';

 	if (forceLabelMap) {

 	  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 labels of the edges.

     ///

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

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

     /// \c _forceLabelMap constructor parameter was true.

     bool isLabelWriter() const {

       return forceLabelMap || labelMap != 0;

     }

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

     ///

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

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

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

     /// its label in the graph. 

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

       if (forceLabelMap) {

 	os << graph.id(item);

       } else {

 	labelMap->write(os, item);

       }

     } 

   private:

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

 				  MapWriterBase<Edge>*> > MapWriters;

     MapWriters writers;

     _writer_bits::MapWriterBase<Edge>* labelMap;

     bool forceLabelMap;

     bool sortByLabel;

     const Graph& graph;   

     std::string name;

     std::auto_ptr<_writer_bits::LabelWriterBase<Node> > nodeLabelWriter;

   };

   /// \ingroup section_io

   /// \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 \@uedgeset 

   /// \c uedgeset_name, but the \c uedgeset_name 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' label 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 "label" named map then it will be

   /// regarded as label map. This map should contain only unique

   /// values and when the \c writeLabel() member will be called with

   /// an undirected edge it will write it's label. Otherwise if the \c

   /// _forceLabelMap constructor parameter is true then the label map

   /// will be the id in the graph.  In addition if the the \c

   /// _sortByLabel is true then the writer will write the edges sorted

   /// by the labels.

   ///

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

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

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

   ///

   /// \relates LemonWriter

   template <typename _Graph, typename _Traits = DefaultWriterTraits>

   class UEdgeSetWriter : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter Parent;

   public:

     typedef _Graph Graph;

     typedef _Traits Traits;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::UEdge UEdge;

     /// \brief Constructor.

     ///

     /// Constructor for UEdgeSetWriter. It creates the UEdgeSetWriter

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

     /// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap

     /// parameter is true then the writer will write own label map if

     /// the user does not give "label" named map. In addition if the

     /// the \c _sortByLabel is true then the writer will write the

     /// edges sorted by the labels.

     template <typename NodeLabelWriter>

     UEdgeSetWriter(LemonWriter& _writer, const Graph& _graph, 

 		       const NodeLabelWriter& _nodeLabelWriter, 

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

 		       bool _forceLabelMap = true, bool _sortByLabel = true)

       : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),

 	sortByLabel(_sortByLabel), graph(_graph), name(_name) {

       checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();

       nodeLabelWriter.reset(new _writer_bits::

 			 LabelWriter<Node, NodeLabelWriter>(_nodeLabelWriter));

     } 

     /// \brief Destructor.

     ///

     /// Destructor for UEdgeSetWriter.

     virtual ~UEdgeSetWriter() {

       typename MapWriters::iterator it;

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

 	delete it->second;

       }

     }

   private:

     UEdgeSetWriter(const UEdgeSetWriter&);

     void operator=(const UEdgeSetWriter&);

   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>

     UEdgeSetWriter& writeUEdgeMap(std::string label, const Map& map) {

       return writeUEdgeMap<typename Traits::

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

     }

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

     ///

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

     template <typename ItemWriter, typename Map>

     UEdgeSetWriter& writeUEdgeMap(std::string label, const Map& map, 

                                   const ItemWriter& iw = ItemWriter()) {

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

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

       writers.push_back(

 	make_pair(label, new _writer_bits::

 		  MapWriter<UEdge, Map, ItemWriter>(map, iw)));

       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>

     UEdgeSetWriter& writeEdgeMap(std::string label, const Map& map) {

       return writeEdgeMap<typename Traits::

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

     }

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

     ///

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

     template <typename ItemWriter, typename Map>

     UEdgeSetWriter& writeEdgeMap(std::string label, const Map& map, 

                                  const ItemWriter& iw = ItemWriter()) {

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

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

       writeUEdgeMap("+" + name, 

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

       writeUEdgeMap("-" + name, 

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

       return *this;

     }

   protected:

     /// \brief The header of the section.

     ///

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

     virtual std::string header() {

       return "@uedgeset " + name;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

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

       if (!nodeLabelWriter->isLabelWriter()) {

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

       }

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

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

 	  labelMap = writers[i].second;

 	  forceLabelMap = false;

 	  break;

 	}

       }

       std::vector<UEdge> items;

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

         items.push_back(it);

       }

       if (sortByLabel) {

         if (labelMap) {

           labelMap->sortByMap(items);

         } else {

           typedef IdMap<Graph, UEdge> Map;

           Map map(graph);

           _writer_bits::ComposeLess<Map> less(map);

           std::sort(items.begin(), items.end(), less);

         }

       }

       os << "\t\t";

       if (forceLabelMap) {

 	os << "label\t";

       }

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

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

       }

       os << std::endl;

       for (typename std::vector<UEdge>::iterator it = items.begin();

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

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

 	os << '\t';

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

 	os << '\t';

 	if (forceLabelMap) {

 	  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 labels of 

     /// the edges.

     ///

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

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

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

     bool isLabelWriter() const {

       return forceLabelMap || labelMap != 0;

     }

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

     ///

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

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

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

     /// will write its id in the graph. 

     void writeLabel(std::ostream& os, const UEdge& item) const {

       if (forceLabelMap) {

 	os << graph.id(item);

       } else {

 	labelMap->write(os, item);

       }

     } 

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

     ///

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

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

     /// edge. Otherwise if the \c forceLabel 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 writeLabel(std::ostream& os, const Edge& item) const {

       if (graph.direction(item)) {

 	os << "+ ";

       } else {

 	os << "- ";

       }

       if (forceLabelMap) {

 	os << graph.id(item);

       } else {

 	labelMap->write(os, item);

       }

     } 

   private:

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

 				  MapWriterBase<UEdge>*> > MapWriters;

     MapWriters writers;

     _writer_bits::MapWriterBase<UEdge>* labelMap;

     bool forceLabelMap;

     bool sortByLabel;

     const Graph& graph;   

     std::string name;

     std::auto_ptr<_writer_bits::LabelWriterBase<Node> > nodeLabelWriter;

   };

   /// \ingroup section_io

   /// \brief SectionWriter for writing named nodes.

   ///

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

   /// \c nodes_name may be empty.

   ///

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

   /// then the node label. 

   ///

   /// \relates LemonWriter

   template <typename _Graph>

   class NodeWriter : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter 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 _LabelWriter

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

     template <typename _LabelWriter>

     NodeWriter(LemonWriter& _writer, const _LabelWriter& _labelWriter, 

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

       : Parent(_writer), name(_name) {

       checkConcept<_writer_bits::ItemLabelWriter<Node>, _LabelWriter>();

       labelWriter.reset(new _writer_bits::LabelWriter<Node, _LabelWriter>

                         (_labelWriter));

     }

     /// \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(std::string label, const Node& item) {

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

     }

   protected:

     /// \brief The header of the section.

     ///

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

     virtual std::string header() {

       return "@nodes " + name;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

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

       if (!labelWriter->isLabelWriter()) {

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

       }

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

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

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

 	os << std::endl;

       }

     }

     /// \brief Gives back true when the section should be written.

     ///

     /// Gives back true when the section should be written.

     virtual bool valid() { return !writers.empty(); }

   private:

     std::string name;

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

     NodeWriters writers;

     std::auto_ptr<_writer_bits::LabelWriterBase<Node> > labelWriter;

   };

   /// \ingroup section_io

   /// \brief SectionWriter for writing named edges.

   ///

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

   /// \c edges_name may be empty.

   ///

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

   /// then the edge label. 

   ///

   /// \relates LemonWriter

   template <typename _Graph>

   class EdgeWriter : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter 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 _LabelWriter

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

     template <typename _LabelWriter>

     EdgeWriter(LemonWriter& _writer, const _LabelWriter& _labelWriter, 

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

       : Parent(_writer), name(_name) {

       checkConcept<_writer_bits::ItemLabelWriter<Edge>, _LabelWriter>();

       labelWriter.reset(new _writer_bits::LabelWriter<Edge, _LabelWriter>(_labelWriter));

     }

     /// \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(std::string label, const Edge& item) {

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

     }

   protected:

     /// \brief The header of the section.

     ///

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

     virtual std::string header() {

       return "@edges " + name;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

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

       if (!labelWriter->isLabelWriter()) {

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

       }

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

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

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

 	os << std::endl;

       }

     }

     /// \brief Gives back true when the section should be written.

     ///

     /// Gives back true when the section should be written.

     virtual bool valid() { return !writers.empty(); }

   private:

     std::string name;

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

     EdgeWriters writers;

     std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > labelWriter;

   };

   /// \ingroup section_io

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

   ///

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

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

   ///

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

   /// then the undirected edge label. 

   ///

   /// \relates LemonWriter

   template <typename _Graph>

   class UEdgeWriter : public LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter Parent;

     typedef _Graph Graph;

     typedef typename Graph::Node Node;

     typedef typename Graph::Edge Edge;

     typedef typename Graph::UEdge UEdge;

   public:

     /// \brief Constructor.

     ///

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

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

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

     /// edgeset writer.

     template <typename _LabelWriter>

     UEdgeWriter(LemonWriter& _writer, const _LabelWriter& _labelWriter, 

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

       : Parent(_writer), name(_name) {

       checkConcept<_writer_bits::ItemLabelWriter<Edge>, _LabelWriter>();

       checkConcept<_writer_bits::ItemLabelWriter<UEdge>, _LabelWriter>();

       uEdgeLabelWriter.reset(new _writer_bits::

 			      LabelWriter<UEdge, _LabelWriter>(_labelWriter));

       edgeLabelWriter.reset(new _writer_bits::

 			 LabelWriter<Edge, _LabelWriter>(_labelWriter));

     }

     /// \brief Destructor.

     ///

     /// Destructor for UEdgeWriter.

     virtual ~UEdgeWriter() {}

   private:

     UEdgeWriter(const UEdgeWriter&);

     void operator=(const UEdgeWriter&);

   public:

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

     ///

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

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

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

     }

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

     ///

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

     void writeUEdge(std::string label, const UEdge& item) {

       uEdgeWriters.push_back(make_pair(label, &item));

     }

   protected:

     /// \brief The header of the section.

     ///

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

     virtual std::string header() {

       return "@uedges " + name;

     }

     /// \brief  Writer function of the section.

     ///

     /// Write the content of the section.

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

       if (!edgeLabelWriter->isLabelWriter()) {

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

       }

       if (!uEdgeLabelWriter->isLabelWriter()) {

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

       }

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

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

 	uEdgeLabelWriter->write(os, *(uEdgeWriters[i].second));

 	os << std::endl;

       }

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

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

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

 	os << std::endl;

       }

     }

     /// \brief Gives back true when the section should be written.

     ///

     /// Gives back true when the section should be written.

     virtual bool valid() { 

       return !uEdgeWriters.empty() || !edgeWriters.empty(); 

     }

   private:

     std::string name;

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

 				  const UEdge*> > UEdgeWriters;

     UEdgeWriters uEdgeWriters;

     std::auto_ptr<_writer_bits::LabelWriterBase<UEdge> > uEdgeLabelWriter;

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

     EdgeWriters edgeWriters;

     std::auto_ptr<_writer_bits::LabelWriterBase<Edge> > edgeLabelWriter;

   };

   /// \ingroup section_io

   /// \brief SectionWriter for attributes.

   ///

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

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

   /// attributeset_name 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 LemonWriter::SectionWriter {

     typedef LemonWriter::SectionWriter 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& _name = std::string()) 

       : Parent(_writer), name(_name) {}

     /// \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(std::string label, 

 				    const Value& value) {

       return 

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

     }

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

     ///

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

     template <typename ItemWriter, typename Value>

     AttributeWriter& writeAttribute(std::string label, const Value& value,

 				    const ItemWriter& iw = ItemWriter()) {

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

       writers.push_back(make_pair(label, new _writer_bits::

 				  ValueWriter<Value, ItemWriter>(value, iw)));

       return *this;

     }

   protected:

     /// \brief The header of section.

     ///

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

     std::string header() {

       return "@attributes " + name;

     }

     /// \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;

       }

     }    

     /// \brief Gives back true when the section should be written.

     ///

     /// Gives back true when the section should be written.

     virtual bool valid() { return !writers.empty(); }

   private:

     std::string name;

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

 				  _writer_bits::ValueWriterBase*> > Writers;

     Writers writers;  

   };

 }

 #endif