Better doc.
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
113 The easiest way of using graph input and output is using the versions of the
114 public \ref readGraph() and \ref writeGraph() functions; if you don't need
115 very sophisticated behaviour then you might be satisfied with
116 those. Otherwise go on reading this page.
118 The graph input and output is based on <em> reading and writing
119 commands</em>. The user gives reading and writing commands to the reader or
120 writer class, then he calls the \c run() method that executes all the given
123 \subsection write Writing a graph
125 The \ref lemon::GraphWriter "GraphWriter" template class
126 provides the graph output. To write a graph
127 you should first give writing commands to the writer. You can declare
128 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
132 GraphWriter<ListGraph> writer(std::cout, graph);
135 The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
136 function declares a \c NodeMap writing command in the
137 \ref lemon::GraphWriter "GraphWriter".
138 You should give a name to the map and the map
139 object as parameters. The NodeMap writing command with name "id" should write a
140 unique map because it will be regarded as an ID map.
142 \see IdMap, DescriptorMap
145 IdMap<ListGraph, Node> nodeIdMap;
146 writer.writeNodeMap("id", nodeIdMap);
148 writer.writeNodeMap("x-coord", xCoordMap);
149 writer.writeNodeMap("y-coord", yCoordMap);
150 writer.writeNodeMap("color", colorMap);
153 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
154 member function you can give an edge map
155 writing command similar to the NodeMaps.
157 \see IdMap, DescriptorMap
160 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
161 writer.writeEdgeMap("descriptor", edgeDescMap);
163 writer.writeEdgeMap("weight", weightMap);
164 writer.writeEdgeMap("label", labelMap);
167 With \ref lemon::GraphWriter::writeNode() "writeNode()"
168 and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
169 functions you can designate Nodes and
170 Edges in the graph. For example, you can write out the source and target node
171 of a maximum flow instance.
174 writer.writeNode("source", sourceNode);
175 writer.writeNode("target", targetNode);
177 writer.writeEdge("observed", edge);
180 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
181 function you can write an attribute to the file.
184 writer.writeAttribute("author", "Balazs DEZSO");
185 writer.writeAttribute("version", 12);
188 After you give all write commands you must call the
189 \ref lemon::GraphWriter::run() "run()" member
190 function, which executes all the writing commands.
196 \subsection reading Reading a graph
198 The file to be read may contain several maps and labeled nodes or edges.
199 If you read a graph you need not read all the maps and items just those
200 that you need. The interface of the \ref lemon::GraphReader "GraphReader"
202 the \ref lemon::GraphWriter "GraphWriter"
203 but the reading method does not depend on the order of the
206 The reader object assumes that each not readed value does not contain
207 whitespaces, therefore it has some extra possibilities to control how
208 it should skip the values when the string representation contains spaces.
211 GraphReader<ListGraph> reader(std::cin, graph);
214 The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
215 function reads a map from the \c nodeset section.
216 If there is a map that you do not want to read from the file and there are
217 whitespaces in the string represenation of the values then you should
218 call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
219 template member function with proper parameters.
221 \see QuotedStringReader
224 reader.readNodeMap("x-coord", xCoordMap);
225 reader.readNodeMap("y-coord", yCoordMap);
227 reader.readNodeMap<QuotedStringReader>("label", labelMap);
228 reader.skipNodeMap<QuotedStringReader>("description");
230 reader.readNodeMap("color", colorMap);
233 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
234 member function you can give an edge map
235 reading command similar to the NodeMaps.
238 reader.readEdgeMap("weight", weightMap);
239 reader.readEdgeMap("label", labelMap);
242 With \ref lemon::GraphReader::readNode() "readNode()"
243 and \ref lemon::GraphReader::readEdge() "readEdge()"
244 functions you can read labeled Nodes and
248 reader.readNode("source", sourceNode);
249 reader.readNode("target", targetNode);
251 reader.readEdge("observed", edge);
254 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
255 function you can read an attribute from the file.
259 writer.readAttribute("author", author);
261 writer.writeAttribute("version", version);
264 After you give all read commands you must call the
265 \ref lemon::GraphReader::run() "run()" member
266 function, which executes all the commands.
273 \section types Background of Reading and Writing
276 To read a map (on the nodes or edges)
277 the \ref lemon::GraphReader "GraphReader"
278 should know how to read a Value from the given map.
279 By the default implementation the input operator reads a value from
280 the stream and the type of the readed value is the value type of the given map.
281 When the reader should skip a value in the stream, because you do not
282 want to store it in a map, the reader skips a character sequence without
285 If you want to change the functionality of the reader, you can use
286 template parameters to specialize it. When you give a reading
287 command for a map you can give a Reader type as template parameter.
288 With this template parameter you can control how the Reader reads
289 a value from the stream.
291 The reader has the next structure:
294 typedef TypeName Value;
296 void read(std::istream& is, Value& value);
300 For example, the \c "strings" nodemap contains strings and you do not need
301 the value of the string just the length. Then you can implement an own Reader
305 struct LengthReader {
308 void read(std::istream& is, Value& value) {
311 value = tmp.length();
315 reader.readNodeMap<LengthReader>("strings", lengthMap);
318 The global functionality of the reader class can be changed by giving a
319 special template parameter to the GraphReader class. By default, the
320 template parameter is \c DefaultReaderTraits. A reader traits class
321 should provide an inner template class Reader for each type, and a
322 DefaultReader for skipping a value.
324 The specialization of writing is very similar to that of reading.
326 \section undir Undirected graphs
328 In a file describing an undirected graph (undir graph, for short) you find an
329 \c undiredgeset section instead of the \c edgeset section. The first line of
330 the section describes the names of the maps on the undirected egdes and all
331 next lines describe one undirected edge with the the incident nodes and the
334 The format handles directed edge maps as a syntactical sugar???, if there
335 are two maps with names being the same with a \c '+' and a \c '-' prefix
336 then this will be read as a directed map.
340 id capacity +flow -flow
346 The \c edges section is changed to \c undiredges section. This section
347 describes labeled edges and undirected edges. The directed edge label
348 should start with a \c '+' or a \c '-' prefix to decide the direction
358 There are similar classes to the \ref lemon::GraphReader "GraphReader" and
359 \ref lemon::GraphWriter "GraphWriter" which
360 handle the undirected graphs. These classes are
361 the \ref lemon::UndirGraphReader "UndirGraphReader"
362 and \ref lemon::UndirGraphWriter "UndirGraphWriter".
364 The \ref lemon::UndirGraphReader::readUndirMap() "readUndirMap()"
365 function reads an undirected map and the
366 \ref lemon::UndirGraphReader::readUndirEdge() "readUndirEdge()"
367 reads an undirected edge from the file,
370 reader.readUndirEdgeMap("capacity", capacityMap);
371 reader.readEdgeMap("flow", flowMap);
373 reader.readUndirEdge("undir_edge", undir_edge);
374 reader.readEdge("edge", edge);
377 \section advanced Advanced features
379 The graph reader and writer classes give an easy way to read and write
380 graphs. But sometimes we want more advanced features. In this case we can
381 use the more general <tt>lemon reader and writer</tt> interface.
383 The LEMON file format is a section oriented file format. It contains one or
384 more sections, each starting with a line identifying its type
385 (the word starting with the \c \@ character).
386 The content of the section this way cannot contain line with \c \@ first
387 character. The file may contains comment lines with \c # first character.
389 The \ref lemon::LemonReader "LemonReader"
390 and \ref lemon::LemonWriter "LemonWriter"
391 gives a framework to read and
392 write sections. There are various section reader and section writer
393 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
394 or a \ref lemon::LemonWriter "LemonWriter".
396 There are default section readers and writers for reading and writing
397 item sets, and labeled items in the graph. These read and write
398 the format described above. Other type of data can be handled with own
399 section reader and writer classes which are inherited from the
400 \c LemonReader::SectionReader or the
401 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
404 The next example defines a special section reader which reads the
405 \c \@description sections into a string:
408 class DescriptionReader : LemonReader::SectionReader {
410 virtual bool header(const std::string& line) {
411 std::istringstream ls(line);
414 return head == "@description";
417 virtual void read(std::istream& is) {
419 while (getline(is, line)) {
425 typedef LemonReader::SectionReader Parent;
427 DescriptionReader(LemonReader& reader) : Parent(reader) {}
429 const std::string& description() const {
438 The other advanced stuff of the generalized file format is that
439 multiple edgesets can be stored to the same nodeset. It can be used
440 for example as a network traffic matrix.
442 In our example there is a network with symmetric links and there are assymetric
443 traffic request on the network. This construction can be stored in an
444 undirected graph and in a directed \c NewEdgeSetAdaptor class. The example
445 shows the input with the \ref lemon::LemonReader "LemonReader" class:
448 UndirListGraph network;
449 UndirListGraph::UndirEdgeSet<double> capacity;
450 NewEdgeSetAdaptor<UndirListGraph> traffic(network);
451 NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
453 LemonReader reader(std::cin);
454 NodeSetReader nodesetReader(reader, network);
455 UndirEdgeSetReader undirEdgesetReader(reader, network, nodesetReader);
456 undirEdgesetReader.readEdgeMap("capacity", capacity);
457 EdgeSetReader edgesetReader(reader, traffic, nodesetReader);
458 edgesetReader.readEdgeMap("request", request);
463 Because both the \ref lemon::GraphReader "GraphReader"
464 and the \ref lemon::UndirGraphReader "UndirGraphReader" can be converted
465 to \ref lemon::LemonReader "LemonReader"
466 and it can resolve the ID's of the items, the previous
467 result can be achived with the \ref lemon::UndirGraphReader "UndirGraphReader"
472 UndirListGraph network;
473 UndirListGraph::UndirEdgeSet<double> capacity;
474 NewEdgeSetAdaptor<UndirListGraph> traffic(network);
475 NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
477 UndirGraphReader reader(std::cin, network);
478 reader.readEdgeMap("capacity", capacity);
479 EdgeSetReader edgesetReader(reader, traffic, reader);
480 edgesetReader.readEdgeMap("request", request);