COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/graph_io.dox @ 1788:614ce2dd3cba

Last change on this file since 1788:614ce2dd3cba was 1788:614ce2dd3cba, checked in by Balazs Dezso, 18 years ago

Some documentation modifications

File size: 14.6 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
113
114The graph input and output is based on <em> reading and writing
115commands</em>. The user gives reading and writing commands to the reader or
116writer class, then he calls the \c run() method that executes all the given
117commands.
118
119\subsection write Writing a graph
120
121The \ref lemon::GraphWriter "GraphWriter" template class
122provides the graph output. To write a graph
123you should first give writing commands to the writer. You can declare
124writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
125Edge writing.
126
127\code
128GraphWriter<ListGraph> writer(std::cout, graph);
129\endcode
130
131The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
132function declares a \c NodeMap writing command in the
133\ref lemon::GraphWriter "GraphWriter".
134You should give a name to the map and the map
135object as parameters. The NodeMap writing command with name "id" should write a
136unique map because it will be regarded as an ID map.
137
138\see IdMap, DescriptorMap 
139
140\code
141IdMap<ListGraph, Node> nodeIdMap;
142writer.writeNodeMap("id", nodeIdMap);
143
144writer.writeNodeMap("x-coord", xCoordMap);
145writer.writeNodeMap("y-coord", yCoordMap);
146writer.writeNodeMap("color", colorMap);
147\endcode
148
149With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
150member 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 \ref lemon::GraphWriter::writeNode() "writeNode()"
164and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
165functions you can designate Nodes and
166Edges in the graph. For example, you can write out the source and target node
167of a maximum flow instance.
168
169\code
170writer.writeNode("source", sourceNode);
171writer.writeNode("target", targetNode);
172
173writer.writeEdge("observed", edge);
174\endcode
175
176With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
177function you can write an attribute to the file.
178
179\code
180writer.writeAttribute("author", "Balazs DEZSO");
181writer.writeAttribute("version", 12);
182\endcode
183
184After you give all write commands you must call the
185\ref lemon::GraphWriter::run() "run()" member
186function, which executes all the writing commands.
187
188\code
189writer.run();
190\endcode
191
192\subsection reading Reading a graph
193
194The file to be read may contain several maps and labeled nodes or edges.
195If you read a graph you need not read all the maps and items just those
196that you need. The interface of the \ref lemon::GraphReader "GraphReader"
197is very similar to
198the \ref lemon::GraphWriter "GraphWriter"
199but the reading method does not depend on the order of the
200given commands.
201
202The reader object assumes that each not readed value does not contain
203whitespaces, therefore it has some extra possibilities to control how
204it should skip the values when the string representation contains spaces.
205
206\code
207GraphReader<ListGraph> reader(std::cin, graph);
208\endcode
209
210The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
211function reads a map from the \c nodeset section.
212If there is a map that you do not want to read from the file and there are
213whitespaces in the string represenation of the values then you should
214call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
215template member function with proper parameters.
216
217\see QuotedStringReader
218
219\code
220reader.readNodeMap("x-coord", xCoordMap);
221reader.readNodeMap("y-coord", yCoordMap);
222
223reader.readNodeMap<QuotedStringReader>("label", labelMap);
224reader.skipNodeMap<QuotedStringReader>("description");
225
226reader.readNodeMap("color", colorMap);
227\endcode
228
229With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
230member function you can give an edge map
231reading command similar to the NodeMaps.
232
233\code
234reader.readEdgeMap("weight", weightMap);
235reader.readEdgeMap("label", labelMap);
236\endcode
237
238With \ref lemon::GraphReader::readNode() "readNode()"
239and \ref lemon::GraphReader::readEdge() "readEdge()"
240functions you can read labeled Nodes and
241Edges.
242
243\code
244reader.readNode("source", sourceNode);
245reader.readNode("target", targetNode);
246
247reader.readEdge("observed", edge);
248\endcode
249
250With \ref lemon::GraphReader::readAttribute() "readAttribute()"
251function you can read an attribute from the file.
252
253\code
254std::string author;
255writer.readAttribute("author", author);
256int version;
257writer.writeAttribute("version", version);
258\endcode
259
260After you give all read commands you must call the
261\ref lemon::GraphReader::run() "run()" member
262function, which executes all the commands.
263
264\code
265reader.run();
266\endcode
267
268\anchor rwbackground
269\section types Background of Reading and Writing
270
271
272To read a map (on the nodes or edges)
273the \ref lemon::GraphReader "GraphReader"
274should know how to read a Value from the given map.
275By the default implementation the input operator reads a value from
276the stream and the type of the readed value is the value type of the given map.
277When the reader should skip a value in the stream, because you do not
278want to store it in a map, the reader skips a character sequence without
279whitespaces.
280
281If you want to change the functionality of the reader, you can use
282template parameters to specialize it. When you give a reading
283command for a map you can give a Reader type as template parameter.
284With this template parameter you can control how the Reader reads
285a value from the stream.
286
287The reader has the next structure:
288\code
289struct TypeReader {
290  typedef TypeName Value;
291
292  void read(std::istream& is, Value& value);
293};
294\endcode
295
296For example, the \c "strings" nodemap contains strings and you do not need
297the value of the string just the length. Then you can implement an own Reader
298struct.
299
300\code
301struct LengthReader {
302  typedef int Value;
303
304  void read(std::istream& is, Value& value) {
305    std::string tmp;
306    is >> tmp;
307    value = tmp.length();
308  }
309};
310...
311reader.readNodeMap<LengthReader>("strings", lengthMap);
312\endcode 
313
314The global functionality of the reader class can be changed by giving a
315special template parameter to the GraphReader class. By default, the
316template parameter is \c DefaultReaderTraits. A reader traits class
317should provide an inner template class Reader for each type, and a
318DefaultReader for skipping a value.
319
320The specialization of  writing is very similar to that of reading.
321
322\section undir Undirected graphs
323
324In a file describing an undirected graph (undir graph, for short) you find an
325\c undiredgeset section instead of the \c edgeset section. The first line of
326the section describes the names of the maps on the undirected egdes and all
327next lines describe one undirected edge with the the incident nodes and the
328values of the map.
329
330The format handles directed edge maps as a syntactical sugar???, if there
331are two maps with names being the same with a \c '+' and a \c '-' prefix
332then this will be read as a directed map.
333
334\code
335@undiredgeset
336             id    capacity +flow -flow
33732   2       1     4.3      2.0   0.0
33821   21      5     2.6      0.0   2.6
33921   12      8     3.4      0.0   0.0
340\endcode
341
342The \c edges section is changed to \c undiredges section. This section
343describes labeled edges and undirected edges. The directed edge label
344should start with a \c '+' or a \c '-' prefix to decide the direction
345of the edge.
346
347\code
348@undiredges
349undiredge 1
350+edge 5
351-back 5
352\endcode
353
354There are similar classes to the \ref lemon::GraphReader "GraphReader" and
355\ref lemon::GraphWriter "GraphWriter" which
356handle the undirected graphs. These classes are
357the \ref lemon::UndirGraphReader "UndirGraphReader"
358and \ref lemon::UndirGraphWriter "UndirGraphWriter".
359
360The \ref lemon::UndirGraphReader::readUndirEdgeMap() "readUndirEdgeMap()"
361function reads an undirected map and the
362\ref lemon::UndirGraphReader::readUndirEdge() "readUndirEdge()"
363reads an undirected edge from the file,
364
365\code
366reader.readUndirEdgeMap("capacity", capacityMap);
367reader.readEdgeMap("flow", flowMap);
368...
369reader.readUndirEdge("undir_edge", undir_edge);
370reader.readEdge("edge", edge);
371\endcode
372
373\section advanced Advanced features
374
375The graph reader and writer classes give an easy way to read and write
376graphs. But sometimes we want more advanced features. In this case we can
377use the more general <tt>lemon reader and writer</tt> interface.
378
379The LEMON file format is a section oriented file format. It contains one or
380more sections, each starting with a line identifying its type
381(the word starting with the \c \@  character).
382The content of the section this way cannot contain line with \c \@ first
383character. The file may contains comment lines with \c # first character.
384
385The \ref lemon::LemonReader "LemonReader"
386and \ref lemon::LemonWriter "LemonWriter"
387gives a framework to read and
388write sections. There are various section reader and section writer
389classes which can be attached to a \ref lemon::LemonReader "LemonReader"
390or a \ref lemon::LemonWriter "LemonWriter".
391
392There are default section readers and writers for reading and writing
393item sets, and labeled items in the graph. These read and write
394the format described above. Other type of data can be handled with own
395section reader and writer classes which are inherited from the
396\c LemonReader::SectionReader or the
397\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
398classes.
399
400The next example defines a special section reader which reads the
401\c \@description sections into a string:
402
403\code
404class DescriptionReader : LemonReader::SectionReader {
405protected:
406  virtual bool header(const std::string& line) {
407    std::istringstream ls(line);
408    std::string head;
409    ls >> head;
410    return head == "@description";
411  }
412
413  virtual void read(std::istream& is) {
414    std::string line;
415    while (getline(is, line)) {
416      desc += line;
417    }
418  }
419public:
420
421  typedef LemonReader::SectionReader Parent;
422 
423  DescriptionReader(LemonReader& reader) : Parent(reader) {}
424
425  const std::string& description() const {
426    return description;
427  }
428
429private:
430  std::string desc;
431};
432\endcode
433
434The other advanced stuff of the generalized file format is that
435multiple edgesets can be stored to the same nodeset. It can be used
436for example as a network traffic matrix.
437
438In our example there is a network with symmetric links and there are assymetric
439traffic request on the network. This construction can be stored in an
440undirected graph and in a directed \c NewEdgeSetAdaptor class. The example
441shows the input with the \ref lemon::LemonReader "LemonReader" class:
442
443\code
444UndirListGraph network;
445UndirListGraph::UndirEdgeSet<double> capacity;
446NewEdgeSetAdaptor<UndirListGraph> traffic(network);
447NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
448
449LemonReader reader(std::cin);
450NodeSetReader nodesetReader(reader, network);
451UndirEdgeSetReader undirEdgesetReader(reader, network, nodesetReader);
452undirEdgesetReader.readEdgeMap("capacity", capacity);
453EdgeSetReader edgesetReader(reader, traffic, nodesetReader);
454edgesetReader.readEdgeMap("request", request);
455
456reader.run();
457\endcode
458
459Because both the \ref lemon::GraphReader "GraphReader"
460and the \ref lemon::UndirGraphReader "UndirGraphReader" can be converted
461to \ref lemon::LemonReader "LemonReader"
462and it can resolve the ID's of the items, the previous
463result can be achived with the \ref lemon::UndirGraphReader "UndirGraphReader"
464class, too.
465
466
467\code
468UndirListGraph network;
469UndirListGraph::UndirEdgeSet<double> capacity;
470NewEdgeSetAdaptor<UndirListGraph> traffic(network);
471NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
472
473UndirGraphReader reader(std::cin, network);
474reader.readEdgeMap("capacity", capacity);
475EdgeSetReader edgesetReader(reader, traffic, reader);
476edgesetReader.readEdgeMap("request", request);
477
478reader.run();
479\endcode
480
481\author Balazs Dezso
482*/
483}
Note: See TracBrowser for help on using the repository browser.