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