COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_io.dox @ 2553:bfced05fa852

Last change on this file since 2553:bfced05fa852 was 2553:bfced05fa852, checked in by Alpar Juttner, 11 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 16.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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 undir Undirected and Bipartite 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 could store directed edge maps, if there are two maps with
347names being the same with a \c '+' and a \c '-' prefix then this could
348be read as such a 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
389The undirected bipartite graphs could be read with the \c BpUGraph
390class and it has specialized nodeset section, which should be start
391with \c "@bpnodeset". This section is separated to two
392subsections. The header line of these sections start with "&anodeset"
393or "&bnodeset" and after that the line contains the names of the
394regular and A-node or B-node maps accordingly. The lines of each
395section contains the mapped values. The labels of the graph should be
396unique overall both subsections.
397
398\code
399@bpnodeset
400&anodeset label   coords        radius
401          0       (0, 0)        14.0
402          1       (0, 1)        12.0
403&bnodeset label   coords
404          2       (1, 0)
405          3       (1, 1)
406\endcode
407
408The reading can be done with \ref lemon::BpUGraphReader::readANodeMap()
409"readANodeMap()", \ref lemon::BpUGraphReader::readBNodeMap()
410"readBNodeMap()" or \ref lemon::BpUGraphReader::readNodeMap()
411"readNodeMap()" members.
412
413\code
414reader.readNodeMap("coords", coords);
415reader.readAnodeMap("radius", radius);
416\endcode
417
418\section advanced Advanced features
419
420The graph reader and writer classes give an easy way to read and write
421graphs. But sometimes we want more advanced features. In this case we can
422use the more general <tt>lemon reader and writer</tt> interface.
423
424The LEMON file format is a section oriented file format. It contains one or
425more sections, each starting with a line identifying its type
426(the word starting with the \c \@  character).
427The content of the section this way cannot contain line with \c \@ first
428character. The file may contains comment lines with \c # first character.
429
430The \ref lemon::LemonReader "LemonReader"
431and \ref lemon::LemonWriter "LemonWriter"
432gives a framework to read and
433write sections. There are various section reader and section writer
434classes which can be attached to a \ref lemon::LemonReader "LemonReader"
435or a \ref lemon::LemonWriter "LemonWriter".
436
437There are default section readers and writers for reading and writing
438item sets, and labeled items in the graph. These read and write
439the format described above. Other type of data can be handled with own
440section reader and writer classes which are inherited from the
441\c LemonReader::SectionReader or the
442\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
443classes.
444
445The next example defines a special section reader which reads the
446\c \@description sections into a string:
447
448\code
449class DescriptionReader : LemonReader::SectionReader {
450protected:
451  virtual bool header(const std::string& line) {
452    std::istringstream ls(line);
453    std::string head;
454    ls >> head;
455    return head == "@description";
456  }
457
458  virtual void read(std::istream& is) {
459    std::string line;
460    while (getline(is, line)) {
461      desc += line;
462    }
463  }
464public:
465
466  typedef LemonReader::SectionReader Parent;
467 
468  DescriptionReader(LemonReader& reader) : Parent(reader) {}
469
470  const std::string& description() const {
471    return description;
472  }
473
474private:
475  std::string desc;
476};
477\endcode
478
479The other advanced stuff of the generalized file format is that
480multiple edgesets can be stored to the same nodeset. It can be used
481for example as a network traffic matrix.
482
483In our example there is a network with symmetric links and there are assymetric
484traffic request on the network. This construction can be stored in an
485undirected graph and in a directed \c ListEdgeSet class. The example
486shows the input with the \ref lemon::LemonReader "LemonReader" class:
487
488\code
489ListUGraph network;
490ListUGraph::UEdgeMap<double> capacity;
491ListEdgeSet<ListUGraph> traffic(network);
492ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
493
494LemonReader reader(std::cin);
495NodeSetReader<ListUGraph> nodesetReader(reader, network);
496UEdgeSetReader<ListUGraph>
497  uEdgesetReader(reader, network, nodesetReader);
498uEdgesetReader.readEdgeMap("capacity", capacity);
499EdgeSetReader<ListEdgeSet<ListUGraph> >
500  edgesetReader(reader, traffic, nodesetReader, "traffic");
501edgesetReader.readEdgeMap("request", request);
502
503reader.run();
504\endcode
505
506Because both the \ref lemon::GraphReader "GraphReader"
507and the \ref lemon::UGraphReader "UGraphReader" can be converted
508to \ref lemon::LemonReader "LemonReader"
509and it can resolve the label's of the items, the previous
510result can be achived with the \ref lemon::UGraphReader "UGraphReader"
511class, too.
512
513
514\code
515ListUGraph network;
516ListUGraph::UEdgeSet<double> capacity;
517ListEdgeSet<ListUGraph> traffic(network);
518ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
519
520UGraphReader<ListUGraph> reader(std::cin, network);
521reader.readEdgeMap("capacity", capacity);
522EdgeSetReader<ListEdgeSet<ListUGraph> >
523  edgesetReader(reader, traffic, reader, "traffic");
524edgesetReader.readEdgeMap("request", request);
525
526reader.run();
527\endcode
528
529\author Balazs Dezso
530*/
531}
Note: See TracBrowser for help on using the repository browser.