doc/graph_io.dox
author deba
Fri, 30 Mar 2007 14:17:28 +0000
changeset 2416 261b4701405d
parent 2100 6fbe90faf02a
child 2502 9c23c3762bc5
permissions -rw-r--r--
Small improvments
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     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.
    12  *
    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
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon {
    20 /*!
    21 
    22 
    23 \page graph-io-page Graph Input-Output
    24 
    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".
    29 
    30 \section format The general file format
    31 
    32 The file contains sections in the following order:
    33 
    34 \li nodeset
    35 \li edgeset
    36 \li nodes
    37 \li edges
    38 \li attributes
    39 
    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). 
    43 
    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
    46 following line:
    47 
    48 <tt>\@nodeset</tt>
    49 
    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:
    55 
    56 \code
    57 @nodeset
    58 label  x-coord  y-coord  color
    59 3   1.0      4.0      blue
    60 5   2.3      5.7      red
    61 12  7.8      2.3      green
    62 \endcode
    63 
    64 The edgeset section is very similar to the nodeset section, it has
    65 the same coloumn oriented structure. It starts with the line 
    66 
    67 <tt>\@edgeset</tt>
    68 
    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
    74 unique in this case).
    75 
    76 \code
    77 @edgeset
    78              label      weight   note
    79 3   5        a          4.3      a-edge
    80 5   12       c          2.6      c-edge
    81 3   12       g          3.4      g-edge
    82 \endcode
    83 
    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
    87 
    88 <tt> \@nodes </tt>
    89 
    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.
    92 
    93 \code
    94 @nodes 
    95 source 3
    96 target 12
    97 \endcode
    98 
    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.
   102 
   103 \code
   104 @edges 
   105 observed c
   106 \endcode
   107 
   108 
   109 The file may contain empty lines and comment lines. The comment lines
   110 start with an \c # character.
   111 
   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.
   115 
   116 \code
   117 @attributes
   118 title "Four colored planar graph"
   119 author "Balazs DEZSO"
   120 copyright "Lemon Library"
   121 version 12
   122 \endcode
   123 
   124 Finally, the file should be closed with \c \@end line.
   125 
   126 
   127 \section use Using graph input-output
   128 
   129 
   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
   133 commands.
   134 
   135 \subsection write Writing a graph
   136 
   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
   141 Edge writing.
   142 
   143 \code
   144 GraphWriter<ListGraph> writer(std::cout, graph);
   145 \endcode
   146 
   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.
   153 
   154 \see IdMap, DescriptorMap  
   155 
   156 \code
   157 IdMap<ListGraph, Node> nodeLabelMap;
   158 writer.writeNodeMap("label", nodeLabelMap);
   159 
   160 writer.writeNodeMap("x-coord", xCoordMap);
   161 writer.writeNodeMap("y-coord", yCoordMap);
   162 writer.writeNodeMap("color", colorMap);
   163 \endcode
   164 
   165 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
   166 member function you can give an edge map
   167 writing command similar to the NodeMaps.
   168 
   169 \see IdMap, DescriptorMap  
   170 
   171 \code
   172 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
   173 writer.writeEdgeMap("descriptor", edgeDescMap);
   174 
   175 writer.writeEdgeMap("weight", weightMap);
   176 writer.writeEdgeMap("note", noteMap);
   177 \endcode
   178 
   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.
   184 
   185 \code
   186 writer.writeNode("source", sourceNode);
   187 writer.writeNode("target", targetNode);
   188 
   189 writer.writeEdge("observed", edge);
   190 \endcode
   191 
   192 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
   193 function you can write an attribute to the file.
   194 
   195 \code
   196 writer.writeAttribute("author", "Balazs DEZSO");
   197 writer.writeAttribute("version", 12);
   198 \endcode
   199 
   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.
   203 
   204 \code
   205 writer.run();
   206 \endcode
   207 
   208 \subsection reading Reading a graph
   209 
   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"
   213 is very similar to
   214 the \ref lemon::GraphWriter "GraphWriter"
   215 but the reading method does not depend on the order of the
   216 given commands.
   217 
   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.
   221 
   222 \code
   223 GraphReader<ListGraph> reader(std::cin, graph);
   224 \endcode
   225 
   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.
   232 
   233 \see QuotedStringReader
   234 
   235 \code
   236 reader.readNodeMap("x-coord", xCoordMap);
   237 reader.readNodeMap("y-coord", yCoordMap);
   238 
   239 reader.readNodeMap<QuotedStringReader>("label", labelMap);
   240 reader.skipNodeMap<QuotedStringReader>("description");
   241 
   242 reader.readNodeMap("color", colorMap);
   243 \endcode
   244 
   245 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
   246 member function you can give an edge map
   247 reading command similar to the NodeMaps. 
   248 
   249 \code
   250 reader.readEdgeMap("weight", weightMap);
   251 reader.readEdgeMap("label", labelMap);
   252 \endcode
   253 
   254 With \ref lemon::GraphReader::readNode() "readNode()"
   255 and \ref lemon::GraphReader::readEdge() "readEdge()"
   256 functions you can read labeled Nodes and
   257 Edges.
   258 
   259 \code
   260 reader.readNode("source", sourceNode);
   261 reader.readNode("target", targetNode);
   262 
   263 reader.readEdge("observed", edge);
   264 \endcode
   265 
   266 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
   267 function you can read an attribute from the file.
   268 
   269 \code
   270 std::string author;
   271 writer.readAttribute("author", author);
   272 int version;
   273 writer.writeAttribute("version", version);
   274 \endcode
   275 
   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.
   279 
   280 \code
   281 reader.run();
   282 \endcode
   283 
   284 \anchor rwbackground
   285 \section types Background of Reading and Writing
   286 
   287 
   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 
   295 whitespaces. 
   296 
   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.
   302 
   303 The reader has the next structure: 
   304 \code
   305 struct TypeReader {
   306   typedef TypeName Value;
   307 
   308   void read(std::istream& is, Value& value);
   309 };
   310 \endcode
   311 
   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
   314 struct.
   315 
   316 \code
   317 struct LengthReader {
   318   typedef int Value;
   319 
   320   void read(std::istream& is, Value& value) {
   321     std::string tmp;
   322     is >> tmp;
   323     value = tmp.length();
   324   }
   325 };
   326 ...
   327 reader.readNodeMap<LengthReader>("strings", lengthMap);
   328 \endcode  
   329 
   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.
   335 
   336 The specialization of writing is very similar to that of reading.
   337 
   338 \section u Undirected graphs
   339 
   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
   344 values of the map.
   345 
   346 The format handles directed edge maps as a syntactical sugar???, if there
   347 are two maps with names being the same with a \c '+' and a \c '-' prefix
   348 then this will be read as a directed map.
   349 
   350 \code
   351 @uedgeset
   352              label      capacity        +flow   -flow
   353 32   2       1          4.3             2.0     0.0
   354 21   21      5          2.6             0.0     2.6
   355 21   12      8          3.4             0.0     0.0
   356 \endcode
   357 
   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
   361 of the edge. 
   362 
   363 \code
   364 @uedges
   365 uedge 1
   366 +edge 5
   367 -back 5
   368 \endcode
   369 
   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".
   375 
   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, 
   380 
   381 \code
   382 reader.readUEdgeMap("capacity", capacityMap);
   383 reader.readEdgeMap("flow", flowMap);
   384 ...
   385 reader.readUEdge("u_edge", u_edge);
   386 reader.readEdge("edge", edge);
   387 \endcode
   388 
   389 \section advanced Advanced features
   390 
   391 The graph reader and writer classes give an easy way to read and write
   392 graphs. But sometimes we want more advanced features. In this case we can
   393 use the more general <tt>lemon reader and writer</tt> interface.
   394 
   395 The LEMON file format is a section oriented file format. It contains one or
   396 more sections, each starting with a line identifying its type 
   397 (the word starting with the \c \@  character).
   398 The content of the section this way cannot contain line with \c \@ first
   399 character. The file may contains comment lines with \c # first character.
   400 
   401 The \ref lemon::LemonReader "LemonReader"
   402 and \ref lemon::LemonWriter "LemonWriter"
   403 gives a framework to read and
   404 write sections. There are various section reader and section writer
   405 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
   406 or a \ref lemon::LemonWriter "LemonWriter".
   407 
   408 There are default section readers and writers for reading and writing
   409 item sets, and labeled items in the graph. These read and write
   410 the format described above. Other type of data can be handled with own
   411 section reader and writer classes which are inherited from the
   412 \c LemonReader::SectionReader or the
   413 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
   414 classes.
   415 
   416 The next example defines a special section reader which reads the
   417 \c \@description sections into a string:
   418 
   419 \code 
   420 class DescriptionReader : LemonReader::SectionReader {
   421 protected:
   422   virtual bool header(const std::string& line) {
   423     std::istringstream ls(line);
   424     std::string head;
   425     ls >> head;
   426     return head == "@description";
   427   }
   428 
   429   virtual void read(std::istream& is) {
   430     std::string line;
   431     while (getline(is, line)) {
   432       desc += line;
   433     }
   434   }
   435 public:
   436 
   437   typedef LemonReader::SectionReader Parent;
   438   
   439   DescriptionReader(LemonReader& reader) : Parent(reader) {}
   440 
   441   const std::string& description() const {
   442     return description;
   443   }
   444 
   445 private:
   446   std::string desc;
   447 };
   448 \endcode
   449 
   450 The other advanced stuff of the generalized file format is that 
   451 multiple edgesets can be stored to the same nodeset. It can be used 
   452 for example as a network traffic matrix.
   453 
   454 In our example there is a network with symmetric links and there are assymetric
   455 traffic request on the network. This construction can be stored in an
   456 undirected graph and in a directed \c ListEdgeSet class. The example
   457 shows the input with the \ref lemon::LemonReader "LemonReader" class:
   458 
   459 \code
   460 ListUGraph network;
   461 ListUGraph::UEdgeMap<double> capacity;
   462 ListEdgeSet<ListUGraph> traffic(network);
   463 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
   464 
   465 LemonReader reader(std::cin);
   466 NodeSetReader<ListUGraph> nodesetReader(reader, network);
   467 UEdgeSetReader<ListUGraph> 
   468   uEdgesetReader(reader, network, nodesetReader);
   469 uEdgesetReader.readEdgeMap("capacity", capacity);
   470 EdgeSetReader<ListEdgeSet<ListUGraph> > 
   471   edgesetReader(reader, traffic, nodesetReader, "traffic");
   472 edgesetReader.readEdgeMap("request", request);
   473 
   474 reader.run();
   475 \endcode
   476 
   477 Because both the \ref lemon::GraphReader "GraphReader"
   478 and the \ref lemon::UGraphReader "UGraphReader" can be converted
   479 to \ref lemon::LemonReader "LemonReader"
   480 and it can resolve the label's of the items, the previous
   481 result can be achived with the \ref lemon::UGraphReader "UGraphReader"
   482 class, too.
   483 
   484 
   485 \code
   486 ListUGraph network;
   487 ListUGraph::UEdgeSet<double> capacity;
   488 ListEdgeSet<ListUGraph> traffic(network);
   489 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
   490 
   491 UGraphReader<ListUGraph> reader(std::cin, network);
   492 reader.readEdgeMap("capacity", capacity);
   493 EdgeSetReader<ListEdgeSet<ListUGraph> > 
   494   edgesetReader(reader, traffic, reader, "traffic");
   495 edgesetReader.readEdgeMap("request", request);
   496 
   497 reader.run();
   498 \endcode
   499 
   500 \author Balazs Dezso
   501 */
   502 }