doc/graph_io.dox
changeset 1582 5fd89def7cbc
parent 1532 aa7428d22aaf
child 1631 e15162d8eca1
equal deleted inserted replaced
7:251784438baa 8:336dfe133429
     2 /*!
     2 /*!
     3 
     3 
     4 
     4 
     5 \page graph-io-page Graph Input-Output
     5 \page graph-io-page Graph Input-Output
     6 
     6 
     7 The standard graph IO enables to store graphs and additional maps
     7 The standard graph IO enables one to store graphs and additional maps
     8 in a flexible and efficient way. 
     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".
     9 
    11 
    10 \section format The general file format
    12 \section format The general file format
    11 
    13 
    12 The file contains sections in the following order:
    14 The file contains sections in the following order:
    13 
    15 
    15 \li edgeset
    17 \li edgeset
    16 \li nodes
    18 \li nodes
    17 \li edges
    19 \li edges
    18 \li attributes
    20 \li attributes
    19 
    21 
    20 The nodeset section starts with the following line:
    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:
    21 
    29 
    22 <tt>\@nodeset</tt>
    30 <tt>\@nodeset</tt>
    23 
    31 
    24 The next line contains the names of the nodemaps, separated by whitespaces.  Each
    32 The next line contains the names of the nodemaps, separated by whitespaces.  Each
    25 following line describes a node in the graph: it contains the values of the
    33 following line describes a node in the graph: it contains the values of the
    26 maps in the right order. The map named "id" should contain unique values
    34 maps in the right order. The map named "id" should contain unique values
    27 because it is regarded as an ID-map. For example:
    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:
    28 
    37 
    29 \code
    38 \code
    30 @nodeset
    39 @nodeset
    31 id  x-coord  y-coord  color
    40 id  x-coord  y-coord  color
    32 3   1.0      4.0      blue
    41 3   1.0      4.0      blue
    37 The edgeset section is very similar to the nodeset section, it has
    46 The edgeset section is very similar to the nodeset section, it has
    38 the same coloumn oriented structure. It starts with the line 
    47 the same coloumn oriented structure. It starts with the line 
    39 
    48 
    40 <tt>\@edgeset</tt>
    49 <tt>\@edgeset</tt>
    41 
    50 
    42 The next line contains the whitespace separated list of names of the maps.
    51 The next line contains the whitespace separated list of names of the edge
    43 Each of the next lines describes one edge. The first two elements in the line
    52 maps.  Each of the next lines describes one edge. The first two elements in
    44 are the IDs of the source and target (or tail and head) node of the edge as they occur in the ID node
    53 the line are the IDs of the source and target (or tail and head) nodes of the
    45 map. You can also have an optional ID map on the edges for later reference.
    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).
    46 
    57 
    47 \code
    58 \code
    48 @edgeset
    59 @edgeset
    49              id    weight   label
    60              id    weight   label
    50 3   5        a     4.3      a-edge
    61 3   5        a     4.3      a-edge
    51 5   12       c     2.6      c-edge
    62 5   12       c     2.6      c-edge
    52 3   12       g     3.4      g-edge
    63 3   12       g     3.4      g-edge
    53 \endcode
    64 \endcode
    54 
    65 
    55 The next section contains <em>labeled nodes</em> (i.e. nodes having a special
    66 The \e nodes section contains <em>labeled (distinguished) nodes</em> 
       
    67 (i.e. nodes having a special
    56 label on them). The section starts with
    68 label on them). The section starts with
    57 
    69 
    58 <tt> \@nodes </tt>
    70 <tt> \@nodes </tt>
    59 
    71 
    60 Each of the next lines contains a label for a node in the graph 
    72 Each of the next lines contains a label for a node in the graph 
    61 and then the ID described in the nodeset section.
    73 and then the ID as described in the \e nodeset section.
    62 
    74 
    63 \code
    75 \code
    64 @nodes 
    76 @nodes 
    65 source 3
    77 source 3
    66 target 12
    78 target 12
    67 \endcode
    79 \endcode
    68 
    80 
    69 The last section describes the <em>labeled edges</em>
    81 The last section describes the <em>labeled (distinguished) edges</em>
    70 (i.e. edges having a special label on them). It starts with \c \@edges
    82 (i.e. edges having a special label on them). It starts with \c \@edges
    71 and then each line contains the name of the edge and the ID.
    83 and then each line contains the name of the edge and the ID.
    72 
    84 
    73 \code
    85 \code
    74 @nodes 
    86 @edges 
    75 observed c
    87 observed c
    76 \endcode
    88 \endcode
    77 
    89 
    78 
    90 
    79 The file may contain empty lines and comment lines. The comment lines
    91 The file may contain empty lines and comment lines. The comment lines
    80 start with an \c # character.
    92 start with an \c # character.
    81 
    93 
    82 The attributes section can handle some information about the graph. It
    94 The attributes section can handle some information about the graph. It
    83 contains in each line an key and the mapped value to key. The key should
    95 contains key-value pairs in each line (a key and the mapped value to key). The
    84 be a string without whitespace, the value can be from various type.
    96 key should be a string without whitespaces, the value can be of various types.
    85 
    97 
    86 \code
    98 \code
    87 @attributes
    99 @attributes
    88 title "Four colored plan graph"
   100 title "Four colored plan graph"
    89 author "Balazs DEZSO"
   101 author "Balazs DEZSO"
    90 copyright "Lemon Library"
   102 copyright "Lemon Library"
    91 version 12
   103 version 12
    92 \endcode
   104 \endcode
    93 
   105 
    94 \code
       
    95 @end
       
    96 \endcode
       
    97 =======
       
    98 The file ends with the 
       
    99 
       
   100 <tt> \@end </tt>
   106 <tt> \@end </tt>
   101 
   107 
   102 line.
   108 line.
   103 
   109 
   104 
   110 
   105 \section use Using graph input-output
   111 \section use Using graph input-output
   106 The graph input and output is based on reading and writing  commands. The user
   112 
   107 adds reading and writing commands to the reader or writer class, then he
   113 The easiest way of using graph input and output is using the versions of the
   108 calls the \c run() method that executes all the given commands.
   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.
   109 
   122 
   110 \subsection write Writing a graph
   123 \subsection write Writing a graph
   111 
   124 
   112 The \c GraphWriter class provides the graph output. To write a graph
   125 The \c GraphWriter class provides the graph output. To write a graph
   113 you should first give writing commands to the writer. You can declare
   126 you should first give writing commands to the writer. You can declare
   114 write command as \c NodeMap or \c EdgeMap writing and labeled Node and
   127 writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
   115 Edge writing.
   128 Edge writing.
   116 
   129 
   117 \code
   130 \code
   118 GraphWriter<ListGraph> writer(std::cout, graph);
   131 GraphWriter<ListGraph> writer(std::cout, graph);
   119 \endcode
   132 \endcode
   120 
   133 
   121 The \c writeNodeMap() function declares a \c NodeMap writing command in the
   134 The \c writeNodeMap() function declares a \c NodeMap writing command in the
   122 \c GraphWriter. You should give a name of the map and the map
   135 \c GraphWriter. You should give a name to the map and the map
   123 object as parameters. The NodeMap writing command with name "id" should write a 
   136 object as parameters. The NodeMap writing command with name "id" should write a 
   124 unique map because it is regarded as ID map.
   137 unique map because it will be regarded as an ID map.
   125 
   138 
   126 \see IdMap, DescriptorMap  
   139 \see IdMap, DescriptorMap  
   127 
   140 
   128 \code
   141 \code
   129 IdMap<ListGraph, Node> nodeIdMap;
   142 IdMap<ListGraph, Node> nodeIdMap;
   172 writer.run();
   185 writer.run();
   173 \endcode
   186 \endcode
   174 
   187 
   175 \subsection reading Reading a graph
   188 \subsection reading Reading a graph
   176 
   189 
   177 The given file format may contain several maps and labeled nodes or edges.
   190 The file to be read may contain several maps and labeled nodes or edges.
   178 If you read a graph you need not read all the maps and items just those
   191 If you read a graph you need not read all the maps and items just those
   179 that you need. The interface of the \c GraphReader is very similar to
   192 that you need. The interface of the \c GraphReader is very similar to
   180 the GraphWriter but the reading method does not depend on the order of the
   193 the GraphWriter but the reading method does not depend on the order of the
   181 given commands.
   194 given commands.
   182 
   195 
   186 
   199 
   187 \code
   200 \code
   188 GraphReader<ListGraph> reader(std::cin, graph);
   201 GraphReader<ListGraph> reader(std::cin, graph);
   189 \endcode
   202 \endcode
   190 
   203 
   191 The \c readNodeMap() function reads a map from the \c \@nodeset section.
   204 The \c readNodeMap() function reads a map from the \c nodeset section.
   192 If there is a map that you do not want to read from the file and there are
   205 If there is a map that you do not want to read from the file and there are
   193 whitespaces in the string represenation of the values then you should
   206 whitespaces in the string represenation of the values then you should
   194 call the \c skipNodeMap() template member function with proper parameters.
   207 call the \c skipNodeMap() template member function with proper parameters.
   195 
   208 
   196 \see QuotedStringReader
   209 \see QuotedStringReader
   237 
   250 
   238 \code
   251 \code
   239 reader.run();
   252 reader.run();
   240 \endcode
   253 \endcode
   241 
   254 
       
   255 \anchor rwbackground
   242 \section types Background of Reading and Writing
   256 \section types Background of Reading and Writing
       
   257 
       
   258 
   243 To read a map (on the nodes or edges)
   259 To read a map (on the nodes or edges)
   244 the \c GraphReader should know how to read a Value from the given map.
   260 the \c GraphReader should know how to read a Value from the given map.
   245 By the default implementation the input operator reads a value from
   261 By the default implementation the input operator reads a value from
   246 the stream and the type of the readed value is the value type of the given map.
   262 the stream and the type of the readed value is the value type of the given map.
   247 When the reader should skip a value in the stream, because you do not
   263 When the reader should skip a value in the stream, because you do not
   248 want to store it in a map, the reader skips a character sequence without 
   264 want to store it in a map, the reader skips a character sequence without 
   249 whitespace. 
   265 whitespaces. 
   250 
   266 
   251 If you want to change the functionality of the reader, you can use
   267 If you want to change the functionality of the reader, you can use
   252 template parameters to specialize it. When you give a reading
   268 template parameters to specialize it. When you give a reading
   253 command for a map you can give a Reader type as template parameter.
   269 command for a map you can give a Reader type as template parameter.
   254 With this template parameter you can control how the Reader reads
   270 With this template parameter you can control how the Reader reads
   262   void read(std::istream& is, Value& value);
   278   void read(std::istream& is, Value& value);
   263 };
   279 };
   264 \endcode
   280 \endcode
   265 
   281 
   266 For example, the \c "strings" nodemap contains strings and you do not need
   282 For example, the \c "strings" nodemap contains strings and you do not need
   267 the value of the string just the length. Then you can implement own Reader
   283 the value of the string just the length. Then you can implement an own Reader
   268 struct.
   284 struct.
   269 
   285 
   270 \code
   286 \code
   271 struct LengthReader {
   287 struct LengthReader {
   272   typedef int Value;
   288   typedef int Value;
   282 \endcode  
   298 \endcode  
   283 
   299 
   284 The global functionality of the reader class can be changed by giving a
   300 The global functionality of the reader class can be changed by giving a
   285 special template parameter to the GraphReader class. By default, the
   301 special template parameter to the GraphReader class. By default, the
   286 template parameter is \c DefaultReaderTraits. A reader traits class 
   302 template parameter is \c DefaultReaderTraits. A reader traits class 
   287 should provide an inner template class Reader for each type, and an 
   303 should provide an inner template class Reader for each type, and a 
   288 DefaultReader for skipping a value.
   304 DefaultReader for skipping a value.
   289 
   305 
   290 The specialization of  writing should be very similar to that of reading.
   306 The specialization of  writing is very similar to that of reading.
   291 
   307 
   292 \section undir Undir graphs
   308 \section undir Undirected graphs
   293 
   309 
   294 In the undir graph format there is an \c undiredgeset section instead of
   310 In a file describing an undirected graph (undir graph, for short) you find an
   295 the \c edgeset section. The first line of the section describes the 
   311 \c undiredgeset section instead of the \c edgeset section. The first line of
   296 undirected egdes' names and all next lines describes one undirected edge
   312 the section describes the names of the maps on the undirected egdes and all
   297 with the the incident nodes and the values of the map.
   313 next lines describe one undirected edge with the the incident nodes and the
   298 
   314 values of the map.
   299 The format handles the directed edge maps as a syntactical sugar, if there
   315 
   300 is two map which names are the same with a \c '+' and a \c '-' prefix
   316 The format handles directed edge maps as a syntactical sugar???, if there
   301 then it can be read as an directed map.
   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.
   302 
   319 
   303 \code
   320 \code
   304 @undiredgeset
   321 @undiredgeset
   305              id    capacity +flow -flow
   322              id    capacity +flow -flow
   306 32   2       1     4.3      2.0	  0.0
   323 32   2       1     4.3      2.0	  0.0
   307 21   21      5     2.6      0.0   2.6
   324 21   21      5     2.6      0.0   2.6
   308 21   12      8     3.4      0.0   0.0
   325 21   12      8     3.4      0.0   0.0
   309 \endcode
   326 \endcode
   310 
   327 
   311 The \c edges section changed to \c undiredges section. This section
   328 The \c edges section is changed to \c undiredges section. This section
   312 describes labeled edges and undirected edges. The directed edge label
   329 describes labeled edges and undirected edges. The directed edge label
   313 should start with a \c '+' and a \c '-' prefix what decide the direction
   330 should start with a \c '+' or a \c '-' prefix to decide the direction
   314 of the edge. 
   331 of the edge. 
   315 
   332 
   316 \code
   333 \code
   317 @undiredges
   334 @undiredges
   318 undiredge 1
   335 undiredge 1
   335 reader.readEdge("edge", edge);
   352 reader.readEdge("edge", edge);
   336 \endcode
   353 \endcode
   337 
   354 
   338 \section advanced Advanced features
   355 \section advanced Advanced features
   339 
   356 
   340 The graph reader and writer classes gives an easy way to read and write
   357 The graph reader and writer classes give an easy way to read and write
   341 graphs. But sometimes we want more advanced features. This way we can
   358 graphs. But sometimes we want more advanced features. In this case we can
   342 use the more general lemon reader and writer interface.
   359 use the more general <tt>lemon reader and writer</tt> interface.
   343 
   360 
   344 The lemon format is an section oriented file format. It contains one or
   361 The LEMON file format is a section oriented file format. It contains one or
   345 more section, each starts with a line with \c \@ first character.
   362 more sections, each starting with a line identifying its type 
       
   363 (the word starting with the \c \@  character).
   346 The content of the section this way cannot contain line with \c \@ first
   364 The content of the section this way cannot contain line with \c \@ first
   347 character. The file may contains comment lines with \c # first character.
   365 character. The file may contains comment lines with \c # first character.
   348 
   366 
   349 The \c LemonReader and \c LemonWriter gives a framework to read and
   367 The \c LemonReader and \c LemonWriter gives a framework to read and
   350 write sections. There are various section reader and section writer
   368 write sections. There are various section reader and section writer
   351 classes which can be attached to a \c LemonReader or a \c LemonWriter.
   369 classes which can be attached to a \c LemonReader or a \c LemonWriter.
   352 
   370 
   353 There are default section readers and writers for reading and writing
   371 There are default section readers and writers for reading and writing
   354 item sets, and labeled items in the graph. These reads and writes
   372 item sets, and labeled items in the graph. These read and write
   355 the format described above. Other type of data can be handled with own
   373 the format described above. Other type of data can be handled with own
   356 section reader and writer classes which are inherited from the
   374 section reader and writer classes which are inherited from the
   357 \c LemonReader::SectionReader or the \c LemonWriter::SectionWriter classes.
   375 \c LemonReader::SectionReader or the \c LemonWriter::SectionWriter classes.
   358 
   376 
   359 The next example defines a special section reader which reads the
   377 The next example defines a special section reader which reads the
   390 };
   408 };
   391 \endcode
   409 \endcode
   392 
   410 
   393 The other advanced stuff of the generalized file format is that 
   411 The other advanced stuff of the generalized file format is that 
   394 multiple edgesets can be stored to the same nodeset. It can be used 
   412 multiple edgesets can be stored to the same nodeset. It can be used 
   395 by example as a network traffic matrix.
   413 for example as a network traffic matrix.
   396 
   414 
   397 In example there is a network with symmetric links and there are assymetric
   415 In our example there is a network with symmetric links and there are assymetric
   398 traffic request on the network. This construction can be stored in an
   416 traffic request on the network. This construction can be stored in an
   399 undirected graph and in an directed NewEdgeSetAdaptor class. The example
   417 undirected graph and in a directed NewEdgeSetAdaptor class. The example
   400 shows the input with the LemonReader class:
   418 shows the input with the LemonReader class:
   401 
   419 
   402 \code
   420 \code
   403 UndirListGraph network;
   421 UndirListGraph network;
   404 UndirListGraph::UndirEdgeSet<double> capacity;
   422 UndirListGraph::UndirEdgeSet<double> capacity;
   415 reader.run();
   433 reader.run();
   416 \endcode
   434 \endcode
   417 
   435 
   418 Because the GraphReader and the UndirGraphReader can be converted
   436 Because the GraphReader and the UndirGraphReader can be converted
   419 to LemonReader and it can resolve the ID's of the items, the previous
   437 to LemonReader and it can resolve the ID's of the items, the previous
   420 result can be achived with the UndirGraphReader class also.
   438 result can be achived with the UndirGraphReader class, too.
   421 
   439 
   422 
   440 
   423 \code
   441 \code
   424 UndirListGraph network;
   442 UndirListGraph network;
   425 UndirListGraph::UndirEdgeSet<double> capacity;
   443 UndirListGraph::UndirEdgeSet<double> capacity;