1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/lgf_writer.h Thu Apr 17 15:18:45 2008 +0100
1.3 @@ -0,0 +1,627 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +///\ingroup lemon_io
1.23 +///\file
1.24 +///\brief Lemon Graph Format writer.
1.25 +
1.26 +
1.27 +#ifndef LEMON_LGF_WRITER_H
1.28 +#define LEMON_LGF_WRITER_H
1.29 +
1.30 +#include <iostream>
1.31 +#include <fstream>
1.32 +#include <sstream>
1.33 +
1.34 +#include <algorithm>
1.35 +
1.36 +#include <vector>
1.37 +#include <functional>
1.38 +
1.39 +#include <lemon/assert.h>
1.40 +#include <lemon/graph_utils.h>
1.41 +
1.42 +namespace lemon {
1.43 +
1.44 + namespace _writer_bits {
1.45 +
1.46 + template <typename Value>
1.47 + struct DefaultConverter {
1.48 + std::string operator()(const Value& value) {
1.49 + std::ostringstream os;
1.50 + os << value;
1.51 + return os.str();
1.52 + }
1.53 + };
1.54 +
1.55 + template <typename T>
1.56 + bool operator<(const T&, const T&) {
1.57 + throw DataFormatError("Label map is not comparable");
1.58 + }
1.59 +
1.60 + template <typename _Map>
1.61 + class MapLess {
1.62 + public:
1.63 + typedef _Map Map;
1.64 + typedef typename Map::Key Item;
1.65 +
1.66 + private:
1.67 + const Map& _map;
1.68 +
1.69 + public:
1.70 + MapLess(const Map& map) : _map(map) {}
1.71 +
1.72 + bool operator()(const Item& left, const Item& right) {
1.73 + return _map[left] < _map[right];
1.74 + }
1.75 + };
1.76 +
1.77 + template <typename _Item>
1.78 + class MapStorageBase {
1.79 + public:
1.80 + typedef _Item Item;
1.81 +
1.82 + public:
1.83 + MapStorageBase() {}
1.84 + virtual ~MapStorageBase() {}
1.85 +
1.86 + virtual std::string get(const Item& item) = 0;
1.87 + virtual void sort(std::vector<Item>&) = 0;
1.88 + };
1.89 +
1.90 + template <typename _Item, typename _Map,
1.91 + typename _Converter = DefaultConverter<typename _Map::Value> >
1.92 + class MapStorage : public MapStorageBase<_Item> {
1.93 + public:
1.94 + typedef _Map Map;
1.95 + typedef _Converter Converter;
1.96 + typedef _Item Item;
1.97 +
1.98 + private:
1.99 + const Map& _map;
1.100 + Converter _converter;
1.101 +
1.102 + public:
1.103 + MapStorage(const Map& map, const Converter& converter = Converter())
1.104 + : _map(map), _converter(converter) {}
1.105 + virtual ~MapStorage() {}
1.106 +
1.107 + virtual std::string get(const Item& item) {
1.108 + return _converter(_map[item]);
1.109 + }
1.110 + virtual void sort(std::vector<Item>& items) {
1.111 + MapLess<Map> less(_map);
1.112 + std::sort(items.begin(), items.end(), less);
1.113 + }
1.114 + };
1.115 +
1.116 + class ValueStorageBase {
1.117 + public:
1.118 + ValueStorageBase() {}
1.119 + virtual ~ValueStorageBase() {}
1.120 +
1.121 + virtual std::string get() = 0;
1.122 + };
1.123 +
1.124 + template <typename _Value, typename _Converter = DefaultConverter<_Value> >
1.125 + class ValueStorage : public ValueStorageBase {
1.126 + public:
1.127 + typedef _Value Value;
1.128 + typedef _Converter Converter;
1.129 +
1.130 + private:
1.131 + const Value& _value;
1.132 + Converter _converter;
1.133 +
1.134 + public:
1.135 + ValueStorage(const Value& value, const Converter& converter = Converter())
1.136 + : _value(value), _converter(converter) {}
1.137 +
1.138 + virtual std::string get() {
1.139 + return _converter(_value);
1.140 + }
1.141 + };
1.142 +
1.143 + template <typename Value>
1.144 + struct MapLookUpConverter {
1.145 + const std::map<Value, std::string>& _map;
1.146 +
1.147 + MapLookUpConverter(const std::map<Value, std::string>& map)
1.148 + : _map(map) {}
1.149 +
1.150 + std::string operator()(const Value& str) {
1.151 + typename std::map<Value, std::string>::const_iterator it =
1.152 + _map.find(str);
1.153 + if (it == _map.end()) {
1.154 + throw DataFormatError("Item not found");
1.155 + }
1.156 + return it->second;
1.157 + }
1.158 + };
1.159 +
1.160 + bool isWhiteSpace(char c) {
1.161 + return c == ' ' || c == '\t' || c == '\v' ||
1.162 + c == '\n' || c == '\r' || c == '\f';
1.163 + }
1.164 +
1.165 + bool isEscaped(char c) {
1.166 + return c == '\\' || c == '\"' || c == '\'' ||
1.167 + c == '\a' || c == '\b';
1.168 + }
1.169 +
1.170 + static void writeEscape(std::ostream& os, char c) {
1.171 + switch (c) {
1.172 + case '\\':
1.173 + os << "\\\\";
1.174 + return;
1.175 + case '\"':
1.176 + os << "\\\"";
1.177 + return;
1.178 + case '\a':
1.179 + os << "\\a";
1.180 + return;
1.181 + case '\b':
1.182 + os << "\\b";
1.183 + return;
1.184 + case '\f':
1.185 + os << "\\f";
1.186 + return;
1.187 + case '\r':
1.188 + os << "\\r";
1.189 + return;
1.190 + case '\n':
1.191 + os << "\\n";
1.192 + return;
1.193 + case '\t':
1.194 + os << "\\t";
1.195 + return;
1.196 + case '\v':
1.197 + os << "\\v";
1.198 + return;
1.199 + default:
1.200 + if (c < 0x20) {
1.201 + os << '\\' << std::oct << static_cast<int>(c);
1.202 + } else {
1.203 + os << c;
1.204 + }
1.205 + return;
1.206 + }
1.207 + }
1.208 +
1.209 + bool requireEscape(const std::string& str) {
1.210 + std::istringstream is(str);
1.211 + char c;
1.212 + while (is.get(c)) {
1.213 + if (isWhiteSpace(c) || isEscaped(c)) {
1.214 + return true;
1.215 + }
1.216 + }
1.217 + return false;
1.218 + }
1.219 +
1.220 + std::ostream& writeToken(std::ostream& os, const std::string& str) {
1.221 +
1.222 + if (requireEscape(str)) {
1.223 + os << '\"';
1.224 + for (std::string::const_iterator it = str.begin();
1.225 + it != str.end(); ++it) {
1.226 + writeEscape(os, *it);
1.227 + }
1.228 + os << '\"';
1.229 + } else {
1.230 + os << str;
1.231 + }
1.232 + return os;
1.233 + }
1.234 +
1.235 + }
1.236 +
1.237 + /// \e
1.238 + template <typename _Digraph>
1.239 + class DigraphWriter {
1.240 + public:
1.241 +
1.242 + typedef _Digraph Digraph;
1.243 + GRAPH_TYPEDEFS(typename Digraph);
1.244 +
1.245 + private:
1.246 +
1.247 +
1.248 + std::ostream* _os;
1.249 + bool local_os;
1.250 +
1.251 + Digraph& _digraph;
1.252 +
1.253 + std::string _nodes_caption;
1.254 + std::string _arcs_caption;
1.255 + std::string _attributes_caption;
1.256 +
1.257 + typedef std::map<Node, std::string> NodeIndex;
1.258 + NodeIndex _node_index;
1.259 + typedef std::map<Arc, std::string> ArcIndex;
1.260 + ArcIndex _arc_index;
1.261 +
1.262 + typedef std::vector<std::pair<std::string,
1.263 + _writer_bits::MapStorageBase<Node>* > > NodeMaps;
1.264 + NodeMaps _node_maps;
1.265 +
1.266 + typedef std::vector<std::pair<std::string,
1.267 + _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
1.268 + ArcMaps _arc_maps;
1.269 +
1.270 + typedef std::vector<std::pair<std::string,
1.271 + _writer_bits::ValueStorageBase*> > Attributes;
1.272 + Attributes _attributes;
1.273 +
1.274 + bool _skip_nodes;
1.275 + bool _skip_arcs;
1.276 +
1.277 + public:
1.278 +
1.279 + /// \e
1.280 + DigraphWriter(std::ostream& is, Digraph& digraph)
1.281 + : _os(&is), local_os(false), _digraph(digraph),
1.282 + _skip_nodes(false), _skip_arcs(false) {}
1.283 +
1.284 + /// \e
1.285 + DigraphWriter(const std::string& fn, Digraph& digraph)
1.286 + : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
1.287 + _skip_nodes(false), _skip_arcs(false) {}
1.288 +
1.289 + /// \e
1.290 + DigraphWriter(const char* fn, Digraph& digraph)
1.291 + : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
1.292 + _skip_nodes(false), _skip_arcs(false) {}
1.293 +
1.294 + DigraphWriter(DigraphWriter& other)
1.295 + : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
1.296 + _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
1.297 +
1.298 + other.is = 0;
1.299 + other.local_os = false;
1.300 +
1.301 + _node_index.swap(other._node_index);
1.302 + _arc_index.swap(other._arc_index);
1.303 +
1.304 + _node_maps.swap(other._node_maps);
1.305 + _arc_maps.swap(other._arc_maps);
1.306 + _attributes.swap(other._attributes);
1.307 +
1.308 + _nodes_caption = other._nodes_caption;
1.309 + _arcs_caption = other._arcs_caption;
1.310 + _attributes_caption = other._attributes_caption;
1.311 + }
1.312 +
1.313 + /// \e
1.314 + ~DigraphWriter() {
1.315 + for (typename NodeMaps::iterator it = _node_maps.begin();
1.316 + it != _node_maps.end(); ++it) {
1.317 + delete it->second;
1.318 + }
1.319 +
1.320 + for (typename ArcMaps::iterator it = _arc_maps.begin();
1.321 + it != _arc_maps.end(); ++it) {
1.322 + delete it->second;
1.323 + }
1.324 +
1.325 + for (typename Attributes::iterator it = _attributes.begin();
1.326 + it != _attributes.end(); ++it) {
1.327 + delete it->second;
1.328 + }
1.329 +
1.330 + if (local_os) {
1.331 + delete _os;
1.332 + }
1.333 + }
1.334 +
1.335 + private:
1.336 +
1.337 + DigraphWriter& operator=(const DigraphWriter&);
1.338 +
1.339 + public:
1.340 +
1.341 + /// \e
1.342 + template <typename Map>
1.343 + DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
1.344 + checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1.345 + _writer_bits::MapStorageBase<Node>* storage =
1.346 + new _writer_bits::MapStorage<Node, Map>(map);
1.347 + _node_maps.push_back(std::make_pair(caption, storage));
1.348 + return *this;
1.349 + }
1.350 +
1.351 + /// \e
1.352 + template <typename Map, typename Converter>
1.353 + DigraphWriter& nodeMap(const std::string& caption, const Map& map,
1.354 + const Converter& converter = Converter()) {
1.355 + checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
1.356 + _writer_bits::MapStorageBase<Node>* storage =
1.357 + new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
1.358 + _node_maps.push_back(std::make_pair(caption, storage));
1.359 + return *this;
1.360 + }
1.361 +
1.362 + /// \e
1.363 + template <typename Map>
1.364 + DigraphWriter& arcMap(const std::string& caption, const Map& map) {
1.365 + checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1.366 + _writer_bits::MapStorageBase<Arc>* storage =
1.367 + new _writer_bits::MapStorage<Arc, Map>(map);
1.368 + _arc_maps.push_back(std::make_pair(caption, storage));
1.369 + return *this;
1.370 + }
1.371 +
1.372 + /// \e
1.373 + template <typename Map, typename Converter>
1.374 + DigraphWriter& arcMap(const std::string& caption, const Map& map,
1.375 + const Converter& converter = Converter()) {
1.376 + checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
1.377 + _writer_bits::MapStorageBase<Arc>* storage =
1.378 + new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
1.379 + _arc_maps.push_back(std::make_pair(caption, storage));
1.380 + return *this;
1.381 + }
1.382 +
1.383 + /// \e
1.384 + template <typename Value>
1.385 + DigraphWriter& attribute(const std::string& caption, const Value& value) {
1.386 + _writer_bits::ValueStorageBase* storage =
1.387 + new _writer_bits::ValueStorage<Value>(value);
1.388 + _attributes.push_back(std::make_pair(caption, storage));
1.389 + return *this;
1.390 + }
1.391 +
1.392 + /// \e
1.393 + template <typename Value, typename Converter>
1.394 + DigraphWriter& attribute(const std::string& caption, const Value& value,
1.395 + const Converter& converter = Converter()) {
1.396 + _writer_bits::ValueStorageBase* storage =
1.397 + new _writer_bits::ValueStorage<Value, Converter>(value, converter);
1.398 + _attributes.push_back(std::make_pair(caption, storage));
1.399 + return *this;
1.400 + }
1.401 +
1.402 + /// \e
1.403 + DigraphWriter& node(const std::string& caption, const Node& node) {
1.404 + typedef _writer_bits::MapLookUpConverter<Node> Converter;
1.405 + Converter converter(_node_index);
1.406 + _writer_bits::ValueStorageBase* storage =
1.407 + new _writer_bits::ValueStorage<Node, Converter>(node, converter);
1.408 + _attributes.push_back(std::make_pair(caption, storage));
1.409 + return *this;
1.410 + }
1.411 +
1.412 + /// \e
1.413 + DigraphWriter& arc(const std::string& caption, const Arc& arc) {
1.414 + typedef _writer_bits::MapLookUpConverter<Arc> Converter;
1.415 + Converter converter(_arc_index);
1.416 + _writer_bits::ValueStorageBase* storage =
1.417 + new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
1.418 + _attributes.push_back(std::make_pair(caption, storage));
1.419 + return *this;
1.420 + }
1.421 +
1.422 + /// \e
1.423 + DigraphWriter& nodes(const std::string& caption) {
1.424 + _nodes_caption = caption;
1.425 + return *this;
1.426 + }
1.427 +
1.428 + /// \e
1.429 + DigraphWriter& arcs(const std::string& caption) {
1.430 + _arcs_caption = caption;
1.431 + return *this;
1.432 + }
1.433 +
1.434 + /// \e
1.435 + DigraphWriter& attributes(const std::string& caption) {
1.436 + _attributes_caption = caption;
1.437 + return *this;
1.438 + }
1.439 +
1.440 + DigraphWriter& skipNodes() {
1.441 + LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
1.442 + return *this;
1.443 + }
1.444 +
1.445 + DigraphWriter& skipArcs() {
1.446 + LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
1.447 + return *this;
1.448 + }
1.449 +
1.450 + private:
1.451 +
1.452 + void writeNodes() {
1.453 + _writer_bits::MapStorageBase<Node>* label = 0;
1.454 + for (typename NodeMaps::iterator it = _node_maps.begin();
1.455 + it != _node_maps.end(); ++it) {
1.456 + if (it->first == "label") {
1.457 + label = it->second;
1.458 + break;
1.459 + }
1.460 + }
1.461 +
1.462 + *_os << "@nodes";
1.463 + if (!_nodes_caption.empty()) {
1.464 + *_os << ' ' << _nodes_caption;
1.465 + }
1.466 + *_os << std::endl;
1.467 +
1.468 + if (label == 0) {
1.469 + *_os << "label" << '\t';
1.470 + }
1.471 + for (typename NodeMaps::iterator it = _node_maps.begin();
1.472 + it != _node_maps.end(); ++it) {
1.473 + *_os << it->first << '\t';
1.474 + }
1.475 + *_os << std::endl;
1.476 +
1.477 + std::vector<Node> nodes;
1.478 + for (NodeIt n(_digraph); n != INVALID; ++n) {
1.479 + nodes.push_back(n);
1.480 + }
1.481 +
1.482 + if (label == 0) {
1.483 + IdMap<Digraph, Node> id_map(_digraph);
1.484 + _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
1.485 + std::sort(nodes.begin(), nodes.end(), id_less);
1.486 + } else {
1.487 + label->sort(nodes);
1.488 + }
1.489 +
1.490 + for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
1.491 + Node n = nodes[i];
1.492 + if (label == 0) {
1.493 + std::ostringstream os;
1.494 + os << _digraph.id(n);
1.495 + _writer_bits::writeToken(*_os, os.str());
1.496 + *_os << '\t';
1.497 + _node_index.insert(std::make_pair(n, os.str()));
1.498 + }
1.499 + for (typename NodeMaps::iterator it = _node_maps.begin();
1.500 + it != _node_maps.end(); ++it) {
1.501 + std::string value = it->second->get(n);
1.502 + _writer_bits::writeToken(*_os, value);
1.503 + if (it->first == "label") {
1.504 + _node_index.insert(std::make_pair(n, value));
1.505 + }
1.506 + *_os << '\t';
1.507 + }
1.508 + *_os << std::endl;
1.509 + }
1.510 + }
1.511 +
1.512 + void writeArcs() {
1.513 + _writer_bits::MapStorageBase<Arc>* label = 0;
1.514 + for (typename ArcMaps::iterator it = _arc_maps.begin();
1.515 + it != _arc_maps.end(); ++it) {
1.516 + if (it->first == "label") {
1.517 + label = it->second;
1.518 + break;
1.519 + }
1.520 + }
1.521 +
1.522 + *_os << "@arcs";
1.523 + if (!_arcs_caption.empty()) {
1.524 + *_os << ' ' << _arcs_caption;
1.525 + }
1.526 + *_os << std::endl;
1.527 +
1.528 + *_os << '\t' << '\t';
1.529 + if (label == 0) {
1.530 + *_os << "label" << '\t';
1.531 + }
1.532 + for (typename ArcMaps::iterator it = _arc_maps.begin();
1.533 + it != _arc_maps.end(); ++it) {
1.534 + *_os << it->first << '\t';
1.535 + }
1.536 + *_os << std::endl;
1.537 +
1.538 + std::vector<Arc> arcs;
1.539 + for (ArcIt n(_digraph); n != INVALID; ++n) {
1.540 + arcs.push_back(n);
1.541 + }
1.542 +
1.543 + if (label == 0) {
1.544 + IdMap<Digraph, Arc> id_map(_digraph);
1.545 + _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
1.546 + std::sort(arcs.begin(), arcs.end(), id_less);
1.547 + } else {
1.548 + label->sort(arcs);
1.549 + }
1.550 +
1.551 + for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
1.552 + Arc a = arcs[i];
1.553 + _writer_bits::writeToken(*_os, _node_index.
1.554 + find(_digraph.source(a))->second);
1.555 + *_os << '\t';
1.556 + _writer_bits::writeToken(*_os, _node_index.
1.557 + find(_digraph.target(a))->second);
1.558 + *_os << '\t';
1.559 + if (label == 0) {
1.560 + std::ostringstream os;
1.561 + os << _digraph.id(a);
1.562 + _writer_bits::writeToken(*_os, os.str());
1.563 + *_os << '\t';
1.564 + _arc_index.insert(std::make_pair(a, os.str()));
1.565 + }
1.566 + for (typename ArcMaps::iterator it = _arc_maps.begin();
1.567 + it != _arc_maps.end(); ++it) {
1.568 + std::string value = it->second->get(a);
1.569 + _writer_bits::writeToken(*_os, value);
1.570 + if (it->first == "label") {
1.571 + _arc_index.insert(std::make_pair(a, value));
1.572 + }
1.573 + *_os << '\t';
1.574 + }
1.575 + *_os << std::endl;
1.576 + }
1.577 + }
1.578 +
1.579 + void writeAttributes() {
1.580 + if (_attributes.empty()) return;
1.581 + *_os << "@attributes";
1.582 + if (!_attributes_caption.empty()) {
1.583 + *_os << ' ' << _attributes_caption;
1.584 + }
1.585 + *_os << std::endl;
1.586 + for (typename Attributes::iterator it = _attributes.begin();
1.587 + it != _attributes.end(); ++it) {
1.588 + *_os << it->first << ' ';
1.589 + _writer_bits::writeToken(*_os, it->second->get());
1.590 + *_os << std::endl;
1.591 + }
1.592 + }
1.593 +
1.594 + public:
1.595 +
1.596 + /// \e
1.597 + void run() {
1.598 + if (!_skip_nodes) {
1.599 + writeNodes();
1.600 + }
1.601 + if (!_skip_arcs) {
1.602 + writeArcs();
1.603 + }
1.604 + writeAttributes();
1.605 + }
1.606 +
1.607 + /// \e
1.608 + std::ostream& stream() {
1.609 + return *_os;
1.610 + }
1.611 + };
1.612 +
1.613 + template <typename Digraph>
1.614 + DigraphWriter<Digraph> digraphWriter(std::istream& is, Digraph& digraph) {
1.615 + return DigraphWriter<Digraph>(is, digraph);
1.616 + }
1.617 +
1.618 + template <typename Digraph>
1.619 + DigraphWriter<Digraph> digraphWriter(const std::string& fn,
1.620 + Digraph& digraph) {
1.621 + return DigraphWriter<Digraph>(fn, digraph);
1.622 + }
1.623 +
1.624 + template <typename Digraph>
1.625 + DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
1.626 + return DigraphWriter<Digraph>(fn, digraph);
1.627 + }
1.628 +}
1.629 +
1.630 +#endif