1.1 --- a/src/lemon/Makefile.am Mon Feb 07 11:28:37 2005 +0000
1.2 +++ b/src/lemon/Makefile.am Mon Feb 07 11:29:25 2005 +0000
1.3 @@ -35,7 +35,10 @@
1.4 extendable_graph_extender.h \
1.5 clearable_graph_extender.h \
1.6 erasable_graph_extender.h \
1.7 - undir_graph_extender.h
1.8 + undir_graph_extender.h \
1.9 + graph_reader.h \
1.10 + graph_writer.h \
1.11 + map_utils.h
1.12
1.13 noinst_HEADERS = \
1.14 concept/graph.h \
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/lemon/graph_reader.h Mon Feb 07 11:29:25 2005 +0000
2.3 @@ -0,0 +1,674 @@
2.4 +/* -*- C++ -*-
2.5 + * src/lemon/graph_reader.h - Part of LEMON, a generic C++ optimization library
2.6 + *
2.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
2.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
2.9 + *
2.10 + * Permission to use, modify and distribute this software is granted
2.11 + * provided that this copyright notice appears in all copies. For
2.12 + * precise terms see the accompanying LICENSE file.
2.13 + *
2.14 + * This software is provided "AS IS" with no warranty of any kind,
2.15 + * express or implied, and with no claim as to its suitability for any
2.16 + * purpose.
2.17 + *
2.18 + */
2.19 +
2.20 +///\ingroup gio
2.21 +///\file
2.22 +///\brief Graph reader.
2.23 +
2.24 +#include <iostream>
2.25 +#include <sstream>
2.26 +
2.27 +#include <map>
2.28 +#include <vector>
2.29 +
2.30 +#include <memory>
2.31 +
2.32 +#include <lemon/error.h>
2.33 +
2.34 +/// \todo fix exceptions
2.35 +
2.36 +
2.37 +namespace lemon {
2.38 +
2.39 + // Exceptions
2.40 +
2.41 + class IOException {
2.42 + public:
2.43 + virtual ~IOException() {}
2.44 + virtual string what() const = 0;
2.45 + };
2.46 +
2.47 + class DataFormatException : public IOException {
2.48 + std::string message;
2.49 + public:
2.50 + DataFormatException(const std::string& _message)
2.51 + : message(_message) {}
2.52 + std::string what() const {
2.53 + return "DataFormatException: " + message;
2.54 + }
2.55 + };
2.56 +
2.57 + template <typename _Exception>
2.58 + class StreamException : public _Exception {
2.59 + public:
2.60 + typedef _Exception Exception;
2.61 + StreamException(int _line, Exception _exception)
2.62 + : Exception(_exception), line_num(_line) {}
2.63 + virtual int line() const {
2.64 + return line_num;
2.65 + }
2.66 +
2.67 + virtual ~StreamException() {}
2.68 +
2.69 + virtual std::string what() const {
2.70 + ostringstream os;
2.71 + os << Exception::what() << " in line " << line();
2.72 + return os.str();
2.73 + }
2.74 + private:
2.75 + int line_num;
2.76 + };
2.77 +
2.78 +
2.79 + /// \brief Standard ReaderTraits for the GraphReader class.
2.80 + ///
2.81 + /// Standard ReaderTraits for the GraphReader class.
2.82 + /// It defines standard reading method for all type of value.
2.83 + struct DefaultReaderTraits {
2.84 +
2.85 + /// \brief Template class for reading an value.
2.86 + ///
2.87 + /// Template class for reading an value.
2.88 + template <typename _Value>
2.89 + struct Reader {
2.90 + /// The value type.
2.91 + typedef _Value Value;
2.92 + /// \brief Reads a value from the given stream.
2.93 + ///
2.94 + /// Reads a value from the given stream.
2.95 + void read(std::istream& is, Value& value) {
2.96 + if (!(is >> value))
2.97 + throw DataFormatException("Default Reader format exception");
2.98 + }
2.99 + };
2.100 +
2.101 + /// The reader class for the not needed maps.
2.102 + typedef Reader<std::string> DefaultReader;
2.103 +
2.104 + };
2.105 +
2.106 + /// \brief Reader class for quoted strings.
2.107 + ///
2.108 + /// Reader class for quoted strings. It can process the escape
2.109 + /// sequences in the string.
2.110 + class QuotedStringReader {
2.111 + public:
2.112 + typedef std::string Value;
2.113 +
2.114 + /// \brief Constructor for the reader.
2.115 + ///
2.116 + /// Constructor for the reader. If the given parameter is true
2.117 + /// the reader processes the escape sequences.
2.118 + QuotedStringReader(bool _escaped = true) : escaped(_escaped) {}
2.119 +
2.120 + /// \brief Reads a quoted string from the given stream.
2.121 + ///
2.122 + /// Reads a quoted string from the given stream.
2.123 + void read(std::istream& is, std::string& value) {
2.124 + char c;
2.125 + value.clear();
2.126 + is >> ws;
2.127 + if (!is.get(c) || c != '\"')
2.128 + throw DataFormatException("Quoted string format");
2.129 + while (is.get(c) && c != '\"') {
2.130 + if (escaped && c == '\\') {
2.131 + value += readEscape(is);
2.132 + } else {
2.133 + value += c;
2.134 + }
2.135 + }
2.136 + if (!is) throw DataFormatException("Quoted string format");
2.137 + }
2.138 +
2.139 + private:
2.140 +
2.141 + static char readEscape(std::istream& is) {
2.142 + char c;
2.143 + switch (is.get(c), c) {
2.144 + case '\\':
2.145 + return '\\';
2.146 + case '\"':
2.147 + return '\"';
2.148 + case '\'':
2.149 + return '\'';
2.150 + case '\?':
2.151 + return '\?';
2.152 + case 'a':
2.153 + return '\a';
2.154 + case 'b':
2.155 + return '\b';
2.156 + case 'f':
2.157 + return '\f';
2.158 + case 'n':
2.159 + return '\n';
2.160 + case 'r':
2.161 + return '\r';
2.162 + case 't':
2.163 + return '\t';
2.164 + case 'v':
2.165 + return '\v';
2.166 + case 'x':
2.167 + {
2.168 + int code;
2.169 + if (!is.get(c) || !isHex(c))
2.170 + throw DataFormatException("Escape format exception");
2.171 + else if (code = valueHex(c), !is.get(c) || !isHex(c)) is.putback(c);
2.172 + else code = code * 16 + valueHex(c);
2.173 + return code;
2.174 + }
2.175 + default:
2.176 + {
2.177 + int code;
2.178 + if (!isOct(c))
2.179 + throw DataFormatException("Escape format exception");
2.180 + else if (code = valueOct(c), !is.get(c) || !isOct(c))
2.181 + is.putback(c);
2.182 + else if (code = code * 8 + valueOct(c), !is.get(c) || !isOct(c))
2.183 + is.putback(c);
2.184 + else code = code * 8 + valueOct(c);
2.185 + return code;
2.186 + }
2.187 + }
2.188 + }
2.189 +
2.190 + static bool isOct(char c) {
2.191 + return '0' <= c && c <='7';
2.192 + }
2.193 +
2.194 + static int valueOct(char c) {
2.195 + return c - '0';
2.196 + }
2.197 +
2.198 + static bool isHex(char c) {
2.199 + return ('0' <= c && c <= '9') ||
2.200 + ('a' <= c && c <= 'z') ||
2.201 + ('A' <= c && c <= 'Z');
2.202 + }
2.203 +
2.204 + static int valueHex(char c) {
2.205 + if ('0' <= c && c <= '9') return c - '0';
2.206 + if ('a' <= c && c <= 'z') return c - 'a' + 10;
2.207 + return c - 'A' + 10;
2.208 + }
2.209 +
2.210 + bool escaped;
2.211 + };
2.212 +
2.213 + /// \brief The graph reader class.
2.214 + ///
2.215 + /// The reader class for the graph input.
2.216 + /// \see graph-io-page
2.217 + template <typename _Graph, typename _ReaderTraits = DefaultReaderTraits>
2.218 + class GraphReader {
2.219 + public:
2.220 +
2.221 + typedef _Graph Graph;
2.222 + typedef typename Graph::Node Node;
2.223 + typedef typename Graph::Edge Edge;
2.224 +
2.225 + typedef _ReaderTraits ReaderTraits;
2.226 + typedef typename ReaderTraits::DefaultReader DefaultReader;
2.227 +
2.228 + /// \brief Construct a new GraphReader.
2.229 + ///
2.230 + /// Construct a new GraphReader. It reads from the given map,
2.231 + /// it constructs the given map and it use the given reader as the
2.232 + /// default skipper.
2.233 + GraphReader(std::istream& _is, Graph& _graph,
2.234 + const DefaultReader& _reader = DefaultReader())
2.235 + : is(_is), graph(_graph), nodeSkipper(_reader), edgeSkipper(_reader) {}
2.236 +
2.237 + /// \brief Destruct the graph reader.
2.238 + ///
2.239 + /// Destruct the graph reader.
2.240 + ~GraphReader() {
2.241 +
2.242 + for (typename NodeMapReaders::iterator it = node_map_readers.begin();
2.243 + it != node_map_readers.end(); ++it) {
2.244 + delete it->second;
2.245 + }
2.246 +
2.247 + for (typename EdgeMapReaders::iterator it = edge_map_readers.begin();
2.248 + it != edge_map_readers.end(); ++it) {
2.249 + delete it->second;
2.250 + }
2.251 +
2.252 + }
2.253 +
2.254 + /// \brief Add a new node map reader command for the reader.
2.255 + ///
2.256 + /// Add a new node map reader command for the reader.
2.257 + template <typename Map>
2.258 + GraphReader& addNodeMap(std::string name, Map& map) {
2.259 + return addNodeMap<typename ReaderTraits::template
2.260 + Reader<typename Map::Value>, Map>(name, map);
2.261 + }
2.262 +
2.263 + /// \brief Add a new node map reader command for the reader.
2.264 + ///
2.265 + /// Add a new node map reader command for the reader.
2.266 + template <typename Reader, typename Map>
2.267 + GraphReader& addNodeMap(std::string name, Map& map,
2.268 + const Reader& reader = Reader()) {
2.269 + if (node_map_readers.find(name) != node_map_readers.end()) {
2.270 + throw Exception() << "Multiple read rule for node map: " << name;
2.271 + }
2.272 + node_map_readers.insert(
2.273 + make_pair(name, new MapReader<Node, Map, Reader>(map, reader)));
2.274 + return *this;
2.275 + }
2.276 +
2.277 + /// \brief Add a new node map skipper command for the reader.
2.278 + ///
2.279 + /// Add a new node map skipper command for the reader.
2.280 + template <typename Reader>
2.281 + GraphReader& skipNodeMap(std::string name,
2.282 + const Reader& reader = Reader()) {
2.283 + if (node_map_readers.find(name) != node_map_readers.end()) {
2.284 + throw Exception() << "Multiple read rule for node map: " << name;
2.285 + }
2.286 + node_map_readers.insert(
2.287 + make_pair(name, new SkipReader<Node, Reader>(reader)));
2.288 + return *this;
2.289 + }
2.290 +
2.291 + /// \brief Add a new edge map reader command for the reader.
2.292 + ///
2.293 + /// Add a new edge map reader command for the reader.
2.294 + template <typename Map>
2.295 + GraphReader& addEdgeMap(std::string name, Map& map) {
2.296 + return addEdgeMap<typename ReaderTraits::template
2.297 + Reader<typename Map::Value>, Map>(name, map);
2.298 + }
2.299 +
2.300 +
2.301 + /// \brief Add a new edge map reader command for the reader.
2.302 + ///
2.303 + /// Add a new edge map reader command for the reader.
2.304 + template <typename Reader, typename Map>
2.305 + GraphReader& addEdgeMap(std::string name, Map& map,
2.306 + const Reader& reader = Reader()) {
2.307 + if (edge_map_readers.find(name) != edge_map_readers.end()) {
2.308 + throw Exception() << "Multiple read rule for edge map: " << name;
2.309 + }
2.310 + edge_map_readers.insert(
2.311 + make_pair(name, new MapReader<Edge, Map, Reader>(map, reader)));
2.312 + return *this;
2.313 + }
2.314 +
2.315 + /// \brief Add a new edge map skipper command for the reader.
2.316 + ///
2.317 + /// Add a new edge map skipper command for the reader.
2.318 + template <typename Reader>
2.319 + GraphReader& skipEdgeMap(std::string name,
2.320 + const Reader& reader = Reader()) {
2.321 + if (edge_map_readers.find(name) != edge_map_readers.end()) {
2.322 + throw Exception() << "Multiple read rule for edge map: " << name;
2.323 + }
2.324 + edge_map_readers.insert(
2.325 + make_pair(name, new SkipReader<Edge, Reader>(reader)));
2.326 + return *this;
2.327 + }
2.328 +
2.329 + /// \brief Add a new labeled node reader for the reader.
2.330 + ///
2.331 + /// Add a new labeled node reader for the reader.
2.332 + GraphReader& addNode(std::string name, Node& node) {
2.333 + if (node_readers.find(name) != node_readers.end()) {
2.334 + throw Exception() << "Multiple read rule for node";
2.335 + }
2.336 + node_readers.insert(make_pair(name, &node));
2.337 + return *this;
2.338 + }
2.339 +
2.340 + /// \brief Add a new labeled edge reader for the reader.
2.341 + ///
2.342 + /// Add a new labeled edge reader for the reader.
2.343 + GraphReader& addEdge(std::string name, Edge& edge) {
2.344 + if (edge_readers.find(name) != edge_readers.end()) {
2.345 + throw Exception() << "Multiple read rule for edge";
2.346 + }
2.347 + edge_readers.insert(make_pair(name, &edge));
2.348 + return *this;
2.349 + }
2.350 +
2.351 + /// \brief Executes the reader commands.
2.352 + ///
2.353 + /// Executes the reader commands.
2.354 + void run() {
2.355 + int line_num = 0;
2.356 + std::auto_ptr<InverterBase<Node> > nodeInverter;
2.357 + std::auto_ptr<InverterBase<Edge> > edgeInverter;
2.358 + try {
2.359 + std::string line = readNotEmptyLine(is, line_num);
2.360 + if (line.find("@nodeset") == 0) {
2.361 + line = readNodeSet(line_num, nodeInverter);
2.362 + }
2.363 + if (line.find("@edgeset") == 0) {
2.364 + line = readEdgeSet(line_num, edgeInverter, nodeInverter);
2.365 + }
2.366 + if (line.find("@nodes") == 0) {
2.367 + line = readNodes(line_num, nodeInverter);
2.368 + }
2.369 + if (line.find("@edges") == 0) {
2.370 + line = readEdges(line_num, edgeInverter);
2.371 + }
2.372 + if (line.find("@end") != 0) {
2.373 + throw DataFormatException("Invalid control sequence: " + line);
2.374 + }
2.375 + } catch (DataFormatException e) {
2.376 + throw StreamException<DataFormatException>(line_num, e);
2.377 + }
2.378 + }
2.379 +
2.380 + private:
2.381 +
2.382 + template <typename Item> class InverterBase;
2.383 +
2.384 + std::string readNodeSet(int& line_num,
2.385 + auto_ptr<InverterBase<Node> > & nodeInverter) {
2.386 + std::vector<ReaderBase<Node>* > index;
2.387 + {
2.388 + std::string line = readNotEmptyLine(is, line_num);
2.389 + std::string id;
2.390 + std::istringstream ls(line);
2.391 + while (ls >> id) {
2.392 + if (id[0] == '#') break;
2.393 + typename NodeMapReaders::iterator it = node_map_readers.find(id);
2.394 + if (it != node_map_readers.end()) {
2.395 + index.push_back(it->second);
2.396 + node_map_readers.erase(it);
2.397 + } else {
2.398 + index.push_back(&nodeSkipper);
2.399 + }
2.400 + }
2.401 + }
2.402 +
2.403 + if (index.size() == 0) {
2.404 + throw DataFormatException("No node map found");
2.405 + }
2.406 +
2.407 + nodeInverter = auto_ptr<InverterBase<Node> >(index[0]->getInverter());
2.408 + std::string line;
2.409 + while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
2.410 + Node node = graph.addNode();
2.411 + std::istringstream ls(line);
2.412 + nodeInverter->read(ls, node);
2.413 + for (int i = 1; i < (int)index.size(); ++i) {
2.414 + index[i]->read(ls, node);
2.415 + }
2.416 + }
2.417 + return line;
2.418 + }
2.419 +
2.420 + std::string readEdgeSet(int& line_num,
2.421 + auto_ptr<InverterBase<Edge> > & edgeInverter,
2.422 + auto_ptr<InverterBase<Node> > & nodeInverter) {
2.423 + std::vector<ReaderBase<Edge>*> index;
2.424 + {
2.425 + std::string line = readNotEmptyLine(is, line_num);
2.426 + std::string id;
2.427 + std::istringstream ls(line);
2.428 + while (ls >> id) {
2.429 + if (id[0] == '#') break;
2.430 + typename EdgeMapReaders::iterator it = edge_map_readers.find(id);
2.431 + if (it != edge_map_readers.end()) {
2.432 + index.push_back(it->second);
2.433 + edge_map_readers.erase(it);
2.434 + } else {
2.435 + index.push_back(&edgeSkipper);
2.436 + }
2.437 + }
2.438 + }
2.439 +
2.440 + if (index.size() == 0) {
2.441 + throw DataFormatException("No edge map found");
2.442 + }
2.443 +
2.444 + edgeInverter = auto_ptr<InverterBase<Edge> >(index[0]->getInverter());
2.445 + std::string line;
2.446 + while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
2.447 + std::istringstream ls(line);
2.448 + Node source = nodeInverter->read(ls);
2.449 + Node target = nodeInverter->read(ls);
2.450 + Edge edge = graph.addEdge(source, target);
2.451 + edgeInverter->read(ls, edge);
2.452 + for (int i = 1; i < (int)index.size(); ++i) {
2.453 + index[i]->read(ls, edge);
2.454 + }
2.455 + }
2.456 + return line;
2.457 + }
2.458 +
2.459 + std::string readNodes(int& line_num,
2.460 + auto_ptr<InverterBase<Node> >& nodeInverter) {
2.461 + std::string line;
2.462 + while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
2.463 + std::istringstream ls(line);
2.464 + std::string name;
2.465 + ls >> name;
2.466 + typename NodeReaders::iterator it = node_readers.find(name);
2.467 + if (it != node_readers.end()) {
2.468 + *(it -> second) = nodeInverter->read(ls);
2.469 + }
2.470 + }
2.471 + return line;
2.472 + }
2.473 +
2.474 + std::string readEdges(int& line_num,
2.475 + auto_ptr<InverterBase<Edge> >& edgeInverter) {
2.476 + std::string line;
2.477 + while (line = readNotEmptyLine(is, line_num), line[0] != '@') {
2.478 + std::istringstream ls(line);
2.479 + std::string name;
2.480 + ls >> name;
2.481 + typename EdgeReaders::iterator it = edge_readers.find(name);
2.482 + if (it != edge_readers.end()) {
2.483 + *(it -> second) = edgeInverter->read(ls);
2.484 + }
2.485 + }
2.486 + return line;
2.487 + }
2.488 +
2.489 + std::string readNotEmptyLine(std::istream& is, int& line_num) {
2.490 + std::string line;
2.491 + while (++line_num, getline(is, line)) {
2.492 + int vi = line.find_first_not_of(" \t");
2.493 + if (vi != (int)string::npos && line[vi] != '#') {
2.494 + return line.substr(vi);
2.495 + }
2.496 + }
2.497 + throw DataFormatException("End of stream");
2.498 + }
2.499 +
2.500 + // Inverters store and give back the Item from the id,
2.501 + // and may put the ids into a map.
2.502 +
2.503 + template <typename _Item>
2.504 + class InverterBase {
2.505 + public:
2.506 + typedef _Item Item;
2.507 + virtual void read(std::istream&, const Item&) = 0;
2.508 + virtual Item read(std::istream&) = 0;
2.509 + };
2.510 +
2.511 + template <typename _Item, typename _Map, typename _Reader>
2.512 + class MapReaderInverter : public InverterBase<_Item> {
2.513 + public:
2.514 + typedef _Item Item;
2.515 + typedef _Reader Reader;
2.516 + typedef typename Reader::Value Value;
2.517 + typedef _Map Map;
2.518 + typedef std::map<Value, Item> Inverse;
2.519 +
2.520 + Map& map;
2.521 + Reader reader;
2.522 + Inverse inverse;
2.523 +
2.524 + MapReaderInverter(Map& _map, const Reader& _reader)
2.525 + : map(_map), reader(_reader) {}
2.526 +
2.527 + virtual ~MapReaderInverter() {}
2.528 +
2.529 + virtual void read(std::istream& is, const Item& item) {
2.530 + Value value;
2.531 + reader.read(is, value);
2.532 + map.set(item, value);
2.533 + typename Inverse::iterator it = inverse.find(value);
2.534 + if (it == inverse.end()) {
2.535 + inverse.insert(make_pair(value, item));
2.536 + } else {
2.537 + throw DataFormatException("Multiple ID occurence");
2.538 + }
2.539 + }
2.540 +
2.541 + virtual Item read(std::istream& is) {
2.542 + Value value;
2.543 + reader.read(is, value);
2.544 + typename Inverse::const_iterator it = inverse.find(value);
2.545 + if (it != inverse.end()) {
2.546 + return it->second;
2.547 + } else {
2.548 + throw DataFormatException("Invalid ID");
2.549 + }
2.550 + }
2.551 + };
2.552 +
2.553 + template <typename _Item, typename _Reader>
2.554 + class SkipReaderInverter : public InverterBase<_Item> {
2.555 + public:
2.556 + typedef _Item Item;
2.557 + typedef _Reader Reader;
2.558 + typedef typename Reader::Value Value;
2.559 + typedef std::map<Value, Item> Inverse;
2.560 +
2.561 + Reader reader;
2.562 +
2.563 + SkipReaderInverter(const Reader& _reader)
2.564 + : reader(_reader) {}
2.565 +
2.566 + virtual ~SkipReaderInverter() {}
2.567 +
2.568 + virtual void read(std::istream& is, const Item& item) {
2.569 + Value value;
2.570 + reader.read(is, value);
2.571 + typename Inverse::iterator it = inverse.find(value);
2.572 + if (it == inverse.end()) {
2.573 + inverse.insert(make_pair(value, item));
2.574 + } else {
2.575 + throw DataFormatException("Multiple ID occurence");
2.576 + }
2.577 + }
2.578 +
2.579 + virtual Item read(std::istream& is) {
2.580 + Value value;
2.581 + reader.read(is, value);
2.582 + typename Inverse::const_iterator it = inverse.find(value);
2.583 + if (it != inverse.end()) {
2.584 + return it->second;
2.585 + } else {
2.586 + throw DataFormatException("Invalid ID");
2.587 + }
2.588 + }
2.589 + private:
2.590 + Inverse inverse;
2.591 + };
2.592 +
2.593 + // Readers
2.594 +
2.595 + template <typename _Item>
2.596 + class ReaderBase {
2.597 + public:
2.598 + typedef _Item Item;
2.599 +
2.600 + // virtual ~ReaderBase() {}
2.601 +
2.602 + virtual void read(std::istream& is, const Item& item) = 0;
2.603 + virtual InverterBase<_Item>* getInverter() = 0;
2.604 + };
2.605 +
2.606 + template <typename _Item, typename _Map, typename _Reader>
2.607 + class MapReader : public ReaderBase<_Item> {
2.608 + public:
2.609 + typedef _Map Map;
2.610 + typedef _Reader Reader;
2.611 + typedef typename Reader::Value Value;
2.612 + typedef _Item Item;
2.613 +
2.614 + Map& map;
2.615 + Reader reader;
2.616 +
2.617 + MapReader(Map& _map, const Reader& _reader)
2.618 + : map(_map), reader(_reader) {}
2.619 +
2.620 + virtual ~MapReader() {}
2.621 +
2.622 + virtual void read(std::istream& is, const Item& item) {
2.623 + Value value;
2.624 + reader.read(is, value);
2.625 + map.set(item, value);
2.626 + }
2.627 +
2.628 + virtual InverterBase<_Item>* getInverter() {
2.629 + return new MapReaderInverter<Item, Map, Reader>(map, reader);
2.630 + }
2.631 + };
2.632 +
2.633 +
2.634 + template <typename _Item, typename _Reader>
2.635 + class SkipReader : public ReaderBase<_Item> {
2.636 + public:
2.637 + typedef _Reader Reader;
2.638 + typedef typename Reader::Value Value;
2.639 + typedef _Item Item;
2.640 +
2.641 + Reader reader;
2.642 + SkipReader(const Reader& _reader) : reader(_reader) {}
2.643 +
2.644 + virtual ~SkipReader() {}
2.645 +
2.646 + virtual void read(std::istream& is, const Item& item) {
2.647 + Value value;
2.648 + reader.read(is, value);
2.649 + }
2.650 +
2.651 + virtual InverterBase<Item>* getInverter() {
2.652 + return new SkipReaderInverter<Item, Reader>(reader);
2.653 + }
2.654 + };
2.655 +
2.656 +
2.657 + typedef std::map<std::string, ReaderBase<Node>*> NodeMapReaders;
2.658 + NodeMapReaders node_map_readers;
2.659 +
2.660 + typedef std::map<std::string, ReaderBase<Edge>*> EdgeMapReaders;
2.661 + EdgeMapReaders edge_map_readers;
2.662 +
2.663 + typedef std::map<std::string, Node*> NodeReaders;
2.664 + NodeReaders node_readers;
2.665 +
2.666 + typedef std::map<std::string, Edge*> EdgeReaders;
2.667 + EdgeReaders edge_readers;
2.668 +
2.669 + std::istream& is;
2.670 + Graph& graph;
2.671 +
2.672 + SkipReader<Node, DefaultReader> nodeSkipper;
2.673 + SkipReader<Edge, DefaultReader> edgeSkipper;
2.674 +
2.675 + };
2.676 +
2.677 +}
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/lemon/graph_writer.h Mon Feb 07 11:29:25 2005 +0000
3.3 @@ -0,0 +1,372 @@
3.4 +/* -*- C++ -*-
3.5 + * src/lemon/graph_writer.h - Part of LEMON, a generic C++ optimization library
3.6 + *
3.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
3.9 + *
3.10 + * Permission to use, modify and distribute this software is granted
3.11 + * provided that this copyright notice appears in all copies. For
3.12 + * precise terms see the accompanying LICENSE file.
3.13 + *
3.14 + * This software is provided "AS IS" with no warranty of any kind,
3.15 + * express or implied, and with no claim as to its suitability for any
3.16 + * purpose.
3.17 + *
3.18 + */
3.19 +
3.20 +///\ingroup gio
3.21 +///\file
3.22 +///\brief Graph writer.
3.23 +
3.24 +
3.25 +#include <iostream>
3.26 +#include <sstream>
3.27 +
3.28 +#include <map>
3.29 +#include <vector>
3.30 +
3.31 +#include <memory>
3.32 +
3.33 +#include <lemon/invalid.h>
3.34 +#include <lemon/error.h>
3.35 +
3.36 +
3.37 +namespace lemon {
3.38 +
3.39 + /// \brief Standard WriterTraits for the GraphWriter class.
3.40 + ///
3.41 + /// Standard WriterTraits for the GraphWriter class.
3.42 + /// It defines standard writing method for all type of value.
3.43 + struct DefaultWriterTraits {
3.44 +
3.45 + /// \brief Template class for writing an value.
3.46 + ///
3.47 + /// Template class for writing an value.
3.48 + template <typename _Value>
3.49 + struct Writer {
3.50 + /// The value type.
3.51 + typedef _Value Value;
3.52 +
3.53 + /// \brief Writes a value from the given stream.
3.54 + ///
3.55 + /// Writes a value from the given stream.
3.56 + void write(std::ostream& os, const Value& value) {
3.57 + os << value << '\t';
3.58 + }
3.59 + };
3.60 +
3.61 + };
3.62 +
3.63 +
3.64 + /// \brief Writer class for quoted strings.
3.65 + ///
3.66 + /// Writer class for quoted strings. It can process the escape
3.67 + /// sequences in the string.
3.68 + class QuotedStringWriter {
3.69 + public:
3.70 + typedef std::string Value;
3.71 +
3.72 + /// \brief Constructor for the writer.
3.73 + ///
3.74 + /// Constructor for the writer. If the given parameter is true
3.75 + /// the writer creates escape sequences from special characters.
3.76 + QuotedStringWriter(bool _escaped = true) : escaped(_escaped) {}
3.77 +
3.78 + /// \brief Writes a quoted string from the given stream.
3.79 + ///
3.80 + /// Writes a quoted string from the given stream.
3.81 + void write(std::ostream& os, const std::string& value) {
3.82 + os << "\"";
3.83 + if (escaped) {
3.84 + ostringstream ls;
3.85 + for (int i = 0; i < (int)value.size(); ++i) {
3.86 + writeEscape(ls, value[i]);
3.87 + }
3.88 + os << ls.str();
3.89 + } else {
3.90 + os << value;
3.91 + }
3.92 + os << "\"";
3.93 + }
3.94 +
3.95 + private:
3.96 +
3.97 + static void writeEscape(std::ostream& os, char c) {
3.98 + switch (c) {
3.99 + case '\\':
3.100 + os << "\\\\";
3.101 + return;
3.102 + case '\"':
3.103 + os << "\\\"";
3.104 + return;
3.105 + case '\'':
3.106 + os << "\\\'";
3.107 + return;
3.108 + case '\?':
3.109 + os << "\\\?";
3.110 + return;
3.111 + case '\a':
3.112 + os << "\\a";
3.113 + return;
3.114 + case '\b':
3.115 + os << "\\b";
3.116 + return;
3.117 + case '\f':
3.118 + os << "\\f";
3.119 + return;
3.120 + case '\r':
3.121 + os << "\\r";
3.122 + return;
3.123 + case '\n':
3.124 + os << "\\n";
3.125 + return;
3.126 + case '\t':
3.127 + os << "\\t";
3.128 + return;
3.129 + case '\v':
3.130 + os << "\\v";
3.131 + return;
3.132 + default:
3.133 + if (c < 0x20) {
3.134 + os << '\\' << oct << (int)c;
3.135 + } else {
3.136 + os << c;
3.137 + }
3.138 + return;
3.139 + }
3.140 + }
3.141 + private:
3.142 + bool escaped;
3.143 + };
3.144 +
3.145 +
3.146 + /// \brief The graph writer class.
3.147 + ///
3.148 + /// The writer class for the graph output.
3.149 + /// \see graph-io-page
3.150 + template <typename _Graph, typename _WriterTraits = DefaultWriterTraits>
3.151 + class GraphWriter {
3.152 + public:
3.153 +
3.154 + typedef _Graph Graph;
3.155 + typedef typename Graph::Node Node;
3.156 + typedef typename Graph::NodeIt NodeIt;
3.157 + typedef typename Graph::Edge Edge;
3.158 + typedef typename Graph::EdgeIt EdgeIt;
3.159 +
3.160 + typedef _WriterTraits WriterTraits;
3.161 +
3.162 + /// \brief Construct a new GraphWriter.
3.163 + ///
3.164 + /// Construct a new GraphWriter. It writes from the given map,
3.165 + /// it constructs the given map and it use the given writer as the
3.166 + /// default skipper.
3.167 + GraphWriter(std::ostream& _os, Graph& _graph) : os(_os), graph(_graph) {}
3.168 +
3.169 +
3.170 + /// \brief Destruct the graph writer.
3.171 + ///
3.172 + /// Destruct the graph writer.
3.173 + ~GraphWriter() {
3.174 + for (typename NodeMapWriters::iterator it = node_map_writers.begin();
3.175 + it != node_map_writers.end(); ++it) {
3.176 + delete it->second;
3.177 + }
3.178 +
3.179 + for (typename EdgeMapWriters::iterator it = edge_map_writers.begin();
3.180 + it != edge_map_writers.end(); ++it) {
3.181 + delete it->second;
3.182 + }
3.183 +
3.184 + }
3.185 +
3.186 + // Node map rules
3.187 +
3.188 + /// \brief Add a new node map writer command for the writer.
3.189 + ///
3.190 + /// Add a new node map writer command for the writer.
3.191 + template <typename Map>
3.192 + GraphWriter& addNodeMap(std::string name, const Map& map) {
3.193 + return addNodeMap<typename WriterTraits::template Writer<
3.194 + typename Map::Value>, Map>(name, map);
3.195 + }
3.196 +
3.197 + /// \brief Add a new node map writer command for the writer.
3.198 + ///
3.199 + /// Add a new node map writer command for the writer.
3.200 + template <typename Writer, typename Map>
3.201 + GraphWriter& addNodeMap(std::string name, const Map& map,
3.202 + const Writer& writer = Writer()) {
3.203 + node_map_writers.push_back(
3.204 + make_pair(name, new MapWriter<Node, Map, Writer>(map, writer)));
3.205 + return *this;
3.206 + }
3.207 +
3.208 + // Edge map rules
3.209 +
3.210 + /// \brief Add a new edge map writer command for the writer.
3.211 + ///
3.212 + /// Add a new edge map writer command for the writer.
3.213 + template <typename Map>
3.214 + GraphWriter& addEdgeMap(std::string name, const Map& map) {
3.215 + return addEdgeMap<typename WriterTraits::template Writer<
3.216 + typename Map::Value>, Map>(name, map);
3.217 + }
3.218 +
3.219 +
3.220 + /// \brief Add a new edge map writer command for the writer.
3.221 + ///
3.222 + /// Add a new edge map writer command for the writer.
3.223 + template <typename Writer, typename Map>
3.224 + GraphWriter& addEdgeMap(std::string name,
3.225 + const Map& map, const Writer& writer = Writer()) {
3.226 + edge_map_writers.push_back(make_pair(name,
3.227 + new MapWriter<Edge, Map, Writer>(map, writer)));
3.228 + return *this;
3.229 + }
3.230 +
3.231 + /// \brief Add a new labeled node writer for the writer.
3.232 + ///
3.233 + /// Add a new labeled node writer for the writer.
3.234 + GraphWriter& addNode(std::string name, const Node& node) {
3.235 + node_writers.push_back(make_pair(name, node));
3.236 + return *this;
3.237 + }
3.238 +
3.239 + /// \brief Add a new labeled edge writer for the writer.
3.240 + ///
3.241 + /// Add a new labeled edge writer for the writer.
3.242 + GraphWriter& addEdge(std::string name, const Edge& edge) {
3.243 + edge_writers.push_back(make_pair(name, edge));
3.244 + return *this;
3.245 + }
3.246 +
3.247 + /// \brief Executes the writer commands.
3.248 + ///
3.249 + /// Executes the writer commands.
3.250 + void run() {
3.251 + writeNodeSet();
3.252 + writeEdgeSet();
3.253 + writeNodes();
3.254 + writeEdges();
3.255 + os << "@end" << std::endl;
3.256 + }
3.257 +
3.258 + private:
3.259 +
3.260 + void writeNodeSet() {
3.261 + if (node_map_writers.size() == 0) return;
3.262 + os << "@nodeset" << std::endl;
3.263 + for (int i = 0; i < (int)node_map_writers.size(); ++i) {
3.264 + os << node_map_writers[i].first << '\t';
3.265 + }
3.266 + os << std::endl;
3.267 + for (NodeIt it(graph); it != INVALID; ++it) {
3.268 + for (int i = 0; i < (int)node_map_writers.size(); ++i) {
3.269 + node_map_writers[i].second->write(os, it);
3.270 + }
3.271 + os << std::endl;
3.272 + }
3.273 +
3.274 + }
3.275 +
3.276 + void writeEdgeSet() {
3.277 + if (edge_map_writers.size() == 0) return;
3.278 + if (node_map_writers.size() == 0) {
3.279 + throw Exception() << "Missing node id map";
3.280 + }
3.281 + os << "@edgeset" << std::endl;
3.282 + os << "\t\t";
3.283 + for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
3.284 + os << edge_map_writers[i].first << '\t';
3.285 + }
3.286 + os << std::endl;
3.287 + for (EdgeIt it(graph); it != INVALID; ++it) {
3.288 + node_map_writers[0].second->write(os, graph.source(it));
3.289 + node_map_writers[0].second->write(os, graph.target(it));
3.290 + for (int i = 0; i < (int)edge_map_writers.size(); ++i) {
3.291 + edge_map_writers[i].second->write(os, it);
3.292 + }
3.293 + os << std::endl;
3.294 + }
3.295 + }
3.296 +
3.297 + void writeNodes() {
3.298 + if (node_writers.size() == 0) return;
3.299 + if (node_map_writers.size() == 0) {
3.300 + throw Exception() << "Missing node id map";
3.301 + }
3.302 + os << "@nodes" << std::endl;
3.303 + for (int i = 0; i < (int)node_writers.size(); ++i) {
3.304 + os << node_writers[i].first << '\t';
3.305 + node_map_writers[0].second->write(os, node_writers[i].second);
3.306 + os << std::endl;
3.307 + }
3.308 + }
3.309 +
3.310 + void writeEdges() {
3.311 + if (edge_writers.size() == 0) return;
3.312 + if (edge_map_writers.size() == 0) {
3.313 + throw Exception() << "Missing edge id map";
3.314 + }
3.315 + os << "@edges" << std::endl;
3.316 + for (int i = 0; i < (int)edge_writers.size(); ++i) {
3.317 + os << edge_writers[i].first << '\t';
3.318 + edge_map_writers[0].second->write(os, edge_writers[i].second);
3.319 + os << std::endl;
3.320 + }
3.321 + }
3.322 +
3.323 + // Writers
3.324 +
3.325 + template <class _Item>
3.326 + class WriterBase {
3.327 + public:
3.328 + typedef _Item Item;
3.329 + virtual void write(std::ostream&, const Item&) = 0;
3.330 + };
3.331 +
3.332 + template <class _Item, typename _Map, typename _Writer>
3.333 + class MapWriter : public WriterBase<_Item> {
3.334 + public:
3.335 + typedef _Map Map;
3.336 + typedef _Writer Writer;
3.337 + typedef typename Writer::Value Value;
3.338 + typedef _Item Item;
3.339 +
3.340 + const Map& map;
3.341 + Writer writer;
3.342 +
3.343 + MapWriter(const Map& _map, const Writer& _writer)
3.344 + : map(_map), writer(_writer) {}
3.345 +
3.346 +
3.347 + virtual void write(std::ostream& os, const Item& item) {
3.348 + writer.write(os, map[item]);
3.349 + }
3.350 +
3.351 + };
3.352 +
3.353 +
3.354 +
3.355 + typedef std::vector< std::pair<std::string, WriterBase<Node>*> >
3.356 + NodeMapWriters;
3.357 + NodeMapWriters node_map_writers;
3.358 +
3.359 + typedef std::vector< std::pair<std::string, WriterBase<Edge>*> >
3.360 + EdgeMapWriters;
3.361 + EdgeMapWriters edge_map_writers;
3.362 +
3.363 + typedef std::vector<std::pair<std::string, Node> > NodeWriters;
3.364 + NodeWriters node_writers;
3.365 +
3.366 + typedef std::vector<std::pair<std::string, Edge> > EdgeWriters;
3.367 + EdgeWriters edge_writers;
3.368 +
3.369 + std::ostream& os;
3.370 + Graph& graph;
3.371 +
3.372 + };
3.373 +
3.374 +
3.375 +}
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/lemon/map_utils.h Mon Feb 07 11:29:25 2005 +0000
4.3 @@ -0,0 +1,276 @@
4.4 +/* -*- C++ -*-
4.5 + * src/lemon/map_utils.h - Part of LEMON, a generic C++ optimization library
4.6 + *
4.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
4.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
4.9 + *
4.10 + * Permission to use, modify and distribute this software is granted
4.11 + * provided that this copyright notice appears in all copies. For
4.12 + * precise terms see the accompanying LICENSE file.
4.13 + *
4.14 + * This software is provided "AS IS" with no warranty of any kind,
4.15 + * express or implied, and with no claim as to its suitability for any
4.16 + * purpose.
4.17 + *
4.18 + */
4.19 +
4.20 +///\ingroup mutils
4.21 +///\file
4.22 +///\brief Map utilities.
4.23 +
4.24 +#include <map>
4.25 +
4.26 +
4.27 +namespace lemon {
4.28 +
4.29 + /// \addtogroup mutils
4.30 + /// @{
4.31 +
4.32 + /// \brief General inversable map type.
4.33 +
4.34 + /// This type provides simple inversable map functions.
4.35 + /// The InversableMap wraps an arbitrary ReadWriteMap
4.36 + /// and if a key is setted to a new value then store it
4.37 + /// in the inverse map.
4.38 + /// \param _Graph The graph type.
4.39 + /// \param _Map The map to extend with inversable functionality.
4.40 + template <
4.41 + typename _Graph,
4.42 + typename _Map
4.43 + >
4.44 + class InversableMap : protected _Map {
4.45 +
4.46 + public:
4.47 + typedef _Graph Graph;
4.48 +
4.49 + typedef _Map Map;
4.50 + /// The key type of InversableMap (Node, Edge, UndirEdge).
4.51 + typedef typename _Map::Key Key;
4.52 + /// The value type of the InversableMap.
4.53 + typedef typename _Map::Value Value;
4.54 + typedef std::map<Value, Key> InverseMap;
4.55 +
4.56 + typedef typename _Map::ConstReference ConstReference;
4.57 +
4.58 + /// \brief Constructor.
4.59 + ///
4.60 + /// Construct a new InversableMap for the graph.
4.61 + ///
4.62 + InversableMap(const Graph& graph) : Map(graph) {}
4.63 +
4.64 + /// \brief The setter function of the map.
4.65 + ///
4.66 + /// It sets the map and the inverse map to given key-value pair.
4.67 + void set(const Key& key, const Value& val) {
4.68 + Value oldval = Map::operator[](key);
4.69 + typename InverseMap::iterator it = invMap.find(oldval);
4.70 + if (it != invMap.end() && it->second == key) {
4.71 + invMap.erase(it);
4.72 + }
4.73 + invMap.insert(make_pair(val, key));
4.74 + Map::set(key, val);
4.75 + }
4.76 +
4.77 + /// \brief The getter function of the map.
4.78 + ///
4.79 + /// It gives back the value associated with the key.
4.80 + ConstReference operator[](const Key& key) const {
4.81 + return Map::operator[](key);
4.82 + }
4.83 +
4.84 + /// \brief Add a new key to the map.
4.85 + ///
4.86 + /// Add a new key to the map. It is called by the
4.87 + /// \c AlterationNotifier.
4.88 + virtual void add(const Key& key) {
4.89 + Map::add(key);
4.90 + }
4.91 +
4.92 + /// \brief Erase the key from the map.
4.93 + ///
4.94 + /// Erase the key to the map. It is called by the
4.95 + /// \c AlterationNotifier.
4.96 + virtual void erase(const Key& key) {
4.97 + Value val = Map::operator[](key);
4.98 + typename InverseMap::iterator it = invMap.find(val);
4.99 + if (it != invMap.end() && it->second == key) {
4.100 + invMap.erase(it);
4.101 + }
4.102 + Map::erase(key);
4.103 + }
4.104 +
4.105 + /// \brief Clear the keys from the map and inverse map.
4.106 + ///
4.107 + /// Clear the keys from the map and inverse map. It is called by the
4.108 + /// \c AlterationNotifier.
4.109 + virtual void clear() {
4.110 + invMap.clear();
4.111 + Map::clear();
4.112 + }
4.113 +
4.114 + /// \brief It gives back the just readeable inverse map.
4.115 + ///
4.116 + /// It gives back the just readeable inverse map.
4.117 + const InverseMap& inverse() const {
4.118 + return invMap;
4.119 + }
4.120 +
4.121 +
4.122 + private:
4.123 + InverseMap invMap;
4.124 + };
4.125 +
4.126 +
4.127 +
4.128 + /// \brief Provides a mutable, continous and unique descriptor for each
4.129 + /// item in the graph.
4.130 + ///
4.131 + /// The DescriptorMap class provides a mutable, continous and immutable
4.132 + /// mapping for each item in the graph.
4.133 + ///
4.134 + /// \param _Graph The graph class the \c DescriptorMap belongs to.
4.135 + /// \param _Item The Item is the Key of the Map. It may be Node, Edge or
4.136 + /// UndirEdge.
4.137 + /// \param _Map A ReadWriteMap mapping from the item type to integer.
4.138 +
4.139 + template <
4.140 + typename _Graph,
4.141 + typename _Item,
4.142 + typename _Map
4.143 + >
4.144 + class DescriptorMap : protected _Map {
4.145 +
4.146 + typedef _Item Item;
4.147 + typedef _Map Map;
4.148 +
4.149 + public:
4.150 + /// The graph class of DescriptorMap.
4.151 + typedef _Graph Graph;
4.152 +
4.153 + /// The key type of DescriptorMap (Node, Edge, UndirEdge).
4.154 + typedef typename _Map::Key Key;
4.155 + /// The value type of DescriptorMap.
4.156 + typedef typename _Map::Value Value;
4.157 +
4.158 + typedef std::vector<Item> InverseMap;
4.159 +
4.160 + /// \brief Constructor.
4.161 + ///
4.162 + /// Constructor for creating descriptor map.
4.163 + DescriptorMap(const Graph& _graph) : Map(_graph) {
4.164 + build();
4.165 + }
4.166 +
4.167 + /// \brief Add a new key to the map.
4.168 + ///
4.169 + /// Add a new key to the map. It is called by the
4.170 + /// \c AlterationNotifier.
4.171 + virtual void add(const Item& item) {
4.172 + Map::add(item);
4.173 + Map::set(item, invMap.size());
4.174 + invMap.push_back(item);
4.175 + }
4.176 +
4.177 + /// \brief Erase the key from the map.
4.178 + ///
4.179 + /// Erase the key to the map. It is called by the
4.180 + /// \c AlterationNotifier.
4.181 + virtual void erase(const Item& item) {
4.182 + Map::set(invMap.back(), Map::operator[](item));
4.183 + invMap[Map::operator[](item)] = invMap.back();
4.184 + Map::erase(item);
4.185 + }
4.186 +
4.187 + /// \brief Build the unique map.
4.188 + ///
4.189 + /// Build the unique map. It is called by the
4.190 + /// \c AlterationNotifier.
4.191 + virtual void build() {
4.192 + Map::build();
4.193 + Item it;
4.194 + for (getGraph()->first(it); it != INVALID; getGraph()->next(it)) {
4.195 + Map::set(it, invMap.size());
4.196 + invMap.push_back(it);
4.197 + }
4.198 + }
4.199 +
4.200 + /// \brief Clear the keys from the map.
4.201 + ///
4.202 + /// Clear the keys from the map. It is called by the
4.203 + /// \c AlterationNotifier.
4.204 + virtual void clear() {
4.205 + invMap.clear();
4.206 + Map::clear();
4.207 + }
4.208 +
4.209 + /// \brief Gives back the \e descriptor of the item.
4.210 + ///
4.211 + /// Gives back the mutable and unique \e descriptor of the map.
4.212 + int operator[](const Item& item) const {
4.213 + return Map::operator[](item);
4.214 + }
4.215 +
4.216 + /// \brief Gives back the inverse of the map.
4.217 + ///
4.218 + /// Gives back the inverse of the map.
4.219 + const InverseMap inverse() const {
4.220 + return invMap;
4.221 + }
4.222 +
4.223 + private:
4.224 + vector<Item> invMap;
4.225 + };
4.226 +
4.227 + /// Provides an immutable and unique id for each item in the graph.
4.228 +
4.229 + /// The IdMap class provides an unique and immutable mapping for each item
4.230 + /// in the graph.
4.231 + ///
4.232 + template <typename _Graph, typename _Item>
4.233 + class IdMap {
4.234 + public:
4.235 + typedef _Graph Graph;
4.236 + typedef int Value;
4.237 + typedef _Item Item;
4.238 +
4.239 + /// \brief The class represents the inverse of the map.
4.240 + ///
4.241 + /// The class represents the inverse of the map.
4.242 + /// \see inverse()
4.243 + class InverseMap {
4.244 + protected:
4.245 + InverseMap(const Graph& _graph) : graph(_graph) {}
4.246 + public:
4.247 + /// \brief Gives back the given item by its id.
4.248 + ///
4.249 + /// Gives back the given item by its id.
4.250 + ///
4.251 + Item operator[](int id) const { return graph->fromId(id, Item());}
4.252 + private:
4.253 + Graph* graph;
4.254 + };
4.255 +
4.256 + /// \brief Constructor.
4.257 + ///
4.258 + /// Constructor for creating id map.
4.259 + IdMap(const Graph& _graph) : graph(&_graph) {}
4.260 +
4.261 + /// \brief Gives back the \e id of the item.
4.262 + ///
4.263 + /// Gives back the immutable and unique \e id of the map.
4.264 + int operator[](const Item& item) const { return graph->id(item);}
4.265 +
4.266 + /// \brief Gives back the inverse of the map.
4.267 + ///
4.268 + /// Gives back the inverse of the map.
4.269 + InverseMap inverse() const { return InverseMap(*graph);}
4.270 +
4.271 + private:
4.272 + const Graph* graph;
4.273 +
4.274 + };
4.275 +
4.276 +
4.277 +
4.278 +}
4.279 +