COIN-OR::LEMON - Graph Library

source: lemon-0.x/doc/read_write_bg.dox @ 2216:1e45cdeea3cc

Last change on this file since 2216:1e45cdeea3cc was 2216:1e45cdeea3cc, checked in by Alpar Juttner, 18 years ago

The recent progresses on the tutorial due to Mark.

File size: 7.0 KB
Line 
1namespace lemon {
2/*!
3\page read_write_bg Background of Reading and Writing
4
5To read a map (on the nodes or edges)
6the \ref lemon::GraphReader "GraphReader"
7should know how to read a Value from the given map.
8By the default implementation the input operator reads a value from
9the stream and the type of the read value is the value type of the given map.
10When the reader should skip a value in the stream, because you do not
11want to store it in a map, the reader skips a character sequence without
12whitespaces.
13
14If you want to change the functionality of the reader, you can use
15template parameters to specialize it. When you give a reading
16command for a map you can give a Reader type as template parameter.
17With this template parameter you can control how the Reader reads
18a value from the stream.
19
20The reader has the next structure:
21\code
22struct TypeReader {
23  typedef TypeName Value;
24
25  void read(std::istream& is, Value& value);
26};
27\endcode
28
29For example, the \c "strings" nodemap contains strings and you do not need
30the value of the string just the length. Then you can implement an own Reader
31struct.
32
33\code
34struct LengthReader {
35  typedef int Value;
36
37  void read(std::istream& is, Value& value) {
38    std::string tmp;
39    is >> tmp;
40    value = tmp.length();
41  }
42};
43...
44reader.readNodeMap<LengthReader>("strings", lengthMap);
45\endcode 
46
47The global functionality of the reader class can be changed by giving a
48special template parameter to the GraphReader class. By default, the
49template parameter is \c DefaultReaderTraits. A reader traits class
50should provide a nested template class Reader for each type, and a
51DefaultReader for skipping a value.
52
53The specialization of writing is very similar to that of reading.
54
55\section u Undirected graphs
56
57In a file describing an undirected graph (ugraph, for short) you find an
58\c uedgeset section instead of the \c edgeset section. The first line of
59the section describes the names of the maps on the undirected egdes and all
60next lines describe one undirected edge with the the incident nodes and the
61values of the map.
62
63The format handles directed edge maps as a syntactical sugar???, if there
64are two maps with names being the same with a \c '+' and a \c '-' prefix
65then this will be read as a directed map.
66
67\code
68@uedgeset
69             label      capacity        +flow   -flow
7032   2       1          4.3             2.0     0.0
7121   21      5          2.6             0.0     2.6
7221   12      8          3.4             0.0     0.0
73\endcode
74
75The \c edges section is changed to \c uedges section. This section
76describes labeled edges and undirected edges. The directed edge label
77should start with a \c '+' or a \c '-' prefix to decide the direction
78of the edge.
79
80\code
81@uedges
82uedge 1
83+edge 5
84-back 5
85\endcode
86
87There are similar classes to the \ref lemon::GraphReader "GraphReader" and
88\ref lemon::GraphWriter "GraphWriter" which
89handle the undirected graphs. These classes are
90the \ref lemon::UGraphReader "UGraphReader"
91and \ref lemon::UGraphWriter "UGraphWriter".
92
93The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
94function reads an undirected map and the
95\ref lemon::UGraphReader::readUEdge() "readUEdge()"
96reads an undirected edge from the file,
97
98\code
99reader.readUEdgeMap("capacity", capacityMap);
100reader.readEdgeMap("flow", flowMap);
101...
102reader.readUEdge("u_edge", u_edge);
103reader.readEdge("edge", edge);
104\endcode
105
106\section advanced Advanced features
107
108The graph reader and writer classes give an easy way to read and write
109graphs. But sometimes we want more advanced features. In this case we can
110use the more general <tt>lemon reader and writer</tt> interface.
111
112The LEMON file format is a section oriented file format. It contains one or
113more sections, each starting with a line identifying its type
114(the word starting with the \c \@  character).
115The content of the section this way cannot contain line with \c \@ first
116character. The file may contains comment lines with \c # first character.
117
118The \ref lemon::LemonReader "LemonReader"
119and \ref lemon::LemonWriter "LemonWriter"
120gives a framework to read and
121write sections. There are various section reader and section writer
122classes which can be attached to a \ref lemon::LemonReader "LemonReader"
123or a \ref lemon::LemonWriter "LemonWriter".
124
125There are default section readers and writers for reading and writing
126item sets, and labeled items in the graph. These read and write
127the format described above. Other type of data can be handled with own
128section reader and writer classes which are inherited from the
129\c LemonReader::SectionReader or the
130\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
131classes.
132
133The next example defines a special section reader which reads the
134\c \@description sections into a string:
135
136\code
137class DescriptionReader : LemonReader::SectionReader {
138protected:
139  virtual bool header(const std::string& line) {
140    std::istringstream ls(line);
141    std::string head;
142    ls >> head;
143    return head == "@description";
144  }
145
146  virtual void read(std::istream& is) {
147    std::string line;
148    while (getline(is, line)) {
149      desc += line;
150    }
151  }
152public:
153
154  typedef LemonReader::SectionReader Parent;
155 
156  DescriptionReader(LemonReader& reader) : Parent(reader) {}
157
158  const std::string& description() const {
159    return description;
160  }
161
162private:
163  std::string desc;
164};
165\endcode
166
167The other advanced stuff of the generalized file format is that
168multiple edgesets can be stored to the same nodeset. It can be used
169for example as a network traffic matrix.
170
171In our example there is a network with symmetric links and there are assymetric
172traffic request on the network. This construction can be stored in an
173undirected graph and in a directed \c ListEdgeSet class. The example
174shows the input with the \ref lemon::LemonReader "LemonReader" class:
175
176\code
177ListUGraph network;
178ListUGraph::UEdgeMap<double> capacity;
179ListEdgeSet<ListUGraph> traffic(network);
180ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
181
182LemonReader reader(std::cin);
183NodeSetReader<ListUGraph> nodesetReader(reader, network);
184UEdgeSetReader<ListUGraph>
185  uEdgesetReader(reader, network, nodesetReader);
186uEdgesetReader.readEdgeMap("capacity", capacity);
187EdgeSetReader<ListEdgeSet<ListUGraph> >
188  edgesetReader(reader, traffic, nodesetReader, "traffic");
189edgesetReader.readEdgeMap("request", request);
190
191reader.run();
192\endcode
193
194Because both the \ref lemon::GraphReader "GraphReader"
195and the \ref lemon::UGraphReader "UGraphReader" can be converted
196to \ref lemon::LemonReader "LemonReader"
197and it can resolve the label's of the items, the previous
198result can be achived with the \ref lemon::UGraphReader "UGraphReader"
199class, too.
200
201
202\code
203ListUGraph network;
204ListUGraph::UEdgeSet<double> capacity;
205ListEdgeSet<ListUGraph> traffic(network);
206ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
207
208UGraphReader<ListUGraph> reader(std::cin, network);
209reader.readEdgeMap("capacity", capacity);
210EdgeSetReader<ListEdgeSet<ListUGraph> >
211  edgesetReader(reader, traffic, reader, "traffic");
212edgesetReader.readEdgeMap("request", request);
213
214reader.run();
215\endcode
216
217\author Balazs Dezso
218*/
219}
Note: See TracBrowser for help on using the repository browser.