Notebook tabs can be closed.
5 \page graph-io-page Graph Input-Output
7 The standard graph IO enables one to store graphs and additional maps
8 (i.e. functions on the nodes or edges) in a flexible and efficient way.
9 Before you read this page you should be familiar with LEMON
10 \ref graphs "graphs" and \ref maps-page "maps".
12 \section format The general file format
14 The file contains sections in the following order:
22 Some of these sections can be omitted, but you will basicly need the nodeset
23 section (unless your graph has no nodes at all) and the edgeset section
24 (unless your graph has no edges at all).
26 The nodeset section describes the nodes of your graph: it identifies the nodes
27 and gives the maps defined on them, if any. It starts with the
32 The next line contains the names of the nodemaps, separated by whitespaces. Each
33 following line describes a node in the graph: it contains the values of the
34 maps in the right order. The map named "id" should contain unique values
35 because it is regarded as an ID-map. These ids need not be numbers but they
36 must identify the nodes uniquely for later reference. For example:
40 id x-coord y-coord color
46 The edgeset section is very similar to the nodeset section, it has
47 the same coloumn oriented structure. It starts with the line
51 The next line contains the whitespace separated list of names of the edge
52 maps. Each of the next lines describes one edge. The first two elements in
53 the line are the IDs of the source and target (or tail and head) nodes of the
54 edge as they occur in the ID node map of the nodeset section. You can also
55 have an optional ID map on the edges for later reference (which has to be
66 The \e nodes section contains <em>labeled (distinguished) nodes</em>
67 (i.e. nodes having a special
68 label on them). The section starts with
72 Each of the next lines contains a label for a node in the graph
73 and then the ID as described in the \e nodeset section.
81 The last section describes the <em>labeled (distinguished) edges</em>
82 (i.e. edges having a special label on them). It starts with \c \@edges
83 and then each line contains the name of the edge and the ID.
91 The file may contain empty lines and comment lines. The comment lines
92 start with an \c # character.
94 The attributes section can handle some information about the graph. It
95 contains key-value pairs in each line (a key and the mapped value to key). The
96 key should be a string without whitespaces, the value can be of various types.
100 title "Four colored plan graph"
101 author "Balazs DEZSO"
102 copyright "Lemon Library"
111 \section use Using graph input-output
114 The graph input and output is based on <em> reading and writing
115 commands</em>. The user gives reading and writing commands to the reader or
116 writer class, then he calls the \c run() method that executes all the given
119 \subsection write Writing a graph
121 The \ref lemon::GraphWriter "GraphWriter" template class
122 provides the graph output. To write a graph
123 you should first give writing commands to the writer. You can declare
124 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
128 GraphWriter<ListGraph> writer(std::cout, graph);
131 The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
132 function declares a \c NodeMap writing command in the
133 \ref lemon::GraphWriter "GraphWriter".
134 You should give a name to the map and the map
135 object as parameters. The NodeMap writing command with name "id" should write a
136 unique map because it will be regarded as an ID map.
138 \see IdMap, DescriptorMap
141 IdMap<ListGraph, Node> nodeIdMap;
142 writer.writeNodeMap("id", nodeIdMap);
144 writer.writeNodeMap("x-coord", xCoordMap);
145 writer.writeNodeMap("y-coord", yCoordMap);
146 writer.writeNodeMap("color", colorMap);
149 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
150 member function you can give an edge map
151 writing command similar to the NodeMaps.
153 \see IdMap, DescriptorMap
156 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
157 writer.writeEdgeMap("descriptor", edgeDescMap);
159 writer.writeEdgeMap("weight", weightMap);
160 writer.writeEdgeMap("label", labelMap);
163 With \ref lemon::GraphWriter::writeNode() "writeNode()"
164 and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
165 functions you can designate Nodes and
166 Edges in the graph. For example, you can write out the source and target node
167 of a maximum flow instance.
170 writer.writeNode("source", sourceNode);
171 writer.writeNode("target", targetNode);
173 writer.writeEdge("observed", edge);
176 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
177 function you can write an attribute to the file.
180 writer.writeAttribute("author", "Balazs DEZSO");
181 writer.writeAttribute("version", 12);
184 After you give all write commands you must call the
185 \ref lemon::GraphWriter::run() "run()" member
186 function, which executes all the writing commands.
192 \subsection reading Reading a graph
194 The file to be read may contain several maps and labeled nodes or edges.
195 If you read a graph you need not read all the maps and items just those
196 that you need. The interface of the \ref lemon::GraphReader "GraphReader"
198 the \ref lemon::GraphWriter "GraphWriter"
199 but the reading method does not depend on the order of the
202 The reader object assumes that each not readed value does not contain
203 whitespaces, therefore it has some extra possibilities to control how
204 it should skip the values when the string representation contains spaces.
207 GraphReader<ListGraph> reader(std::cin, graph);
210 The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
211 function reads a map from the \c nodeset section.
212 If there is a map that you do not want to read from the file and there are
213 whitespaces in the string represenation of the values then you should
214 call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
215 template member function with proper parameters.
217 \see QuotedStringReader
220 reader.readNodeMap("x-coord", xCoordMap);
221 reader.readNodeMap("y-coord", yCoordMap);
223 reader.readNodeMap<QuotedStringReader>("label", labelMap);
224 reader.skipNodeMap<QuotedStringReader>("description");
226 reader.readNodeMap("color", colorMap);
229 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
230 member function you can give an edge map
231 reading command similar to the NodeMaps.
234 reader.readEdgeMap("weight", weightMap);
235 reader.readEdgeMap("label", labelMap);
238 With \ref lemon::GraphReader::readNode() "readNode()"
239 and \ref lemon::GraphReader::readEdge() "readEdge()"
240 functions you can read labeled Nodes and
244 reader.readNode("source", sourceNode);
245 reader.readNode("target", targetNode);
247 reader.readEdge("observed", edge);
250 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
251 function you can read an attribute from the file.
255 writer.readAttribute("author", author);
257 writer.writeAttribute("version", version);
260 After you give all read commands you must call the
261 \ref lemon::GraphReader::run() "run()" member
262 function, which executes all the commands.
269 \section types Background of Reading and Writing
272 To read a map (on the nodes or edges)
273 the \ref lemon::GraphReader "GraphReader"
274 should know how to read a Value from the given map.
275 By the default implementation the input operator reads a value from
276 the stream and the type of the readed value is the value type of the given map.
277 When the reader should skip a value in the stream, because you do not
278 want to store it in a map, the reader skips a character sequence without
281 If you want to change the functionality of the reader, you can use
282 template parameters to specialize it. When you give a reading
283 command for a map you can give a Reader type as template parameter.
284 With this template parameter you can control how the Reader reads
285 a value from the stream.
287 The reader has the next structure:
290 typedef TypeName Value;
292 void read(std::istream& is, Value& value);
296 For example, the \c "strings" nodemap contains strings and you do not need
297 the value of the string just the length. Then you can implement an own Reader
301 struct LengthReader {
304 void read(std::istream& is, Value& value) {
307 value = tmp.length();
311 reader.readNodeMap<LengthReader>("strings", lengthMap);
314 The global functionality of the reader class can be changed by giving a
315 special template parameter to the GraphReader class. By default, the
316 template parameter is \c DefaultReaderTraits. A reader traits class
317 should provide an inner template class Reader for each type, and a
318 DefaultReader for skipping a value.
320 The specialization of writing is very similar to that of reading.
322 \section undir Undirected graphs
324 In a file describing an undirected graph (undir graph, for short) you find an
325 \c undiredgeset section instead of the \c edgeset section. The first line of
326 the section describes the names of the maps on the undirected egdes and all
327 next lines describe one undirected edge with the the incident nodes and the
330 The format handles directed edge maps as a syntactical sugar???, if there
331 are two maps with names being the same with a \c '+' and a \c '-' prefix
332 then this will be read as a directed map.
336 id capacity +flow -flow
342 The \c edges section is changed to \c undiredges section. This section
343 describes labeled edges and undirected edges. The directed edge label
344 should start with a \c '+' or a \c '-' prefix to decide the direction
354 There are similar classes to the \ref lemon::GraphReader "GraphReader" and
355 \ref lemon::GraphWriter "GraphWriter" which
356 handle the undirected graphs. These classes are
357 the \ref lemon::UndirGraphReader "UndirGraphReader"
358 and \ref lemon::UndirGraphWriter "UndirGraphWriter".
360 The \ref lemon::UndirGraphReader::readUndirEdgeMap() "readUndirEdgeMap()"
361 function reads an undirected map and the
362 \ref lemon::UndirGraphReader::readUndirEdge() "readUndirEdge()"
363 reads an undirected edge from the file,
366 reader.readUndirEdgeMap("capacity", capacityMap);
367 reader.readEdgeMap("flow", flowMap);
369 reader.readUndirEdge("undir_edge", undir_edge);
370 reader.readEdge("edge", edge);
373 \section advanced Advanced features
375 The graph reader and writer classes give an easy way to read and write
376 graphs. But sometimes we want more advanced features. In this case we can
377 use the more general <tt>lemon reader and writer</tt> interface.
379 The LEMON file format is a section oriented file format. It contains one or
380 more sections, each starting with a line identifying its type
381 (the word starting with the \c \@ character).
382 The content of the section this way cannot contain line with \c \@ first
383 character. The file may contains comment lines with \c # first character.
385 The \ref lemon::LemonReader "LemonReader"
386 and \ref lemon::LemonWriter "LemonWriter"
387 gives a framework to read and
388 write sections. There are various section reader and section writer
389 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
390 or a \ref lemon::LemonWriter "LemonWriter".
392 There are default section readers and writers for reading and writing
393 item sets, and labeled items in the graph. These read and write
394 the format described above. Other type of data can be handled with own
395 section reader and writer classes which are inherited from the
396 \c LemonReader::SectionReader or the
397 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
400 The next example defines a special section reader which reads the
401 \c \@description sections into a string:
404 class DescriptionReader : LemonReader::SectionReader {
406 virtual bool header(const std::string& line) {
407 std::istringstream ls(line);
410 return head == "@description";
413 virtual void read(std::istream& is) {
415 while (getline(is, line)) {
421 typedef LemonReader::SectionReader Parent;
423 DescriptionReader(LemonReader& reader) : Parent(reader) {}
425 const std::string& description() const {
434 The other advanced stuff of the generalized file format is that
435 multiple edgesets can be stored to the same nodeset. It can be used
436 for example as a network traffic matrix.
438 In our example there is a network with symmetric links and there are assymetric
439 traffic request on the network. This construction can be stored in an
440 undirected graph and in a directed \c ListEdgeSet class. The example
441 shows the input with the \ref lemon::LemonReader "LemonReader" class:
444 UndirListGraph network;
445 UndirListGraph::UndirEdgeMap<double> capacity;
446 ListEdgeSet<UndirListGraph> traffic(network);
447 ListEdgeSet<UndirListGraph>::EdgeMap<double> request(network);
449 LemonReader reader(std::cin);
450 NodeSetReader<UndirListGraph> nodesetReader(reader, network);
451 UndirEdgeSetReader<UndirListGraph>
452 undirEdgesetReader(reader, network, nodesetReader);
453 undirEdgesetReader.readEdgeMap("capacity", capacity);
454 EdgeSetReader<ListEdgeSet<UndirListGraph> >
455 edgesetReader(reader, traffic, nodesetReader, "traffic");
456 edgesetReader.readEdgeMap("request", request);
461 Because both the \ref lemon::GraphReader "GraphReader"
462 and the \ref lemon::UndirGraphReader "UndirGraphReader" can be converted
463 to \ref lemon::LemonReader "LemonReader"
464 and it can resolve the ID's of the items, the previous
465 result can be achived with the \ref lemon::UndirGraphReader "UndirGraphReader"
470 UndirListGraph network;
471 UndirListGraph::UndirEdgeSet<double> capacity;
472 ListEdgeSet<UndirListGraph> traffic(network);
473 ListEdgeSet<UndirListGraph>::EdgeMap<double> request(network);
475 UndirGraphReader<UndirListGraph> reader(std::cin, network);
476 reader.readEdgeMap("capacity", capacity);
477 EdgeSetReader<ListEdgeSet<UndirListGraph> >
478 edgesetReader(reader, traffic, reader, "traffic");
479 edgesetReader.readEdgeMap("request", request);