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