deba@127: /* -*- C++ -*- deba@127: * deba@127: * This file is a part of LEMON, a generic C++ optimization library deba@127: * deba@127: * Copyright (C) 2003-2008 deba@127: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@127: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@127: * deba@127: * Permission to use, modify and distribute this software is granted deba@127: * provided that this copyright notice appears in all copies. For deba@127: * precise terms see the accompanying LICENSE file. deba@127: * deba@127: * This software is provided "AS IS" with no warranty of any kind, deba@127: * express or implied, and with no claim as to its suitability for any deba@127: * purpose. deba@127: * deba@127: */ deba@127: deba@127: ///\ingroup lemon_io deba@127: ///\file deba@127: ///\brief Lemon Graph Format writer. deba@127: deba@127: deba@127: #ifndef LEMON_LGF_WRITER_H deba@127: #define LEMON_LGF_WRITER_H deba@127: deba@127: #include deba@127: #include deba@127: #include deba@127: deba@127: #include deba@127: deba@127: #include deba@127: #include deba@127: deba@127: #include deba@127: #include deba@127: deba@127: namespace lemon { deba@127: deba@127: namespace _writer_bits { deba@127: deba@127: template deba@127: struct DefaultConverter { deba@127: std::string operator()(const Value& value) { deba@127: std::ostringstream os; deba@127: os << value; deba@127: return os.str(); deba@127: } deba@127: }; deba@127: deba@127: template deba@127: bool operator<(const T&, const T&) { deba@127: throw DataFormatError("Label map is not comparable"); deba@127: } deba@127: deba@127: template deba@127: class MapLess { deba@127: public: deba@127: typedef _Map Map; deba@127: typedef typename Map::Key Item; deba@127: deba@127: private: deba@127: const Map& _map; deba@127: deba@127: public: deba@127: MapLess(const Map& map) : _map(map) {} deba@127: deba@127: bool operator()(const Item& left, const Item& right) { deba@127: return _map[left] < _map[right]; deba@127: } deba@127: }; deba@127: deba@127: template deba@127: class MapStorageBase { deba@127: public: deba@127: typedef _Item Item; deba@127: deba@127: public: deba@127: MapStorageBase() {} deba@127: virtual ~MapStorageBase() {} deba@127: deba@127: virtual std::string get(const Item& item) = 0; deba@127: virtual void sort(std::vector&) = 0; deba@127: }; deba@127: deba@127: template > deba@127: class MapStorage : public MapStorageBase<_Item> { deba@127: public: deba@127: typedef _Map Map; deba@127: typedef _Converter Converter; deba@127: typedef _Item Item; deba@127: deba@127: private: deba@127: const Map& _map; deba@127: Converter _converter; deba@127: deba@127: public: deba@127: MapStorage(const Map& map, const Converter& converter = Converter()) deba@127: : _map(map), _converter(converter) {} deba@127: virtual ~MapStorage() {} deba@127: deba@127: virtual std::string get(const Item& item) { deba@127: return _converter(_map[item]); deba@127: } deba@127: virtual void sort(std::vector& items) { deba@127: MapLess less(_map); deba@127: std::sort(items.begin(), items.end(), less); deba@127: } deba@127: }; deba@127: deba@127: class ValueStorageBase { deba@127: public: deba@127: ValueStorageBase() {} deba@127: virtual ~ValueStorageBase() {} deba@127: deba@127: virtual std::string get() = 0; deba@127: }; deba@127: deba@127: template > deba@127: class ValueStorage : public ValueStorageBase { deba@127: public: deba@127: typedef _Value Value; deba@127: typedef _Converter Converter; deba@127: deba@127: private: deba@127: const Value& _value; deba@127: Converter _converter; deba@127: deba@127: public: deba@127: ValueStorage(const Value& value, const Converter& converter = Converter()) deba@127: : _value(value), _converter(converter) {} deba@127: deba@127: virtual std::string get() { deba@127: return _converter(_value); deba@127: } deba@127: }; deba@127: deba@127: template deba@127: struct MapLookUpConverter { deba@127: const std::map& _map; deba@127: deba@127: MapLookUpConverter(const std::map& map) deba@127: : _map(map) {} deba@127: deba@127: std::string operator()(const Value& str) { deba@127: typename std::map::const_iterator it = deba@127: _map.find(str); deba@127: if (it == _map.end()) { deba@127: throw DataFormatError("Item not found"); deba@127: } deba@127: return it->second; deba@127: } deba@127: }; deba@127: deba@127: bool isWhiteSpace(char c) { deba@127: return c == ' ' || c == '\t' || c == '\v' || deba@127: c == '\n' || c == '\r' || c == '\f'; deba@127: } deba@127: deba@127: bool isEscaped(char c) { deba@127: return c == '\\' || c == '\"' || c == '\'' || deba@127: c == '\a' || c == '\b'; deba@127: } deba@127: deba@127: static void writeEscape(std::ostream& os, char c) { deba@127: switch (c) { deba@127: case '\\': deba@127: os << "\\\\"; deba@127: return; deba@127: case '\"': deba@127: os << "\\\""; deba@127: return; deba@127: case '\a': deba@127: os << "\\a"; deba@127: return; deba@127: case '\b': deba@127: os << "\\b"; deba@127: return; deba@127: case '\f': deba@127: os << "\\f"; deba@127: return; deba@127: case '\r': deba@127: os << "\\r"; deba@127: return; deba@127: case '\n': deba@127: os << "\\n"; deba@127: return; deba@127: case '\t': deba@127: os << "\\t"; deba@127: return; deba@127: case '\v': deba@127: os << "\\v"; deba@127: return; deba@127: default: deba@127: if (c < 0x20) { deba@127: os << '\\' << std::oct << static_cast(c); deba@127: } else { deba@127: os << c; deba@127: } deba@127: return; deba@127: } deba@127: } deba@127: deba@127: bool requireEscape(const std::string& str) { deba@127: std::istringstream is(str); deba@127: char c; deba@127: while (is.get(c)) { deba@127: if (isWhiteSpace(c) || isEscaped(c)) { deba@127: return true; deba@127: } deba@127: } deba@127: return false; deba@127: } deba@127: deba@127: std::ostream& writeToken(std::ostream& os, const std::string& str) { deba@127: deba@127: if (requireEscape(str)) { deba@127: os << '\"'; deba@127: for (std::string::const_iterator it = str.begin(); deba@127: it != str.end(); ++it) { deba@127: writeEscape(os, *it); deba@127: } deba@127: os << '\"'; deba@127: } else { deba@127: os << str; deba@127: } deba@127: return os; deba@127: } deba@127: deba@127: } deba@127: deba@127: /// \e deba@127: template deba@127: class DigraphWriter { deba@127: public: deba@127: deba@127: typedef _Digraph Digraph; deba@127: GRAPH_TYPEDEFS(typename Digraph); deba@127: deba@127: private: deba@127: deba@127: deba@127: std::ostream* _os; deba@127: bool local_os; deba@127: deba@127: Digraph& _digraph; deba@127: deba@127: std::string _nodes_caption; deba@127: std::string _arcs_caption; deba@127: std::string _attributes_caption; deba@127: deba@127: typedef std::map NodeIndex; deba@127: NodeIndex _node_index; deba@127: typedef std::map ArcIndex; deba@127: ArcIndex _arc_index; deba@127: deba@127: typedef std::vector* > > NodeMaps; deba@127: NodeMaps _node_maps; deba@127: deba@127: typedef std::vector* > >ArcMaps; deba@127: ArcMaps _arc_maps; deba@127: deba@127: typedef std::vector > Attributes; deba@127: Attributes _attributes; deba@127: deba@127: bool _skip_nodes; deba@127: bool _skip_arcs; deba@127: deba@127: public: deba@127: deba@127: /// \e deba@127: DigraphWriter(std::ostream& is, Digraph& digraph) deba@127: : _os(&is), local_os(false), _digraph(digraph), deba@127: _skip_nodes(false), _skip_arcs(false) {} deba@127: deba@127: /// \e deba@127: DigraphWriter(const std::string& fn, Digraph& digraph) deba@127: : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph), deba@127: _skip_nodes(false), _skip_arcs(false) {} deba@127: deba@127: /// \e deba@127: DigraphWriter(const char* fn, Digraph& digraph) deba@127: : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph), deba@127: _skip_nodes(false), _skip_arcs(false) {} deba@127: deba@127: DigraphWriter(DigraphWriter& other) deba@127: : _os(other._os), local_os(other.local_os), _digraph(other._digraph), deba@127: _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) { deba@127: deba@127: other.is = 0; deba@127: other.local_os = false; deba@127: deba@127: _node_index.swap(other._node_index); deba@127: _arc_index.swap(other._arc_index); deba@127: deba@127: _node_maps.swap(other._node_maps); deba@127: _arc_maps.swap(other._arc_maps); deba@127: _attributes.swap(other._attributes); deba@127: deba@127: _nodes_caption = other._nodes_caption; deba@127: _arcs_caption = other._arcs_caption; deba@127: _attributes_caption = other._attributes_caption; deba@127: } deba@127: deba@127: /// \e deba@127: ~DigraphWriter() { deba@127: for (typename NodeMaps::iterator it = _node_maps.begin(); deba@127: it != _node_maps.end(); ++it) { deba@127: delete it->second; deba@127: } deba@127: deba@127: for (typename ArcMaps::iterator it = _arc_maps.begin(); deba@127: it != _arc_maps.end(); ++it) { deba@127: delete it->second; deba@127: } deba@127: deba@127: for (typename Attributes::iterator it = _attributes.begin(); deba@127: it != _attributes.end(); ++it) { deba@127: delete it->second; deba@127: } deba@127: deba@127: if (local_os) { deba@127: delete _os; deba@127: } deba@127: } deba@127: deba@127: private: deba@127: deba@127: DigraphWriter& operator=(const DigraphWriter&); deba@127: deba@127: public: deba@127: deba@127: /// \e deba@127: template deba@127: DigraphWriter& nodeMap(const std::string& caption, const Map& map) { deba@127: checkConcept, Map>(); deba@127: _writer_bits::MapStorageBase* storage = deba@127: new _writer_bits::MapStorage(map); deba@127: _node_maps.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: template deba@127: DigraphWriter& nodeMap(const std::string& caption, const Map& map, deba@127: const Converter& converter = Converter()) { deba@127: checkConcept, Map>(); deba@127: _writer_bits::MapStorageBase* storage = deba@127: new _writer_bits::MapStorage(map, converter); deba@127: _node_maps.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: template deba@127: DigraphWriter& arcMap(const std::string& caption, const Map& map) { deba@127: checkConcept, Map>(); deba@127: _writer_bits::MapStorageBase* storage = deba@127: new _writer_bits::MapStorage(map); deba@127: _arc_maps.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: template deba@127: DigraphWriter& arcMap(const std::string& caption, const Map& map, deba@127: const Converter& converter = Converter()) { deba@127: checkConcept, Map>(); deba@127: _writer_bits::MapStorageBase* storage = deba@127: new _writer_bits::MapStorage(map, converter); deba@127: _arc_maps.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: template deba@127: DigraphWriter& attribute(const std::string& caption, const Value& value) { deba@127: _writer_bits::ValueStorageBase* storage = deba@127: new _writer_bits::ValueStorage(value); deba@127: _attributes.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: template deba@127: DigraphWriter& attribute(const std::string& caption, const Value& value, deba@127: const Converter& converter = Converter()) { deba@127: _writer_bits::ValueStorageBase* storage = deba@127: new _writer_bits::ValueStorage(value, converter); deba@127: _attributes.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: DigraphWriter& node(const std::string& caption, const Node& node) { deba@127: typedef _writer_bits::MapLookUpConverter Converter; deba@127: Converter converter(_node_index); deba@127: _writer_bits::ValueStorageBase* storage = deba@127: new _writer_bits::ValueStorage(node, converter); deba@127: _attributes.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: DigraphWriter& arc(const std::string& caption, const Arc& arc) { deba@127: typedef _writer_bits::MapLookUpConverter Converter; deba@127: Converter converter(_arc_index); deba@127: _writer_bits::ValueStorageBase* storage = deba@127: new _writer_bits::ValueStorage(arc, converter); deba@127: _attributes.push_back(std::make_pair(caption, storage)); deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: DigraphWriter& nodes(const std::string& caption) { deba@127: _nodes_caption = caption; deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: DigraphWriter& arcs(const std::string& caption) { deba@127: _arcs_caption = caption; deba@127: return *this; deba@127: } deba@127: deba@127: /// \e deba@127: DigraphWriter& attributes(const std::string& caption) { deba@127: _attributes_caption = caption; deba@127: return *this; deba@127: } deba@127: deba@127: DigraphWriter& skipNodes() { deba@127: LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member"); deba@127: return *this; deba@127: } deba@127: deba@127: DigraphWriter& skipArcs() { deba@127: LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member"); deba@127: return *this; deba@127: } deba@127: deba@127: private: deba@127: deba@127: void writeNodes() { deba@127: _writer_bits::MapStorageBase* label = 0; deba@127: for (typename NodeMaps::iterator it = _node_maps.begin(); deba@127: it != _node_maps.end(); ++it) { deba@127: if (it->first == "label") { deba@127: label = it->second; deba@127: break; deba@127: } deba@127: } deba@127: deba@127: *_os << "@nodes"; deba@127: if (!_nodes_caption.empty()) { deba@127: *_os << ' ' << _nodes_caption; deba@127: } deba@127: *_os << std::endl; deba@127: deba@127: if (label == 0) { deba@127: *_os << "label" << '\t'; deba@127: } deba@127: for (typename NodeMaps::iterator it = _node_maps.begin(); deba@127: it != _node_maps.end(); ++it) { deba@127: *_os << it->first << '\t'; deba@127: } deba@127: *_os << std::endl; deba@127: deba@127: std::vector nodes; deba@127: for (NodeIt n(_digraph); n != INVALID; ++n) { deba@127: nodes.push_back(n); deba@127: } deba@127: deba@127: if (label == 0) { deba@127: IdMap id_map(_digraph); deba@127: _writer_bits::MapLess > id_less(id_map); deba@127: std::sort(nodes.begin(), nodes.end(), id_less); deba@127: } else { deba@127: label->sort(nodes); deba@127: } deba@127: deba@127: for (int i = 0; i < static_cast(nodes.size()); ++i) { deba@127: Node n = nodes[i]; deba@127: if (label == 0) { deba@127: std::ostringstream os; deba@127: os << _digraph.id(n); deba@127: _writer_bits::writeToken(*_os, os.str()); deba@127: *_os << '\t'; deba@127: _node_index.insert(std::make_pair(n, os.str())); deba@127: } deba@127: for (typename NodeMaps::iterator it = _node_maps.begin(); deba@127: it != _node_maps.end(); ++it) { deba@127: std::string value = it->second->get(n); deba@127: _writer_bits::writeToken(*_os, value); deba@127: if (it->first == "label") { deba@127: _node_index.insert(std::make_pair(n, value)); deba@127: } deba@127: *_os << '\t'; deba@127: } deba@127: *_os << std::endl; deba@127: } deba@127: } deba@127: deba@127: void writeArcs() { deba@127: _writer_bits::MapStorageBase* label = 0; deba@127: for (typename ArcMaps::iterator it = _arc_maps.begin(); deba@127: it != _arc_maps.end(); ++it) { deba@127: if (it->first == "label") { deba@127: label = it->second; deba@127: break; deba@127: } deba@127: } deba@127: deba@127: *_os << "@arcs"; deba@127: if (!_arcs_caption.empty()) { deba@127: *_os << ' ' << _arcs_caption; deba@127: } deba@127: *_os << std::endl; deba@127: deba@127: *_os << '\t' << '\t'; deba@127: if (label == 0) { deba@127: *_os << "label" << '\t'; deba@127: } deba@127: for (typename ArcMaps::iterator it = _arc_maps.begin(); deba@127: it != _arc_maps.end(); ++it) { deba@127: *_os << it->first << '\t'; deba@127: } deba@127: *_os << std::endl; deba@127: deba@127: std::vector arcs; deba@127: for (ArcIt n(_digraph); n != INVALID; ++n) { deba@127: arcs.push_back(n); deba@127: } deba@127: deba@127: if (label == 0) { deba@127: IdMap id_map(_digraph); deba@127: _writer_bits::MapLess > id_less(id_map); deba@127: std::sort(arcs.begin(), arcs.end(), id_less); deba@127: } else { deba@127: label->sort(arcs); deba@127: } deba@127: deba@127: for (int i = 0; i < static_cast(arcs.size()); ++i) { deba@127: Arc a = arcs[i]; deba@127: _writer_bits::writeToken(*_os, _node_index. deba@127: find(_digraph.source(a))->second); deba@127: *_os << '\t'; deba@127: _writer_bits::writeToken(*_os, _node_index. deba@127: find(_digraph.target(a))->second); deba@127: *_os << '\t'; deba@127: if (label == 0) { deba@127: std::ostringstream os; deba@127: os << _digraph.id(a); deba@127: _writer_bits::writeToken(*_os, os.str()); deba@127: *_os << '\t'; deba@127: _arc_index.insert(std::make_pair(a, os.str())); deba@127: } deba@127: for (typename ArcMaps::iterator it = _arc_maps.begin(); deba@127: it != _arc_maps.end(); ++it) { deba@127: std::string value = it->second->get(a); deba@127: _writer_bits::writeToken(*_os, value); deba@127: if (it->first == "label") { deba@127: _arc_index.insert(std::make_pair(a, value)); deba@127: } deba@127: *_os << '\t'; deba@127: } deba@127: *_os << std::endl; deba@127: } deba@127: } deba@127: deba@127: void writeAttributes() { deba@127: if (_attributes.empty()) return; deba@127: *_os << "@attributes"; deba@127: if (!_attributes_caption.empty()) { deba@127: *_os << ' ' << _attributes_caption; deba@127: } deba@127: *_os << std::endl; deba@127: for (typename Attributes::iterator it = _attributes.begin(); deba@127: it != _attributes.end(); ++it) { deba@127: *_os << it->first << ' '; deba@127: _writer_bits::writeToken(*_os, it->second->get()); deba@127: *_os << std::endl; deba@127: } deba@127: } deba@127: deba@127: public: deba@127: deba@127: /// \e deba@127: void run() { deba@127: if (!_skip_nodes) { deba@127: writeNodes(); deba@127: } deba@127: if (!_skip_arcs) { deba@127: writeArcs(); deba@127: } deba@127: writeAttributes(); deba@127: } deba@127: deba@127: /// \e deba@127: std::ostream& stream() { deba@127: return *_os; deba@127: } deba@127: }; deba@127: deba@127: template deba@127: DigraphWriter digraphWriter(std::istream& is, Digraph& digraph) { deba@127: return DigraphWriter(is, digraph); deba@127: } deba@127: deba@127: template deba@127: DigraphWriter digraphWriter(const std::string& fn, deba@127: Digraph& digraph) { deba@127: return DigraphWriter(fn, digraph); deba@127: } deba@127: deba@127: template deba@127: DigraphWriter digraphWriter(const char* fn, Digraph& digraph) { deba@127: return DigraphWriter(fn, digraph); deba@127: } deba@127: } deba@127: deba@127: #endif