1.1 --- a/lemon/lemon_writer.h Tue Jun 06 12:47:01 2006 +0000
1.2 +++ b/lemon/lemon_writer.h Mon Jun 19 13:44:06 2006 +0000
1.3 @@ -47,6 +47,30 @@
1.4
1.5 namespace _writer_bits {
1.6
1.7 + template <typename T>
1.8 + bool operator<(T, T) {
1.9 + throw DataFormatError("Label is not comparable");
1.10 + }
1.11 +
1.12 + template <typename T>
1.13 + struct Less {
1.14 + bool operator()(const T& p, const T& q) const {
1.15 + return p < q;
1.16 + }
1.17 + };
1.18 +
1.19 + template <typename Map>
1.20 + struct ComposeLess {
1.21 + ComposeLess(const Map& _map) : map(_map), less() {}
1.22 +
1.23 + bool operator()(const typename Map::Key& p,
1.24 + const typename Map::Key& q) const {
1.25 + return less(map[p], map[q]);
1.26 + }
1.27 + const Map& map;
1.28 + Less<typename Map::Value> less;
1.29 + };
1.30 +
1.31 template <typename Item>
1.32 class ItemLabelWriter {
1.33 public:
1.34 @@ -175,6 +199,7 @@
1.35 virtual ~MapWriterBase() {}
1.36
1.37 virtual void write(std::ostream& os, const Item& item) const = 0;
1.38 + virtual void sortByMap(std::vector<Item>&) const = 0;
1.39 };
1.40
1.41
1.42 @@ -199,6 +224,11 @@
1.43 writer.write(os, value);
1.44 }
1.45
1.46 + virtual void sortByMap(std::vector<Item>& items) const {
1.47 + ComposeLess<Map> less(map);
1.48 + std::sort(items.begin(), items.end(), less);
1.49 + }
1.50 +
1.51 };
1.52
1.53
1.54 @@ -394,7 +424,9 @@
1.55 /// as label map. This map should contain only unique values and when the
1.56 /// \c writeLabel() member will be called with a node it will write it's
1.57 /// label. Otherwise if the \c _forceLabelMap constructor parameter is true
1.58 - /// then the label map will be the id in the graph.
1.59 + /// then the label map will be the id in the graph. In addition if the
1.60 + /// the \c _sortByLabel is true then the writer will write the edges
1.61 + /// sorted by the labels.
1.62 ///
1.63 /// \relates LemonWriter
1.64 template <typename _Graph, typename _Traits = DefaultWriterTraits>
1.65 @@ -411,12 +443,14 @@
1.66 /// Constructor for NodeSetWriter. It creates the NodeSetWriter and
1.67 /// attach it into the given LemonWriter. If the \c _forceLabelMap
1.68 /// parameter is true then the writer will write own label map when
1.69 - /// the user does not give "label" named map.
1.70 + /// the user does not give "label" named map. In addition if the
1.71 + /// the \c _sortByLabel is true then the writer will write the edges
1.72 + /// sorted by the labels.
1.73 NodeSetWriter(LemonWriter& _writer, const Graph& _graph,
1.74 const std::string& _name = std::string(),
1.75 - bool _forceLabelMap = true)
1.76 + bool _forceLabelMap = true, bool _sortByLabel = true)
1.77 : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
1.78 - graph(_graph), name(_name) {}
1.79 + sortByLabel(_sortByLabel), graph(_graph), name(_name) {}
1.80
1.81 /// \brief Destructor.
1.82 ///
1.83 @@ -477,6 +511,20 @@
1.84 break;
1.85 }
1.86 }
1.87 + std::vector<Node> items;
1.88 + for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
1.89 + items.push_back(it);
1.90 + }
1.91 + if (sortByLabel) {
1.92 + if (labelMap) {
1.93 + labelMap->sortByMap(items);
1.94 + } else {
1.95 + typedef IdMap<Graph, Node> Map;
1.96 + Map map(graph);
1.97 + _writer_bits::ComposeLess<Map> less(map);
1.98 + std::sort(items.begin(), items.end(), less);
1.99 + }
1.100 + }
1.101 if (forceLabelMap) {
1.102 os << "label\t";
1.103 }
1.104 @@ -484,12 +532,13 @@
1.105 os << writers[i].first << '\t';
1.106 }
1.107 os << std::endl;
1.108 - for (typename Graph::NodeIt it(graph); it != INVALID; ++it) {
1.109 + for (typename std::vector<Node>::iterator it = items.begin();
1.110 + it != items.end(); ++it) {
1.111 if (forceLabelMap) {
1.112 - os << graph.id(it) << '\t';
1.113 + os << graph.id(*it) << '\t';
1.114 }
1.115 for (int i = 0; i < (int)writers.size(); ++i) {
1.116 - writers[i].second->write(os, it);
1.117 + writers[i].second->write(os, *it);
1.118 os << '\t';
1.119 }
1.120 os << std::endl;
1.121 @@ -529,6 +578,7 @@
1.122
1.123 _writer_bits::MapWriterBase<Node>* labelMap;
1.124 bool forceLabelMap;
1.125 + bool sortByLabel;
1.126
1.127 const Graph& graph;
1.128 std::string name;
1.129 @@ -551,7 +601,9 @@
1.130 /// as label map. This map should contain only unique values and when the
1.131 /// \c writeLabel() member will be called with an edge it will write it's
1.132 /// label. Otherwise if the \c _forceLabelMap constructor parameter is true
1.133 - /// then the label map will be the id in the graph.
1.134 + /// then the label map will be the id in the graph. In addition if the
1.135 + /// the \c _sortByLabel is true then the writer will write the edges
1.136 + /// sorted by the labels.
1.137 ///
1.138 /// The edgeset writer needs a node label writer to identify which nodes
1.139 /// have to be connected. If a NodeSetWriter can write the nodes' label,
1.140 @@ -570,18 +622,20 @@
1.141
1.142 /// \brief Constructor.
1.143 ///
1.144 - /// Constructor for EdgeSetWriter. It creates the EdgeSetWriter and
1.145 - /// attach it into the given LemonWriter. It will write node labels by
1.146 - /// the \c _nodeLabelWriter. If the \c _forceLabelMap parameter is true
1.147 - /// then the writer will write own label map if the user does not give
1.148 - /// "label" named map.
1.149 + /// Constructor for EdgeSetWriter. It creates the EdgeSetWriter
1.150 + /// and attach it into the given LemonWriter. It will write node
1.151 + /// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap
1.152 + /// parameter is true then the writer will write own label map if
1.153 + /// the user does not give "label" named map. In addition if the
1.154 + /// the \c _sortByLabel is true then the writer will write the
1.155 + /// edges sorted by the labels.
1.156 template <typename NodeLabelWriter>
1.157 EdgeSetWriter(LemonWriter& _writer, const Graph& _graph,
1.158 const NodeLabelWriter& _nodeLabelWriter,
1.159 const std::string& _name = std::string(),
1.160 - bool _forceLabelMap = true)
1.161 + bool _forceLabelMap = true, bool _sortByLabel = true)
1.162 : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
1.163 - graph(_graph), name(_name) {
1.164 + sortByLabel(_sortByLabel), graph(_graph), name(_name) {
1.165 checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();
1.166 nodeLabelWriter.reset(new _writer_bits::
1.167 LabelWriter<Node, NodeLabelWriter>(_nodeLabelWriter));
1.168 @@ -649,6 +703,20 @@
1.169 break;
1.170 }
1.171 }
1.172 + std::vector<Edge> items;
1.173 + for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
1.174 + items.push_back(it);
1.175 + }
1.176 + if (sortByLabel) {
1.177 + if (labelMap) {
1.178 + labelMap->sortByMap(items);
1.179 + } else {
1.180 + typedef IdMap<Graph, Edge> Map;
1.181 + Map map(graph);
1.182 + _writer_bits::ComposeLess<Map> less(map);
1.183 + std::sort(items.begin(), items.end(), less);
1.184 + }
1.185 + }
1.186 os << "\t\t";
1.187 if (forceLabelMap) {
1.188 os << "label\t";
1.189 @@ -657,16 +725,17 @@
1.190 os << writers[i].first << '\t';
1.191 }
1.192 os << std::endl;
1.193 - for (typename Graph::EdgeIt it(graph); it != INVALID; ++it) {
1.194 - nodeLabelWriter->write(os, graph.source(it));
1.195 + for (typename std::vector<Edge>::iterator it = items.begin();
1.196 + it != items.end(); ++it) {
1.197 + nodeLabelWriter->write(os, graph.source(*it));
1.198 os << '\t';
1.199 - nodeLabelWriter->write(os, graph.target(it));
1.200 + nodeLabelWriter->write(os, graph.target(*it));
1.201 os << '\t';
1.202 if (forceLabelMap) {
1.203 - os << graph.id(it) << '\t';
1.204 + os << graph.id(*it) << '\t';
1.205 }
1.206 for (int i = 0; i < (int)writers.size(); ++i) {
1.207 - writers[i].second->write(os, it);
1.208 + writers[i].second->write(os, *it);
1.209 os << '\t';
1.210 }
1.211 os << std::endl;
1.212 @@ -706,6 +775,7 @@
1.213
1.214 _writer_bits::MapWriterBase<Edge>* labelMap;
1.215 bool forceLabelMap;
1.216 + bool sortByLabel;
1.217
1.218 const Graph& graph;
1.219 std::string name;
1.220 @@ -731,11 +801,14 @@
1.221 /// is near the same just with a prefix \c '+' or \c '-' character
1.222 /// difference.
1.223 ///
1.224 - /// If the edgeset contains an \c "label" named map then it will be regarded
1.225 - /// as label map. This map should contain only unique values and when the
1.226 - /// \c writeLabel() member will be called with an undirected edge it will
1.227 - /// write it's label. Otherwise if the \c _forceLabelMap constructor
1.228 - /// parameter is true then the label map will be the id in the graph.
1.229 + /// If the edgeset contains an \c "label" named map then it will be
1.230 + /// regarded as label map. This map should contain only unique
1.231 + /// values and when the \c writeLabel() member will be called with
1.232 + /// an undirected edge it will write it's label. Otherwise if the \c
1.233 + /// _forceLabelMap constructor parameter is true then the label map
1.234 + /// will be the id in the graph. In addition if the the \c
1.235 + /// _sortByLabel is true then the writer will write the edges sorted
1.236 + /// by the labels.
1.237 ///
1.238 /// The undirected edgeset writer needs a node label writer to identify
1.239 /// which nodes have to be connected. If a NodeSetWriter can write the
1.240 @@ -756,17 +829,19 @@
1.241 /// \brief Constructor.
1.242 ///
1.243 /// Constructor for UEdgeSetWriter. It creates the UEdgeSetWriter
1.244 - /// and attach it into the given LemonWriter. It will write node labels by
1.245 - /// the \c _nodeLabelWriter. If the \c _forceLabelMap parameter is true
1.246 - /// then the writer will write own label map if the user does not give
1.247 - /// "label" named map.
1.248 + /// and attach it into the given LemonWriter. It will write node
1.249 + /// labels by the \c _nodeLabelWriter. If the \c _forceLabelMap
1.250 + /// parameter is true then the writer will write own label map if
1.251 + /// the user does not give "label" named map. In addition if the
1.252 + /// the \c _sortByLabel is true then the writer will write the
1.253 + /// edges sorted by the labels.
1.254 template <typename NodeLabelWriter>
1.255 UEdgeSetWriter(LemonWriter& _writer, const Graph& _graph,
1.256 const NodeLabelWriter& _nodeLabelWriter,
1.257 const std::string& _name = std::string(),
1.258 - bool _forceLabelMap = true)
1.259 + bool _forceLabelMap = true, bool _sortByLabel = true)
1.260 : Parent(_writer), labelMap(0), forceLabelMap(_forceLabelMap),
1.261 - graph(_graph), name(_name) {
1.262 + sortByLabel(_sortByLabel), graph(_graph), name(_name) {
1.263 checkConcept<_writer_bits::ItemLabelWriter<Node>, NodeLabelWriter>();
1.264 nodeLabelWriter.reset(new _writer_bits::
1.265 LabelWriter<Node, NodeLabelWriter>(_nodeLabelWriter));
1.266 @@ -858,6 +933,20 @@
1.267 break;
1.268 }
1.269 }
1.270 + std::vector<UEdge> items;
1.271 + for (typename Graph::UEdgeIt it(graph); it != INVALID; ++it) {
1.272 + items.push_back(it);
1.273 + }
1.274 + if (sortByLabel) {
1.275 + if (labelMap) {
1.276 + labelMap->sortByMap(items);
1.277 + } else {
1.278 + typedef IdMap<Graph, UEdge> Map;
1.279 + Map map(graph);
1.280 + _writer_bits::ComposeLess<Map> less(map);
1.281 + std::sort(items.begin(), items.end(), less);
1.282 + }
1.283 + }
1.284 os << "\t\t";
1.285 if (forceLabelMap) {
1.286 os << "label\t";
1.287 @@ -866,16 +955,17 @@
1.288 os << writers[i].first << '\t';
1.289 }
1.290 os << std::endl;
1.291 - for (typename Graph::UEdgeIt it(graph); it != INVALID; ++it) {
1.292 - nodeLabelWriter->write(os, graph.source(it));
1.293 + for (typename std::vector<Edge>::iterator it = items.begin();
1.294 + it != items.end(); ++it) {
1.295 + nodeLabelWriter->write(os, graph.source(*it));
1.296 os << '\t';
1.297 - nodeLabelWriter->write(os, graph.target(it));
1.298 + nodeLabelWriter->write(os, graph.target(*it));
1.299 os << '\t';
1.300 if (forceLabelMap) {
1.301 - os << graph.id(it) << '\t';
1.302 + os << graph.id(*it) << '\t';
1.303 }
1.304 for (int i = 0; i < (int)writers.size(); ++i) {
1.305 - writers[i].second->write(os, it);
1.306 + writers[i].second->write(os, *it);
1.307 os << '\t';
1.308 }
1.309 os << std::endl;
1.310 @@ -936,6 +1026,7 @@
1.311
1.312 _writer_bits::MapWriterBase<UEdge>* labelMap;
1.313 bool forceLabelMap;
1.314 + bool sortByLabel;
1.315
1.316 const Graph& graph;
1.317 std::string name;