/* -*- 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 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<concepts::ReadMap<Node, typename Map::Value>, Map>();

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

      writers.push_back(

	make_pair(name, new _writer_bits::

		  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 " + 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 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<concepts::ReadMap<Edge, typename Map::Value>, Map>();

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

      writers.push_back(

	make_pair(name, new _writer_bits::

		  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 " + 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 name, const Map& map) {

      return writeUEdgeMap<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>

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

                                  const Writer& writer = Writer()) {

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

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

      writers.push_back(

	make_pair(name, new _writer_bits::

		  MapWriter<UEdge, 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>

    UEdgeSetWriter& 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>

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

                                 const Writer& writer = Writer()) {

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

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

      writeUEdgeMap("+" + name, 

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

      writeUEdgeMap("-" + 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 "@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 {