3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
23 \page graph-io-page Graph Input-Output
25 The standard graph IO enables one to store graphs and additional maps
26 (i.e. functions on the nodes or edges) in a flexible and efficient way.
27 Before you read this page you should be familiar with LEMON
28 \ref graphs "graphs" and \ref maps-page "maps".
30 \section format The general file format
32 The file contains sections in the following order:
40 Some of these sections can be omitted, but you will basicly need the nodeset
41 section (unless your graph has no nodes at all) and the edgeset section
42 (unless your graph has no edges at all).
44 The nodeset section describes the nodes of your graph: it identifies the nodes
45 and gives the maps defined on them, if any. It starts with the
50 The next line contains the names of the nodemaps, separated by whitespaces. Each
51 following line describes a node in the graph: it contains the values of the
52 maps in the right order. The map named "label" should contain unique values
53 because it is regarded as a label map. These labels need not be numbers but they
54 must identify the nodes uniquely for later reference. For example:
58 label x-coord y-coord color
64 The edgeset section is very similar to the nodeset section, it has
65 the same coloumn oriented structure. It starts with the line
69 The next line contains the whitespace separated list of names of the edge
70 maps. Each of the next lines describes one edge. The first two elements in
71 the line are the labels of the source and target (or tail and head) nodes of the
72 edge as they occur in the label node map of the nodeset section. You can also
73 have an optional label map on the edges for later reference (which has to be
84 The \e nodes section contains <em>labeled (distinguished) nodes</em>
85 (i.e. nodes having a special
86 label on them). The section starts with
90 Each of the next lines contains a label for a node in the graph
91 and then the label as described in the \e nodeset section.
99 The last section describes the <em>labeled (distinguished) edges</em>
100 (i.e. edges having a special label on them). It starts with \c \@edges
101 and then each line contains the name of the edge and the label.
109 The file may contain empty lines and comment lines. The comment lines
110 start with an \c # character.
112 The attributes section can handle some information about the graph. It
113 contains key-value pairs in each line (a key and the mapped value to key). The
114 key should be a string without whitespaces, the value can be of various types.
118 title "Four colored planar graph"
119 author "Balazs DEZSO"
120 copyright "Lemon Library"
124 Finally, the file should be closed with \c \@end line.
127 \section use Using graph input-output
130 The graph input and output is based on <em> reading and writing
131 commands</em>. The user gives reading and writing commands to the reader or
132 writer class, then he calls the \c run() method that executes all the given
135 \subsection write Writing a graph
137 The \ref lemon::GraphWriter "GraphWriter" template class
138 provides the graph output. To write a graph
139 you should first give writing commands to the writer. You can declare
140 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
144 GraphWriter<ListGraph> writer(std::cout, graph);
147 The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
148 function declares a \c NodeMap writing command in the
149 \ref lemon::GraphWriter "GraphWriter".
150 You should give a name to the map and the map
151 object as parameters. The NodeMap writing command with name "label" should write a
152 unique map because it will be regarded as a label map.
154 \see IdMap, DescriptorMap
157 IdMap<ListGraph, Node> nodeLabelMap;
158 writer.writeNodeMap("label", nodeLabelMap);
160 writer.writeNodeMap("x-coord", xCoordMap);
161 writer.writeNodeMap("y-coord", yCoordMap);
162 writer.writeNodeMap("color", colorMap);
165 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
166 member function you can give an edge map
167 writing command similar to the NodeMaps.
169 \see IdMap, DescriptorMap
172 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
173 writer.writeEdgeMap("descriptor", edgeDescMap);
175 writer.writeEdgeMap("weight", weightMap);
176 writer.writeEdgeMap("note", noteMap);
179 With \ref lemon::GraphWriter::writeNode() "writeNode()"
180 and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
181 functions you can designate Nodes and
182 Edges in the graph. For example, you can write out the source and target node
183 of a maximum flow instance.
186 writer.writeNode("source", sourceNode);
187 writer.writeNode("target", targetNode);
189 writer.writeEdge("observed", edge);
192 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
193 function you can write an attribute to the file.
196 writer.writeAttribute("author", "Balazs DEZSO");
197 writer.writeAttribute("version", 12);
200 After you give all write commands you must call the
201 \ref lemon::GraphWriter::run() "run()" member
202 function, which executes all the writing commands.
208 \subsection reading Reading a graph
210 The file to be read may contain several maps and labeled nodes or edges.
211 If you read a graph you need not read all the maps and items just those
212 that you need. The interface of the \ref lemon::GraphReader "GraphReader"
214 the \ref lemon::GraphWriter "GraphWriter"
215 but the reading method does not depend on the order of the
218 The reader object assumes that each not read value does not contain
219 whitespaces, therefore it has some extra possibilities to control how
220 it should skip the values when the string representation contains spaces.
223 GraphReader<ListGraph> reader(std::cin, graph);
226 The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
227 function reads a map from the \c nodeset section.
228 If there is a map that you do not want to read from the file and there are
229 whitespaces in the string represenation of the values then you should
230 call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
231 template member function with proper parameters.
233 \see QuotedStringReader
236 reader.readNodeMap("x-coord", xCoordMap);
237 reader.readNodeMap("y-coord", yCoordMap);
239 reader.readNodeMap<QuotedStringReader>("label", labelMap);
240 reader.skipNodeMap<QuotedStringReader>("description");
242 reader.readNodeMap("color", colorMap);
245 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
246 member function you can give an edge map
247 reading command similar to the NodeMaps.
250 reader.readEdgeMap("weight", weightMap);
251 reader.readEdgeMap("label", labelMap);
254 With \ref lemon::GraphReader::readNode() "readNode()"
255 and \ref lemon::GraphReader::readEdge() "readEdge()"
256 functions you can read labeled Nodes and
260 reader.readNode("source", sourceNode);
261 reader.readNode("target", targetNode);
263 reader.readEdge("observed", edge);
266 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
267 function you can read an attribute from the file.
271 writer.readAttribute("author", author);
273 writer.writeAttribute("version", version);
276 After you give all read commands you must call the
277 \ref lemon::GraphReader::run() "run()" member
278 function, which executes all the commands.
285 \section types Background of Reading and Writing
288 To read a map (on the nodes or edges)
289 the \ref lemon::GraphReader "GraphReader"
290 should know how to read a Value from the given map.
291 By the default implementation the input operator reads a value from
292 the stream and the type of the read value is the value type of the given map.
293 When the reader should skip a value in the stream, because you do not
294 want to store it in a map, the reader skips a character sequence without
297 If you want to change the functionality of the reader, you can use
298 template parameters to specialize it. When you give a reading
299 command for a map you can give a Reader type as template parameter.
300 With this template parameter you can control how the Reader reads
301 a value from the stream.
303 The reader has the next structure:
306 typedef TypeName Value;
308 void read(std::istream& is, Value& value);
312 For example, the \c "strings" nodemap contains strings and you do not need
313 the value of the string just the length. Then you can implement an own Reader
317 struct LengthReader {
320 void read(std::istream& is, Value& value) {
323 value = tmp.length();
327 reader.readNodeMap<LengthReader>("strings", lengthMap);
330 The global functionality of the reader class can be changed by giving a
331 special template parameter to the GraphReader class. By default, the
332 template parameter is \c DefaultReaderTraits. A reader traits class
333 should provide a nested template class Reader for each type, and a
334 DefaultReader for skipping a value.
336 The specialization of writing is very similar to that of reading.
338 \section u Undirected graphs
340 In a file describing an undirected graph (ugraph, for short) you find an
341 \c uedgeset section instead of the \c edgeset section. The first line of
342 the section describes the names of the maps on the undirected egdes and all
343 next lines describe one undirected edge with the the incident nodes and the
346 The format handles directed edge maps as a syntactical sugar???, if there
347 are two maps with names being the same with a \c '+' and a \c '-' prefix
348 then this will be read as a directed map.
352 label capacity +flow -flow
358 The \c edges section is changed to \c uedges section. This section
359 describes labeled edges and undirected edges. The directed edge label
360 should start with a \c '+' or a \c '-' prefix to decide the direction
370 There are similar classes to the \ref lemon::GraphReader "GraphReader" and
371 \ref lemon::GraphWriter "GraphWriter" which
372 handle the undirected graphs. These classes are
373 the \ref lemon::UGraphReader "UGraphReader"
374 and \ref lemon::UGraphWriter "UGraphWriter".
376 The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
377 function reads an undirected map and the
378 \ref lemon::UGraphReader::readUEdge() "readUEdge()"
379 reads an undirected edge from the file,
382 reader.readUEdgeMap("capacity", capacityMap);
383 reader.readEdgeMap("flow", flowMap);
385 reader.readUEdge("u_edge", u_edge);
386 reader.readEdge("edge", edge);
389 \section advanced Advanced features
391 The graph reader and writer classes give an easy way to read and write
392 graphs. But sometimes we want more advanced features. In this case we can
393 use the more general <tt>lemon reader and writer</tt> interface.
395 The LEMON file format is a section oriented file format. It contains one or
396 more sections, each starting with a line identifying its type
397 (the word starting with the \c \@ character).
398 The content of the section this way cannot contain line with \c \@ first
399 character. The file may contains comment lines with \c # first character.
401 The \ref lemon::LemonReader "LemonReader"
402 and \ref lemon::LemonWriter "LemonWriter"
403 gives a framework to read and
404 write sections. There are various section reader and section writer
405 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
406 or a \ref lemon::LemonWriter "LemonWriter".
408 There are default section readers and writers for reading and writing
409 item sets, and labeled items in the graph. These read and write
410 the format described above. Other type of data can be handled with own
411 section reader and writer classes which are inherited from the
412 \c LemonReader::SectionReader or the
413 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
416 The next example defines a special section reader which reads the
417 \c \@description sections into a string:
420 class DescriptionReader : LemonReader::SectionReader {
422 virtual bool header(const std::string& line) {
423 std::istringstream ls(line);
426 return head == "@description";
429 virtual void read(std::istream& is) {
431 while (getline(is, line)) {
437 typedef LemonReader::SectionReader Parent;
439 DescriptionReader(LemonReader& reader) : Parent(reader) {}
441 const std::string& description() const {
450 The other advanced stuff of the generalized file format is that
451 multiple edgesets can be stored to the same nodeset. It can be used
452 for example as a network traffic matrix.
454 In our example there is a network with symmetric links and there are assymetric
455 traffic request on the network. This construction can be stored in an
456 undirected graph and in a directed \c ListEdgeSet class. The example
457 shows the input with the \ref lemon::LemonReader "LemonReader" class:
461 ListUGraph::UEdgeMap<double> capacity;
462 ListEdgeSet<ListUGraph> traffic(network);
463 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
465 LemonReader reader(std::cin);
466 NodeSetReader<ListUGraph> nodesetReader(reader, network);
467 UEdgeSetReader<ListUGraph>
468 uEdgesetReader(reader, network, nodesetReader);
469 uEdgesetReader.readEdgeMap("capacity", capacity);
470 EdgeSetReader<ListEdgeSet<ListUGraph> >
471 edgesetReader(reader, traffic, nodesetReader, "traffic");
472 edgesetReader.readEdgeMap("request", request);
477 Because both the \ref lemon::GraphReader "GraphReader"
478 and the \ref lemon::UGraphReader "UGraphReader" can be converted
479 to \ref lemon::LemonReader "LemonReader"
480 and it can resolve the label's of the items, the previous
481 result can be achived with the \ref lemon::UGraphReader "UGraphReader"
487 ListUGraph::UEdgeSet<double> capacity;
488 ListEdgeSet<ListUGraph> traffic(network);
489 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
491 UGraphReader<ListUGraph> reader(std::cin, network);
492 reader.readEdgeMap("capacity", capacity);
493 EdgeSetReader<ListEdgeSet<ListUGraph> >
494 edgesetReader(reader, traffic, reader, "traffic");
495 edgesetReader.readEdgeMap("request", request);