doc/graph_io.dox
author alpar
Fri, 04 Nov 2005 15:48:06 +0000
changeset 1766 6c59b1386fe8
parent 1540 7d028a73d7f2
child 1788 614ce2dd3cba
permissions -rw-r--r--
Tons of todos have been removed.
     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 "id" should contain unique values
    35 because it is regarded as an ID-map. These ids need not be numbers but they
    36 must identify the nodes uniquely for later reference. For example:
    37 
    38 \code
    39 @nodeset
    40 id  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 IDs of the source and target (or tail and head) nodes of the
    54 edge as they occur in the ID node map of the nodeset section. You can also
    55 have an optional ID map on the edges for later reference (which has to be
    56 unique in this case).
    57 
    58 \code
    59 @edgeset
    60              id    weight   label
    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 ID 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 ID.
    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 plan graph"
   101 author "Balazs DEZSO"
   102 copyright "Lemon Library"
   103 version 12
   104 \endcode
   105 
   106 <tt> \@end </tt>
   107 
   108 line.
   109 
   110 
   111 \section use Using graph input-output
   112 
   113 The easiest way of using graph input and output is using the versions of the
   114   public \ref readGraph() and \ref writeGraph() functions; if you don't need
   115   very sophisticated behaviour then you might be satisfied with
   116   those. Otherwise go on reading this page.
   117 
   118 The graph input and output is based on <em> reading and writing
   119 commands</em>. The user gives reading and writing commands to the reader or
   120 writer class, then he calls the \c run() method that executes all the given
   121 commands.
   122 
   123 \subsection write Writing a graph
   124 
   125 The \ref lemon::GraphWriter "GraphWriter" template class
   126 provides the graph output. To write a graph
   127 you should first give writing commands to the writer. You can declare
   128 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
   129 Edge writing.
   130 
   131 \code
   132 GraphWriter<ListGraph> writer(std::cout, graph);
   133 \endcode
   134 
   135 The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
   136 function declares a \c NodeMap writing command in the
   137 \ref lemon::GraphWriter "GraphWriter".
   138 You should give a name to the map and the map
   139 object as parameters. The NodeMap writing command with name "id" should write a 
   140 unique map because it will be regarded as an ID map.
   141 
   142 \see IdMap, DescriptorMap  
   143 
   144 \code
   145 IdMap<ListGraph, Node> nodeIdMap;
   146 writer.writeNodeMap("id", nodeIdMap);
   147 
   148 writer.writeNodeMap("x-coord", xCoordMap);
   149 writer.writeNodeMap("y-coord", yCoordMap);
   150 writer.writeNodeMap("color", colorMap);
   151 \endcode
   152 
   153 With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
   154 member function you can give an edge map
   155 writing command similar to the NodeMaps.
   156 
   157 \see IdMap, DescriptorMap  
   158 
   159 \code
   160 DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
   161 writer.writeEdgeMap("descriptor", edgeDescMap);
   162 
   163 writer.writeEdgeMap("weight", weightMap);
   164 writer.writeEdgeMap("label", labelMap);
   165 \endcode
   166 
   167 With \ref lemon::GraphWriter::writeNode() "writeNode()"
   168 and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
   169 functions you can designate Nodes and
   170 Edges in the graph. For example, you can write out the source and target node
   171 of a maximum flow instance.
   172 
   173 \code
   174 writer.writeNode("source", sourceNode);
   175 writer.writeNode("target", targetNode);
   176 
   177 writer.writeEdge("observed", edge);
   178 \endcode
   179 
   180 With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
   181 function you can write an attribute to the file.
   182 
   183 \code
   184 writer.writeAttribute("author", "Balazs DEZSO");
   185 writer.writeAttribute("version", 12);
   186 \endcode
   187 
   188 After you give all write commands you must call the
   189 \ref lemon::GraphWriter::run() "run()" member
   190 function, which executes all the writing commands.
   191 
   192 \code
   193 writer.run();
   194 \endcode
   195 
   196 \subsection reading Reading a graph
   197 
   198 The file to be read may contain several maps and labeled nodes or edges.
   199 If you read a graph you need not read all the maps and items just those
   200 that you need. The interface of the \ref lemon::GraphReader "GraphReader"
   201 is very similar to
   202 the \ref lemon::GraphWriter "GraphWriter"
   203 but the reading method does not depend on the order of the
   204 given commands.
   205 
   206 The reader object assumes that each not readed value does not contain 
   207 whitespaces, therefore it has some extra possibilities to control how
   208 it should skip the values when the string representation contains spaces.
   209 
   210 \code
   211 GraphReader<ListGraph> reader(std::cin, graph);
   212 \endcode
   213 
   214 The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
   215 function reads a map from the \c nodeset section.
   216 If there is a map that you do not want to read from the file and there are
   217 whitespaces in the string represenation of the values then you should
   218 call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
   219 template member function with proper parameters.
   220 
   221 \see QuotedStringReader
   222 
   223 \code
   224 reader.readNodeMap("x-coord", xCoordMap);
   225 reader.readNodeMap("y-coord", yCoordMap);
   226 
   227 reader.readNodeMap<QuotedStringReader>("label", labelMap);
   228 reader.skipNodeMap<QuotedStringReader>("description");
   229 
   230 reader.readNodeMap("color", colorMap);
   231 \endcode
   232 
   233 With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
   234 member function you can give an edge map
   235 reading command similar to the NodeMaps. 
   236 
   237 \code
   238 reader.readEdgeMap("weight", weightMap);
   239 reader.readEdgeMap("label", labelMap);
   240 \endcode
   241 
   242 With \ref lemon::GraphReader::readNode() "readNode()"
   243 and \ref lemon::GraphReader::readEdge() "readEdge()"
   244 functions you can read labeled Nodes and
   245 Edges.
   246 
   247 \code
   248 reader.readNode("source", sourceNode);
   249 reader.readNode("target", targetNode);
   250 
   251 reader.readEdge("observed", edge);
   252 \endcode
   253 
   254 With \ref lemon::GraphReader::readAttribute() "readAttribute()"
   255 function you can read an attribute from the file.
   256 
   257 \code
   258 std::string author;
   259 writer.readAttribute("author", author);
   260 int version;
   261 writer.writeAttribute("version", version);
   262 \endcode
   263 
   264 After you give all read commands you must call the
   265 \ref lemon::GraphReader::run() "run()" member
   266 function, which executes all the commands.
   267 
   268 \code
   269 reader.run();
   270 \endcode
   271 
   272 \anchor rwbackground
   273 \section types Background of Reading and Writing
   274 
   275 
   276 To read a map (on the nodes or edges)
   277 the \ref lemon::GraphReader "GraphReader"
   278 should know how to read a Value from the given map.
   279 By the default implementation the input operator reads a value from
   280 the stream and the type of the readed value is the value type of the given map.
   281 When the reader should skip a value in the stream, because you do not
   282 want to store it in a map, the reader skips a character sequence without 
   283 whitespaces. 
   284 
   285 If you want to change the functionality of the reader, you can use
   286 template parameters to specialize it. When you give a reading
   287 command for a map you can give a Reader type as template parameter.
   288 With this template parameter you can control how the Reader reads
   289 a value from the stream.
   290 
   291 The reader has the next structure: 
   292 \code
   293 struct TypeReader {
   294   typedef TypeName Value;
   295 
   296   void read(std::istream& is, Value& value);
   297 };
   298 \endcode
   299 
   300 For example, the \c "strings" nodemap contains strings and you do not need
   301 the value of the string just the length. Then you can implement an own Reader
   302 struct.
   303 
   304 \code
   305 struct LengthReader {
   306   typedef int Value;
   307 
   308   void read(std::istream& is, Value& value) {
   309     std::string tmp;
   310     is >> tmp;
   311     value = tmp.length();
   312   }
   313 };
   314 ...
   315 reader.readNodeMap<LengthReader>("strings", lengthMap);
   316 \endcode  
   317 
   318 The global functionality of the reader class can be changed by giving a
   319 special template parameter to the GraphReader class. By default, the
   320 template parameter is \c DefaultReaderTraits. A reader traits class 
   321 should provide an inner template class Reader for each type, and a 
   322 DefaultReader for skipping a value.
   323 
   324 The specialization of  writing is very similar to that of reading.
   325 
   326 \section undir Undirected graphs
   327 
   328 In a file describing an undirected graph (undir graph, for short) you find an
   329 \c undiredgeset section instead of the \c edgeset section. The first line of
   330 the section describes the names of the maps on the undirected egdes and all
   331 next lines describe one undirected edge with the the incident nodes and the
   332 values of the map.
   333 
   334 The format handles directed edge maps as a syntactical sugar???, if there
   335 are two maps with names being the same with a \c '+' and a \c '-' prefix
   336 then this will be read as a directed map.
   337 
   338 \code
   339 @undiredgeset
   340              id    capacity +flow -flow
   341 32   2       1     4.3      2.0	  0.0
   342 21   21      5     2.6      0.0   2.6
   343 21   12      8     3.4      0.0   0.0
   344 \endcode
   345 
   346 The \c edges section is changed to \c undiredges section. This section
   347 describes labeled edges and undirected edges. The directed edge label
   348 should start with a \c '+' or a \c '-' prefix to decide the direction
   349 of the edge. 
   350 
   351 \code
   352 @undiredges
   353 undiredge 1
   354 +edge 5
   355 -back 5
   356 \endcode
   357 
   358 There are similar classes to the \ref lemon::GraphReader "GraphReader" and
   359 \ref lemon::GraphWriter "GraphWriter" which
   360 handle the undirected graphs. These classes are
   361 the \ref lemon::UndirGraphReader "UndirGraphReader"
   362 and \ref lemon::UndirGraphWriter "UndirGraphWriter".
   363 
   364 The \ref lemon::UndirGraphReader::readUndirMap() "readUndirMap()"
   365 function reads an undirected map and the
   366 \ref lemon::UndirGraphReader::readUndirEdge() "readUndirEdge()"
   367 reads an undirected edge from the file, 
   368 
   369 \code
   370 reader.readUndirEdgeMap("capacity", capacityMap);
   371 reader.readEdgeMap("flow", flowMap);
   372 ...
   373 reader.readUndirEdge("undir_edge", undir_edge);
   374 reader.readEdge("edge", edge);
   375 \endcode
   376 
   377 \section advanced Advanced features
   378 
   379 The graph reader and writer classes give an easy way to read and write
   380 graphs. But sometimes we want more advanced features. In this case we can
   381 use the more general <tt>lemon reader and writer</tt> interface.
   382 
   383 The LEMON file format is a section oriented file format. It contains one or
   384 more sections, each starting with a line identifying its type 
   385 (the word starting with the \c \@  character).
   386 The content of the section this way cannot contain line with \c \@ first
   387 character. The file may contains comment lines with \c # first character.
   388 
   389 The \ref lemon::LemonReader "LemonReader"
   390 and \ref lemon::LemonWriter "LemonWriter"
   391 gives a framework to read and
   392 write sections. There are various section reader and section writer
   393 classes which can be attached to a \ref lemon::LemonReader "LemonReader"
   394 or a \ref lemon::LemonWriter "LemonWriter".
   395 
   396 There are default section readers and writers for reading and writing
   397 item sets, and labeled items in the graph. These read and write
   398 the format described above. Other type of data can be handled with own
   399 section reader and writer classes which are inherited from the
   400 \c LemonReader::SectionReader or the
   401 \ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
   402 classes.
   403 
   404 The next example defines a special section reader which reads the
   405 \c \@description sections into a string:
   406 
   407 \code 
   408 class DescriptionReader : LemonReader::SectionReader {
   409 protected:
   410   virtual bool header(const std::string& line) {
   411     std::istringstream ls(line);
   412     std::string head;
   413     ls >> head;
   414     return head == "@description";
   415   }
   416 
   417   virtual void read(std::istream& is) {
   418     std::string line;
   419     while (getline(is, line)) {
   420       desc += line;
   421     }
   422   }
   423 public:
   424 
   425   typedef LemonReader::SectionReader Parent;
   426   
   427   DescriptionReader(LemonReader& reader) : Parent(reader) {}
   428 
   429   const std::string& description() const {
   430     return description;
   431   }
   432 
   433 private:
   434   std::string desc;
   435 };
   436 \endcode
   437 
   438 The other advanced stuff of the generalized file format is that 
   439 multiple edgesets can be stored to the same nodeset. It can be used 
   440 for example as a network traffic matrix.
   441 
   442 In our example there is a network with symmetric links and there are assymetric
   443 traffic request on the network. This construction can be stored in an
   444 undirected graph and in a directed \c NewEdgeSetAdaptor class. The example
   445 shows the input with the \ref lemon::LemonReader "LemonReader" class:
   446 
   447 \code
   448 UndirListGraph network;
   449 UndirListGraph::UndirEdgeSet<double> capacity;
   450 NewEdgeSetAdaptor<UndirListGraph> traffic(network);
   451 NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
   452 
   453 LemonReader reader(std::cin);
   454 NodeSetReader nodesetReader(reader, network);
   455 UndirEdgeSetReader undirEdgesetReader(reader, network, nodesetReader);
   456 undirEdgesetReader.readEdgeMap("capacity", capacity);
   457 EdgeSetReader edgesetReader(reader, traffic, nodesetReader);
   458 edgesetReader.readEdgeMap("request", request);
   459 
   460 reader.run();
   461 \endcode
   462 
   463 Because both the \ref lemon::GraphReader "GraphReader"
   464 and the \ref lemon::UndirGraphReader "UndirGraphReader" can be converted
   465 to \ref lemon::LemonReader "LemonReader"
   466 and it can resolve the ID's of the items, the previous
   467 result can be achived with the \ref lemon::UndirGraphReader "UndirGraphReader"
   468 class, too.
   469 
   470 
   471 \code
   472 UndirListGraph network;
   473 UndirListGraph::UndirEdgeSet<double> capacity;
   474 NewEdgeSetAdaptor<UndirListGraph> traffic(network);
   475 NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
   476 
   477 UndirGraphReader reader(std::cin, network);
   478 reader.readEdgeMap("capacity", capacity);
   479 EdgeSetReader edgesetReader(reader, traffic, reader);
   480 edgesetReader.readEdgeMap("request", request);
   481 
   482 reader.run();
   483 \endcode
   484 
   485 \author Balazs Dezso
   486 */
   487 }