COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_io.dox @ 1555:48769ac7ec32

Last change on this file since 1555:48769ac7ec32 was 1540:7d028a73d7f2, checked in by athos, 14 years ago

Documented Balazs's stuff. Quite enough of that.

File size: 13.8 KB
Line 
1namespace lemon {
2/*!
3
4
5\page graph-io-page Graph Input-Output
6
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".
11
12\section format The general file format
13
14The file contains sections in the following order:
15
16\li nodeset
17\li edgeset
18\li nodes
19\li edges
20\li attributes
21
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:
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
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:
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
47the same coloumn oriented structure. It starts with the line
48
49<tt>\@edgeset</tt>
50
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).
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
66The \e nodes section contains <em>labeled (distinguished) nodes</em>
67(i.e. nodes having a special
68label on them). The section starts with
69
70<tt> \@nodes </tt>
71
72Each of the next lines contains a label for a node in the graph
73and then the ID as described in the \e nodeset section.
74
75\code
76@nodes
77source 3
78target 12
79\endcode
80
81The last section describes the <em>labeled (distinguished) edges</em>
82(i.e. edges having a special label on them). It starts with \c \@edges
83and then each line contains the name of the edge and the ID.
84
85\code
86@edges
87observed c
88\endcode
89
90
91The file may contain empty lines and comment lines. The comment lines
92start with an \c # character.
93
94The attributes section can handle some information about the graph. It
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.
97
98\code
99@attributes
100title "Four colored plan graph"
101author "Balazs DEZSO"
102copyright "Lemon Library"
103version 12
104\endcode
105
106<tt> \@end </tt>
107
108line.
109
110
111\section use Using graph input-output
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.
122
123\subsection write Writing a graph
124
125The \c GraphWriter class provides the graph output. To write a graph
126you should first give writing commands to the writer. You can declare
127writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
128Edge writing.
129
130\code
131GraphWriter<ListGraph> writer(std::cout, graph);
132\endcode
133
134The \c writeNodeMap() function declares a \c NodeMap writing command in the
135\c GraphWriter. You should give a name to the map and the map
136object as parameters. The NodeMap writing command with name "id" should write a
137unique map because it will be regarded as an ID map.
138
139\see IdMap, DescriptorMap 
140
141\code
142IdMap<ListGraph, Node> nodeIdMap;
143writer.writeNodeMap("id", nodeIdMap);
144
145writer.writeNodeMap("x-coord", xCoordMap);
146writer.writeNodeMap("y-coord", yCoordMap);
147writer.writeNodeMap("color", colorMap);
148\endcode
149
150With the \c writeEdgeMap() member function you can give an edge map
151writing command similar to the NodeMaps.
152
153\see IdMap, DescriptorMap 
154
155\code
156DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
157writer.writeEdgeMap("descriptor", edgeDescMap);
158
159writer.writeEdgeMap("weight", weightMap);
160writer.writeEdgeMap("label", labelMap);
161\endcode
162
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.
166
167\code
168writer.writeNode("source", sourceNode);
169writer.writeNode("target", targetNode);
170
171writer.writeEdge("observed", edge);
172\endcode
173
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
181After you give all write commands you must call the \c run() member
182function, which executes all the writing commands.
183
184\code
185writer.run();
186\endcode
187
188\subsection reading Reading a graph
189
190The file to be read may contain several maps and labeled nodes or edges.
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
193the GraphWriter but the reading method does not depend on the order of the
194given commands.
195
196The reader object assumes that each not readed value does not contain
197whitespaces, therefore it has some extra possibilities to control how
198it should skip the values when the string representation contains spaces.
199
200\code
201GraphReader<ListGraph> reader(std::cin, graph);
202\endcode
203
204The \c readNodeMap() function reads a map from the \c nodeset section.
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
207call the \c skipNodeMap() template member function with proper parameters.
208
209\see QuotedStringReader
210
211\code
212reader.readNodeMap("x-coord", xCoordMap);
213reader.readNodeMap("y-coord", yCoordMap);
214
215reader.readNodeMap<QuotedStringReader>("label", labelMap);
216reader.skipNodeMap<QuotedStringReader>("description");
217
218reader.readNodeMap("color", colorMap);
219\endcode
220
221With the \c readEdgeMap() member function you can give an edge map
222reading command similar to the NodeMaps.
223
224\code
225reader.readEdgeMap("weight", weightMap);
226reader.readEdgeMap("label", labelMap);
227\endcode
228
229With \c readNode() and \c readEdge() functions you can read labeled Nodes and
230Edges.
231
232\code
233reader.readNode("source", sourceNode);
234reader.readNode("target", targetNode);
235
236reader.readEdge("observed", edge);
237\endcode
238
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
248After you give all read commands you must call the \c run() member
249function, which executes all the commands.
250
251\code
252reader.run();
253\endcode
254
255\anchor rwbackground
256\section types Background of Reading and Writing
257
258
259To read a map (on the nodes or edges)
260the \c GraphReader should know how to read a Value from the given map.
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
264want to store it in a map, the reader skips a character sequence without
265whitespaces.
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.
270With this template parameter you can control how the Reader reads
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
282For example, the \c "strings" nodemap contains strings and you do not need
283the value of the string just the length. Then you can implement an own Reader
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...
297reader.readNodeMap<LengthReader>("strings", lengthMap);
298\endcode 
299
300The global functionality of the reader class can be changed by giving a
301special template parameter to the GraphReader class. By default, the
302template parameter is \c DefaultReaderTraits. A reader traits class
303should provide an inner template class Reader for each type, and a
304DefaultReader for skipping a value.
305
306The specialization of  writing is very similar to that of reading.
307
308\section undir Undirected graphs
309
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.
315
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.
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
328The \c edges section is changed to \c undiredges section. This section
329describes labeled edges and undirected edges. The directed edge label
330should start with a \c '+' or a \c '-' prefix to decide the direction
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
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.
360
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).
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
372item sets, and labeled items in the graph. These read and write
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
413for example as a network traffic matrix.
414
415In our example there is a network with symmetric links and there are assymetric
416traffic request on the network. This construction can be stored in an
417undirected graph and in a directed NewEdgeSetAdaptor class. The example
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
438result can be achived with the UndirGraphReader class, too.
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
455\author Balazs Dezso
456*/
457}
Note: See TracBrowser for help on using the repository browser.