COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_io.dox @ 2470:46818ce27a60

Last change on this file since 2470:46818ce27a60 was 2391:14a343be7a5a, checked in by Alpar Juttner, 13 years ago

Happy New Year to all source files!

File size: 15.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19namespace lemon {
20/*!
21
22
23\page graph-io-page Graph Input-Output
24
25The 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.
27Before you read this page you should be familiar with LEMON
28\ref graphs "graphs" and \ref maps-page "maps".
29
30\section format The general file format
31
32The file contains sections in the following order:
33
34\li nodeset
35\li edgeset
36\li nodes
37\li edges
38\li attributes
39
40Some of these sections can be omitted, but you will basicly need the nodeset
41section (unless your graph has no nodes at all) and the edgeset section
42(unless your graph has no edges at all).
43
44The nodeset section describes the nodes of your graph: it identifies the nodes
45and gives the maps defined on them, if any. It starts with the
46following line:
47
48<tt>\@nodeset</tt>
49
50The next line contains the names of the nodemaps, separated by whitespaces.  Each
51following line describes a node in the graph: it contains the values of the
52maps in the right order. The map named "label" should contain unique values
53because it is regarded as a label map. These labels need not be numbers but they
54must identify the nodes uniquely for later reference. For example:
55
56\code
57@nodeset
58label  x-coord  y-coord  color
593   1.0      4.0      blue
605   2.3      5.7      red
6112  7.8      2.3      green
62\endcode
63
64The edgeset section is very similar to the nodeset section, it has
65the same coloumn oriented structure. It starts with the line
66
67<tt>\@edgeset</tt>
68
69The next line contains the whitespace separated list of names of the edge
70maps.  Each of the next lines describes one edge. The first two elements in
71the line are the labels of the source and target (or tail and head) nodes of the
72edge as they occur in the label node map of the nodeset section. You can also
73have an optional label map on the edges for later reference (which has to be
74unique in this case).
75
76\code
77@edgeset
78             label      weight   note
793   5        a          4.3      a-edge
805   12       c          2.6      c-edge
813   12       g          3.4      g-edge
82\endcode
83
84The \e nodes section contains <em>labeled (distinguished) nodes</em>
85(i.e. nodes having a special
86label on them). The section starts with
87
88<tt> \@nodes </tt>
89
90Each of the next lines contains a label for a node in the graph
91and then the label as described in the \e nodeset section.
92
93\code
94@nodes
95source 3
96target 12
97\endcode
98
99The last section describes the <em>labeled (distinguished) edges</em>
100(i.e. edges having a special label on them). It starts with \c \@edges
101and then each line contains the name of the edge and the label.
102
103\code
104@edges
105observed c
106\endcode
107
108
109The file may contain empty lines and comment lines. The comment lines
110start with an \c # character.
111
112The attributes section can handle some information about the graph. It
113contains key-value pairs in each line (a key and the mapped value to key). The
114key should be a string without whitespaces, the value can be of various types.
115
116\code
117@attributes
118title "Four colored planar graph"
119author "Balazs DEZSO"
120copyright "Lemon Library"
121version 12
122\endcode
123
124Finally, the file should be closed with \c \@end line.
125
126
127\section use Using graph input-output
128
129
130The graph input and output is based on <em> reading and writing
131commands</em>. The user gives reading and writing commands to the reader or
132writer class, then he calls the \c run() method that executes all the given
133commands.
134
135\subsection write Writing a graph
136
137The \ref lemon::GraphWriter "GraphWriter" template class
138provides the graph output. To write a graph
139you should first give writing commands to the writer. You can declare
140writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
141Edge writing.
142
143\code
144GraphWriter<ListGraph> writer(std::cout, graph);
145\endcode
146
147The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
148function declares a \c NodeMap writing command in the
149\ref lemon::GraphWriter "GraphWriter".
150You should give a name to the map and the map
151object as parameters. The NodeMap writing command with name "label" should write a
152unique map because it will be regarded as a label map.
153
154\see IdMap, DescriptorMap 
155
156\code
157IdMap<ListGraph, Node> nodeLabelMap;
158writer.writeNodeMap("label", nodeLabelMap);
159
160writer.writeNodeMap("x-coord", xCoordMap);
161writer.writeNodeMap("y-coord", yCoordMap);
162writer.writeNodeMap("color", colorMap);
163\endcode
164
165With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
166member function you can give an edge map
167writing command similar to the NodeMaps.
168
169\see IdMap, DescriptorMap 
170
171\code
172DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
173writer.writeEdgeMap("descriptor", edgeDescMap);
174
175writer.writeEdgeMap("weight", weightMap);
176writer.writeEdgeMap("note", noteMap);
177\endcode
178
179With \ref lemon::GraphWriter::writeNode() "writeNode()"
180and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
181functions you can designate Nodes and
182Edges in the graph. For example, you can write out the source and target node
183of a maximum flow instance.
184
185\code
186writer.writeNode("source", sourceNode);
187writer.writeNode("target", targetNode);
188
189writer.writeEdge("observed", edge);
190\endcode
191
192With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
193function you can write an attribute to the file.
194
195\code
196writer.writeAttribute("author", "Balazs DEZSO");
197writer.writeAttribute("version", 12);
198\endcode
199
200After you give all write commands you must call the
201\ref lemon::GraphWriter::run() "run()" member
202function, which executes all the writing commands.
203
204\code
205writer.run();
206\endcode
207
208\subsection reading Reading a graph
209
210The file to be read may contain several maps and labeled nodes or edges.
211If you read a graph you need not read all the maps and items just those
212that you need. The interface of the \ref lemon::GraphReader "GraphReader"
213is very similar to
214the \ref lemon::GraphWriter "GraphWriter"
215but the reading method does not depend on the order of the
216given commands.
217
218The reader object assumes that each not read value does not contain
219whitespaces, therefore it has some extra possibilities to control how
220it should skip the values when the string representation contains spaces.
221
222\code
223GraphReader<ListGraph> reader(std::cin, graph);
224\endcode
225
226The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
227function reads a map from the \c nodeset section.
228If there is a map that you do not want to read from the file and there are
229whitespaces in the string represenation of the values then you should
230call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
231template member function with proper parameters.
232
233\see QuotedStringReader
234
235\code
236reader.readNodeMap("x-coord", xCoordMap);
237reader.readNodeMap("y-coord", yCoordMap);
238
239reader.readNodeMap<QuotedStringReader>("label", labelMap);
240reader.skipNodeMap<QuotedStringReader>("description");
241
242reader.readNodeMap("color", colorMap);
243\endcode
244
245With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
246member function you can give an edge map
247reading command similar to the NodeMaps.
248
249\code
250reader.readEdgeMap("weight", weightMap);
251reader.readEdgeMap("label", labelMap);
252\endcode
253
254With \ref lemon::GraphReader::readNode() "readNode()"
255and \ref lemon::GraphReader::readEdge() "readEdge()"
256functions you can read labeled Nodes and
257Edges.
258
259\code
260reader.readNode("source", sourceNode);
261reader.readNode("target", targetNode);
262
263reader.readEdge("observed", edge);
264\endcode
265
266With \ref lemon::GraphReader::readAttribute() "readAttribute()"
267function you can read an attribute from the file.
268
269\code
270std::string author;
271writer.readAttribute("author", author);
272int version;
273writer.writeAttribute("version", version);
274\endcode
275
276After you give all read commands you must call the
277\ref lemon::GraphReader::run() "run()" member
278function, which executes all the commands.
279
280\code
281reader.run();
282\endcode
283
284\anchor rwbackground
285\section types Background of Reading and Writing
286
287
288To read a map (on the nodes or edges)
289the \ref lemon::GraphReader "GraphReader"
290should know how to read a Value from the given map.
291By the default implementation the input operator reads a value from
292the stream and the type of the read value is the value type of the given map.
293When the reader should skip a value in the stream, because you do not
294want to store it in a map, the reader skips a character sequence without
295whitespaces.
296
297If you want to change the functionality of the reader, you can use
298template parameters to specialize it. When you give a reading
299command for a map you can give a Reader type as template parameter.
300With this template parameter you can control how the Reader reads
301a value from the stream.
302
303The reader has the next structure:
304\code
305struct TypeReader {
306  typedef TypeName Value;
307
308  void read(std::istream& is, Value& value);
309};
310\endcode
311
312For example, the \c "strings" nodemap contains strings and you do not need
313the value of the string just the length. Then you can implement an own Reader
314struct.
315
316\code
317struct LengthReader {
318  typedef int Value;
319
320  void read(std::istream& is, Value& value) {
321    std::string tmp;
322    is >> tmp;
323    value = tmp.length();
324  }
325};
326...
327reader.readNodeMap<LengthReader>("strings", lengthMap);
328\endcode 
329
330The global functionality of the reader class can be changed by giving a
331special template parameter to the GraphReader class. By default, the
332template parameter is \c DefaultReaderTraits. A reader traits class
333should provide a nested template class Reader for each type, and a
334DefaultReader for skipping a value.
335
336The specialization of writing is very similar to that of reading.
337
338\section u Undirected graphs
339
340In 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
342the section describes the names of the maps on the undirected egdes and all
343next lines describe one undirected edge with the the incident nodes and the
344values of the map.
345
346The format handles directed edge maps as a syntactical sugar???, if there
347are two maps with names being the same with a \c '+' and a \c '-' prefix
348then this will be read as a directed map.
349
350\code
351@uedgeset
352             label      capacity        +flow   -flow
35332   2       1          4.3             2.0     0.0
35421   21      5          2.6             0.0     2.6
35521   12      8          3.4             0.0     0.0
356\endcode
357
358The \c edges section is changed to \c uedges section. This section
359describes labeled edges and undirected edges. The directed edge label
360should start with a \c '+' or a \c '-' prefix to decide the direction
361of the edge.
362
363\code
364@uedges
365uedge 1
366+edge 5
367-back 5
368\endcode
369
370There are similar classes to the \ref lemon::GraphReader "GraphReader" and
371\ref lemon::GraphWriter "GraphWriter" which
372handle the undirected graphs. These classes are
373the \ref lemon::UGraphReader "UGraphReader"
374and \ref lemon::UGraphWriter "UGraphWriter".
375
376The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
377function reads an undirected map and the
378\ref lemon::UGraphReader::readUEdge() "readUEdge()"
379reads an undirected edge from the file,
380
381\code
382reader.readUEdgeMap("capacity", capacityMap);
383reader.readEdgeMap("flow", flowMap);
384...
385reader.readUEdge("u_edge", u_edge);
386reader.readEdge("edge", edge);
387\endcode
388
389\section advanced Advanced features
390
391The graph reader and writer classes give an easy way to read and write
392graphs. But sometimes we want more advanced features. In this case we can
393use the more general <tt>lemon reader and writer</tt> interface.
394
395The LEMON file format is a section oriented file format. It contains one or
396more sections, each starting with a line identifying its type
397(the word starting with the \c \@  character).
398The content of the section this way cannot contain line with \c \@ first
399character. The file may contains comment lines with \c # first character.
400
401The \ref lemon::LemonReader "LemonReader"
402and \ref lemon::LemonWriter "LemonWriter"
403gives a framework to read and
404write sections. There are various section reader and section writer
405classes which can be attached to a \ref lemon::LemonReader "LemonReader"
406or a \ref lemon::LemonWriter "LemonWriter".
407
408There are default section readers and writers for reading and writing
409item sets, and labeled items in the graph. These read and write
410the format described above. Other type of data can be handled with own
411section reader and writer classes which are inherited from the
412\c LemonReader::SectionReader or the
413\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
414classes.
415
416The next example defines a special section reader which reads the
417\c \@description sections into a string:
418
419\code
420class DescriptionReader : LemonReader::SectionReader {
421protected:
422  virtual bool header(const std::string& line) {
423    std::istringstream ls(line);
424    std::string head;
425    ls >> head;
426    return head == "@description";
427  }
428
429  virtual void read(std::istream& is) {
430    std::string line;
431    while (getline(is, line)) {
432      desc += line;
433    }
434  }
435public:
436
437  typedef LemonReader::SectionReader Parent;
438 
439  DescriptionReader(LemonReader& reader) : Parent(reader) {}
440
441  const std::string& description() const {
442    return description;
443  }
444
445private:
446  std::string desc;
447};
448\endcode
449
450The other advanced stuff of the generalized file format is that
451multiple edgesets can be stored to the same nodeset. It can be used
452for example as a network traffic matrix.
453
454In our example there is a network with symmetric links and there are assymetric
455traffic request on the network. This construction can be stored in an
456undirected graph and in a directed \c ListEdgeSet class. The example
457shows the input with the \ref lemon::LemonReader "LemonReader" class:
458
459\code
460ListUGraph network;
461ListUGraph::UEdgeMap<double> capacity;
462ListEdgeSet<ListUGraph> traffic(network);
463ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
464
465LemonReader reader(std::cin);
466NodeSetReader<ListUGraph> nodesetReader(reader, network);
467UEdgeSetReader<ListUGraph>
468  uEdgesetReader(reader, network, nodesetReader);
469uEdgesetReader.readEdgeMap("capacity", capacity);
470EdgeSetReader<ListEdgeSet<ListUGraph> >
471  edgesetReader(reader, traffic, nodesetReader, "traffic");
472edgesetReader.readEdgeMap("request", request);
473
474reader.run();
475\endcode
476
477Because both the \ref lemon::GraphReader "GraphReader"
478and the \ref lemon::UGraphReader "UGraphReader" can be converted
479to \ref lemon::LemonReader "LemonReader"
480and it can resolve the label's of the items, the previous
481result can be achived with the \ref lemon::UGraphReader "UGraphReader"
482class, too.
483
484
485\code
486ListUGraph network;
487ListUGraph::UEdgeSet<double> capacity;
488ListEdgeSet<ListUGraph> traffic(network);
489ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
490
491UGraphReader<ListUGraph> reader(std::cin, network);
492reader.readEdgeMap("capacity", capacity);
493EdgeSetReader<ListEdgeSet<ListUGraph> >
494  edgesetReader(reader, traffic, reader, "traffic");
495edgesetReader.readEdgeMap("request", request);
496
497reader.run();
498\endcode
499
500\author Balazs Dezso
501*/
502}
Note: See TracBrowser for help on using the repository browser.