1.1 --- a/demo/Makefile.am Mon Apr 14 10:46:41 2008 +0200
1.2 +++ b/demo/Makefile.am Thu Apr 17 15:18:45 2008 +0100
1.3 @@ -4,9 +4,11 @@
1.4 if WANT_DEMO
1.5
1.6 noinst_PROGRAMS += \
1.7 - demo/arg_parser_demo
1.8 + demo/arg_parser_demo \
1.9 + demo/lgf_demo
1.10
1.11 endif WANT_DEMO
1.12
1.13 demo_arg_parser_demo_SOURCES = demo/arg_parser_demo.cc
1.14 +demo_lgf_demo_SOURCES = demo/lgf_demo.cc
1.15
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/lgf_demo.cc Thu Apr 17 15:18:45 2008 +0100
2.3 @@ -0,0 +1,153 @@
2.4 +/* -*- C++ -*-
2.5 + *
2.6 + * This file is a part of LEMON, a generic C++ optimization library
2.7 + *
2.8 + * Copyright (C) 2003-2008
2.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
2.11 + *
2.12 + * Permission to use, modify and distribute this software is granted
2.13 + * provided that this copyright notice appears in all copies. For
2.14 + * precise terms see the accompanying LICENSE file.
2.15 + *
2.16 + * This software is provided "AS IS" with no warranty of any kind,
2.17 + * express or implied, and with no claim as to its suitability for any
2.18 + * purpose.
2.19 + *
2.20 + */
2.21 +
2.22 +///\ingroup demos
2.23 +///\file
2.24 +///\brief Demonstrating graph input and output
2.25 +///
2.26 +/// This simple demo program gives an example of how to read and write
2.27 +/// a graph and additional maps (on the nodes or the edges) from/to a
2.28 +/// stream.
2.29 +///
2.30 +/// \include reader_writer_demo.cc
2.31 +
2.32 +#include <iostream>
2.33 +#include <lemon/smart_graph.h>
2.34 +#include <lemon/lgf_reader.h>
2.35 +#include <lemon/lgf_writer.h>
2.36 +#include <lemon/random.h>
2.37 +
2.38 +
2.39 +using namespace lemon;
2.40 +
2.41 +int main(int argc, const char *argv[]) {
2.42 + const int n = argc > 1 ? std::atoi(argv[1]) : 20;
2.43 + const int e = argc > 2 ? std::atoi(argv[2]) : static_cast<int>(n * log(n));
2.44 + const int m = argc > 3 ? std::atoi(argv[3]) : 100;
2.45 +
2.46 + SmartDigraph digraph;
2.47 +
2.48 + std::stringstream ss;
2.49 +
2.50 + try {
2.51 +
2.52 + typedef SmartDigraph Digraph;
2.53 + typedef Digraph::Node Node;
2.54 + typedef Digraph::Arc Arc;
2.55 + typedef Digraph::ArcIt ArcIt;
2.56 +
2.57 + typedef Digraph::NodeMap<int> PotentialMap;
2.58 + typedef Digraph::ArcMap<int> CapacityMap;
2.59 + typedef Digraph::ArcMap<std::string> NameMap;
2.60 +
2.61 + Digraph digraph;
2.62 + PotentialMap potential(digraph);
2.63 + CapacityMap capacity(digraph);
2.64 + NameMap name(digraph);
2.65 +
2.66 + std::vector<Node> nodes;
2.67 + for (int i = 0; i < n; ++i) {
2.68 + Node node = digraph.addNode();
2.69 + potential[node] = rnd[m];
2.70 + nodes.push_back(node);
2.71 + }
2.72 +
2.73 + std::vector<Arc> arcs;
2.74 + for (int i = 0; i < e; ++i) {
2.75 + int s = rnd[n];
2.76 + int t = rnd[n];
2.77 + int c = rnd[m];
2.78 + Arc arc = digraph.addArc(nodes[s], nodes[t]);
2.79 + capacity[arc] = c;
2.80 + std::ostringstream os;
2.81 + os << "arc \t" << i << std::endl;
2.82 + name[arc] = os.str();
2.83 + arcs.push_back(arc);
2.84 + }
2.85 +
2.86 +
2.87 + DigraphWriter<Digraph>(ss, digraph).
2.88 + nodeMap("potential", potential).
2.89 + arcMap("capacity", capacity).
2.90 + arcMap("name", name).
2.91 + node("source", nodes[0]).
2.92 + node("target", nodes[1]).
2.93 + arc("bottleneck", arcs[e / 2]).
2.94 + attribute("creator", "lemon library").
2.95 + run();
2.96 +
2.97 + } catch (DataFormatError& error) {
2.98 + std::cerr << error.what() << std::endl;
2.99 + }
2.100 +
2.101 + try {
2.102 +
2.103 + typedef SmartDigraph Digraph;
2.104 + typedef Digraph::Node Node;
2.105 + typedef Digraph::Arc Arc;
2.106 + typedef Digraph::ArcIt ArcIt;
2.107 +
2.108 + typedef Digraph::NodeMap<int> LabelMap;
2.109 + typedef Digraph::NodeMap<int> PotentialMap;
2.110 + typedef Digraph::ArcMap<int> CapacityMap;
2.111 + typedef Digraph::ArcMap<std::string> NameMap;
2.112 +
2.113 + Digraph digraph;
2.114 + LabelMap label(digraph);
2.115 + PotentialMap potential(digraph);
2.116 + CapacityMap capacity(digraph);
2.117 + NameMap name(digraph);
2.118 +
2.119 + Node s, t;
2.120 + Arc a;
2.121 +
2.122 + std::string creator;
2.123 +
2.124 + for (int i = 0; i < n; ++i) {
2.125 + Node node = digraph.addNode();
2.126 + label[node] = i;
2.127 + }
2.128 +
2.129 + DigraphReader<Digraph>(ss, digraph).
2.130 + useNodes(label).
2.131 + nodeMap("potential", potential).
2.132 + arcMap("capacity", capacity).
2.133 + arcMap("name", name).
2.134 + node("source", s).
2.135 + node("target", t).
2.136 + arc("bottleneck", a).
2.137 + attribute("creator", creator).
2.138 + run();
2.139 +
2.140 + DigraphWriter<Digraph>(std::cout, digraph).
2.141 + nodeMap("potential", potential).
2.142 + arcMap("capacity", capacity).
2.143 + arcMap("name", name).
2.144 + node("source", s).
2.145 + node("target", t).
2.146 + arc("bottleneck", a).
2.147 + attribute("creator", creator).
2.148 + run();
2.149 +
2.150 + } catch (DataFormatError& error) {
2.151 + std::cerr << error.what() << std::endl;
2.152 + }
2.153 +
2.154 +
2.155 + return 0;
2.156 +}
3.1 --- a/lemon/Makefile.am Mon Apr 14 10:46:41 2008 +0200
3.2 +++ b/lemon/Makefile.am Thu Apr 17 15:18:45 2008 +0100
3.3 @@ -27,6 +27,7 @@
3.4 lemon/error.h \
3.5 lemon/graph_utils.h \
3.6 lemon/kruskal.h \
3.7 + lemon/lgf_reader.h \
3.8 lemon/list_graph.h \
3.9 lemon/maps.h \
3.10 lemon/math.h \
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/lemon/lgf_reader.h Thu Apr 17 15:18:45 2008 +0100
4.3 @@ -0,0 +1,914 @@
4.4 +/* -*- C++ -*-
4.5 + *
4.6 + * This file is a part of LEMON, a generic C++ optimization library
4.7 + *
4.8 + * Copyright (C) 2003-2008
4.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
4.11 + *
4.12 + * Permission to use, modify and distribute this software is granted
4.13 + * provided that this copyright notice appears in all copies. For
4.14 + * precise terms see the accompanying LICENSE file.
4.15 + *
4.16 + * This software is provided "AS IS" with no warranty of any kind,
4.17 + * express or implied, and with no claim as to its suitability for any
4.18 + * purpose.
4.19 + *
4.20 + */
4.21 +
4.22 +///\ingroup lemon_io
4.23 +///\file
4.24 +///\brief Lemon Graph Format reader.
4.25 +
4.26 +
4.27 +#ifndef LEMON_LGF_READER_H
4.28 +#define LEMON_LGF_READER_H
4.29 +
4.30 +#include <iostream>
4.31 +#include <fstream>
4.32 +#include <sstream>
4.33 +
4.34 +#include <set>
4.35 +#include <map>
4.36 +
4.37 +#include <lemon/assert.h>
4.38 +#include <lemon/graph_utils.h>
4.39 +
4.40 +#include <lemon/lgf_writer.h>
4.41 +
4.42 +#include <lemon/concept_check.h>
4.43 +#include <lemon/concepts/maps.h>
4.44 +
4.45 +namespace lemon {
4.46 +
4.47 + namespace _reader_bits {
4.48 +
4.49 + template <typename Value>
4.50 + struct DefaultConverter {
4.51 + Value operator()(const std::string& str) {
4.52 + std::istringstream is(str);
4.53 + Value value;
4.54 + is >> value;
4.55 +
4.56 + char c;
4.57 + if (is >> std::ws >> c) {
4.58 + throw DataFormatError("Remaining characters in token");
4.59 + }
4.60 + return value;
4.61 + }
4.62 + };
4.63 +
4.64 + template <>
4.65 + struct DefaultConverter<std::string> {
4.66 + std::string operator()(const std::string& str) {
4.67 + return str;
4.68 + }
4.69 + };
4.70 +
4.71 + template <typename _Item>
4.72 + class MapStorageBase {
4.73 + public:
4.74 + typedef _Item Item;
4.75 +
4.76 + public:
4.77 + MapStorageBase() {}
4.78 + virtual ~MapStorageBase() {}
4.79 +
4.80 + virtual void set(const Item& item, const std::string& value) = 0;
4.81 +
4.82 + };
4.83 +
4.84 + template <typename _Item, typename _Map,
4.85 + typename _Converter = DefaultConverter<typename _Map::Value> >
4.86 + class MapStorage : public MapStorageBase<_Item> {
4.87 + public:
4.88 + typedef _Map Map;
4.89 + typedef _Converter Converter;
4.90 + typedef _Item Item;
4.91 +
4.92 + private:
4.93 + Map& _map;
4.94 + Converter _converter;
4.95 +
4.96 + public:
4.97 + MapStorage(Map& map, const Converter& converter = Converter())
4.98 + : _map(map), _converter(converter) {}
4.99 + virtual ~MapStorage() {}
4.100 +
4.101 + virtual void set(const Item& item ,const std::string& value) {
4.102 + _map.set(item, _converter(value));
4.103 + }
4.104 + };
4.105 +
4.106 + class ValueStorageBase {
4.107 + public:
4.108 + ValueStorageBase() {}
4.109 + virtual ~ValueStorageBase() {}
4.110 +
4.111 + virtual void set(const std::string&) = 0;
4.112 + };
4.113 +
4.114 + template <typename _Value, typename _Converter = DefaultConverter<_Value> >
4.115 + class ValueStorage : public ValueStorageBase {
4.116 + public:
4.117 + typedef _Value Value;
4.118 + typedef _Converter Converter;
4.119 +
4.120 + private:
4.121 + Value& _value;
4.122 + Converter _converter;
4.123 +
4.124 + public:
4.125 + ValueStorage(Value& value, const Converter& converter = Converter())
4.126 + : _value(value), _converter(converter) {}
4.127 +
4.128 + virtual void set(const std::string& value) {
4.129 + _value = _converter(value);
4.130 + }
4.131 + };
4.132 +
4.133 + template <typename Value>
4.134 + struct MapLookUpConverter {
4.135 + const std::map<std::string, Value>& _map;
4.136 +
4.137 + MapLookUpConverter(const std::map<std::string, Value>& map)
4.138 + : _map(map) {}
4.139 +
4.140 + Value operator()(const std::string& str) {
4.141 + typename std::map<std::string, Value>::const_iterator it =
4.142 + _map.find(str);
4.143 + if (it == _map.end()) {
4.144 + std::ostringstream msg;
4.145 + msg << "Item not found: " << str;
4.146 + throw DataFormatError(msg.str().c_str());
4.147 + }
4.148 + return it->second;
4.149 + }
4.150 + };
4.151 +
4.152 + bool isWhiteSpace(char c) {
4.153 + return c == ' ' || c == '\t' || c == '\v' ||
4.154 + c == '\n' || c == '\r' || c == '\f';
4.155 + }
4.156 +
4.157 + bool isOct(char c) {
4.158 + return '0' <= c && c <='7';
4.159 + }
4.160 +
4.161 + int valueOct(char c) {
4.162 + LEMON_ASSERT(isOct(c), "The character is not octal.");
4.163 + return c - '0';
4.164 + }
4.165 +
4.166 + bool isHex(char c) {
4.167 + return ('0' <= c && c <= '9') ||
4.168 + ('a' <= c && c <= 'z') ||
4.169 + ('A' <= c && c <= 'Z');
4.170 + }
4.171 +
4.172 + int valueHex(char c) {
4.173 + LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
4.174 + if ('0' <= c && c <= '9') return c - '0';
4.175 + if ('a' <= c && c <= 'z') return c - 'a' + 10;
4.176 + return c - 'A' + 10;
4.177 + }
4.178 +
4.179 + bool isIdentifierFirstChar(char c) {
4.180 + return ('a' <= c && c <= 'z') ||
4.181 + ('A' <= c && c <= 'Z') || c == '_';
4.182 + }
4.183 +
4.184 + bool isIdentifierChar(char c) {
4.185 + return isIdentifierFirstChar(c) ||
4.186 + ('0' <= c && c <= '9');
4.187 + }
4.188 +
4.189 + char readEscape(std::istream& is) {
4.190 + char c;
4.191 + if (!is.get(c))
4.192 + throw DataFormatError("Escape format error");
4.193 +
4.194 + switch (c) {
4.195 + case '\\':
4.196 + return '\\';
4.197 + case '\"':
4.198 + return '\"';
4.199 + case '\'':
4.200 + return '\'';
4.201 + case '\?':
4.202 + return '\?';
4.203 + case 'a':
4.204 + return '\a';
4.205 + case 'b':
4.206 + return '\b';
4.207 + case 'f':
4.208 + return '\f';
4.209 + case 'n':
4.210 + return '\n';
4.211 + case 'r':
4.212 + return '\r';
4.213 + case 't':
4.214 + return '\t';
4.215 + case 'v':
4.216 + return '\v';
4.217 + case 'x':
4.218 + {
4.219 + int code;
4.220 + if (!is.get(c) || !isHex(c))
4.221 + throw DataFormatError("Escape format error");
4.222 + else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
4.223 + else code = code * 16 + valueHex(c);
4.224 + return code;
4.225 + }
4.226 + default:
4.227 + {
4.228 + int code;
4.229 + if (!isOct(c))
4.230 + throw DataFormatError("Escape format error");
4.231 + else if (code = valueOct(c), !is.get(c) || !isOct(c))
4.232 + is.putback(c);
4.233 + else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
4.234 + is.putback(c);
4.235 + else code = code * 8 + valueOct(c);
4.236 + return code;
4.237 + }
4.238 + }
4.239 + }
4.240 +
4.241 + std::istream& readToken(std::istream& is, std::string& str) {
4.242 + std::ostringstream os;
4.243 +
4.244 + char c;
4.245 + is >> std::ws;
4.246 +
4.247 + if (!is.get(c))
4.248 + return is;
4.249 +
4.250 + if (c == '\"') {
4.251 + while (is.get(c) && c != '\"') {
4.252 + if (c == '\\')
4.253 + c = readEscape(is);
4.254 + os << c;
4.255 + }
4.256 + if (!is)
4.257 + throw DataFormatError("Quoted format error");
4.258 + } else {
4.259 + is.putback(c);
4.260 + while (is.get(c) && !isWhiteSpace(c)) {
4.261 + if (c == '\\')
4.262 + c = readEscape(is);
4.263 + os << c;
4.264 + }
4.265 + if (!is) {
4.266 + is.clear();
4.267 + } else {
4.268 + is.putback(c);
4.269 + }
4.270 + }
4.271 + str = os.str();
4.272 + return is;
4.273 + }
4.274 +
4.275 + std::istream& readIdentifier(std::istream& is, std::string& str) {
4.276 + std::ostringstream os;
4.277 +
4.278 + char c;
4.279 + is >> std::ws;
4.280 +
4.281 + if (!is.get(c))
4.282 + return is;
4.283 +
4.284 + if (!isIdentifierFirstChar(c))
4.285 + throw DataFormatError("Wrong char in identifier");
4.286 +
4.287 + os << c;
4.288 +
4.289 + while (is.get(c) && !isWhiteSpace(c)) {
4.290 + if (!isIdentifierChar(c))
4.291 + throw DataFormatError("Wrong char in identifier");
4.292 + os << c;
4.293 + }
4.294 + if (!is) is.clear();
4.295 +
4.296 + str = os.str();
4.297 + return is;
4.298 + }
4.299 +
4.300 + }
4.301 +
4.302 + /// \e
4.303 + template <typename _Digraph>
4.304 + class DigraphReader {
4.305 + public:
4.306 +
4.307 + typedef _Digraph Digraph;
4.308 + GRAPH_TYPEDEFS(typename Digraph);
4.309 +
4.310 + private:
4.311 +
4.312 +
4.313 + std::istream* _is;
4.314 + bool local_is;
4.315 +
4.316 + Digraph& _digraph;
4.317 +
4.318 + std::string _nodes_caption;
4.319 + std::string _arcs_caption;
4.320 + std::string _attributes_caption;
4.321 +
4.322 + typedef std::map<std::string, Node> NodeIndex;
4.323 + NodeIndex _node_index;
4.324 + typedef std::map<std::string, Arc> ArcIndex;
4.325 + ArcIndex _arc_index;
4.326 +
4.327 + typedef std::vector<std::pair<std::string,
4.328 + _reader_bits::MapStorageBase<Node>*> > NodeMaps;
4.329 + NodeMaps _node_maps;
4.330 +
4.331 + typedef std::vector<std::pair<std::string,
4.332 + _reader_bits::MapStorageBase<Arc>*> >ArcMaps;
4.333 + ArcMaps _arc_maps;
4.334 +
4.335 + typedef std::multimap<std::string, _reader_bits::ValueStorageBase*>
4.336 + Attributes;
4.337 + Attributes _attributes;
4.338 +
4.339 + bool _use_nodes;
4.340 + bool _use_arcs;
4.341 +
4.342 + int line_num;
4.343 + std::istringstream line;
4.344 +
4.345 + public:
4.346 +
4.347 + /// \e
4.348 + DigraphReader(std::istream& is, Digraph& digraph)
4.349 + : _is(&is), local_is(false), _digraph(digraph),
4.350 + _use_nodes(false), _use_arcs(false) {}
4.351 +
4.352 + /// \e
4.353 + DigraphReader(const std::string& fn, Digraph& digraph)
4.354 + : _is(new std::ifstream(fn.c_str())), local_is(true), _digraph(digraph),
4.355 + _use_nodes(false), _use_arcs(false) {}
4.356 +
4.357 +
4.358 + /// \e
4.359 + DigraphReader(const char* fn, Digraph& digraph)
4.360 + : _is(new std::ifstream(fn)), local_is(true), _digraph(digraph),
4.361 + _use_nodes(false), _use_arcs(false) {}
4.362 +
4.363 + /// \e
4.364 + DigraphReader(DigraphReader& other)
4.365 + : _is(other._is), local_is(other.local_is), _digraph(other._digraph),
4.366 + _use_nodes(other._use_nodes), _use_arcs(other._use_arcs) {
4.367 +
4.368 + other.is = 0;
4.369 + other.local_is = false;
4.370 +
4.371 + _node_index.swap(other._node_index);
4.372 + _arc_index.swap(other._arc_index);
4.373 +
4.374 + _node_maps.swap(other._node_maps);
4.375 + _arc_maps.swap(other._arc_maps);
4.376 + _attributes.swap(other._attributes);
4.377 +
4.378 + _nodes_caption = other._nodes_caption;
4.379 + _arcs_caption = other._arcs_caption;
4.380 + _attributes_caption = other._attributes_caption;
4.381 + }
4.382 +
4.383 + /// \e
4.384 + ~DigraphReader() {
4.385 + for (typename NodeMaps::iterator it = _node_maps.begin();
4.386 + it != _node_maps.end(); ++it) {
4.387 + delete it->second;
4.388 + }
4.389 +
4.390 + for (typename ArcMaps::iterator it = _arc_maps.begin();
4.391 + it != _arc_maps.end(); ++it) {
4.392 + delete it->second;
4.393 + }
4.394 +
4.395 + for (typename Attributes::iterator it = _attributes.begin();
4.396 + it != _attributes.end(); ++it) {
4.397 + delete it->second;
4.398 + }
4.399 +
4.400 + if (local_is) {
4.401 + delete _is;
4.402 + }
4.403 +
4.404 + }
4.405 +
4.406 + private:
4.407 +
4.408 + DigraphReader& operator=(const DigraphReader&);
4.409 +
4.410 + public:
4.411 +
4.412 + /// \e
4.413 + template <typename Map>
4.414 + DigraphReader& nodeMap(const std::string& caption, Map& map) {
4.415 + checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
4.416 + _reader_bits::MapStorageBase<Node>* storage =
4.417 + new _reader_bits::MapStorage<Node, Map>(map);
4.418 + _node_maps.push_back(std::make_pair(caption, storage));
4.419 + return *this;
4.420 + }
4.421 +
4.422 + /// \e
4.423 + template <typename Map, typename Converter>
4.424 + DigraphReader& nodeMap(const std::string& caption, Map& map,
4.425 + const Converter& converter = Converter()) {
4.426 + checkConcept<concepts::WriteMap<Node, typename Map::Value>, Map>();
4.427 + _reader_bits::MapStorageBase<Node>* storage =
4.428 + new _reader_bits::MapStorage<Node, Map, Converter>(map, converter);
4.429 + _node_maps.push_back(std::make_pair(caption, storage));
4.430 + return *this;
4.431 + }
4.432 +
4.433 + /// \e
4.434 + template <typename Map>
4.435 + DigraphReader& arcMap(const std::string& caption, Map& map) {
4.436 + checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
4.437 + _reader_bits::MapStorageBase<Arc>* storage =
4.438 + new _reader_bits::MapStorage<Arc, Map>(map);
4.439 + _arc_maps.push_back(std::make_pair(caption, storage));
4.440 + return *this;
4.441 + }
4.442 +
4.443 + /// \e
4.444 + template <typename Map, typename Converter>
4.445 + DigraphReader& arcMap(const std::string& caption, Map& map,
4.446 + const Converter& converter = Converter()) {
4.447 + checkConcept<concepts::WriteMap<Arc, typename Map::Value>, Map>();
4.448 + _reader_bits::MapStorageBase<Arc>* storage =
4.449 + new _reader_bits::MapStorage<Arc, Map, Converter>(map, converter);
4.450 + _arc_maps.push_back(std::make_pair(caption, storage));
4.451 + return *this;
4.452 + }
4.453 +
4.454 + /// \e
4.455 + template <typename Value>
4.456 + DigraphReader& attribute(const std::string& caption, Value& value) {
4.457 + _reader_bits::ValueStorageBase* storage =
4.458 + new _reader_bits::ValueStorage<Value>(value);
4.459 + _attributes.insert(std::make_pair(caption, storage));
4.460 + return *this;
4.461 + }
4.462 +
4.463 + /// \e
4.464 + template <typename Value, typename Converter>
4.465 + DigraphReader& attribute(const std::string& caption, Value& value,
4.466 + const Converter& converter = Converter()) {
4.467 + _reader_bits::ValueStorageBase* storage =
4.468 + new _reader_bits::ValueStorage<Value, Converter>(value, converter);
4.469 + _attributes.insert(std::make_pair(caption, storage));
4.470 + return *this;
4.471 + }
4.472 +
4.473 + /// \e
4.474 + DigraphReader& node(const std::string& caption, Node& node) {
4.475 + typedef _reader_bits::MapLookUpConverter<Node> Converter;
4.476 + Converter converter(_node_index);
4.477 + _reader_bits::ValueStorageBase* storage =
4.478 + new _reader_bits::ValueStorage<Node, Converter>(node, converter);
4.479 + _attributes.insert(std::make_pair(caption, storage));
4.480 + return *this;
4.481 + }
4.482 +
4.483 + /// \e
4.484 + DigraphReader& arc(const std::string& caption, Arc& arc) {
4.485 + typedef _reader_bits::MapLookUpConverter<Arc> Converter;
4.486 + Converter converter(_arc_index);
4.487 + _reader_bits::ValueStorageBase* storage =
4.488 + new _reader_bits::ValueStorage<Arc, Converter>(arc, converter);
4.489 + _attributes.insert(std::make_pair(caption, storage));
4.490 + return *this;
4.491 + }
4.492 +
4.493 + /// \e
4.494 + DigraphReader& nodes(const std::string& caption) {
4.495 + _nodes_caption = caption;
4.496 + return *this;
4.497 + }
4.498 +
4.499 + /// \e
4.500 + DigraphReader& arcs(const std::string& caption) {
4.501 + _arcs_caption = caption;
4.502 + return *this;
4.503 + }
4.504 +
4.505 + /// \e
4.506 + DigraphReader& attributes(const std::string& caption) {
4.507 + _attributes_caption = caption;
4.508 + return *this;
4.509 + }
4.510 +
4.511 + /// \e
4.512 + template <typename Map>
4.513 + DigraphReader& useNodes(const Map& map) {
4.514 + checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
4.515 + LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
4.516 + _use_nodes = true;
4.517 + _writer_bits::DefaultConverter<typename Map::Value> converter;
4.518 + for (NodeIt n(_digraph); n != INVALID; ++n) {
4.519 + _node_index.insert(std::make_pair(converter(map[n]), n));
4.520 + }
4.521 + return *this;
4.522 + }
4.523 +
4.524 + /// \e
4.525 + template <typename Map, typename Converter>
4.526 + DigraphReader& useNodes(const Map& map,
4.527 + const Converter& converter = Converter()) {
4.528 + checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
4.529 + LEMON_ASSERT(!_use_nodes, "Multiple usage of useNodes() member");
4.530 + _use_nodes = true;
4.531 + for (NodeIt n(_digraph); n != INVALID; ++n) {
4.532 + _node_index.insert(std::make_pair(converter(map[n]), n));
4.533 + }
4.534 + return *this;
4.535 + }
4.536 +
4.537 + /// \e
4.538 + template <typename Map>
4.539 + DigraphReader& useArcs(const Map& map) {
4.540 + checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
4.541 + LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
4.542 + _use_arcs = true;
4.543 + _writer_bits::DefaultConverter<typename Map::Value> converter;
4.544 + for (ArcIt a(_digraph); a != INVALID; ++a) {
4.545 + _arc_index.insert(std::make_pair(converter(map[a]), a));
4.546 + }
4.547 + return *this;
4.548 + }
4.549 +
4.550 + /// \e
4.551 + template <typename Map, typename Converter>
4.552 + DigraphReader& useArcs(const Map& map,
4.553 + const Converter& converter = Converter()) {
4.554 + checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
4.555 + LEMON_ASSERT(!_use_arcs, "Multiple usage of useArcs() member");
4.556 + _use_arcs = true;
4.557 + for (ArcIt a(_digraph); a != INVALID; ++a) {
4.558 + _arc_index.insert(std::make_pair(converter(map[a]), a));
4.559 + }
4.560 + return *this;
4.561 + }
4.562 +
4.563 + private:
4.564 +
4.565 + bool readLine() {
4.566 + std::string str;
4.567 + while(++line_num, std::getline(*_is, str)) {
4.568 + line.clear(); line.str(str);
4.569 + char c;
4.570 + if (line >> std::ws >> c && c != '#') {
4.571 + line.putback(c);
4.572 + return true;
4.573 + }
4.574 + }
4.575 + return false;
4.576 + }
4.577 +
4.578 + bool readSuccess() {
4.579 + return static_cast<bool>(*_is);
4.580 + }
4.581 +
4.582 + void skipSection() {
4.583 + char c;
4.584 + while (readSuccess() && line >> c && c != '@') {
4.585 + readLine();
4.586 + }
4.587 + line.putback(c);
4.588 + }
4.589 +
4.590 + void readNodes() {
4.591 +
4.592 + std::vector<int> map_index(_node_maps.size());
4.593 + int map_num, label_index;
4.594 +
4.595 + if (!readLine())
4.596 + throw DataFormatError("Cannot find map captions");
4.597 +
4.598 + {
4.599 + std::map<std::string, int> maps;
4.600 +
4.601 + std::string map;
4.602 + int index = 0;
4.603 + while (_reader_bits::readIdentifier(line, map)) {
4.604 + if (maps.find(map) != maps.end()) {
4.605 + std::ostringstream msg;
4.606 + msg << "Multiple occurence of node map: " << map;
4.607 + throw DataFormatError(msg.str().c_str());
4.608 + }
4.609 + maps.insert(std::make_pair(map, index));
4.610 + ++index;
4.611 + }
4.612 +
4.613 + for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
4.614 + std::map<std::string, int>::iterator jt =
4.615 + maps.find(_node_maps[i].first);
4.616 + if (jt == maps.end()) {
4.617 + std::ostringstream msg;
4.618 + msg << "Map not found in file: " << _node_maps[i].first;
4.619 + throw DataFormatError(msg.str().c_str());
4.620 + }
4.621 + map_index[i] = jt->second;
4.622 + }
4.623 +
4.624 + {
4.625 + std::map<std::string, int>::iterator jt = maps.find("label");
4.626 + if (jt == maps.end())
4.627 + throw DataFormatError("Label map not found in file");
4.628 + label_index = jt->second;
4.629 + }
4.630 + map_num = maps.size();
4.631 + }
4.632 +
4.633 + char c;
4.634 + while (readLine() && line >> c && c != '@') {
4.635 + line.putback(c);
4.636 +
4.637 + std::vector<std::string> tokens(map_num);
4.638 + for (int i = 0; i < map_num; ++i) {
4.639 + if (!_reader_bits::readToken(line, tokens[i])) {
4.640 + std::ostringstream msg;
4.641 + msg << "Column not found (" << i + 1 << ")";
4.642 + throw DataFormatError(msg.str().c_str());
4.643 + }
4.644 + }
4.645 + if (line >> std::ws >> c)
4.646 + throw DataFormatError("Extra character on the end of line");
4.647 +
4.648 + Node n;
4.649 + if (!_use_nodes) {
4.650 + n = _digraph.addNode();
4.651 + _node_index.insert(std::make_pair(tokens[label_index], n));
4.652 + } else {
4.653 + typename std::map<std::string, Node>::iterator it =
4.654 + _node_index.find(tokens[label_index]);
4.655 + if (it == _node_index.end()) {
4.656 + std::ostringstream msg;
4.657 + msg << "Node with label not found: " << tokens[label_index];
4.658 + throw DataFormatError(msg.str().c_str());
4.659 + }
4.660 + n = it->second;
4.661 + }
4.662 +
4.663 + for (int i = 0; i < static_cast<int>(_node_maps.size()); ++i) {
4.664 + _node_maps[i].second->set(n, tokens[map_index[i]]);
4.665 + }
4.666 +
4.667 + }
4.668 + if (readSuccess()) {
4.669 + line.putback(c);
4.670 + }
4.671 + }
4.672 +
4.673 + void readArcs() {
4.674 +
4.675 + std::vector<int> map_index(_arc_maps.size());
4.676 + int map_num, label_index;
4.677 +
4.678 + if (!readLine())
4.679 + throw DataFormatError("Cannot find map captions");
4.680 +
4.681 + {
4.682 + std::map<std::string, int> maps;
4.683 +
4.684 + std::string map;
4.685 + int index = 0;
4.686 + while (_reader_bits::readIdentifier(line, map)) {
4.687 + if (maps.find(map) != maps.end()) {
4.688 + std::ostringstream msg;
4.689 + msg << "Multiple occurence of arc map: " << map;
4.690 + throw DataFormatError(msg.str().c_str());
4.691 + }
4.692 + maps.insert(std::make_pair(map, index));
4.693 + ++index;
4.694 + }
4.695 +
4.696 + for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
4.697 + std::map<std::string, int>::iterator jt =
4.698 + maps.find(_arc_maps[i].first);
4.699 + if (jt == maps.end()) {
4.700 + std::ostringstream msg;
4.701 + msg << "Map not found in file: " << _arc_maps[i].first;
4.702 + throw DataFormatError(msg.str().c_str());
4.703 + }
4.704 + map_index[i] = jt->second;
4.705 + }
4.706 +
4.707 + {
4.708 + std::map<std::string, int>::iterator jt = maps.find("label");
4.709 + if (jt == maps.end())
4.710 + throw DataFormatError("Label map not found in file");
4.711 + label_index = jt->second;
4.712 + }
4.713 + map_num = maps.size();
4.714 + }
4.715 +
4.716 + char c;
4.717 + while (readLine() && line >> c && c != '@') {
4.718 + line.putback(c);
4.719 +
4.720 + std::string source_token;
4.721 + std::string target_token;
4.722 +
4.723 + if (!_reader_bits::readToken(line, source_token))
4.724 + throw DataFormatError("Source not found");
4.725 +
4.726 + if (!_reader_bits::readToken(line, target_token))
4.727 + throw DataFormatError("Source not found");
4.728 +
4.729 + std::vector<std::string> tokens(map_num);
4.730 + for (int i = 0; i < map_num; ++i) {
4.731 + if (!_reader_bits::readToken(line, tokens[i])) {
4.732 + std::ostringstream msg;
4.733 + msg << "Column not found (" << i + 1 << ")";
4.734 + throw DataFormatError(msg.str().c_str());
4.735 + }
4.736 + }
4.737 + if (line >> std::ws >> c)
4.738 + throw DataFormatError("Extra character on the end of line");
4.739 +
4.740 + Arc a;
4.741 + if (!_use_arcs) {
4.742 +
4.743 + typename NodeIndex::iterator it;
4.744 +
4.745 + it = _node_index.find(source_token);
4.746 + if (it == _node_index.end()) {
4.747 + std::ostringstream msg;
4.748 + msg << "Item not found: " << source_token;
4.749 + throw DataFormatError(msg.str().c_str());
4.750 + }
4.751 + Node source = it->second;
4.752 +
4.753 + it = _node_index.find(target_token);
4.754 + if (it == _node_index.end()) {
4.755 + std::ostringstream msg;
4.756 + msg << "Item not found: " << target_token;
4.757 + throw DataFormatError(msg.str().c_str());
4.758 + }
4.759 + Node target = it->second;
4.760 +
4.761 + a = _digraph.addArc(source, target);
4.762 + _arc_index.insert(std::make_pair(tokens[label_index], a));
4.763 + } else {
4.764 + typename std::map<std::string, Arc>::iterator it =
4.765 + _arc_index.find(tokens[label_index]);
4.766 + if (it == _arc_index.end()) {
4.767 + std::ostringstream msg;
4.768 + msg << "Arc with label not found: " << tokens[label_index];
4.769 + throw DataFormatError(msg.str().c_str());
4.770 + }
4.771 + a = it->second;
4.772 + }
4.773 +
4.774 + for (int i = 0; i < static_cast<int>(_arc_maps.size()); ++i) {
4.775 + _arc_maps[i].second->set(a, tokens[map_index[i]]);
4.776 + }
4.777 +
4.778 + }
4.779 + if (readSuccess()) {
4.780 + line.putback(c);
4.781 + }
4.782 + }
4.783 +
4.784 + void readAttributes() {
4.785 +
4.786 + std::set<std::string> read_attr;
4.787 +
4.788 + char c;
4.789 + while (readLine() && line >> c && c != '@') {
4.790 + line.putback(c);
4.791 +
4.792 + std::string attr, token;
4.793 + if (!_reader_bits::readIdentifier(line, attr))
4.794 + throw DataFormatError("Attribute name not found");
4.795 + if (!_reader_bits::readToken(line, token))
4.796 + throw DataFormatError("Attribute value not found");
4.797 + if (line >> c)
4.798 + throw DataFormatError("Extra character on the end of line");
4.799 +
4.800 + {
4.801 + std::set<std::string>::iterator it = read_attr.find(attr);
4.802 + if (it != read_attr.end()) {
4.803 + std::ostringstream msg;
4.804 + msg << "Multiple occurence of attribute " << attr;
4.805 + throw DataFormatError(msg.str().c_str());
4.806 + }
4.807 + read_attr.insert(attr);
4.808 + }
4.809 +
4.810 + {
4.811 + typename Attributes::iterator it = _attributes.lower_bound(attr);
4.812 + while (it != _attributes.end() && it->first == attr) {
4.813 + it->second->set(token);
4.814 + ++it;
4.815 + }
4.816 + }
4.817 +
4.818 + }
4.819 + if (readSuccess()) {
4.820 + line.putback(c);
4.821 + }
4.822 + for (typename Attributes::iterator it = _attributes.begin();
4.823 + it != _attributes.end(); ++it) {
4.824 + if (read_attr.find(it->first) == read_attr.end()) {
4.825 + std::ostringstream msg;
4.826 + msg << "Attribute not found in file: " << it->first;
4.827 + throw DataFormatError(msg.str().c_str());
4.828 + }
4.829 + }
4.830 + }
4.831 +
4.832 + public:
4.833 +
4.834 + /// \e
4.835 + void run() {
4.836 +
4.837 + LEMON_ASSERT(_is != 0, "This reader assigned to an other reader");
4.838 +
4.839 + bool nodes_done = false;
4.840 + bool arcs_done = false;
4.841 + bool attributes_done = false;
4.842 +
4.843 + line_num = 0;
4.844 + readLine();
4.845 +
4.846 + while (readSuccess()) {
4.847 + skipSection();
4.848 + try {
4.849 + char c;
4.850 + std::string section, caption;
4.851 + line >> c;
4.852 + _reader_bits::readIdentifier(line, section);
4.853 + _reader_bits::readIdentifier(line, caption);
4.854 +
4.855 + if (line >> c)
4.856 + throw DataFormatError("Extra character on the end of line");
4.857 +
4.858 + if (section == "nodes" && !nodes_done) {
4.859 + if (_nodes_caption.empty() || _nodes_caption == caption) {
4.860 + readNodes();
4.861 + nodes_done = true;
4.862 + }
4.863 + } else if ((section == "arcs" || section == "edges") &&
4.864 + !arcs_done) {
4.865 + if (_arcs_caption.empty() || _arcs_caption == caption) {
4.866 + readArcs();
4.867 + arcs_done = true;
4.868 + }
4.869 + } else if (section == "attributes" && !attributes_done) {
4.870 + if (_attributes_caption.empty() || _attributes_caption == caption) {
4.871 + readAttributes();
4.872 + attributes_done = true;
4.873 + }
4.874 + } else {
4.875 + readLine();
4.876 + skipSection();
4.877 + }
4.878 + } catch (DataFormatError& error) {
4.879 + error.line(line_num);
4.880 + throw;
4.881 + }
4.882 + }
4.883 +
4.884 + if (!nodes_done) {
4.885 + throw DataFormatError("Section @nodes not found");
4.886 + }
4.887 +
4.888 + if (!arcs_done) {
4.889 + throw DataFormatError("Section @arcs not found");
4.890 + }
4.891 +
4.892 + if (!attributes_done && !_attributes.empty()) {
4.893 + throw DataFormatError("Section @attributes not found");
4.894 + }
4.895 +
4.896 + }
4.897 +
4.898 + };
4.899 +
4.900 + template <typename Digraph>
4.901 + DigraphReader<Digraph> digraphReader(std::istream& is, Digraph& digraph) {
4.902 + return DigraphReader<Digraph>(is, digraph);
4.903 + }
4.904 +
4.905 + template <typename Digraph>
4.906 + DigraphReader<Digraph> digraphReader(const std::string& fn,
4.907 + Digraph& digraph) {
4.908 + return DigraphReader<Digraph>(fn, digraph);
4.909 + }
4.910 +
4.911 + template <typename Digraph>
4.912 + DigraphReader<Digraph> digraphReader(const char* fn, Digraph& digraph) {
4.913 + return DigraphReader<Digraph>(fn, digraph);
4.914 + }
4.915 +}
4.916 +
4.917 +#endif
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/lgf_writer.h Thu Apr 17 15:18:45 2008 +0100
5.3 @@ -0,0 +1,627 @@
5.4 +/* -*- C++ -*-
5.5 + *
5.6 + * This file is a part of LEMON, a generic C++ optimization library
5.7 + *
5.8 + * Copyright (C) 2003-2008
5.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.11 + *
5.12 + * Permission to use, modify and distribute this software is granted
5.13 + * provided that this copyright notice appears in all copies. For
5.14 + * precise terms see the accompanying LICENSE file.
5.15 + *
5.16 + * This software is provided "AS IS" with no warranty of any kind,
5.17 + * express or implied, and with no claim as to its suitability for any
5.18 + * purpose.
5.19 + *
5.20 + */
5.21 +
5.22 +///\ingroup lemon_io
5.23 +///\file
5.24 +///\brief Lemon Graph Format writer.
5.25 +
5.26 +
5.27 +#ifndef LEMON_LGF_WRITER_H
5.28 +#define LEMON_LGF_WRITER_H
5.29 +
5.30 +#include <iostream>
5.31 +#include <fstream>
5.32 +#include <sstream>
5.33 +
5.34 +#include <algorithm>
5.35 +
5.36 +#include <vector>
5.37 +#include <functional>
5.38 +
5.39 +#include <lemon/assert.h>
5.40 +#include <lemon/graph_utils.h>
5.41 +
5.42 +namespace lemon {
5.43 +
5.44 + namespace _writer_bits {
5.45 +
5.46 + template <typename Value>
5.47 + struct DefaultConverter {
5.48 + std::string operator()(const Value& value) {
5.49 + std::ostringstream os;
5.50 + os << value;
5.51 + return os.str();
5.52 + }
5.53 + };
5.54 +
5.55 + template <typename T>
5.56 + bool operator<(const T&, const T&) {
5.57 + throw DataFormatError("Label map is not comparable");
5.58 + }
5.59 +
5.60 + template <typename _Map>
5.61 + class MapLess {
5.62 + public:
5.63 + typedef _Map Map;
5.64 + typedef typename Map::Key Item;
5.65 +
5.66 + private:
5.67 + const Map& _map;
5.68 +
5.69 + public:
5.70 + MapLess(const Map& map) : _map(map) {}
5.71 +
5.72 + bool operator()(const Item& left, const Item& right) {
5.73 + return _map[left] < _map[right];
5.74 + }
5.75 + };
5.76 +
5.77 + template <typename _Item>
5.78 + class MapStorageBase {
5.79 + public:
5.80 + typedef _Item Item;
5.81 +
5.82 + public:
5.83 + MapStorageBase() {}
5.84 + virtual ~MapStorageBase() {}
5.85 +
5.86 + virtual std::string get(const Item& item) = 0;
5.87 + virtual void sort(std::vector<Item>&) = 0;
5.88 + };
5.89 +
5.90 + template <typename _Item, typename _Map,
5.91 + typename _Converter = DefaultConverter<typename _Map::Value> >
5.92 + class MapStorage : public MapStorageBase<_Item> {
5.93 + public:
5.94 + typedef _Map Map;
5.95 + typedef _Converter Converter;
5.96 + typedef _Item Item;
5.97 +
5.98 + private:
5.99 + const Map& _map;
5.100 + Converter _converter;
5.101 +
5.102 + public:
5.103 + MapStorage(const Map& map, const Converter& converter = Converter())
5.104 + : _map(map), _converter(converter) {}
5.105 + virtual ~MapStorage() {}
5.106 +
5.107 + virtual std::string get(const Item& item) {
5.108 + return _converter(_map[item]);
5.109 + }
5.110 + virtual void sort(std::vector<Item>& items) {
5.111 + MapLess<Map> less(_map);
5.112 + std::sort(items.begin(), items.end(), less);
5.113 + }
5.114 + };
5.115 +
5.116 + class ValueStorageBase {
5.117 + public:
5.118 + ValueStorageBase() {}
5.119 + virtual ~ValueStorageBase() {}
5.120 +
5.121 + virtual std::string get() = 0;
5.122 + };
5.123 +
5.124 + template <typename _Value, typename _Converter = DefaultConverter<_Value> >
5.125 + class ValueStorage : public ValueStorageBase {
5.126 + public:
5.127 + typedef _Value Value;
5.128 + typedef _Converter Converter;
5.129 +
5.130 + private:
5.131 + const Value& _value;
5.132 + Converter _converter;
5.133 +
5.134 + public:
5.135 + ValueStorage(const Value& value, const Converter& converter = Converter())
5.136 + : _value(value), _converter(converter) {}
5.137 +
5.138 + virtual std::string get() {
5.139 + return _converter(_value);
5.140 + }
5.141 + };
5.142 +
5.143 + template <typename Value>
5.144 + struct MapLookUpConverter {
5.145 + const std::map<Value, std::string>& _map;
5.146 +
5.147 + MapLookUpConverter(const std::map<Value, std::string>& map)
5.148 + : _map(map) {}
5.149 +
5.150 + std::string operator()(const Value& str) {
5.151 + typename std::map<Value, std::string>::const_iterator it =
5.152 + _map.find(str);
5.153 + if (it == _map.end()) {
5.154 + throw DataFormatError("Item not found");
5.155 + }
5.156 + return it->second;
5.157 + }
5.158 + };
5.159 +
5.160 + bool isWhiteSpace(char c) {
5.161 + return c == ' ' || c == '\t' || c == '\v' ||
5.162 + c == '\n' || c == '\r' || c == '\f';
5.163 + }
5.164 +
5.165 + bool isEscaped(char c) {
5.166 + return c == '\\' || c == '\"' || c == '\'' ||
5.167 + c == '\a' || c == '\b';
5.168 + }
5.169 +
5.170 + static void writeEscape(std::ostream& os, char c) {
5.171 + switch (c) {
5.172 + case '\\':
5.173 + os << "\\\\";
5.174 + return;
5.175 + case '\"':
5.176 + os << "\\\"";
5.177 + return;
5.178 + case '\a':
5.179 + os << "\\a";
5.180 + return;
5.181 + case '\b':
5.182 + os << "\\b";
5.183 + return;
5.184 + case '\f':
5.185 + os << "\\f";
5.186 + return;
5.187 + case '\r':
5.188 + os << "\\r";
5.189 + return;
5.190 + case '\n':
5.191 + os << "\\n";
5.192 + return;
5.193 + case '\t':
5.194 + os << "\\t";
5.195 + return;
5.196 + case '\v':
5.197 + os << "\\v";
5.198 + return;
5.199 + default:
5.200 + if (c < 0x20) {
5.201 + os << '\\' << std::oct << static_cast<int>(c);
5.202 + } else {
5.203 + os << c;
5.204 + }
5.205 + return;
5.206 + }
5.207 + }
5.208 +
5.209 + bool requireEscape(const std::string& str) {
5.210 + std::istringstream is(str);
5.211 + char c;
5.212 + while (is.get(c)) {
5.213 + if (isWhiteSpace(c) || isEscaped(c)) {
5.214 + return true;
5.215 + }
5.216 + }
5.217 + return false;
5.218 + }
5.219 +
5.220 + std::ostream& writeToken(std::ostream& os, const std::string& str) {
5.221 +
5.222 + if (requireEscape(str)) {
5.223 + os << '\"';
5.224 + for (std::string::const_iterator it = str.begin();
5.225 + it != str.end(); ++it) {
5.226 + writeEscape(os, *it);
5.227 + }
5.228 + os << '\"';
5.229 + } else {
5.230 + os << str;
5.231 + }
5.232 + return os;
5.233 + }
5.234 +
5.235 + }
5.236 +
5.237 + /// \e
5.238 + template <typename _Digraph>
5.239 + class DigraphWriter {
5.240 + public:
5.241 +
5.242 + typedef _Digraph Digraph;
5.243 + GRAPH_TYPEDEFS(typename Digraph);
5.244 +
5.245 + private:
5.246 +
5.247 +
5.248 + std::ostream* _os;
5.249 + bool local_os;
5.250 +
5.251 + Digraph& _digraph;
5.252 +
5.253 + std::string _nodes_caption;
5.254 + std::string _arcs_caption;
5.255 + std::string _attributes_caption;
5.256 +
5.257 + typedef std::map<Node, std::string> NodeIndex;
5.258 + NodeIndex _node_index;
5.259 + typedef std::map<Arc, std::string> ArcIndex;
5.260 + ArcIndex _arc_index;
5.261 +
5.262 + typedef std::vector<std::pair<std::string,
5.263 + _writer_bits::MapStorageBase<Node>* > > NodeMaps;
5.264 + NodeMaps _node_maps;
5.265 +
5.266 + typedef std::vector<std::pair<std::string,
5.267 + _writer_bits::MapStorageBase<Arc>* > >ArcMaps;
5.268 + ArcMaps _arc_maps;
5.269 +
5.270 + typedef std::vector<std::pair<std::string,
5.271 + _writer_bits::ValueStorageBase*> > Attributes;
5.272 + Attributes _attributes;
5.273 +
5.274 + bool _skip_nodes;
5.275 + bool _skip_arcs;
5.276 +
5.277 + public:
5.278 +
5.279 + /// \e
5.280 + DigraphWriter(std::ostream& is, Digraph& digraph)
5.281 + : _os(&is), local_os(false), _digraph(digraph),
5.282 + _skip_nodes(false), _skip_arcs(false) {}
5.283 +
5.284 + /// \e
5.285 + DigraphWriter(const std::string& fn, Digraph& digraph)
5.286 + : _os(new std::ofstream(fn.c_str())), local_os(true), _digraph(digraph),
5.287 + _skip_nodes(false), _skip_arcs(false) {}
5.288 +
5.289 + /// \e
5.290 + DigraphWriter(const char* fn, Digraph& digraph)
5.291 + : _os(new std::ofstream(fn)), local_os(true), _digraph(digraph),
5.292 + _skip_nodes(false), _skip_arcs(false) {}
5.293 +
5.294 + DigraphWriter(DigraphWriter& other)
5.295 + : _os(other._os), local_os(other.local_os), _digraph(other._digraph),
5.296 + _skip_nodes(other._skip_nodes), _skip_arcs(other._skip_arcs) {
5.297 +
5.298 + other.is = 0;
5.299 + other.local_os = false;
5.300 +
5.301 + _node_index.swap(other._node_index);
5.302 + _arc_index.swap(other._arc_index);
5.303 +
5.304 + _node_maps.swap(other._node_maps);
5.305 + _arc_maps.swap(other._arc_maps);
5.306 + _attributes.swap(other._attributes);
5.307 +
5.308 + _nodes_caption = other._nodes_caption;
5.309 + _arcs_caption = other._arcs_caption;
5.310 + _attributes_caption = other._attributes_caption;
5.311 + }
5.312 +
5.313 + /// \e
5.314 + ~DigraphWriter() {
5.315 + for (typename NodeMaps::iterator it = _node_maps.begin();
5.316 + it != _node_maps.end(); ++it) {
5.317 + delete it->second;
5.318 + }
5.319 +
5.320 + for (typename ArcMaps::iterator it = _arc_maps.begin();
5.321 + it != _arc_maps.end(); ++it) {
5.322 + delete it->second;
5.323 + }
5.324 +
5.325 + for (typename Attributes::iterator it = _attributes.begin();
5.326 + it != _attributes.end(); ++it) {
5.327 + delete it->second;
5.328 + }
5.329 +
5.330 + if (local_os) {
5.331 + delete _os;
5.332 + }
5.333 + }
5.334 +
5.335 + private:
5.336 +
5.337 + DigraphWriter& operator=(const DigraphWriter&);
5.338 +
5.339 + public:
5.340 +
5.341 + /// \e
5.342 + template <typename Map>
5.343 + DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
5.344 + checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
5.345 + _writer_bits::MapStorageBase<Node>* storage =
5.346 + new _writer_bits::MapStorage<Node, Map>(map);
5.347 + _node_maps.push_back(std::make_pair(caption, storage));
5.348 + return *this;
5.349 + }
5.350 +
5.351 + /// \e
5.352 + template <typename Map, typename Converter>
5.353 + DigraphWriter& nodeMap(const std::string& caption, const Map& map,
5.354 + const Converter& converter = Converter()) {
5.355 + checkConcept<concepts::ReadMap<Node, typename Map::Value>, Map>();
5.356 + _writer_bits::MapStorageBase<Node>* storage =
5.357 + new _writer_bits::MapStorage<Node, Map, Converter>(map, converter);
5.358 + _node_maps.push_back(std::make_pair(caption, storage));
5.359 + return *this;
5.360 + }
5.361 +
5.362 + /// \e
5.363 + template <typename Map>
5.364 + DigraphWriter& arcMap(const std::string& caption, const Map& map) {
5.365 + checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
5.366 + _writer_bits::MapStorageBase<Arc>* storage =
5.367 + new _writer_bits::MapStorage<Arc, Map>(map);
5.368 + _arc_maps.push_back(std::make_pair(caption, storage));
5.369 + return *this;
5.370 + }
5.371 +
5.372 + /// \e
5.373 + template <typename Map, typename Converter>
5.374 + DigraphWriter& arcMap(const std::string& caption, const Map& map,
5.375 + const Converter& converter = Converter()) {
5.376 + checkConcept<concepts::ReadMap<Arc, typename Map::Value>, Map>();
5.377 + _writer_bits::MapStorageBase<Arc>* storage =
5.378 + new _writer_bits::MapStorage<Arc, Map, Converter>(map, converter);
5.379 + _arc_maps.push_back(std::make_pair(caption, storage));
5.380 + return *this;
5.381 + }
5.382 +
5.383 + /// \e
5.384 + template <typename Value>
5.385 + DigraphWriter& attribute(const std::string& caption, const Value& value) {
5.386 + _writer_bits::ValueStorageBase* storage =
5.387 + new _writer_bits::ValueStorage<Value>(value);
5.388 + _attributes.push_back(std::make_pair(caption, storage));
5.389 + return *this;
5.390 + }
5.391 +
5.392 + /// \e
5.393 + template <typename Value, typename Converter>
5.394 + DigraphWriter& attribute(const std::string& caption, const Value& value,
5.395 + const Converter& converter = Converter()) {
5.396 + _writer_bits::ValueStorageBase* storage =
5.397 + new _writer_bits::ValueStorage<Value, Converter>(value, converter);
5.398 + _attributes.push_back(std::make_pair(caption, storage));
5.399 + return *this;
5.400 + }
5.401 +
5.402 + /// \e
5.403 + DigraphWriter& node(const std::string& caption, const Node& node) {
5.404 + typedef _writer_bits::MapLookUpConverter<Node> Converter;
5.405 + Converter converter(_node_index);
5.406 + _writer_bits::ValueStorageBase* storage =
5.407 + new _writer_bits::ValueStorage<Node, Converter>(node, converter);
5.408 + _attributes.push_back(std::make_pair(caption, storage));
5.409 + return *this;
5.410 + }
5.411 +
5.412 + /// \e
5.413 + DigraphWriter& arc(const std::string& caption, const Arc& arc) {
5.414 + typedef _writer_bits::MapLookUpConverter<Arc> Converter;
5.415 + Converter converter(_arc_index);
5.416 + _writer_bits::ValueStorageBase* storage =
5.417 + new _writer_bits::ValueStorage<Arc, Converter>(arc, converter);
5.418 + _attributes.push_back(std::make_pair(caption, storage));
5.419 + return *this;
5.420 + }
5.421 +
5.422 + /// \e
5.423 + DigraphWriter& nodes(const std::string& caption) {
5.424 + _nodes_caption = caption;
5.425 + return *this;
5.426 + }
5.427 +
5.428 + /// \e
5.429 + DigraphWriter& arcs(const std::string& caption) {
5.430 + _arcs_caption = caption;
5.431 + return *this;
5.432 + }
5.433 +
5.434 + /// \e
5.435 + DigraphWriter& attributes(const std::string& caption) {
5.436 + _attributes_caption = caption;
5.437 + return *this;
5.438 + }
5.439 +
5.440 + DigraphWriter& skipNodes() {
5.441 + LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
5.442 + return *this;
5.443 + }
5.444 +
5.445 + DigraphWriter& skipArcs() {
5.446 + LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
5.447 + return *this;
5.448 + }
5.449 +
5.450 + private:
5.451 +
5.452 + void writeNodes() {
5.453 + _writer_bits::MapStorageBase<Node>* label = 0;
5.454 + for (typename NodeMaps::iterator it = _node_maps.begin();
5.455 + it != _node_maps.end(); ++it) {
5.456 + if (it->first == "label") {
5.457 + label = it->second;
5.458 + break;
5.459 + }
5.460 + }
5.461 +
5.462 + *_os << "@nodes";
5.463 + if (!_nodes_caption.empty()) {
5.464 + *_os << ' ' << _nodes_caption;
5.465 + }
5.466 + *_os << std::endl;
5.467 +
5.468 + if (label == 0) {
5.469 + *_os << "label" << '\t';
5.470 + }
5.471 + for (typename NodeMaps::iterator it = _node_maps.begin();
5.472 + it != _node_maps.end(); ++it) {
5.473 + *_os << it->first << '\t';
5.474 + }
5.475 + *_os << std::endl;
5.476 +
5.477 + std::vector<Node> nodes;
5.478 + for (NodeIt n(_digraph); n != INVALID; ++n) {
5.479 + nodes.push_back(n);
5.480 + }
5.481 +
5.482 + if (label == 0) {
5.483 + IdMap<Digraph, Node> id_map(_digraph);
5.484 + _writer_bits::MapLess<IdMap<Digraph, Node> > id_less(id_map);
5.485 + std::sort(nodes.begin(), nodes.end(), id_less);
5.486 + } else {
5.487 + label->sort(nodes);
5.488 + }
5.489 +
5.490 + for (int i = 0; i < static_cast<int>(nodes.size()); ++i) {
5.491 + Node n = nodes[i];
5.492 + if (label == 0) {
5.493 + std::ostringstream os;
5.494 + os << _digraph.id(n);
5.495 + _writer_bits::writeToken(*_os, os.str());
5.496 + *_os << '\t';
5.497 + _node_index.insert(std::make_pair(n, os.str()));
5.498 + }
5.499 + for (typename NodeMaps::iterator it = _node_maps.begin();
5.500 + it != _node_maps.end(); ++it) {
5.501 + std::string value = it->second->get(n);
5.502 + _writer_bits::writeToken(*_os, value);
5.503 + if (it->first == "label") {
5.504 + _node_index.insert(std::make_pair(n, value));
5.505 + }
5.506 + *_os << '\t';
5.507 + }
5.508 + *_os << std::endl;
5.509 + }
5.510 + }
5.511 +
5.512 + void writeArcs() {
5.513 + _writer_bits::MapStorageBase<Arc>* label = 0;
5.514 + for (typename ArcMaps::iterator it = _arc_maps.begin();
5.515 + it != _arc_maps.end(); ++it) {
5.516 + if (it->first == "label") {
5.517 + label = it->second;
5.518 + break;
5.519 + }
5.520 + }
5.521 +
5.522 + *_os << "@arcs";
5.523 + if (!_arcs_caption.empty()) {
5.524 + *_os << ' ' << _arcs_caption;
5.525 + }
5.526 + *_os << std::endl;
5.527 +
5.528 + *_os << '\t' << '\t';
5.529 + if (label == 0) {
5.530 + *_os << "label" << '\t';
5.531 + }
5.532 + for (typename ArcMaps::iterator it = _arc_maps.begin();
5.533 + it != _arc_maps.end(); ++it) {
5.534 + *_os << it->first << '\t';
5.535 + }
5.536 + *_os << std::endl;
5.537 +
5.538 + std::vector<Arc> arcs;
5.539 + for (ArcIt n(_digraph); n != INVALID; ++n) {
5.540 + arcs.push_back(n);
5.541 + }
5.542 +
5.543 + if (label == 0) {
5.544 + IdMap<Digraph, Arc> id_map(_digraph);
5.545 + _writer_bits::MapLess<IdMap<Digraph, Arc> > id_less(id_map);
5.546 + std::sort(arcs.begin(), arcs.end(), id_less);
5.547 + } else {
5.548 + label->sort(arcs);
5.549 + }
5.550 +
5.551 + for (int i = 0; i < static_cast<int>(arcs.size()); ++i) {
5.552 + Arc a = arcs[i];
5.553 + _writer_bits::writeToken(*_os, _node_index.
5.554 + find(_digraph.source(a))->second);
5.555 + *_os << '\t';
5.556 + _writer_bits::writeToken(*_os, _node_index.
5.557 + find(_digraph.target(a))->second);
5.558 + *_os << '\t';
5.559 + if (label == 0) {
5.560 + std::ostringstream os;
5.561 + os << _digraph.id(a);
5.562 + _writer_bits::writeToken(*_os, os.str());
5.563 + *_os << '\t';
5.564 + _arc_index.insert(std::make_pair(a, os.str()));
5.565 + }
5.566 + for (typename ArcMaps::iterator it = _arc_maps.begin();
5.567 + it != _arc_maps.end(); ++it) {
5.568 + std::string value = it->second->get(a);
5.569 + _writer_bits::writeToken(*_os, value);
5.570 + if (it->first == "label") {
5.571 + _arc_index.insert(std::make_pair(a, value));
5.572 + }
5.573 + *_os << '\t';
5.574 + }
5.575 + *_os << std::endl;
5.576 + }
5.577 + }
5.578 +
5.579 + void writeAttributes() {
5.580 + if (_attributes.empty()) return;
5.581 + *_os << "@attributes";
5.582 + if (!_attributes_caption.empty()) {
5.583 + *_os << ' ' << _attributes_caption;
5.584 + }
5.585 + *_os << std::endl;
5.586 + for (typename Attributes::iterator it = _attributes.begin();
5.587 + it != _attributes.end(); ++it) {
5.588 + *_os << it->first << ' ';
5.589 + _writer_bits::writeToken(*_os, it->second->get());
5.590 + *_os << std::endl;
5.591 + }
5.592 + }
5.593 +
5.594 + public:
5.595 +
5.596 + /// \e
5.597 + void run() {
5.598 + if (!_skip_nodes) {
5.599 + writeNodes();
5.600 + }
5.601 + if (!_skip_arcs) {
5.602 + writeArcs();
5.603 + }
5.604 + writeAttributes();
5.605 + }
5.606 +
5.607 + /// \e
5.608 + std::ostream& stream() {
5.609 + return *_os;
5.610 + }
5.611 + };
5.612 +
5.613 + template <typename Digraph>
5.614 + DigraphWriter<Digraph> digraphWriter(std::istream& is, Digraph& digraph) {
5.615 + return DigraphWriter<Digraph>(is, digraph);
5.616 + }
5.617 +
5.618 + template <typename Digraph>
5.619 + DigraphWriter<Digraph> digraphWriter(const std::string& fn,
5.620 + Digraph& digraph) {
5.621 + return DigraphWriter<Digraph>(fn, digraph);
5.622 + }
5.623 +
5.624 + template <typename Digraph>
5.625 + DigraphWriter<Digraph> digraphWriter(const char* fn, Digraph& digraph) {
5.626 + return DigraphWriter<Digraph>(fn, digraph);
5.627 + }
5.628 +}
5.629 +
5.630 +#endif