alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2391: * Copyright (C) 2003-2007 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@1118: namespace lemon { deba@1114: /*! deba@1114: deba@1114: deba@1114: \page graph-io-page Graph Input-Output deba@1114: athos@1540: The standard graph IO enables one to store graphs and additional maps athos@1540: (i.e. functions on the nodes or edges) in a flexible and efficient way. athos@1540: Before you read this page you should be familiar with LEMON athos@1540: \ref graphs "graphs" and \ref maps-page "maps". deba@1114: deba@1114: \section format The general file format deba@1114: deba@1532: The file contains sections in the following order: deba@1114: deba@1114: \li nodeset deba@1114: \li edgeset deba@1114: \li nodes deba@1114: \li edges deba@1532: \li attributes deba@1114: athos@1540: Some of these sections can be omitted, but you will basicly need the nodeset athos@1540: section (unless your graph has no nodes at all) and the edgeset section athos@1540: (unless your graph has no edges at all). athos@1540: athos@1540: The nodeset section describes the nodes of your graph: it identifies the nodes athos@1540: and gives the maps defined on them, if any. It starts with the athos@1540: following line: athos@1522: athos@1522: \@nodeset athos@1522: athos@1522: The next line contains the names of the nodemaps, separated by whitespaces. Each athos@1522: following line describes a node in the graph: it contains the values of the deba@1901: maps in the right order. The map named "label" should contain unique values deba@1901: because it is regarded as a label map. These labels need not be numbers but they athos@1540: must identify the nodes uniquely for later reference. For example: deba@1114: deba@1114: \code deba@1114: @nodeset deba@1901: label x-coord y-coord color deba@1114: 3 1.0 4.0 blue deba@1114: 5 2.3 5.7 red deba@1114: 12 7.8 2.3 green deba@1114: \endcode deba@1114: deba@1114: The edgeset section is very similar to the nodeset section, it has athos@1522: the same coloumn oriented structure. It starts with the line athos@1522: athos@1522: \@edgeset athos@1522: athos@1540: The next line contains the whitespace separated list of names of the edge athos@1540: maps. Each of the next lines describes one edge. The first two elements in deba@1901: the line are the labels of the source and target (or tail and head) nodes of the deba@1901: edge as they occur in the label node map of the nodeset section. You can also deba@1901: have an optional label map on the edges for later reference (which has to be athos@1540: unique in this case). deba@1114: deba@1114: \code deba@1114: @edgeset deba@1901: label weight note deba@1901: 3 5 a 4.3 a-edge deba@1901: 5 12 c 2.6 c-edge deba@1901: 3 12 g 3.4 g-edge deba@1114: \endcode deba@1114: athos@1540: The \e nodes section contains labeled (distinguished) nodes athos@1540: (i.e. nodes having a special alpar@1118: label on them). The section starts with athos@1522: athos@1522: \@nodes athos@1522: athos@1522: Each of the next lines contains a label for a node in the graph deba@1901: and then the label as described in the \e nodeset section. deba@1114: deba@1114: \code deba@1114: @nodes deba@1114: source 3 deba@1114: target 12 deba@1114: \endcode deba@1114: athos@1540: The last section describes the labeled (distinguished) edges deba@1333: (i.e. edges having a special label on them). It starts with \c \@edges deba@1901: and then each line contains the name of the edge and the label. deba@1114: deba@1114: \code athos@1540: @edges deba@1114: observed c deba@1114: \endcode deba@1114: deba@1114: deba@1114: The file may contain empty lines and comment lines. The comment lines deba@1114: start with an \c # character. deba@1114: deba@1532: The attributes section can handle some information about the graph. It athos@1540: contains key-value pairs in each line (a key and the mapped value to key). The athos@1540: key should be a string without whitespaces, the value can be of various types. deba@1532: deba@1532: \code deba@1532: @attributes alpar@1959: title "Four colored planar graph" deba@1532: author "Balazs DEZSO" deba@1532: copyright "Lemon Library" deba@1532: version 12 deba@1532: \endcode deba@1532: deba@1901: Finally, the file should be closed with \c \@end line. athos@1522: deba@1114: deba@1114: \section use Using graph input-output athos@1540: athos@1540: athos@1540: The graph input and output is based on reading and writing athos@1540: commands. The user gives reading and writing commands to the reader or athos@1540: writer class, then he calls the \c run() method that executes all the given athos@1540: commands. deba@1114: deba@1114: \subsection write Writing a graph deba@1114: alpar@1631: The \ref lemon::GraphWriter "GraphWriter" template class alpar@1631: provides the graph output. To write a graph athos@1526: you should first give writing commands to the writer. You can declare athos@1540: writing command as \c NodeMap or \c EdgeMap writing and labeled Node and deba@1114: Edge writing. deba@1114: deba@1114: \code deba@1333: GraphWriter writer(std::cout, graph); deba@1114: \endcode deba@1114: alpar@1631: The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()" alpar@1631: function declares a \c NodeMap writing command in the alpar@1631: \ref lemon::GraphWriter "GraphWriter". alpar@1631: You should give a name to the map and the map deba@1901: object as parameters. The NodeMap writing command with name "label" should write a deba@1901: unique map because it will be regarded as a label map. deba@1114: deba@1114: \see IdMap, DescriptorMap deba@1114: deba@1114: \code deba@1901: IdMap nodeLabelMap; deba@1901: writer.writeNodeMap("label", nodeLabelMap); deba@1114: deba@1394: writer.writeNodeMap("x-coord", xCoordMap); deba@1394: writer.writeNodeMap("y-coord", yCoordMap); deba@1394: writer.writeNodeMap("color", colorMap); deba@1114: \endcode deba@1114: alpar@1631: With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()" alpar@1631: member function you can give an edge map deba@1333: writing command similar to the NodeMaps. deba@1114: deba@1114: \see IdMap, DescriptorMap athos@1522: deba@1114: \code deba@1114: DescriptorMap > edgeDescMap(graph); deba@1394: writer.writeEdgeMap("descriptor", edgeDescMap); deba@1114: deba@1394: writer.writeEdgeMap("weight", weightMap); deba@1901: writer.writeEdgeMap("note", noteMap); deba@1114: \endcode deba@1114: alpar@1631: With \ref lemon::GraphWriter::writeNode() "writeNode()" alpar@1631: and \ref lemon::GraphWriter::writeEdge() "writeEdge()" alpar@1631: functions you can designate Nodes and athos@1522: Edges in the graph. For example, you can write out the source and target node athos@1522: of a maximum flow instance. deba@1114: deba@1114: \code deba@1394: writer.writeNode("source", sourceNode); deba@1394: writer.writeNode("target", targetNode); deba@1114: deba@1394: writer.writeEdge("observed", edge); deba@1114: \endcode deba@1114: alpar@1631: With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()" alpar@1631: function you can write an attribute to the file. deba@1532: deba@1532: \code deba@1532: writer.writeAttribute("author", "Balazs DEZSO"); deba@1532: writer.writeAttribute("version", 12); deba@1532: \endcode deba@1532: alpar@1631: After you give all write commands you must call the alpar@1631: \ref lemon::GraphWriter::run() "run()" member athos@1522: function, which executes all the writing commands. deba@1114: deba@1114: \code deba@1114: writer.run(); deba@1114: \endcode deba@1114: deba@1114: \subsection reading Reading a graph deba@1114: athos@1540: The file to be read may contain several maps and labeled nodes or edges. deba@1114: If you read a graph you need not read all the maps and items just those alpar@1631: that you need. The interface of the \ref lemon::GraphReader "GraphReader" alpar@1631: is very similar to alpar@1631: the \ref lemon::GraphWriter "GraphWriter" alpar@1631: but the reading method does not depend on the order of the deba@1114: given commands. deba@1114: deba@2100: The reader object assumes that each not read value does not contain alpar@1118: whitespaces, therefore it has some extra possibilities to control how alpar@1118: it should skip the values when the string representation contains spaces. deba@1114: deba@1114: \code deba@1333: GraphReader reader(std::cin, graph); deba@1114: \endcode deba@1114: alpar@1631: The \ref lemon::GraphReader::readNodeMap() "readNodeMap()" alpar@1631: function reads a map from the \c nodeset section. athos@1522: If there is a map that you do not want to read from the file and there are athos@1522: whitespaces in the string represenation of the values then you should alpar@1631: call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()" alpar@1631: template member function with proper parameters. deba@1114: deba@1114: \see QuotedStringReader athos@1522: deba@1114: \code deba@1394: reader.readNodeMap("x-coord", xCoordMap); deba@1394: reader.readNodeMap("y-coord", yCoordMap); deba@1114: deba@1394: reader.readNodeMap("label", labelMap); deba@1114: reader.skipNodeMap("description"); deba@1114: deba@1394: reader.readNodeMap("color", colorMap); deba@1114: \endcode deba@1114: alpar@1631: With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()" alpar@1631: member function you can give an edge map deba@1114: reading command similar to the NodeMaps. deba@1114: deba@1114: \code deba@1394: reader.readEdgeMap("weight", weightMap); deba@1394: reader.readEdgeMap("label", labelMap); deba@1114: \endcode deba@1114: alpar@1631: With \ref lemon::GraphReader::readNode() "readNode()" alpar@1631: and \ref lemon::GraphReader::readEdge() "readEdge()" alpar@1631: functions you can read labeled Nodes and deba@1114: Edges. deba@1114: deba@1114: \code deba@1394: reader.readNode("source", sourceNode); deba@1394: reader.readNode("target", targetNode); deba@1114: deba@1394: reader.readEdge("observed", edge); deba@1114: \endcode deba@1114: alpar@1631: With \ref lemon::GraphReader::readAttribute() "readAttribute()" alpar@1631: function you can read an attribute from the file. deba@1532: deba@1532: \code deba@1532: std::string author; deba@1532: writer.readAttribute("author", author); deba@1532: int version; deba@1532: writer.writeAttribute("version", version); deba@1532: \endcode deba@1532: alpar@1631: After you give all read commands you must call the alpar@1631: \ref lemon::GraphReader::run() "run()" member athos@1522: function, which executes all the commands. deba@1114: deba@1114: \code deba@1114: reader.run(); deba@1114: \endcode deba@1114: athos@1540: \anchor rwbackground athos@1527: \section types Background of Reading and Writing athos@1540: athos@1540: athos@1527: To read a map (on the nodes or edges) alpar@1631: the \ref lemon::GraphReader "GraphReader" alpar@1631: should know how to read a Value from the given map. deba@1114: By the default implementation the input operator reads a value from deba@2100: the stream and the type of the read value is the value type of the given map. deba@1114: When the reader should skip a value in the stream, because you do not athos@1527: want to store it in a map, the reader skips a character sequence without athos@1540: whitespaces. deba@1114: deba@1114: If you want to change the functionality of the reader, you can use deba@1114: template parameters to specialize it. When you give a reading deba@1114: command for a map you can give a Reader type as template parameter. deba@1333: With this template parameter you can control how the Reader reads deba@1114: a value from the stream. deba@1114: deba@1114: The reader has the next structure: deba@1114: \code deba@1114: struct TypeReader { deba@1114: typedef TypeName Value; deba@1114: deba@1114: void read(std::istream& is, Value& value); deba@1114: }; deba@1114: \endcode deba@1114: athos@1527: For example, the \c "strings" nodemap contains strings and you do not need athos@1540: the value of the string just the length. Then you can implement an own Reader deba@1114: struct. deba@1114: deba@1114: \code deba@1114: struct LengthReader { deba@1114: typedef int Value; deba@1114: deba@1114: void read(std::istream& is, Value& value) { deba@1114: std::string tmp; deba@1114: is >> tmp; deba@1114: value = tmp.length(); deba@1114: } deba@1114: }; deba@1114: ... deba@1394: reader.readNodeMap("strings", lengthMap); deba@1114: \endcode deba@1114: deba@1114: The global functionality of the reader class can be changed by giving a athos@1526: special template parameter to the GraphReader class. By default, the alpar@1118: template parameter is \c DefaultReaderTraits. A reader traits class deba@1901: should provide a nested template class Reader for each type, and a deba@1114: DefaultReader for skipping a value. deba@1114: deba@1901: The specialization of writing is very similar to that of reading. deba@1114: deba@2502: \section undir Undirected and Bipartite graphs deba@1532: klao@1909: In a file describing an undirected graph (ugraph, for short) you find an klao@1909: \c uedgeset section instead of the \c edgeset section. The first line of athos@1540: the section describes the names of the maps on the undirected egdes and all athos@1540: next lines describe one undirected edge with the the incident nodes and the athos@1540: values of the map. deba@1532: deba@2502: The format could store directed edge maps, if there are two maps with deba@2502: names being the same with a \c '+' and a \c '-' prefix then this could deba@2502: be read as such a map. deba@1532: deba@1532: \code klao@1909: @uedgeset deba@1901: label capacity +flow -flow deba@1901: 32 2 1 4.3 2.0 0.0 deba@1901: 21 21 5 2.6 0.0 2.6 deba@1901: 21 12 8 3.4 0.0 0.0 deba@1532: \endcode deba@1532: klao@1909: The \c edges section is changed to \c uedges section. This section deba@1532: describes labeled edges and undirected edges. The directed edge label athos@1540: should start with a \c '+' or a \c '-' prefix to decide the direction deba@1532: of the edge. deba@1532: deba@1532: \code klao@1909: @uedges klao@1909: uedge 1 deba@1532: +edge 5 deba@1532: -back 5 deba@1532: \endcode deba@1532: alpar@1631: There are similar classes to the \ref lemon::GraphReader "GraphReader" and alpar@1631: \ref lemon::GraphWriter "GraphWriter" which alpar@1631: handle the undirected graphs. These classes are klao@1909: the \ref lemon::UGraphReader "UGraphReader" klao@1909: and \ref lemon::UGraphWriter "UGraphWriter". deba@1532: klao@1909: The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()" alpar@1631: function reads an undirected map and the klao@1909: \ref lemon::UGraphReader::readUEdge() "readUEdge()" alpar@1631: reads an undirected edge from the file, deba@1532: deba@1532: \code klao@1909: reader.readUEdgeMap("capacity", capacityMap); deba@1532: reader.readEdgeMap("flow", flowMap); deba@1532: ... klao@1909: reader.readUEdge("u_edge", u_edge); deba@1532: reader.readEdge("edge", edge); deba@1532: \endcode deba@1532: deba@2502: The undirected bipartite graphs could be read with the \c BpUGraph deba@2502: class and it has specialized nodeset section, which should be start deba@2502: with \c "@bpnodeset". This section is separated to two deba@2502: subsections. The header line of these sections start with "&anodeset" deba@2502: or "&bnodeset" and after that the line contains the names of the deba@2502: regular and A-node or B-node maps accordingly. The lines of each deba@2502: section contains the mapped values. The labels of the graph should be deba@2502: unique overall both subsections. deba@2502: deba@2502: \code deba@2502: @bpnodeset deba@2502: &anodeset label coords radius deba@2502: 0 (0, 0) 14.0 deba@2502: 1 (0, 1) 12.0 deba@2502: &bnodeset label coords deba@2502: 2 (1, 0) deba@2502: 3 (1, 1) deba@2502: \endcode deba@2502: deba@2502: The reading can be done with \ref lemon::BpUGraphReader::readANodeMap() deba@2502: "readANodeMap()", \ref lemon::BpUGraphReader::readBNodeMap() deba@2502: "readBNodeMap()" or \ref lemon::BpUGraphReader::readNodeMap() deba@2502: "readNodeMap()" members. deba@2502: deba@2502: \code deba@2502: reader.readNodeMap("coords", coords); deba@2502: reader.readAnodeMap("radius", radius); deba@2502: \endcode deba@2502: deba@1532: \section advanced Advanced features deba@1532: athos@1540: The graph reader and writer classes give an easy way to read and write athos@1540: graphs. But sometimes we want more advanced features. In this case we can athos@1540: use the more general lemon reader and writer interface. deba@1532: athos@1540: The LEMON file format is a section oriented file format. It contains one or athos@1540: more sections, each starting with a line identifying its type athos@1540: (the word starting with the \c \@ character). deba@1532: The content of the section this way cannot contain line with \c \@ first deba@1532: character. The file may contains comment lines with \c # first character. deba@1532: alpar@1631: The \ref lemon::LemonReader "LemonReader" alpar@1631: and \ref lemon::LemonWriter "LemonWriter" alpar@1631: gives a framework to read and deba@1532: write sections. There are various section reader and section writer alpar@1631: classes which can be attached to a \ref lemon::LemonReader "LemonReader" alpar@1631: or a \ref lemon::LemonWriter "LemonWriter". deba@1532: deba@1532: There are default section readers and writers for reading and writing athos@1540: item sets, and labeled items in the graph. These read and write deba@1532: the format described above. Other type of data can be handled with own deba@1532: section reader and writer classes which are inherited from the alpar@1631: \c LemonReader::SectionReader or the alpar@1631: \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter" alpar@1631: classes. deba@1532: deba@1532: The next example defines a special section reader which reads the deba@1532: \c \@description sections into a string: deba@1532: deba@1532: \code deba@1532: class DescriptionReader : LemonReader::SectionReader { deba@1532: protected: deba@1532: virtual bool header(const std::string& line) { deba@1532: std::istringstream ls(line); deba@1532: std::string head; deba@1532: ls >> head; deba@1532: return head == "@description"; deba@1532: } deba@1532: deba@1532: virtual void read(std::istream& is) { deba@1532: std::string line; deba@1532: while (getline(is, line)) { deba@1532: desc += line; deba@1532: } deba@1532: } deba@1532: public: deba@1532: deba@1532: typedef LemonReader::SectionReader Parent; deba@1532: deba@1532: DescriptionReader(LemonReader& reader) : Parent(reader) {} deba@1532: deba@1532: const std::string& description() const { deba@1532: return description; deba@1532: } deba@1532: deba@1532: private: deba@1532: std::string desc; deba@1532: }; deba@1532: \endcode deba@1532: deba@1532: The other advanced stuff of the generalized file format is that deba@1532: multiple edgesets can be stored to the same nodeset. It can be used athos@1540: for example as a network traffic matrix. deba@1532: athos@1540: In our example there is a network with symmetric links and there are assymetric deba@1532: traffic request on the network. This construction can be stored in an deba@1842: undirected graph and in a directed \c ListEdgeSet class. The example alpar@1631: shows the input with the \ref lemon::LemonReader "LemonReader" class: deba@1532: deba@1532: \code klao@1909: ListUGraph network; klao@1909: ListUGraph::UEdgeMap capacity; klao@1909: ListEdgeSet traffic(network); klao@1909: ListEdgeSet::EdgeMap request(network); deba@1532: deba@1532: LemonReader reader(std::cin); klao@1909: NodeSetReader nodesetReader(reader, network); klao@1909: UEdgeSetReader klao@1909: uEdgesetReader(reader, network, nodesetReader); klao@1909: uEdgesetReader.readEdgeMap("capacity", capacity); klao@1909: EdgeSetReader > deba@1848: edgesetReader(reader, traffic, nodesetReader, "traffic"); deba@1532: edgesetReader.readEdgeMap("request", request); deba@1532: deba@1532: reader.run(); deba@1532: \endcode deba@1532: alpar@1631: Because both the \ref lemon::GraphReader "GraphReader" klao@1909: and the \ref lemon::UGraphReader "UGraphReader" can be converted alpar@1631: to \ref lemon::LemonReader "LemonReader" deba@1901: and it can resolve the label's of the items, the previous klao@1909: result can be achived with the \ref lemon::UGraphReader "UGraphReader" alpar@1631: class, too. deba@1532: deba@1532: deba@1532: \code klao@1909: ListUGraph network; klao@1909: ListUGraph::UEdgeSet capacity; klao@1909: ListEdgeSet traffic(network); klao@1909: ListEdgeSet::EdgeMap request(network); deba@1532: klao@1909: UGraphReader reader(std::cin, network); deba@1532: reader.readEdgeMap("capacity", capacity); klao@1909: EdgeSetReader > deba@1848: edgesetReader(reader, traffic, reader, "traffic"); deba@1532: edgesetReader.readEdgeMap("request", request); deba@1532: deba@1532: reader.run(); deba@1532: \endcode deba@1532: deba@1333: \author Balazs Dezso deba@1114: */ alpar@2391: }