COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_io.dox @ 2391:14a343be7a5a

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

Happy New Year to all source files!

File size: 15.2 KB
RevLine 
[2391]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
[1118]19namespace lemon {
[1114]20/*!
21
22
23\page graph-io-page Graph Input-Output
24
[1540]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".
[1114]29
30\section format The general file format
31
[1532]32The file contains sections in the following order:
[1114]33
34\li nodeset
35\li edgeset
36\li nodes
37\li edges
[1532]38\li attributes
[1114]39
[1540]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:
[1522]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
[1901]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
[1540]54must identify the nodes uniquely for later reference. For example:
[1114]55
56\code
57@nodeset
[1901]58label  x-coord  y-coord  color
[1114]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
[1522]65the same coloumn oriented structure. It starts with the line
66
67<tt>\@edgeset</tt>
68
[1540]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
[1901]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
[1540]74unique in this case).
[1114]75
76\code
77@edgeset
[1901]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
[1114]82\endcode
83
[1540]84The \e nodes section contains <em>labeled (distinguished) nodes</em>
85(i.e. nodes having a special
[1118]86label on them). The section starts with
[1522]87
88<tt> \@nodes </tt>
89
90Each of the next lines contains a label for a node in the graph
[1901]91and then the label as described in the \e nodeset section.
[1114]92
93\code
94@nodes
95source 3
96target 12
97\endcode
98
[1540]99The last section describes the <em>labeled (distinguished) edges</em>
[1333]100(i.e. edges having a special label on them). It starts with \c \@edges
[1901]101and then each line contains the name of the edge and the label.
[1114]102
103\code
[1540]104@edges
[1114]105observed c
106\endcode
107
108
109The file may contain empty lines and comment lines. The comment lines
110start with an \c # character.
111
[1532]112The attributes section can handle some information about the graph. It
[1540]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.
[1532]115
116\code
117@attributes
[1959]118title "Four colored planar graph"
[1532]119author "Balazs DEZSO"
120copyright "Lemon Library"
121version 12
122\endcode
123
[1901]124Finally, the file should be closed with \c \@end line.
[1522]125
[1114]126
127\section use Using graph input-output
[1540]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.
[1114]134
135\subsection write Writing a graph
136
[1631]137The \ref lemon::GraphWriter "GraphWriter" template class
138provides the graph output. To write a graph
[1526]139you should first give writing commands to the writer. You can declare
[1540]140writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
[1114]141Edge writing.
142
143\code
[1333]144GraphWriter<ListGraph> writer(std::cout, graph);
[1114]145\endcode
146
[1631]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
[1901]151object as parameters. The NodeMap writing command with name "label" should write a
152unique map because it will be regarded as a label map.
[1114]153
154\see IdMap, DescriptorMap 
155
156\code
[1901]157IdMap<ListGraph, Node> nodeLabelMap;
158writer.writeNodeMap("label", nodeLabelMap);
[1114]159
[1394]160writer.writeNodeMap("x-coord", xCoordMap);
161writer.writeNodeMap("y-coord", yCoordMap);
162writer.writeNodeMap("color", colorMap);
[1114]163\endcode
164
[1631]165With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
166member function you can give an edge map
[1333]167writing command similar to the NodeMaps.
[1114]168
169\see IdMap, DescriptorMap 
[1522]170
[1114]171\code
172DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
[1394]173writer.writeEdgeMap("descriptor", edgeDescMap);
[1114]174
[1394]175writer.writeEdgeMap("weight", weightMap);
[1901]176writer.writeEdgeMap("note", noteMap);
[1114]177\endcode
178
[1631]179With \ref lemon::GraphWriter::writeNode() "writeNode()"
180and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
181functions you can designate Nodes and
[1522]182Edges in the graph. For example, you can write out the source and target node
183of a maximum flow instance.
[1114]184
185\code
[1394]186writer.writeNode("source", sourceNode);
187writer.writeNode("target", targetNode);
[1114]188
[1394]189writer.writeEdge("observed", edge);
[1114]190\endcode
191
[1631]192With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
193function you can write an attribute to the file.
[1532]194
195\code
196writer.writeAttribute("author", "Balazs DEZSO");
197writer.writeAttribute("version", 12);
198\endcode
199
[1631]200After you give all write commands you must call the
201\ref lemon::GraphWriter::run() "run()" member
[1522]202function, which executes all the writing commands.
[1114]203
204\code
205writer.run();
206\endcode
207
208\subsection reading Reading a graph
209
[1540]210The file to be read may contain several maps and labeled nodes or edges.
[1114]211If you read a graph you need not read all the maps and items just those
[1631]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
[1114]216given commands.
217
[2100]218The reader object assumes that each not read value does not contain
[1118]219whitespaces, therefore it has some extra possibilities to control how
220it should skip the values when the string representation contains spaces.
[1114]221
222\code
[1333]223GraphReader<ListGraph> reader(std::cin, graph);
[1114]224\endcode
225
[1631]226The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
227function reads a map from the \c nodeset section.
[1522]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
[1631]230call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
231template member function with proper parameters.
[1114]232
233\see QuotedStringReader
[1522]234
[1114]235\code
[1394]236reader.readNodeMap("x-coord", xCoordMap);
237reader.readNodeMap("y-coord", yCoordMap);
[1114]238
[1394]239reader.readNodeMap<QuotedStringReader>("label", labelMap);
[1114]240reader.skipNodeMap<QuotedStringReader>("description");
241
[1394]242reader.readNodeMap("color", colorMap);
[1114]243\endcode
244
[1631]245With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
246member function you can give an edge map
[1114]247reading command similar to the NodeMaps.
248
249\code
[1394]250reader.readEdgeMap("weight", weightMap);
251reader.readEdgeMap("label", labelMap);
[1114]252\endcode
253
[1631]254With \ref lemon::GraphReader::readNode() "readNode()"
255and \ref lemon::GraphReader::readEdge() "readEdge()"
256functions you can read labeled Nodes and
[1114]257Edges.
258
259\code
[1394]260reader.readNode("source", sourceNode);
261reader.readNode("target", targetNode);
[1114]262
[1394]263reader.readEdge("observed", edge);
[1114]264\endcode
265
[1631]266With \ref lemon::GraphReader::readAttribute() "readAttribute()"
267function you can read an attribute from the file.
[1532]268
269\code
270std::string author;
271writer.readAttribute("author", author);
272int version;
273writer.writeAttribute("version", version);
274\endcode
275
[1631]276After you give all read commands you must call the
277\ref lemon::GraphReader::run() "run()" member
[1522]278function, which executes all the commands.
[1114]279
280\code
281reader.run();
282\endcode
283
[1540]284\anchor rwbackground
[1527]285\section types Background of Reading and Writing
[1540]286
287
[1527]288To read a map (on the nodes or edges)
[1631]289the \ref lemon::GraphReader "GraphReader"
290should know how to read a Value from the given map.
[1114]291By the default implementation the input operator reads a value from
[2100]292the stream and the type of the read value is the value type of the given map.
[1114]293When the reader should skip a value in the stream, because you do not
[1527]294want to store it in a map, the reader skips a character sequence without
[1540]295whitespaces.
[1114]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.
[1333]300With this template parameter you can control how the Reader reads
[1114]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
[1527]312For example, the \c "strings" nodemap contains strings and you do not need
[1540]313the value of the string just the length. Then you can implement an own Reader
[1114]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...
[1394]327reader.readNodeMap<LengthReader>("strings", lengthMap);
[1114]328\endcode 
329
330The global functionality of the reader class can be changed by giving a
[1526]331special template parameter to the GraphReader class. By default, the
[1118]332template parameter is \c DefaultReaderTraits. A reader traits class
[1901]333should provide a nested template class Reader for each type, and a
[1114]334DefaultReader for skipping a value.
335
[1901]336The specialization of writing is very similar to that of reading.
[1114]337
[1909]338\section u Undirected graphs
[1532]339
[1909]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
[1540]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.
[1532]345
[1540]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.
[1532]349
350\code
[1909]351@uedgeset
[1901]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
[1532]356\endcode
357
[1909]358The \c edges section is changed to \c uedges section. This section
[1532]359describes labeled edges and undirected edges. The directed edge label
[1540]360should start with a \c '+' or a \c '-' prefix to decide the direction
[1532]361of the edge.
362
363\code
[1909]364@uedges
365uedge 1
[1532]366+edge 5
367-back 5
368\endcode
369
[1631]370There are similar classes to the \ref lemon::GraphReader "GraphReader" and
371\ref lemon::GraphWriter "GraphWriter" which
372handle the undirected graphs. These classes are
[1909]373the \ref lemon::UGraphReader "UGraphReader"
374and \ref lemon::UGraphWriter "UGraphWriter".
[1532]375
[1909]376The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
[1631]377function reads an undirected map and the
[1909]378\ref lemon::UGraphReader::readUEdge() "readUEdge()"
[1631]379reads an undirected edge from the file,
[1532]380
381\code
[1909]382reader.readUEdgeMap("capacity", capacityMap);
[1532]383reader.readEdgeMap("flow", flowMap);
384...
[1909]385reader.readUEdge("u_edge", u_edge);
[1532]386reader.readEdge("edge", edge);
387\endcode
388
389\section advanced Advanced features
390
[1540]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.
[1532]394
[1540]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).
[1532]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
[1631]401The \ref lemon::LemonReader "LemonReader"
402and \ref lemon::LemonWriter "LemonWriter"
403gives a framework to read and
[1532]404write sections. There are various section reader and section writer
[1631]405classes which can be attached to a \ref lemon::LemonReader "LemonReader"
406or a \ref lemon::LemonWriter "LemonWriter".
[1532]407
408There are default section readers and writers for reading and writing
[1540]409item sets, and labeled items in the graph. These read and write
[1532]410the format described above. Other type of data can be handled with own
411section reader and writer classes which are inherited from the
[1631]412\c LemonReader::SectionReader or the
413\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
414classes.
[1532]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
[1540]452for example as a network traffic matrix.
[1532]453
[1540]454In our example there is a network with symmetric links and there are assymetric
[1532]455traffic request on the network. This construction can be stored in an
[1842]456undirected graph and in a directed \c ListEdgeSet class. The example
[1631]457shows the input with the \ref lemon::LemonReader "LemonReader" class:
[1532]458
459\code
[1909]460ListUGraph network;
461ListUGraph::UEdgeMap<double> capacity;
462ListEdgeSet<ListUGraph> traffic(network);
463ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
[1532]464
465LemonReader reader(std::cin);
[1909]466NodeSetReader<ListUGraph> nodesetReader(reader, network);
467UEdgeSetReader<ListUGraph>
468  uEdgesetReader(reader, network, nodesetReader);
469uEdgesetReader.readEdgeMap("capacity", capacity);
470EdgeSetReader<ListEdgeSet<ListUGraph> >
[1848]471  edgesetReader(reader, traffic, nodesetReader, "traffic");
[1532]472edgesetReader.readEdgeMap("request", request);
473
474reader.run();
475\endcode
476
[1631]477Because both the \ref lemon::GraphReader "GraphReader"
[1909]478and the \ref lemon::UGraphReader "UGraphReader" can be converted
[1631]479to \ref lemon::LemonReader "LemonReader"
[1901]480and it can resolve the label's of the items, the previous
[1909]481result can be achived with the \ref lemon::UGraphReader "UGraphReader"
[1631]482class, too.
[1532]483
484
485\code
[1909]486ListUGraph network;
487ListUGraph::UEdgeSet<double> capacity;
488ListEdgeSet<ListUGraph> traffic(network);
489ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
[1532]490
[1909]491UGraphReader<ListUGraph> reader(std::cin, network);
[1532]492reader.readEdgeMap("capacity", capacity);
[1909]493EdgeSetReader<ListEdgeSet<ListUGraph> >
[1848]494  edgesetReader(reader, traffic, reader, "traffic");
[1532]495edgesetReader.readEdgeMap("request", request);
496
497reader.run();
498\endcode
499
[1333]500\author Balazs Dezso
[1114]501*/
[2391]502}
Note: See TracBrowser for help on using the repository browser.