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 athos@1522: maps in the right order. The map named "id" should contain unique values athos@1540: because it is regarded as an ID-map. These ids 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@1114: id 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 athos@1540: the line are the IDs of the source and target (or tail and head) nodes of the athos@1540: edge as they occur in the ID node map of the nodeset section. You can also athos@1540: have an optional ID 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@1114: id weight label deba@1114: 3 5 a 4.3 a-edge deba@1114: 5 12 c 2.6 c-edge deba@1114: 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 athos@1540: and then the ID 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@1114: and then each line contains the name of the edge and the ID. 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 deba@1532: title "Four colored plan graph" deba@1532: author "Balazs DEZSO" deba@1532: copyright "Lemon Library" deba@1532: version 12 deba@1532: \endcode deba@1532: athos@1522: \@end athos@1522: athos@1522: line. athos@1522: deba@1114: deba@1114: \section use Using graph input-output athos@1540: athos@1540: The easiest way of using graph input and output is using the versions of the athos@1540: public \ref readGraph() and \ref writeGraph() functions; if you don't need athos@1540: very sophisticated behaviour then you might be satisfied with athos@1540: those. Otherwise go on reading this page. 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: deba@1114: The \c GraphWriter class 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: deba@1394: The \c writeNodeMap() function declares a \c NodeMap writing command in the athos@1540: \c GraphWriter. You should give a name to the map and the map athos@1522: object as parameters. The NodeMap writing command with name "id" should write a athos@1540: unique map because it will be regarded as an ID map. deba@1114: deba@1114: \see IdMap, DescriptorMap deba@1114: deba@1114: \code deba@1114: IdMap nodeIdMap; deba@1394: writer.writeNodeMap("id", nodeIdMap); 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: deba@1394: With the \c writeEdgeMap() 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@1394: writer.writeEdgeMap("label", labelMap); deba@1114: \endcode deba@1114: athos@1522: With \c writeNode() and \c writeEdge() 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: deba@1532: With \c writeAttribute() 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: deba@1114: After you give all write commands you must call the \c 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 deba@1114: that you need. The interface of the \c GraphReader is very similar to athos@1522: the GraphWriter but the reading method does not depend on the order of the deba@1114: given commands. deba@1114: athos@1522: The reader object assumes that each not readed 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: athos@1540: The \c readNodeMap() 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 deba@1114: call the \c skipNodeMap() 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: deba@1394: With the \c readEdgeMap() 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: deba@1394: With \c readNode() and \c readEdge() 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: deba@1532: With \c readAttribute() 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: deba@1114: After you give all read commands you must call the \c 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) athos@1527: the \c GraphReader 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@1114: the stream and the type of the readed 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 athos@1540: should provide an inner template class Reader for each type, and a deba@1114: DefaultReader for skipping a value. deba@1114: athos@1540: The specialization of writing is very similar to that of reading. deba@1114: athos@1540: \section undir Undirected graphs deba@1532: athos@1540: In a file describing an undirected graph (undir graph, for short) you find an athos@1540: \c undiredgeset 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: athos@1540: The format handles directed edge maps as a syntactical sugar???, if there athos@1540: are two maps with names being the same with a \c '+' and a \c '-' prefix athos@1540: then this will be read as a directed map. deba@1532: deba@1532: \code deba@1532: @undiredgeset deba@1532: id capacity +flow -flow deba@1532: 32 2 1 4.3 2.0 0.0 deba@1532: 21 21 5 2.6 0.0 2.6 deba@1532: 21 12 8 3.4 0.0 0.0 deba@1532: \endcode deba@1532: athos@1540: The \c edges section is changed to \c undiredges 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 deba@1532: @undiredges deba@1532: undiredge 1 deba@1532: +edge 5 deba@1532: -back 5 deba@1532: \endcode deba@1532: deba@1532: There are similar classes to the \c GraphReader ans \c GraphWriter deba@1532: which handle the undirected graphs. These classes are the deba@1532: \c UndirGraphReader and \UndirGraphWriter. deba@1532: deba@1532: The \c readUndirMap() function reads an undirected map and the deba@1532: \c readUndirEdge() reads an undirected edge from the file, deba@1532: deba@1532: \code deba@1532: reader.readUndirEdgeMap("capacity", capacityMap); deba@1532: reader.readEdgeMap("flow", flowMap); deba@1532: ... deba@1532: reader.readUndirEdge("undir_edge", undir_edge); deba@1532: reader.readEdge("edge", edge); deba@1532: \endcode deba@1532: 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: deba@1532: The \c LemonReader and \c LemonWriter gives a framework to read and deba@1532: write sections. There are various section reader and section writer deba@1532: classes which can be attached to a \c LemonReader or a \c 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 deba@1532: \c LemonReader::SectionReader or the \c LemonWriter::SectionWriter 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 athos@1540: undirected graph and in a directed NewEdgeSetAdaptor class. The example deba@1532: shows the input with the LemonReader class: deba@1532: deba@1532: \code deba@1532: UndirListGraph network; deba@1532: UndirListGraph::UndirEdgeSet capacity; deba@1532: NewEdgeSetAdaptor traffic(network); deba@1532: NewEdgeSetAdaptor::EdgeSet request(network); deba@1532: deba@1532: LemonReader reader(std::cin); deba@1532: NodeSetReader nodesetReader(reader, network); deba@1532: UndirEdgeSetReader undirEdgesetReader(reader, network, nodesetReader); deba@1532: undirEdgesetReader.readEdgeMap("capacity", capacity); deba@1532: EdgeSetReader edgesetReader(reader, traffic, nodesetReader); deba@1532: edgesetReader.readEdgeMap("request", request); deba@1532: deba@1532: reader.run(); deba@1532: \endcode deba@1532: deba@1532: Because the GraphReader and the UndirGraphReader can be converted deba@1532: to LemonReader and it can resolve the ID's of the items, the previous athos@1540: result can be achived with the UndirGraphReader class, too. deba@1532: deba@1532: deba@1532: \code deba@1532: UndirListGraph network; deba@1532: UndirListGraph::UndirEdgeSet capacity; deba@1532: NewEdgeSetAdaptor traffic(network); deba@1532: NewEdgeSetAdaptor::EdgeSet request(network); deba@1532: deba@1532: UndirGraphReader reader(std::cin, network); deba@1532: reader.readEdgeMap("capacity", capacity); deba@1532: EdgeSetReader edgesetReader(reader, traffic, reader); deba@1532: edgesetReader.readEdgeMap("request", request); deba@1532: deba@1532: reader.run(); deba@1532: \endcode deba@1532: deba@1333: \author Balazs Dezso deba@1114: */ deba@1333: }