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
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:
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:
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:
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@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
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:
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@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:
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:
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
alpar@1631: the \ref lemon::UndirGraphReader "UndirGraphReader"
alpar@1631: and \ref lemon::UndirGraphWriter "UndirGraphWriter".
deba@1532:
deba@1788: The \ref lemon::UndirGraphReader::readUndirEdgeMap() "readUndirEdgeMap()"
alpar@1631: function reads an undirected map and the
alpar@1631: \ref lemon::UndirGraphReader::readUndirEdge() "readUndirEdge()"
alpar@1631: 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:
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
deba@1532: UndirListGraph network;
deba@1839: UndirListGraph::UndirEdgeMap capacity;
deba@1842: ListEdgeSet traffic(network);
deba@1842: ListEdgeSet::EdgeMap request(network);
deba@1532:
deba@1532: LemonReader reader(std::cin);
deba@1839: NodeSetReader nodesetReader(reader, network);
deba@1839: UndirEdgeSetReader
deba@1839: undirEdgesetReader(reader, network, nodesetReader);
deba@1532: undirEdgesetReader.readEdgeMap("capacity", capacity);
deba@1842: 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"
alpar@1631: and the \ref lemon::UndirGraphReader "UndirGraphReader" can be converted
alpar@1631: to \ref lemon::LemonReader "LemonReader"
deba@1901: and it can resolve the label's of the items, the previous
alpar@1631: result can be achived with the \ref lemon::UndirGraphReader "UndirGraphReader"
alpar@1631: class, too.
deba@1532:
deba@1532:
deba@1532: \code
deba@1532: UndirListGraph network;
deba@1532: UndirListGraph::UndirEdgeSet capacity;
deba@1842: ListEdgeSet traffic(network);
deba@1842: ListEdgeSet::EdgeMap request(network);
deba@1532:
deba@1842: UndirGraphReader reader(std::cin, network);
deba@1532: reader.readEdgeMap("capacity", capacity);
deba@1842: 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@1631: }