Changeset 2101:439b7f21ccc4 in lemon-0.x

Timestamp:

06/19/06 15:44:06 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2787

Message:

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.

File:

• lemon/lemon_writer.h (modified) (18 diffs)

lemon/lemon_writer.h

@@ -48 +48 @@
   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 +200 @@
 
       virtual void write(std::ostream& os, const Item& item) const = 0;
+      virtual void sortByMap(std::vector<Item>&) const = 0;
     };
 
@@ -198 +223 @@
         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 +425 @@
   /// \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 +444 @@
     /// 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 +512 @@
         }
       }
+      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 +533 @@
       }
       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 +579 @@
     _writer_bits::MapWriterBase<Node>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
@@ -552 +602 @@
   /// \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 +623 @@
     /// \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 +704 @@
         }
       }
+      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 +726 @@
       }
       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 +776 @@
     _writer_bits::MapWriterBase<Edge>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;   
@@ -732 +802 @@
   /// 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 +830 @@
     ///
     /// 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 +934 @@
         }
       }
+      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 +956 @@
       }
       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 +1027 @@
     _writer_bits::MapWriterBase<UEdge>* labelMap;
     bool forceLabelMap;
+    bool sortByLabel;
    
     const Graph& graph;