Bug fix in CapacityScaling.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
23 \page graph-io-page Graph Input-Output
25 The standard graph IO enables one to store graphs and additional maps
26 (i.e. functions on the nodes or edges) in a flexible and efficient way.
27 Before you read this page you should be familiar with LEMON
28 \ref graphs "graphs" and \ref maps-page "maps".
30 \section format The general file format
32 The file contains sections in the following order:
40 Some of these sections can be omitted, but you will basicly need the nodeset
41 section (unless your graph has no nodes at all) and the edgeset section
42 (unless your graph has no edges at all).
44 The nodeset section describes the nodes of your graph: it identifies the nodes
45 and gives the maps defined on them, if any. It starts with the
50 The next line contains the names of the nodemaps, separated by whitespaces. Each
51 following line describes a node in the graph: it contains the values of the
52 maps in the right order. The map named "label" should contain unique values
53 because it is regarded as a label map. These labels need not be numbers but they
54 must identify the nodes uniquely for later reference. For example:
58 label x-coord y-coord color
64 The edgeset section is very similar to the nodeset section, it has
65 the same coloumn oriented structure. It starts with the line
69 The next line contains the whitespace separated list of names of the edge
70 maps. Each of the next lines describes one edge. The first two elements in
71 the line are the labels of the source and target (or tail and head) nodes of the
72 edge as they occur in the label node map of the nodeset section. You can also
73 have an optional label map on the edges for later reference (which has to be
84 The \e nodes section contains <em>labeled (distinguished) nodes</em>
85 (i.e. nodes having a special
86 label on them). The section starts with
90 Each of the next lines contains a label for a node in the graph
91 and then the label as described in the \e nodeset section.
99 The last section describes the <em>labeled (distinguished) edges</em>
100 (i.e. edges having a special label on them). It starts with \c \@edges
101 and then each line contains the name of the edge and the label.
109 The file may contain empty lines and comment lines. The comment lines
110 start with an \c # character.
112 The attributes section can handle some information about the graph. It
113 contains key-value pairs in each line (a key and the mapped value to key). The
114 key should be a string without whitespaces, the value can be of various types.
118 title "Four colored planar graph"
119 author "Balazs DEZSO"
120 copyright "Lemon Library"
124 Finally, the file should be closed with \c \@end line.
127 \section use Using graph input-output
130 The graph input and output is based on <em> reading and writing
131 commands</em>. The user gives reading and writing commands to the reader or
132 writer class, then he calls the \c run() method that executes all the given
135 \subsection write Writing a graph
137 The \ref lemon::GraphWriter "GraphWriter" template class
138 provides the graph output. To write a graph
139 you should first give writing commands to the writer. You can declare
140 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
144 GraphWriter<ListGraph> writer(std::cout, graph);
147 The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
148 function declares a \c NodeMap writing command in the
149 \ref lemon::GraphWriter "GraphWriter".
150 You should give a name to the map and the map
151 object as parameters. The NodeMap writing command with name "label" should write a
152 unique map because it will be regarded as a label map.
154 \see IdMap, DescriptorMap
157 IdMap<ListGraph, Node> nodeLabelMap;
158 writer.writeNodeMap("label", nodeLabelMap);
160 writer.writeNodeMap("x-coord", xCoordMap);
161 writer.writeNodeMap("y-coord", yCoordMap);
162 writer.writeNodeMap("color", colorMap);
165 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
166 member function you can give an edge map
167 writing command similar to the NodeMaps.
169 \see IdMap, DescriptorMap
172 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
173 writer.writeEdgeMap("descriptor", edgeDescMap);
175 writer.writeEdgeMap("weight", weightMap);
176 writer.writeEdgeMap("note", noteMap);
179 With \ref lemon::GraphWriter::writeNode() "writeNode()"
180 and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
181 functions you can designate Nodes and
182 Edges in the graph. For example, you can write out the source and target node
183 of a maximum flow instance.
186 writer.writeNode("source", sourceNode);
187 writer.writeNode("target", targetNode);
189 writer.writeEdge("observed", edge);
192 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
193 function you can write an attribute to the file.
196 writer.writeAttribute("author", "Balazs DEZSO");
197 writer.writeAttribute("version", 12);
200 After you give all write commands you must call the
201 \ref lemon::GraphWriter::run() "run()" member
202 function, which executes all the writing commands.
208 \subsection reading Reading a graph
210 The file to be read may contain several maps and labeled nodes or edges.
211 If you read a graph you need not read all the maps and items just those
212 that you need. The interface of the \ref lemon::GraphReader "GraphReader"
214 the \ref lemon::GraphWriter "GraphWriter"
215 but the reading method does not depend on the order of the
218 The reader object assumes that each not read value does not contain
219 whitespaces, therefore it has some extra possibilities to control how
220 it should skip the values when the string representation contains spaces.
223 GraphReader<ListGraph> reader(std::cin, graph);
226 The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
227 function reads a map from the \c nodeset section.
228 If there is a map that you do not want to read from the file and there are
229 whitespaces in the string represenation of the values then you should
230 call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
231 template member function with proper parameters.
233 \see QuotedStringReader
236 reader.readNodeMap("x-coord", xCoordMap);
237 reader.readNodeMap("y-coord", yCoordMap);
239 reader.readNodeMap<QuotedStringReader>("label", labelMap);
240 reader.skipNodeMap<QuotedStringReader>("description");
242 reader.readNodeMap("color", colorMap);
245 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
246 member function you can give an edge map
247 reading command similar to the NodeMaps.
250 reader.readEdgeMap("weight", weightMap);
251 reader.readEdgeMap("label", labelMap);
254 With \ref lemon::GraphReader::readNode() "readNode()"
255 and \ref lemon::GraphReader::readEdge() "readEdge()"
256 functions you can read labeled Nodes and
260 reader.readNode("source", sourceNode);
261 reader.readNode("target", targetNode);
263 reader.readEdge("observed", edge);
266 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
267 function you can read an attribute from the file.
271 writer.readAttribute("author", author);
273 writer.writeAttribute("version", version);
276 After you give all read commands you must call the
277 \ref lemon::GraphReader::run() "run()" member
278 function, which executes all the commands.
285 \section types Background of Reading and Writing
288 To read a map (on the nodes or edges)
289 the \ref lemon::GraphReader "GraphReader"
290 should know how to read a Value from the given map.
291 By the default implementation the input operator reads a value from
292 the stream and the type of the read value is the value type of the given map.
293 When the reader should skip a value in the stream, because you do not
294 want to store it in a map, the reader skips a character sequence without
297 If you want to change the functionality of the reader, you can use
298 template parameters to specialize it. When you give a reading
299 command for a map you can give a Reader type as template parameter.
300 With this template parameter you can control how the Reader reads
301 a value from the stream.
303 The reader has the next structure:
306 typedef TypeName Value;
308 void read(std::istream& is, Value& value);
312 For example, the \c "strings" nodemap contains strings and you do not need
313 the value of the string just the length. Then you can implement an own Reader
317 struct LengthReader {
320 void read(std::istream& is, Value& value) {
323 value = tmp.length();
327 reader.readNodeMap<LengthReader>("strings", lengthMap);
330 The global functionality of the reader class can be changed by giving a
331 special template parameter to the GraphReader class. By default, the
332 template parameter is \c DefaultReaderTraits. A reader traits class
333 should provide a nested template class Reader for each type, and a
334 DefaultReader for skipping a value.
336 The specialization of writing is very similar to that of reading.
338 \section undir Undirected and Bipartite graphs
340 In a file describing an undirected graph (ugraph, for short) you find an
341 \c uedgeset section instead of the \c edgeset section. The first line of
342 the section describes the names of the maps on the undirected egdes and all
343 next lines describe one undirected edge with the the incident nodes and the
346 The format could store directed edge maps, if there are two maps with
347 names being the same with a \c '+' and a \c '-' prefix then this could
348 be read as such a map.
352 label capacity +flow -flow
358 The \c edges section is changed to \c uedges section. This section
359 describes labeled edges and undirected edges. The directed edge label
360 should start with a \c '+' or a \c '-' prefix to decide the direction
370 There are similar classes to the \ref lemon::GraphReader "GraphReader" and
371 \ref lemon::GraphWriter "GraphWriter" which
372 handle the undirected graphs. These classes are
373 the \ref lemon::UGraphReader "UGraphReader"
374 and \ref lemon::UGraphWriter "UGraphWriter".
376 The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
377 function reads an undirected map and the
378 \ref lemon::UGraphReader::readUEdge() "readUEdge()"
379 reads an undirected edge from the file,
382 reader.readUEdgeMap("capacity", capacityMap);
383 reader.readEdgeMap("flow", flowMap);
385 reader.readUEdge("u_edge", u_edge);
386 reader.readEdge("edge", edge);
389 The undirected bipartite graphs could be read with the \c BpUGraph
390 class and it has specialized nodeset section, which should be start
391 with \c "@bpnodeset". This section is separated to two
392 subsections. The header line of these sections start with "&anodeset"
393 or "&bnodeset" and after that the line contains the names of the
394 regular and A-node or B-node maps accordingly. The lines of each
395 section contains the mapped values. The labels of the graph should be
396 unique overall both subsections.
400 &anodeset label coords radius
403 &bnodeset label coords
408 The reading can be done with \ref lemon::BpUGraphReader::readANodeMap()
409 "readANodeMap()", \ref lemon::BpUGraphReader::readBNodeMap()
410 "readBNodeMap()" or \ref lemon::BpUGraphReader::readNodeMap()
411 "readNodeMap()" members.
414 reader.readNodeMap("coords", coords);
415 reader.readAnodeMap("radius", radius);
418 \section advanced Advanced features
420 The graph reader and writer classes give an easy way to read and write
421 graphs. But sometimes we want more advanced features. In this case we can
422 use the more general <tt>lemon reader and writer</tt> interface.
424 The LEMON file format is a section oriented file format. It contains one or
425 more sections, each starting with a line identifying its type
426 (the word starting with the \c \@ character).
427 The content of the section this way cannot contain line with \c \@ first
428 character. The file may contains comment lines with \c # first character.
430 The \ref lemon::LemonReader "LemonReader"
431 and \ref lemon::LemonWriter "LemonWriter"
432 gives a framework to read and
433 write sections. There are various section reader and section writer
434 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
435 or a \ref lemon::LemonWriter "LemonWriter".
437 There are default section readers and writers for reading and writing
438 item sets, and labeled items in the graph. These read and write
439 the format described above. Other type of data can be handled with own
440 section reader and writer classes which are inherited from the
441 \c LemonReader::SectionReader or the
442 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
445 The next example defines a special section reader which reads the
446 \c \@description sections into a string:
449 class DescriptionReader : LemonReader::SectionReader {
451 virtual bool header(const std::string& line) {
452 std::istringstream ls(line);
455 return head == "@description";
458 virtual void read(std::istream& is) {
460 while (getline(is, line)) {
466 typedef LemonReader::SectionReader Parent;
468 DescriptionReader(LemonReader& reader) : Parent(reader) {}
470 const std::string& description() const {
479 The other advanced stuff of the generalized file format is that
480 multiple edgesets can be stored to the same nodeset. It can be used
481 for example as a network traffic matrix.
483 In our example there is a network with symmetric links and there are assymetric
484 traffic request on the network. This construction can be stored in an
485 undirected graph and in a directed \c ListEdgeSet class. The example
486 shows the input with the \ref lemon::LemonReader "LemonReader" class:
490 ListUGraph::UEdgeMap<double> capacity;
491 ListEdgeSet<ListUGraph> traffic(network);
492 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
494 LemonReader reader(std::cin);
495 NodeSetReader<ListUGraph> nodesetReader(reader, network);
496 UEdgeSetReader<ListUGraph>
497 uEdgesetReader(reader, network, nodesetReader);
498 uEdgesetReader.readEdgeMap("capacity", capacity);
499 EdgeSetReader<ListEdgeSet<ListUGraph> >
500 edgesetReader(reader, traffic, nodesetReader, "traffic");
501 edgesetReader.readEdgeMap("request", request);
506 Because both the \ref lemon::GraphReader "GraphReader"
507 and the \ref lemon::UGraphReader "UGraphReader" can be converted
508 to \ref lemon::LemonReader "LemonReader"
509 and it can resolve the label's of the items, the previous
510 result can be achived with the \ref lemon::UGraphReader "UGraphReader"
516 ListUGraph::UEdgeSet<double> capacity;
517 ListEdgeSet<ListUGraph> traffic(network);
518 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
520 UGraphReader<ListUGraph> reader(std::cin, network);
521 reader.readEdgeMap("capacity", capacity);
522 EdgeSetReader<ListEdgeSet<ListUGraph> >
523 edgesetReader(reader, traffic, reader, "traffic");
524 edgesetReader.readEdgeMap("request", request);