# HG changeset patch
# User deba
# Date 1150724646 0
# Node ID 439b7f21ccc4e8b7f9a4349ffca892a89db2c15c
# Parent  6fbe90faf02a5991cbc0298629468779e43ab4a6
Improvement:

The item sets are written in the order sorted by the labels.

It solves the problem if we read a graph from a file and
then write it back then the nodes will be reversed.
It can be switched off with the LemonWriter interface.

diff -r 6fbe90faf02a -r 439b7f21ccc4 lemon/lemon_writer.h
--- a/lemon/lemon_writer.h	Tue Jun 06 12:47:01 2006 +0000
+++ b/lemon/lemon_writer.h	Mon Jun 19 13:44:06 2006 +0000
@@ -47,6 +47,30 @@
 
   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:
@@ -175,6 +199,7 @@
       virtual ~MapWriterBase() {}
 
       virtual void write(std::ostream& os, const Item& item) const = 0;
+      virtual void sortByMap(std::vector<Item>&) const = 0;
     };
 
 
@@ -199,6 +224,11 @@
 	writer.write(os, value);
       }
 
+      virtual void sortByMap(std::vector<Item>& items) const {
+        ComposeLess<Map> less(map);
+        std::sort(items.begin(), items.end(), less);
+      }
+
     };
 
 
@@ -394,7 +424,9 @@
   /// 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.
+  /// 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>
@@ -411,12 +443,14 @@
     /// 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.
+    /// 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.
     ///
@@ -477,6 +511,20 @@
 	  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";
       }
@@ -484,12 +532,13 @@
 	os << writers[i].first << '\t';
       }
       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';
 	}
 	os << std::endl;
@@ -529,6 +578,7 @@
 
     _writer_bits::MapWriterBase<Node>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
     std::string name;
@@ -551,7 +601,9 @@
   /// 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.
+  /// 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,
@@ -570,18 +622,20 @@
 
     /// \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::
 			 LabelWriter<Node, NodeLabelWriter>(_nodeLabelWriter));
@@ -649,6 +703,20 @@
 	  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";
@@ -657,16 +725,17 @@
 	os << writers[i].first << '\t';
       }
       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';
 	}
 	os << std::endl;
@@ -706,6 +775,7 @@
 
     _writer_bits::MapWriterBase<Edge>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
     std::string name;
@@ -731,11 +801,14 @@
   /// 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.
+  /// 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 
@@ -756,17 +829,19 @@
     /// \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.
+    /// 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::
 			 LabelWriter<Node, NodeLabelWriter>(_nodeLabelWriter));
@@ -858,6 +933,20 @@
 	  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";
@@ -866,16 +955,17 @@
 	os << writers[i].first << '\t';
       }
       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';
 	}
 	os << std::endl;
@@ -936,6 +1026,7 @@
 
     _writer_bits::MapWriterBase<UEdge>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
     std::string name;