lemon-0.x: comparison lemon/lemon

equal deleted inserted replaced

-:ee9bb6fc00c0
+:119334684e83
 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; }
 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> {
 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);
 }
 };
 ///
 /// 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.
+/// 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;
 /// \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.
+/// 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.
 ///
 /// Destructor for NodeSetWriter.
 virtual ~NodeSetWriter() {
 	  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 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;
 }
 }
 				  MapWriterBase<Node>*> > MapWriters;
 MapWriters writers;
 _writer_bits::MapWriterBase<Node>* labelMap;
 bool forceLabelMap;
+bool sortByLabel;
 const Graph& graph;
 std::string name;
 };
 ///
 /// 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.
+/// 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.
 ///
 typedef typename Graph::Node Node;
 typedef typename Graph::Edge Edge;
 /// \brief Constructor.
 ///
-/// Constructor for EdgeSetWriter. It creates the EdgeSetWriter and
+/// Constructor for EdgeSetWriter. It creates the EdgeSetWriter
-/// attach it into the given LemonWriter. It will write node labels by
+/// and attach it into the given LemonWriter. It will write node
-/// the \c _nodeLabelWriter. If the \c _forceLabelMap parameter is true
+/// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap
-/// then the writer will write own label map if the user does not give
+/// parameter is true then the writer will write own label map if
-/// "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.
 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));
 }
 	  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 Graph::EdgeIt it(graph); it != INVALID; ++it) {
+for (typename std::vector<Edge>::iterator it = items.begin();
-	nodeLabelWriter->write(os, graph.source(it));
+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;
 }
 }
 				  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;
 /// 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
+/// If the edgeset contains an \c "label" named map then it will be
-/// as label map. This map should contain only unique values and when the
+/// regarded as label map. This map should contain only unique
-/// \c writeLabel() member will be called with an undirected edge it will
+/// values and when the \c writeLabel() member will be called with
-/// write it's label. Otherwise if the \c _forceLabelMap constructor
+/// an undirected edge it will write it's label. Otherwise if the \c
-/// parameter is true then the label map will be the id in the graph.
+/// _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.
 ///
 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
+/// and attach it into the given LemonWriter. It will write node
-/// the \c _nodeLabelWriter. If the \c _forceLabelMap parameter is true
+/// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap
-/// then the writer will write own label map if the user does not give
+/// parameter is true then the writer will write own label map if
-/// "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.
 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));
 }
 	  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 Graph::UEdgeIt it(graph); it != INVALID; ++it) {
+for (typename std::vector<Edge>::iterator it = items.begin();
-	nodeLabelWriter->write(os, graph.source(it));
+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;
 }
 }
 				  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;

changeset 2126	2c8adbee9fa6
parent 2084	59769591eb60
child 2207	75a29ac69c19