doc/graph_io.dox
author alpar
Fri, 08 Feb 2008 10:18:55 +0000
changeset 2568 046c055217f6
parent 2502 9c23c3762bc5
permissions -rw-r--r--
Math constants + configure bugfix backported
from hg a315a588a20d and 761622e5ed4c
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     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 undir Undirected and Bipartite 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 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.
   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 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.
   397 
   398 \code
   399 @bpnodeset
   400 &anodeset label   coords	radius
   401 	  0       (0, 0)	14.0
   402 	  1       (0, 1)	12.0
   403 &bnodeset label	  coords
   404 	  2       (1, 0)
   405 	  3       (1, 1)
   406 \endcode
   407 
   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.
   412 
   413 \code
   414 reader.readNodeMap("coords", coords);
   415 reader.readAnodeMap("radius", radius);
   416 \endcode
   417 
   418 \section advanced Advanced features
   419 
   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.
   423 
   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.
   429 
   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".
   436 
   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"
   443 classes.
   444 
   445 The next example defines a special section reader which reads the
   446 \c \@description sections into a string:
   447 
   448 \code 
   449 class DescriptionReader : LemonReader::SectionReader {
   450 protected:
   451   virtual bool header(const std::string& line) {
   452     std::istringstream ls(line);
   453     std::string head;
   454     ls >> head;
   455     return head == "@description";
   456   }
   457 
   458   virtual void read(std::istream& is) {
   459     std::string line;
   460     while (getline(is, line)) {
   461       desc += line;
   462     }
   463   }
   464 public:
   465 
   466   typedef LemonReader::SectionReader Parent;
   467   
   468   DescriptionReader(LemonReader& reader) : Parent(reader) {}
   469 
   470   const std::string& description() const {
   471     return description;
   472   }
   473 
   474 private:
   475   std::string desc;
   476 };
   477 \endcode
   478 
   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.
   482 
   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:
   487 
   488 \code
   489 ListUGraph network;
   490 ListUGraph::UEdgeMap<double> capacity;
   491 ListEdgeSet<ListUGraph> traffic(network);
   492 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
   493 
   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);
   502 
   503 reader.run();
   504 \endcode
   505 
   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"
   511 class, too.
   512 
   513 
   514 \code
   515 ListUGraph network;
   516 ListUGraph::UEdgeSet<double> capacity;
   517 ListEdgeSet<ListUGraph> traffic(network);
   518 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
   519 
   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);
   525 
   526 reader.run();
   527 \endcode
   528 
   529 \author Balazs Dezso
   530 */
   531 }