doc/graph_io.dox
author deba
Tue, 31 Oct 2006 14:27:58 +0000
changeset 2282 9d7b12f83daa
parent 1959 264811b995f3
child 2391 14a343be7a5a
permissions -rw-r--r--
Bug fixes
     1 namespace lemon {
     2 /*!
     3 
     4 
     5 \page graph-io-page Graph Input-Output
     6 
     7 The standard graph IO enables one to store graphs and additional maps
     8 (i.e. functions on the nodes or edges) in a flexible and efficient way. 
     9 Before you read this page you should be familiar with LEMON 
    10 \ref graphs "graphs" and \ref maps-page "maps".
    11 
    12 \section format The general file format
    13 
    14 The file contains sections in the following order:
    15 
    16 \li nodeset
    17 \li edgeset
    18 \li nodes
    19 \li edges
    20 \li attributes
    21 
    22 Some of these sections can be omitted, but you will basicly need the nodeset
    23 section (unless your graph has no nodes at all) and the edgeset section
    24 (unless your graph has no edges at all). 
    25 
    26 The nodeset section describes the nodes of your graph: it identifies the nodes
    27 and gives the maps defined on them, if any. It starts with the
    28 following line:
    29 
    30 <tt>\@nodeset</tt>
    31 
    32 The next line contains the names of the nodemaps, separated by whitespaces.  Each
    33 following line describes a node in the graph: it contains the values of the
    34 maps in the right order. The map named "label" should contain unique values
    35 because it is regarded as a label map. These labels need not be numbers but they
    36 must identify the nodes uniquely for later reference. For example:
    37 
    38 \code
    39 @nodeset
    40 label  x-coord  y-coord  color
    41 3   1.0      4.0      blue
    42 5   2.3      5.7      red
    43 12  7.8      2.3      green
    44 \endcode
    45 
    46 The edgeset section is very similar to the nodeset section, it has
    47 the same coloumn oriented structure. It starts with the line 
    48 
    49 <tt>\@edgeset</tt>
    50 
    51 The next line contains the whitespace separated list of names of the edge
    52 maps.  Each of the next lines describes one edge. The first two elements in
    53 the line are the labels of the source and target (or tail and head) nodes of the
    54 edge as they occur in the label node map of the nodeset section. You can also
    55 have an optional label map on the edges for later reference (which has to be
    56 unique in this case).
    57 
    58 \code
    59 @edgeset
    60              label      weight   note
    61 3   5        a          4.3      a-edge
    62 5   12       c          2.6      c-edge
    63 3   12       g          3.4      g-edge
    64 \endcode
    65 
    66 The \e nodes section contains <em>labeled (distinguished) nodes</em> 
    67 (i.e. nodes having a special
    68 label on them). The section starts with
    69 
    70 <tt> \@nodes </tt>
    71 
    72 Each of the next lines contains a label for a node in the graph 
    73 and then the label as described in the \e nodeset section.
    74 
    75 \code
    76 @nodes 
    77 source 3
    78 target 12
    79 \endcode
    80 
    81 The last section describes the <em>labeled (distinguished) edges</em>
    82 (i.e. edges having a special label on them). It starts with \c \@edges
    83 and then each line contains the name of the edge and the label.
    84 
    85 \code
    86 @edges 
    87 observed c
    88 \endcode
    89 
    90 
    91 The file may contain empty lines and comment lines. The comment lines
    92 start with an \c # character.
    93 
    94 The attributes section can handle some information about the graph. It
    95 contains key-value pairs in each line (a key and the mapped value to key). The
    96 key should be a string without whitespaces, the value can be of various types.
    97 
    98 \code
    99 @attributes
   100 title "Four colored planar graph"
   101 author "Balazs DEZSO"
   102 copyright "Lemon Library"
   103 version 12
   104 \endcode
   105 
   106 Finally, the file should be closed with \c \@end line.
   107 
   108 
   109 \section use Using graph input-output
   110 
   111 
   112 The graph input and output is based on <em> reading and writing
   113 commands</em>. The user gives reading and writing commands to the reader or
   114 writer class, then he calls the \c run() method that executes all the given
   115 commands.
   116 
   117 \subsection write Writing a graph
   118 
   119 The \ref lemon::GraphWriter "GraphWriter" template class
   120 provides the graph output. To write a graph
   121 you should first give writing commands to the writer. You can declare
   122 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
   123 Edge writing.
   124 
   125 \code
   126 GraphWriter<ListGraph> writer(std::cout, graph);
   127 \endcode
   128 
   129 The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
   130 function declares a \c NodeMap writing command in the
   131 \ref lemon::GraphWriter "GraphWriter".
   132 You should give a name to the map and the map
   133 object as parameters. The NodeMap writing command with name "label" should write a 
   134 unique map because it will be regarded as a label map.
   135 
   136 \see IdMap, DescriptorMap  
   137 
   138 \code
   139 IdMap<ListGraph, Node> nodeLabelMap;
   140 writer.writeNodeMap("label", nodeLabelMap);
   141 
   142 writer.writeNodeMap("x-coord", xCoordMap);
   143 writer.writeNodeMap("y-coord", yCoordMap);
   144 writer.writeNodeMap("color", colorMap);
   145 \endcode
   146 
   147 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
   148 member function you can give an edge map
   149 writing command similar to the NodeMaps.
   150 
   151 \see IdMap, DescriptorMap  
   152 
   153 \code
   154 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
   155 writer.writeEdgeMap("descriptor", edgeDescMap);
   156 
   157 writer.writeEdgeMap("weight", weightMap);
   158 writer.writeEdgeMap("note", noteMap);
   159 \endcode
   160 
   161 With \ref lemon::GraphWriter::writeNode() "writeNode()"
   162 and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
   163 functions you can designate Nodes and
   164 Edges in the graph. For example, you can write out the source and target node
   165 of a maximum flow instance.
   166 
   167 \code
   168 writer.writeNode("source", sourceNode);
   169 writer.writeNode("target", targetNode);
   170 
   171 writer.writeEdge("observed", edge);
   172 \endcode
   173 
   174 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
   175 function you can write an attribute to the file.
   176 
   177 \code
   178 writer.writeAttribute("author", "Balazs DEZSO");
   179 writer.writeAttribute("version", 12);
   180 \endcode
   181 
   182 After you give all write commands you must call the
   183 \ref lemon::GraphWriter::run() "run()" member
   184 function, which executes all the writing commands.
   185 
   186 \code
   187 writer.run();
   188 \endcode
   189 
   190 \subsection reading Reading a graph
   191 
   192 The file to be read may contain several maps and labeled nodes or edges.
   193 If you read a graph you need not read all the maps and items just those
   194 that you need. The interface of the \ref lemon::GraphReader "GraphReader"
   195 is very similar to
   196 the \ref lemon::GraphWriter "GraphWriter"
   197 but the reading method does not depend on the order of the
   198 given commands.
   199 
   200 The reader object assumes that each not read value does not contain 
   201 whitespaces, therefore it has some extra possibilities to control how
   202 it should skip the values when the string representation contains spaces.
   203 
   204 \code
   205 GraphReader<ListGraph> reader(std::cin, graph);
   206 \endcode
   207 
   208 The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
   209 function reads a map from the \c nodeset section.
   210 If there is a map that you do not want to read from the file and there are
   211 whitespaces in the string represenation of the values then you should
   212 call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
   213 template member function with proper parameters.
   214 
   215 \see QuotedStringReader
   216 
   217 \code
   218 reader.readNodeMap("x-coord", xCoordMap);
   219 reader.readNodeMap("y-coord", yCoordMap);
   220 
   221 reader.readNodeMap<QuotedStringReader>("label", labelMap);
   222 reader.skipNodeMap<QuotedStringReader>("description");
   223 
   224 reader.readNodeMap("color", colorMap);
   225 \endcode
   226 
   227 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
   228 member function you can give an edge map
   229 reading command similar to the NodeMaps. 
   230 
   231 \code
   232 reader.readEdgeMap("weight", weightMap);
   233 reader.readEdgeMap("label", labelMap);
   234 \endcode
   235 
   236 With \ref lemon::GraphReader::readNode() "readNode()"
   237 and \ref lemon::GraphReader::readEdge() "readEdge()"
   238 functions you can read labeled Nodes and
   239 Edges.
   240 
   241 \code
   242 reader.readNode("source", sourceNode);
   243 reader.readNode("target", targetNode);
   244 
   245 reader.readEdge("observed", edge);
   246 \endcode
   247 
   248 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
   249 function you can read an attribute from the file.
   250 
   251 \code
   252 std::string author;
   253 writer.readAttribute("author", author);
   254 int version;
   255 writer.writeAttribute("version", version);
   256 \endcode
   257 
   258 After you give all read commands you must call the
   259 \ref lemon::GraphReader::run() "run()" member
   260 function, which executes all the commands.
   261 
   262 \code
   263 reader.run();
   264 \endcode
   265 
   266 \anchor rwbackground
   267 \section types Background of Reading and Writing
   268 
   269 
   270 To read a map (on the nodes or edges)
   271 the \ref lemon::GraphReader "GraphReader"
   272 should know how to read a Value from the given map.
   273 By the default implementation the input operator reads a value from
   274 the stream and the type of the read value is the value type of the given map.
   275 When the reader should skip a value in the stream, because you do not
   276 want to store it in a map, the reader skips a character sequence without 
   277 whitespaces. 
   278 
   279 If you want to change the functionality of the reader, you can use
   280 template parameters to specialize it. When you give a reading
   281 command for a map you can give a Reader type as template parameter.
   282 With this template parameter you can control how the Reader reads
   283 a value from the stream.
   284 
   285 The reader has the next structure: 
   286 \code
   287 struct TypeReader {
   288   typedef TypeName Value;
   289 
   290   void read(std::istream& is, Value& value);
   291 };
   292 \endcode
   293 
   294 For example, the \c "strings" nodemap contains strings and you do not need
   295 the value of the string just the length. Then you can implement an own Reader
   296 struct.
   297 
   298 \code
   299 struct LengthReader {
   300   typedef int Value;
   301 
   302   void read(std::istream& is, Value& value) {
   303     std::string tmp;
   304     is >> tmp;
   305     value = tmp.length();
   306   }
   307 };
   308 ...
   309 reader.readNodeMap<LengthReader>("strings", lengthMap);
   310 \endcode  
   311 
   312 The global functionality of the reader class can be changed by giving a
   313 special template parameter to the GraphReader class. By default, the
   314 template parameter is \c DefaultReaderTraits. A reader traits class 
   315 should provide a nested template class Reader for each type, and a 
   316 DefaultReader for skipping a value.
   317 
   318 The specialization of writing is very similar to that of reading.
   319 
   320 \section u Undirected graphs
   321 
   322 In a file describing an undirected graph (ugraph, for short) you find an
   323 \c uedgeset section instead of the \c edgeset section. The first line of
   324 the section describes the names of the maps on the undirected egdes and all
   325 next lines describe one undirected edge with the the incident nodes and the
   326 values of the map.
   327 
   328 The format handles directed edge maps as a syntactical sugar???, if there
   329 are two maps with names being the same with a \c '+' and a \c '-' prefix
   330 then this will be read as a directed map.
   331 
   332 \code
   333 @uedgeset
   334              label      capacity        +flow   -flow
   335 32   2       1          4.3             2.0     0.0
   336 21   21      5          2.6             0.0     2.6
   337 21   12      8          3.4             0.0     0.0
   338 \endcode
   339 
   340 The \c edges section is changed to \c uedges section. This section
   341 describes labeled edges and undirected edges. The directed edge label
   342 should start with a \c '+' or a \c '-' prefix to decide the direction
   343 of the edge. 
   344 
   345 \code
   346 @uedges
   347 uedge 1
   348 +edge 5
   349 -back 5
   350 \endcode
   351 
   352 There are similar classes to the \ref lemon::GraphReader "GraphReader" and
   353 \ref lemon::GraphWriter "GraphWriter" which
   354 handle the undirected graphs. These classes are
   355 the \ref lemon::UGraphReader "UGraphReader"
   356 and \ref lemon::UGraphWriter "UGraphWriter".
   357 
   358 The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
   359 function reads an undirected map and the
   360 \ref lemon::UGraphReader::readUEdge() "readUEdge()"
   361 reads an undirected edge from the file, 
   362 
   363 \code
   364 reader.readUEdgeMap("capacity", capacityMap);
   365 reader.readEdgeMap("flow", flowMap);
   366 ...
   367 reader.readUEdge("u_edge", u_edge);
   368 reader.readEdge("edge", edge);
   369 \endcode
   370 
   371 \section advanced Advanced features
   372 
   373 The graph reader and writer classes give an easy way to read and write
   374 graphs. But sometimes we want more advanced features. In this case we can
   375 use the more general <tt>lemon reader and writer</tt> interface.
   376 
   377 The LEMON file format is a section oriented file format. It contains one or
   378 more sections, each starting with a line identifying its type 
   379 (the word starting with the \c \@  character).
   380 The content of the section this way cannot contain line with \c \@ first
   381 character. The file may contains comment lines with \c # first character.
   382 
   383 The \ref lemon::LemonReader "LemonReader"
   384 and \ref lemon::LemonWriter "LemonWriter"
   385 gives a framework to read and
   386 write sections. There are various section reader and section writer
   387 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
   388 or a \ref lemon::LemonWriter "LemonWriter".
   389 
   390 There are default section readers and writers for reading and writing
   391 item sets, and labeled items in the graph. These read and write
   392 the format described above. Other type of data can be handled with own
   393 section reader and writer classes which are inherited from the
   394 \c LemonReader::SectionReader or the
   395 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
   396 classes.
   397 
   398 The next example defines a special section reader which reads the
   399 \c \@description sections into a string:
   400 
   401 \code 
   402 class DescriptionReader : LemonReader::SectionReader {
   403 protected:
   404   virtual bool header(const std::string& line) {
   405     std::istringstream ls(line);
   406     std::string head;
   407     ls >> head;
   408     return head == "@description";
   409   }
   410 
   411   virtual void read(std::istream& is) {
   412     std::string line;
   413     while (getline(is, line)) {
   414       desc += line;
   415     }
   416   }
   417 public:
   418 
   419   typedef LemonReader::SectionReader Parent;
   420   
   421   DescriptionReader(LemonReader& reader) : Parent(reader) {}
   422 
   423   const std::string& description() const {
   424     return description;
   425   }
   426 
   427 private:
   428   std::string desc;
   429 };
   430 \endcode
   431 
   432 The other advanced stuff of the generalized file format is that 
   433 multiple edgesets can be stored to the same nodeset. It can be used 
   434 for example as a network traffic matrix.
   435 
   436 In our example there is a network with symmetric links and there are assymetric
   437 traffic request on the network. This construction can be stored in an
   438 undirected graph and in a directed \c ListEdgeSet class. The example
   439 shows the input with the \ref lemon::LemonReader "LemonReader" class:
   440 
   441 \code
   442 ListUGraph network;
   443 ListUGraph::UEdgeMap<double> capacity;
   444 ListEdgeSet<ListUGraph> traffic(network);
   445 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
   446 
   447 LemonReader reader(std::cin);
   448 NodeSetReader<ListUGraph> nodesetReader(reader, network);
   449 UEdgeSetReader<ListUGraph> 
   450   uEdgesetReader(reader, network, nodesetReader);
   451 uEdgesetReader.readEdgeMap("capacity", capacity);
   452 EdgeSetReader<ListEdgeSet<ListUGraph> > 
   453   edgesetReader(reader, traffic, nodesetReader, "traffic");
   454 edgesetReader.readEdgeMap("request", request);
   455 
   456 reader.run();
   457 \endcode
   458 
   459 Because both the \ref lemon::GraphReader "GraphReader"
   460 and the \ref lemon::UGraphReader "UGraphReader" can be converted
   461 to \ref lemon::LemonReader "LemonReader"
   462 and it can resolve the label's of the items, the previous
   463 result can be achived with the \ref lemon::UGraphReader "UGraphReader"
   464 class, too.
   465 
   466 
   467 \code
   468 ListUGraph network;
   469 ListUGraph::UEdgeSet<double> capacity;
   470 ListEdgeSet<ListUGraph> traffic(network);
   471 ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
   472 
   473 UGraphReader<ListUGraph> reader(std::cin, network);
   474 reader.readEdgeMap("capacity", capacity);
   475 EdgeSetReader<ListEdgeSet<ListUGraph> > 
   476   edgesetReader(reader, traffic, reader, "traffic");
   477 edgesetReader.readEdgeMap("request", request);
   478 
   479 reader.run();
   480 \endcode
   481 
   482 \author Balazs Dezso
   483 */
   484 }