Index: lemon/lemon_writer.h
===================================================================
--- lemon/lemon_writer.h	(revision 2084)
+++ lemon/lemon_writer.h	(revision 2101)
@@ -48,4 +48,28 @@
   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 {
@@ -176,4 +200,5 @@
 
       virtual void write(std::ostream& os, const Item& item) const = 0;
+      virtual void sortByMap(std::vector<Item>&) const = 0;
     };
 
@@ -198,4 +223,9 @@
 	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);
       }
 
@@ -395,5 +425,7 @@
   /// \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.
+  /// 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
@@ -412,10 +444,12 @@
     /// 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.
+    /// 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 _forceLabelMap = true, bool _sortByLabel = true) 
       : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap), 
-	graph(_graph), name(_name) {}
+	sortByLabel(_sortByLabel), graph(_graph), name(_name) {}
 
     /// \brief Destructor.
@@ -478,4 +512,18 @@
 	}
       }
+      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";
@@ -485,10 +533,11 @@
       }
       os << std::endl;
-      for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
+      for (typename std::vector<Node>::iterator it = items.begin();
+           it != items.end(); ++it) {
 	if (forceLabelMap) {
-	  os << graph.id(it) << '\t';
+	  os << graph.id(*it) << '\t';
 	}
 	for (int i = 0; i < (int)writers.size(); ++i) {
-	  writers[i].second->write(os, it);
+	  writers[i].second->write(os, *it);
 	  os << '\t';
 	}
@@ -530,4 +579,5 @@
     _writer_bits::MapWriterBase<Node>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
@@ -552,5 +602,7 @@
   /// \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.
+  /// 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
@@ -571,16 +623,18 @@
     /// \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.
+    /// 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 _forceLabelMap = true, bool _sortByLabel = true)
       : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
-	graph(_graph), name(_name) {
+	sortByLabel(_sortByLabel), graph(_graph), name(_name) {
       checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();
       nodeLabelWriter.reset(new _writer_bits::
@@ -650,4 +704,18 @@
 	}
       }
+      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) {
@@ -658,14 +726,15 @@
       }
       os << std::endl;
-      for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
-	nodeLabelWriter->write(os, graph.source(it));
+      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));
+	nodeLabelWriter->write(os, graph.target(*it));
 	os << '\t';
 	if (forceLabelMap) {
-	  os << graph.id(it) << '\t';
+	  os << graph.id(*it) << '\t';
 	}
 	for (int i = 0; i < (int)writers.size(); ++i) {
-	  writers[i].second->write(os, it);
+	  writers[i].second->write(os, *it);
 	  os << '\t';
 	}
@@ -707,4 +776,5 @@
     _writer_bits::MapWriterBase<Edge>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
@@ -732,9 +802,12 @@
   /// 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.
+  /// 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 
@@ -757,15 +830,17 @@
     ///
     /// 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.
+    /// 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 _forceLabelMap = true, bool _sortByLabel = true)
       : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
-	graph(_graph), name(_name) {
+	sortByLabel(_sortByLabel), graph(_graph), name(_name) {
       checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();
       nodeLabelWriter.reset(new _writer_bits::
@@ -859,4 +934,18 @@
 	}
       }
+      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) {
@@ -867,14 +956,15 @@
       }
       os << std::endl;
-      for (typename Graph::UEdgeIt it(graph); it != INVALID; ++it) {
-	nodeLabelWriter->write(os, graph.source(it));
+      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));
+	nodeLabelWriter->write(os, graph.target(*it));
 	os << '\t';
 	if (forceLabelMap) {
-	  os << graph.id(it) << '\t';
+	  os << graph.id(*it) << '\t';
 	}
 	for (int i = 0; i < (int)writers.size(); ++i) {
-	  writers[i].second->write(os, it);
+	  writers[i].second->write(os, *it);
 	  os << '\t';
 	}
@@ -937,4 +1027,5 @@
     _writer_bits::MapWriterBase<UEdge>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
