alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@2391: alpar@2216: namespace lemon { alpar@2216: /*! alpar@2216: \page read_write_bg Background of Reading and Writing alpar@2216: alpar@2216: To read a map (on the nodes or edges) alpar@2216: the \ref lemon::GraphReader "GraphReader" alpar@2216: should know how to read a Value from the given map. alpar@2216: By the default implementation the input operator reads a value from alpar@2216: the stream and the type of the read value is the value type of the given map. alpar@2216: When the reader should skip a value in the stream, because you do not alpar@2216: want to store it in a map, the reader skips a character sequence without alpar@2216: whitespaces. alpar@2216: alpar@2216: If you want to change the functionality of the reader, you can use alpar@2216: template parameters to specialize it. When you give a reading alpar@2216: command for a map you can give a Reader type as template parameter. alpar@2216: With this template parameter you can control how the Reader reads alpar@2216: a value from the stream. alpar@2216: alpar@2216: The reader has the next structure: alpar@2216: \code alpar@2216: struct TypeReader { alpar@2216: typedef TypeName Value; alpar@2216: alpar@2216: void read(std::istream& is, Value& value); alpar@2216: }; alpar@2216: \endcode alpar@2216: alpar@2216: For example, the \c "strings" nodemap contains strings and you do not need alpar@2216: the value of the string just the length. Then you can implement an own Reader alpar@2216: struct. alpar@2216: alpar@2216: \code alpar@2216: struct LengthReader { alpar@2216: typedef int Value; alpar@2216: alpar@2216: void read(std::istream& is, Value& value) { alpar@2216: std::string tmp; alpar@2216: is >> tmp; alpar@2216: value = tmp.length(); alpar@2216: } alpar@2216: }; alpar@2216: ... alpar@2216: reader.readNodeMap("strings", lengthMap); alpar@2216: \endcode alpar@2216: alpar@2216: The global functionality of the reader class can be changed by giving a alpar@2216: special template parameter to the GraphReader class. By default, the alpar@2216: template parameter is \c DefaultReaderTraits. A reader traits class alpar@2216: should provide a nested template class Reader for each type, and a alpar@2216: DefaultReader for skipping a value. alpar@2216: alpar@2216: The specialization of writing is very similar to that of reading. alpar@2216: alpar@2216: \section u Undirected graphs alpar@2216: alpar@2216: In a file describing an undirected graph (ugraph, for short) you find an alpar@2216: \c uedgeset section instead of the \c edgeset section. The first line of alpar@2216: the section describes the names of the maps on the undirected egdes and all alpar@2216: next lines describe one undirected edge with the the incident nodes and the alpar@2216: values of the map. alpar@2216: alpar@2216: The format handles directed edge maps as a syntactical sugar???, if there alpar@2216: are two maps with names being the same with a \c '+' and a \c '-' prefix alpar@2216: then this will be read as a directed map. alpar@2216: alpar@2216: \code alpar@2216: @uedgeset alpar@2216: label capacity +flow -flow alpar@2216: 32 2 1 4.3 2.0 0.0 alpar@2216: 21 21 5 2.6 0.0 2.6 alpar@2216: 21 12 8 3.4 0.0 0.0 alpar@2216: \endcode alpar@2216: alpar@2216: The \c edges section is changed to \c uedges section. This section alpar@2216: describes labeled edges and undirected edges. The directed edge label alpar@2216: should start with a \c '+' or a \c '-' prefix to decide the direction alpar@2216: of the edge. alpar@2216: alpar@2216: \code alpar@2216: @uedges alpar@2216: uedge 1 alpar@2216: +edge 5 alpar@2216: -back 5 alpar@2216: \endcode alpar@2216: alpar@2216: There are similar classes to the \ref lemon::GraphReader "GraphReader" and alpar@2216: \ref lemon::GraphWriter "GraphWriter" which alpar@2216: handle the undirected graphs. These classes are alpar@2216: the \ref lemon::UGraphReader "UGraphReader" alpar@2216: and \ref lemon::UGraphWriter "UGraphWriter". alpar@2216: alpar@2216: The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()" alpar@2216: function reads an undirected map and the alpar@2216: \ref lemon::UGraphReader::readUEdge() "readUEdge()" alpar@2216: reads an undirected edge from the file, alpar@2216: alpar@2216: \code alpar@2216: reader.readUEdgeMap("capacity", capacityMap); alpar@2216: reader.readEdgeMap("flow", flowMap); alpar@2216: ... alpar@2216: reader.readUEdge("u_edge", u_edge); alpar@2216: reader.readEdge("edge", edge); alpar@2216: \endcode alpar@2216: alpar@2216: \section advanced Advanced features alpar@2216: alpar@2216: The graph reader and writer classes give an easy way to read and write alpar@2216: graphs. But sometimes we want more advanced features. In this case we can alpar@2216: use the more general lemon reader and writer interface. alpar@2216: alpar@2216: The LEMON file format is a section oriented file format. It contains one or alpar@2216: more sections, each starting with a line identifying its type alpar@2216: (the word starting with the \c \@ character). alpar@2216: The content of the section this way cannot contain line with \c \@ first alpar@2216: character. The file may contains comment lines with \c # first character. alpar@2216: alpar@2216: The \ref lemon::LemonReader "LemonReader" alpar@2216: and \ref lemon::LemonWriter "LemonWriter" alpar@2216: gives a framework to read and alpar@2216: write sections. There are various section reader and section writer alpar@2216: classes which can be attached to a \ref lemon::LemonReader "LemonReader" alpar@2216: or a \ref lemon::LemonWriter "LemonWriter". alpar@2216: alpar@2216: There are default section readers and writers for reading and writing alpar@2216: item sets, and labeled items in the graph. These read and write alpar@2216: the format described above. Other type of data can be handled with own alpar@2216: section reader and writer classes which are inherited from the alpar@2216: \c LemonReader::SectionReader or the alpar@2216: \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter" alpar@2216: classes. alpar@2216: alpar@2216: The next example defines a special section reader which reads the alpar@2216: \c \@description sections into a string: alpar@2216: alpar@2216: \code alpar@2216: class DescriptionReader : LemonReader::SectionReader { alpar@2216: protected: alpar@2216: virtual bool header(const std::string& line) { alpar@2216: std::istringstream ls(line); alpar@2216: std::string head; alpar@2216: ls >> head; alpar@2216: return head == "@description"; alpar@2216: } alpar@2216: alpar@2216: virtual void read(std::istream& is) { alpar@2216: std::string line; alpar@2216: while (getline(is, line)) { alpar@2216: desc += line; alpar@2216: } alpar@2216: } alpar@2216: public: alpar@2216: alpar@2216: typedef LemonReader::SectionReader Parent; alpar@2216: alpar@2216: DescriptionReader(LemonReader& reader) : Parent(reader) {} alpar@2216: alpar@2216: const std::string& description() const { alpar@2216: return description; alpar@2216: } alpar@2216: alpar@2216: private: alpar@2216: std::string desc; alpar@2216: }; alpar@2216: \endcode alpar@2216: alpar@2216: The other advanced stuff of the generalized file format is that alpar@2216: multiple edgesets can be stored to the same nodeset. It can be used alpar@2216: for example as a network traffic matrix. alpar@2216: alpar@2216: In our example there is a network with symmetric links and there are assymetric alpar@2216: traffic request on the network. This construction can be stored in an alpar@2216: undirected graph and in a directed \c ListEdgeSet class. The example alpar@2216: shows the input with the \ref lemon::LemonReader "LemonReader" class: alpar@2216: alpar@2216: \code alpar@2216: ListUGraph network; alpar@2216: ListUGraph::UEdgeMap capacity; alpar@2216: ListEdgeSet traffic(network); alpar@2216: ListEdgeSet::EdgeMap request(network); alpar@2216: alpar@2216: LemonReader reader(std::cin); alpar@2216: NodeSetReader nodesetReader(reader, network); alpar@2216: UEdgeSetReader alpar@2216: uEdgesetReader(reader, network, nodesetReader); alpar@2216: uEdgesetReader.readEdgeMap("capacity", capacity); alpar@2216: EdgeSetReader > alpar@2216: edgesetReader(reader, traffic, nodesetReader, "traffic"); alpar@2216: edgesetReader.readEdgeMap("request", request); alpar@2216: alpar@2216: reader.run(); alpar@2216: \endcode alpar@2216: alpar@2216: Because both the \ref lemon::GraphReader "GraphReader" alpar@2216: and the \ref lemon::UGraphReader "UGraphReader" can be converted alpar@2216: to \ref lemon::LemonReader "LemonReader" alpar@2216: and it can resolve the label's of the items, the previous alpar@2216: result can be achived with the \ref lemon::UGraphReader "UGraphReader" alpar@2216: class, too. alpar@2216: alpar@2216: alpar@2216: \code alpar@2216: ListUGraph network; alpar@2216: ListUGraph::UEdgeSet capacity; alpar@2216: ListEdgeSet traffic(network); alpar@2216: ListEdgeSet::EdgeMap request(network); alpar@2216: alpar@2216: UGraphReader reader(std::cin, network); alpar@2216: reader.readEdgeMap("capacity", capacity); alpar@2216: EdgeSetReader > alpar@2216: edgesetReader(reader, traffic, reader, "traffic"); alpar@2216: edgesetReader.readEdgeMap("request", request); alpar@2216: alpar@2216: reader.run(); alpar@2216: \endcode alpar@2216: alpar@2216: \author Balazs Dezso alpar@2216: */ alpar@2216: }