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: }