COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_io.dox @ 1591:03aa0a6c8dca

Last change on this file since 1591:03aa0a6c8dca was 1540:7d028a73d7f2, checked in by athos, 19 years ago

Documented Balazs's stuff. Quite enough of that.

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