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<LengthReader>("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 <tt>lemon reader and writer</tt> 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<double> capacity;
alpar@2216: ListEdgeSet<ListUGraph> traffic(network);
alpar@2216: ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
alpar@2216: 
alpar@2216: LemonReader reader(std::cin);
alpar@2216: NodeSetReader<ListUGraph> nodesetReader(reader, network);
alpar@2216: UEdgeSetReader<ListUGraph> 
alpar@2216:   uEdgesetReader(reader, network, nodesetReader);
alpar@2216: uEdgesetReader.readEdgeMap("capacity", capacity);
alpar@2216: EdgeSetReader<ListEdgeSet<ListUGraph> > 
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<double> capacity;
alpar@2216: ListEdgeSet<ListUGraph> traffic(network);
alpar@2216: ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
alpar@2216: 
alpar@2216: UGraphReader<ListUGraph> reader(std::cin, network);
alpar@2216: reader.readEdgeMap("capacity", capacity);
alpar@2216: EdgeSetReader<ListEdgeSet<ListUGraph> > 
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: }