alpar@1118
|
1 |
namespace lemon {
|
deba@1114
|
2 |
/*!
|
deba@1114
|
3 |
|
deba@1114
|
4 |
|
deba@1114
|
5 |
\page graph-io-page Graph Input-Output
|
deba@1114
|
6 |
|
athos@1522
|
7 |
The standard graph IO enables to store graphs and additional maps
|
alpar@1118
|
8 |
in a flexible and efficient way.
|
deba@1114
|
9 |
|
deba@1114
|
10 |
\section format The general file format
|
deba@1114
|
11 |
|
athos@1522
|
12 |
The file contains at most four sections in the following order:
|
deba@1114
|
13 |
|
deba@1114
|
14 |
\li nodeset
|
deba@1114
|
15 |
\li edgeset
|
deba@1114
|
16 |
\li nodes
|
deba@1114
|
17 |
\li edges
|
deba@1114
|
18 |
|
athos@1522
|
19 |
The nodeset section starts with the following line:
|
athos@1522
|
20 |
|
athos@1522
|
21 |
<tt>\@nodeset</tt>
|
athos@1522
|
22 |
|
athos@1522
|
23 |
The next line contains the names of the nodemaps, separated by whitespaces. Each
|
athos@1522
|
24 |
following line describes a node in the graph: it contains the values of the
|
athos@1522
|
25 |
maps in the right order. The map named "id" should contain unique values
|
athos@1522
|
26 |
because it is regarded as an ID-map. For example:
|
deba@1114
|
27 |
|
deba@1114
|
28 |
\code
|
deba@1114
|
29 |
@nodeset
|
deba@1114
|
30 |
id x-coord y-coord color
|
deba@1114
|
31 |
3 1.0 4.0 blue
|
deba@1114
|
32 |
5 2.3 5.7 red
|
deba@1114
|
33 |
12 7.8 2.3 green
|
deba@1114
|
34 |
\endcode
|
deba@1114
|
35 |
|
deba@1114
|
36 |
The edgeset section is very similar to the nodeset section, it has
|
athos@1522
|
37 |
the same coloumn oriented structure. It starts with the line
|
athos@1522
|
38 |
|
athos@1522
|
39 |
<tt>\@edgeset</tt>
|
athos@1522
|
40 |
|
athos@1522
|
41 |
The next line contains the whitespace separated list of names of the maps.
|
alpar@1118
|
42 |
Each of the next lines describes one edge. The first two elements in the line
|
athos@1522
|
43 |
are the IDs of the source and target (or tail and head) node of the edge as they occur in the ID node
|
athos@1522
|
44 |
map. You can also have an optional ID map on the edges for later reference.
|
deba@1114
|
45 |
|
deba@1114
|
46 |
\code
|
deba@1114
|
47 |
@edgeset
|
deba@1114
|
48 |
id weight label
|
deba@1114
|
49 |
3 5 a 4.3 a-edge
|
deba@1114
|
50 |
5 12 c 2.6 c-edge
|
deba@1114
|
51 |
3 12 g 3.4 g-edge
|
deba@1114
|
52 |
\endcode
|
deba@1114
|
53 |
|
deba@1333
|
54 |
The next section contains <em>labeled nodes</em> (i.e. nodes having a special
|
alpar@1118
|
55 |
label on them). The section starts with
|
athos@1522
|
56 |
|
athos@1522
|
57 |
<tt> \@nodes </tt>
|
athos@1522
|
58 |
|
athos@1522
|
59 |
Each of the next lines contains a label for a node in the graph
|
athos@1522
|
60 |
and then the ID described in the nodeset section.
|
deba@1114
|
61 |
|
deba@1114
|
62 |
\code
|
deba@1114
|
63 |
@nodes
|
deba@1114
|
64 |
source 3
|
deba@1114
|
65 |
target 12
|
deba@1114
|
66 |
\endcode
|
deba@1114
|
67 |
|
deba@1333
|
68 |
The last section describes the <em>labeled edges</em>
|
deba@1333
|
69 |
(i.e. edges having a special label on them). It starts with \c \@edges
|
deba@1114
|
70 |
and then each line contains the name of the edge and the ID.
|
deba@1114
|
71 |
|
deba@1114
|
72 |
\code
|
deba@1114
|
73 |
@nodes
|
deba@1114
|
74 |
observed c
|
deba@1114
|
75 |
\endcode
|
deba@1114
|
76 |
|
deba@1114
|
77 |
|
deba@1114
|
78 |
The file may contain empty lines and comment lines. The comment lines
|
deba@1114
|
79 |
start with an \c # character.
|
deba@1114
|
80 |
|
athos@1522
|
81 |
The file ends with the
|
athos@1522
|
82 |
|
athos@1522
|
83 |
<tt> \@end </tt>
|
athos@1522
|
84 |
|
athos@1522
|
85 |
line.
|
athos@1522
|
86 |
|
deba@1114
|
87 |
|
deba@1114
|
88 |
\section use Using graph input-output
|
athos@1522
|
89 |
The graph input and output is based on reading and writing commands. The user
|
athos@1522
|
90 |
adds reading and writing commands to the reader or writer class, then he
|
alpar@1118
|
91 |
calls the \c run() method that executes all the given commands.
|
deba@1114
|
92 |
|
deba@1114
|
93 |
\subsection write Writing a graph
|
deba@1114
|
94 |
|
deba@1114
|
95 |
The \c GraphWriter class provides the graph output. To write a graph
|
deba@1114
|
96 |
you should first give writing commands for the writer. You can declare
|
alpar@1118
|
97 |
write command as \c NodeMap or \c EdgeMap writing and labeled Node and
|
deba@1114
|
98 |
Edge writing.
|
deba@1114
|
99 |
|
deba@1114
|
100 |
\code
|
deba@1333
|
101 |
GraphWriter<ListGraph> writer(std::cout, graph);
|
deba@1114
|
102 |
\endcode
|
deba@1114
|
103 |
|
deba@1394
|
104 |
The \c writeNodeMap() function declares a \c NodeMap writing command in the
|
athos@1522
|
105 |
\c GraphWriter. You should give a name of the map and the map
|
athos@1522
|
106 |
object as parameters. The NodeMap writing command with name "id" should write a
|
deba@1333
|
107 |
unique map because it is regarded as ID map.
|
deba@1114
|
108 |
|
deba@1114
|
109 |
\see IdMap, DescriptorMap
|
deba@1114
|
110 |
|
deba@1114
|
111 |
\code
|
deba@1114
|
112 |
IdMap<ListGraph, Node> nodeIdMap;
|
deba@1394
|
113 |
writer.writeNodeMap("id", nodeIdMap);
|
deba@1114
|
114 |
|
deba@1394
|
115 |
writer.writeNodeMap("x-coord", xCoordMap);
|
deba@1394
|
116 |
writer.writeNodeMap("y-coord", yCoordMap);
|
deba@1394
|
117 |
writer.writeNodeMap("color", colorMap);
|
deba@1114
|
118 |
\endcode
|
deba@1114
|
119 |
|
deba@1394
|
120 |
With the \c writeEdgeMap() member function you can give an edge map
|
deba@1333
|
121 |
writing command similar to the NodeMaps.
|
deba@1114
|
122 |
|
deba@1114
|
123 |
\see IdMap, DescriptorMap
|
athos@1522
|
124 |
|
deba@1114
|
125 |
\code
|
deba@1114
|
126 |
DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
|
deba@1394
|
127 |
writer.writeEdgeMap("descriptor", edgeDescMap);
|
deba@1114
|
128 |
|
deba@1394
|
129 |
writer.writeEdgeMap("weight", weightMap);
|
deba@1394
|
130 |
writer.writeEdgeMap("label", labelMap);
|
deba@1114
|
131 |
\endcode
|
deba@1114
|
132 |
|
athos@1522
|
133 |
With \c writeNode() and \c writeEdge() functions you can designate Nodes and
|
athos@1522
|
134 |
Edges in the graph. For example, you can write out the source and target node
|
athos@1522
|
135 |
of a maximum flow instance.
|
deba@1114
|
136 |
|
deba@1114
|
137 |
\code
|
deba@1394
|
138 |
writer.writeNode("source", sourceNode);
|
deba@1394
|
139 |
writer.writeNode("target", targetNode);
|
deba@1114
|
140 |
|
deba@1394
|
141 |
writer.writeEdge("observed", edge);
|
deba@1114
|
142 |
\endcode
|
deba@1114
|
143 |
|
deba@1114
|
144 |
After you give all write commands you must call the \c run() member
|
athos@1522
|
145 |
function, which executes all the writing commands.
|
deba@1114
|
146 |
|
deba@1114
|
147 |
\code
|
deba@1114
|
148 |
writer.run();
|
deba@1114
|
149 |
\endcode
|
deba@1114
|
150 |
|
deba@1114
|
151 |
\subsection reading Reading a graph
|
deba@1114
|
152 |
|
alpar@1118
|
153 |
The given file format may contain several maps and labeled nodes or edges.
|
deba@1114
|
154 |
If you read a graph you need not read all the maps and items just those
|
deba@1114
|
155 |
that you need. The interface of the \c GraphReader is very similar to
|
athos@1522
|
156 |
the GraphWriter but the reading method does not depend on the order of the
|
deba@1114
|
157 |
given commands.
|
deba@1114
|
158 |
|
athos@1522
|
159 |
The reader object assumes that each not readed value does not contain
|
alpar@1118
|
160 |
whitespaces, therefore it has some extra possibilities to control how
|
alpar@1118
|
161 |
it should skip the values when the string representation contains spaces.
|
deba@1114
|
162 |
|
deba@1114
|
163 |
\code
|
deba@1333
|
164 |
GraphReader<ListGraph> reader(std::cin, graph);
|
deba@1114
|
165 |
\endcode
|
deba@1114
|
166 |
|
deba@1394
|
167 |
The \c readNodeMap() function reads a map from the \c \@nodeset section.
|
athos@1522
|
168 |
If there is a map that you do not want to read from the file and there are
|
athos@1522
|
169 |
whitespaces in the string represenation of the values then you should
|
deba@1114
|
170 |
call the \c skipNodeMap() template member function with proper parameters.
|
deba@1114
|
171 |
|
deba@1114
|
172 |
\see QuotedStringReader
|
athos@1522
|
173 |
|
deba@1114
|
174 |
\code
|
deba@1394
|
175 |
reader.readNodeMap("x-coord", xCoordMap);
|
deba@1394
|
176 |
reader.readNodeMap("y-coord", yCoordMap);
|
deba@1114
|
177 |
|
deba@1394
|
178 |
reader.readNodeMap<QuotedStringReader>("label", labelMap);
|
deba@1114
|
179 |
reader.skipNodeMap<QuotedStringReader>("description");
|
deba@1114
|
180 |
|
deba@1394
|
181 |
reader.readNodeMap("color", colorMap);
|
deba@1114
|
182 |
\endcode
|
deba@1114
|
183 |
|
deba@1394
|
184 |
With the \c readEdgeMap() member function you can give an edge map
|
deba@1114
|
185 |
reading command similar to the NodeMaps.
|
deba@1114
|
186 |
|
deba@1114
|
187 |
\code
|
deba@1394
|
188 |
reader.readEdgeMap("weight", weightMap);
|
deba@1394
|
189 |
reader.readEdgeMap("label", labelMap);
|
deba@1114
|
190 |
\endcode
|
deba@1114
|
191 |
|
deba@1394
|
192 |
With \c readNode() and \c readEdge() functions you can read labeled Nodes and
|
deba@1114
|
193 |
Edges.
|
deba@1114
|
194 |
|
deba@1114
|
195 |
\code
|
deba@1394
|
196 |
reader.readNode("source", sourceNode);
|
deba@1394
|
197 |
reader.readNode("target", targetNode);
|
deba@1114
|
198 |
|
deba@1394
|
199 |
reader.readEdge("observed", edge);
|
deba@1114
|
200 |
\endcode
|
deba@1114
|
201 |
|
deba@1114
|
202 |
After you give all read commands you must call the \c run() member
|
athos@1522
|
203 |
function, which executes all the commands.
|
deba@1114
|
204 |
|
deba@1114
|
205 |
\code
|
deba@1114
|
206 |
reader.run();
|
deba@1114
|
207 |
\endcode
|
deba@1114
|
208 |
|
athos@1522
|
209 |
\section types The background of Reading and Writing
|
athos@1522
|
210 |
The \c GraphReader should know how to read a Value from the given map.
|
deba@1114
|
211 |
By the default implementation the input operator reads a value from
|
deba@1114
|
212 |
the stream and the type of the readed value is the value type of the given map.
|
deba@1114
|
213 |
When the reader should skip a value in the stream, because you do not
|
deba@1114
|
214 |
want to store it in map, the reader skips a character sequence without
|
deba@1114
|
215 |
whitespace.
|
deba@1114
|
216 |
|
deba@1114
|
217 |
If you want to change the functionality of the reader, you can use
|
deba@1114
|
218 |
template parameters to specialize it. When you give a reading
|
deba@1114
|
219 |
command for a map you can give a Reader type as template parameter.
|
deba@1333
|
220 |
With this template parameter you can control how the Reader reads
|
deba@1114
|
221 |
a value from the stream.
|
deba@1114
|
222 |
|
deba@1114
|
223 |
The reader has the next structure:
|
deba@1114
|
224 |
\code
|
deba@1114
|
225 |
struct TypeReader {
|
deba@1114
|
226 |
typedef TypeName Value;
|
deba@1114
|
227 |
|
deba@1114
|
228 |
void read(std::istream& is, Value& value);
|
deba@1114
|
229 |
};
|
deba@1114
|
230 |
\endcode
|
deba@1114
|
231 |
|
deba@1114
|
232 |
By example, the \c "strings" nodemap contains strings and you do not need
|
deba@1114
|
233 |
the value of the string just the length. Then you can implement own Reader
|
deba@1114
|
234 |
struct.
|
deba@1114
|
235 |
|
deba@1114
|
236 |
\code
|
deba@1114
|
237 |
struct LengthReader {
|
deba@1114
|
238 |
typedef int Value;
|
deba@1114
|
239 |
|
deba@1114
|
240 |
void read(std::istream& is, Value& value) {
|
deba@1114
|
241 |
std::string tmp;
|
deba@1114
|
242 |
is >> tmp;
|
deba@1114
|
243 |
value = tmp.length();
|
deba@1114
|
244 |
}
|
deba@1114
|
245 |
};
|
deba@1114
|
246 |
...
|
deba@1394
|
247 |
reader.readNodeMap<LengthReader>("strings", lengthMap);
|
deba@1114
|
248 |
\endcode
|
deba@1114
|
249 |
|
deba@1114
|
250 |
The global functionality of the reader class can be changed by giving a
|
alpar@1118
|
251 |
special template parameter for the GraphReader class. By default, the
|
alpar@1118
|
252 |
template parameter is \c DefaultReaderTraits. A reader traits class
|
deba@1114
|
253 |
should provide an inner template class Reader for each type, and an
|
deba@1114
|
254 |
DefaultReader for skipping a value.
|
deba@1114
|
255 |
|
deba@1114
|
256 |
The specialization of the writing should be very similar to the reading.
|
deba@1114
|
257 |
|
deba@1333
|
258 |
\author Balazs Dezso
|
deba@1114
|
259 |
*/
|
deba@1333
|
260 |
}
|