doc/lemon_file_format.dox
author convert-repo
Thu, 04 Mar 2010 19:34:55 +0000
changeset 2659 611ced85018b
parent 2391 14a343be7a5a
permissions -rw-r--r--
update tags
alpar@2391
     1
/* -*- C++ -*-
alpar@2391
     2
 *
alpar@2391
     3
 * This file is a part of LEMON, a generic C++ optimization library
alpar@2391
     4
 *
alpar@2553
     5
 * Copyright (C) 2003-2008
alpar@2391
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391
     8
 *
alpar@2391
     9
 * Permission to use, modify and distribute this software is granted
alpar@2391
    10
 * provided that this copyright notice appears in all copies. For
alpar@2391
    11
 * precise terms see the accompanying LICENSE file.
alpar@2391
    12
 *
alpar@2391
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@2391
    14
 * express or implied, and with no claim as to its suitability for any
alpar@2391
    15
 * purpose.
alpar@2391
    16
 *
alpar@2391
    17
 */
alpar@2391
    18
alpar@2216
    19
namespace lemon {
alpar@2216
    20
/*!
alpar@2216
    21
alpar@2216
    22
alpar@2216
    23
\page lemon_file_format LEMON Graph File Format
alpar@2216
    24
alpar@2216
    25
The standard graph IO enables one to store graphs and additional maps
alpar@2216
    26
(i.e. functions on the nodes or edges) in a flexible and efficient way. 
alpar@2216
    27
Before you read this page you should be familiar with LEMON 
alpar@2216
    28
\ref graphs "graphs" and \ref maps-page "maps".
alpar@2216
    29
alpar@2216
    30
\section format The general file format
alpar@2216
    31
alpar@2216
    32
The file contains sections in the following order:
alpar@2216
    33
alpar@2216
    34
\li nodeset
alpar@2216
    35
\li edgeset
alpar@2216
    36
\li nodes
alpar@2216
    37
\li edges
alpar@2216
    38
\li attributes
alpar@2216
    39
alpar@2216
    40
Some of these sections can be omitted, but you will basicly need the nodeset
alpar@2216
    41
section (unless your graph has no nodes at all) and the edgeset section
alpar@2216
    42
(unless your graph has no edges at all). 
alpar@2216
    43
alpar@2216
    44
The nodeset section describes the nodes of your graph: it identifies the nodes
alpar@2216
    45
and gives the maps defined on them, if any. It starts with the
alpar@2216
    46
following line:
alpar@2216
    47
alpar@2216
    48
<tt>\@nodeset</tt>
alpar@2216
    49
alpar@2216
    50
The next line contains the names of the nodemaps, separated by whitespaces.  Each
alpar@2216
    51
following line describes a node in the graph: it contains the values of the
alpar@2216
    52
maps in the right order. The map named "label" should contain unique values
alpar@2216
    53
because it is regarded as a label map. These labels need not be numbers but they
alpar@2216
    54
must identify the nodes uniquely for later reference. For example:
alpar@2216
    55
alpar@2216
    56
\code
alpar@2216
    57
@nodeset
alpar@2216
    58
label  x-coord  y-coord  color
alpar@2216
    59
3   1.0      4.0      blue
alpar@2216
    60
5   2.3      5.7      red
alpar@2216
    61
12  7.8      2.3      green
alpar@2216
    62
\endcode
alpar@2216
    63
alpar@2216
    64
The edgeset section is very similar to the nodeset section, it has
alpar@2216
    65
the same coloumn oriented structure. It starts with the line 
alpar@2216
    66
alpar@2216
    67
<tt>\@edgeset</tt>
alpar@2216
    68
alpar@2216
    69
The next line contains the whitespace separated list of names of the edge
alpar@2216
    70
maps.  Each of the next lines describes one edge. The first two elements in
alpar@2216
    71
the line are the labels of the source and target (or tail and head) nodes of the
alpar@2216
    72
edge as they occur in the label node map of the nodeset section. You can also
alpar@2216
    73
have an optional label map on the edges for later reference (which has to be
alpar@2216
    74
unique in this case).
alpar@2216
    75
alpar@2216
    76
\code
alpar@2216
    77
@edgeset
alpar@2216
    78
             label      weight   note
alpar@2216
    79
3   5        a          4.3      a-edge
alpar@2216
    80
5   12       c          2.6      c-edge
alpar@2216
    81
3   12       g          3.4      g-edge
alpar@2216
    82
\endcode
alpar@2216
    83
alpar@2216
    84
The \e nodes section contains <em>labeled (distinguished) nodes</em> 
alpar@2216
    85
(i.e. nodes having a special
alpar@2216
    86
label on them). The section starts with
alpar@2216
    87
alpar@2216
    88
<tt> \@nodes </tt>
alpar@2216
    89
alpar@2216
    90
Each of the next lines contains a label for a node in the graph 
alpar@2216
    91
and then the label as described in the \e nodeset section.
alpar@2216
    92
alpar@2216
    93
\code
alpar@2216
    94
@nodes 
alpar@2216
    95
source 3
alpar@2216
    96
target 12
alpar@2216
    97
\endcode
alpar@2216
    98
alpar@2216
    99
The last section describes the <em>labeled (distinguished) edges</em>
alpar@2216
   100
(i.e. edges having a special label on them). It starts with \c \@edges
alpar@2216
   101
and then each line contains the name of the edge and the label.
alpar@2216
   102
alpar@2216
   103
\code
alpar@2216
   104
@edges 
alpar@2216
   105
observed c
alpar@2216
   106
\endcode
alpar@2216
   107
alpar@2216
   108
alpar@2216
   109
The file may contain empty lines and comment lines. The comment lines
alpar@2216
   110
start with an \c # character.
alpar@2216
   111
alpar@2216
   112
The attributes section can handle some information about the graph. It
alpar@2216
   113
contains key-value pairs in each line (a key and the mapped value to key). The
alpar@2216
   114
key should be a string without whitespaces, the value can be of various types.
alpar@2216
   115
alpar@2216
   116
\code
alpar@2216
   117
@attributes
alpar@2216
   118
title "Four colored planar graph"
alpar@2216
   119
author "Balazs DEZSO"
alpar@2216
   120
copyright "Lemon Library"
alpar@2216
   121
version 12
alpar@2216
   122
\endcode
alpar@2216
   123
alpar@2216
   124
Finally, the file should be closed with \c \@end line.
alpar@2216
   125
alpar@2216
   126
alpar@2216
   127
\section use Using graph input-output
alpar@2216
   128
alpar@2216
   129
alpar@2216
   130
The graph input and output is based on <em> reading and writing
alpar@2216
   131
commands</em>. The user gives reading and writing commands to the reader or
alpar@2216
   132
writer class, then he calls the \c run() method that executes all the given
alpar@2216
   133
commands.
alpar@2216
   134
alpar@2216
   135
\subsection write Writing a graph
alpar@2216
   136
alpar@2216
   137
The \ref lemon::GraphWriter "GraphWriter" template class
alpar@2216
   138
provides the graph output. To write a graph
alpar@2216
   139
you should first give writing commands to the writer. You can declare
alpar@2216
   140
writing command as \c NodeMap or \c EdgeMap writing and labeled Node and
alpar@2216
   141
Edge writing.
alpar@2216
   142
alpar@2216
   143
\code
alpar@2216
   144
GraphWriter<ListGraph> writer(std::cout, graph);
alpar@2216
   145
\endcode
alpar@2216
   146
alpar@2216
   147
The \ref lemon::GraphWriter::writeNodeMap() "writeNodeMap()"
alpar@2216
   148
function declares a \c NodeMap writing command in the
alpar@2216
   149
\ref lemon::GraphWriter "GraphWriter".
alpar@2216
   150
You should give a name to the map and the map
alpar@2216
   151
object as parameters. The NodeMap writing command with name "label" should write a 
alpar@2216
   152
unique map because it will be regarded as a label map.
alpar@2216
   153
alpar@2216
   154
\see IdMap, DescriptorMap  
alpar@2216
   155
alpar@2216
   156
\code
alpar@2216
   157
IdMap<ListGraph, Node> nodeLabelMap;
alpar@2216
   158
writer.writeNodeMap("label", nodeLabelMap);
alpar@2216
   159
alpar@2216
   160
writer.writeNodeMap("x-coord", xCoordMap);
alpar@2216
   161
writer.writeNodeMap("y-coord", yCoordMap);
alpar@2216
   162
writer.writeNodeMap("color", colorMap);
alpar@2216
   163
\endcode
alpar@2216
   164
alpar@2216
   165
With the \ref lemon::GraphWriter::writeEdgeMap() "writeEdgeMap()"
alpar@2216
   166
member function you can give an edge map
alpar@2216
   167
writing command similar to the NodeMaps.
alpar@2216
   168
alpar@2216
   169
\see IdMap, DescriptorMap  
alpar@2216
   170
alpar@2216
   171
\code
alpar@2216
   172
DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph);
alpar@2216
   173
writer.writeEdgeMap("descriptor", edgeDescMap);
alpar@2216
   174
alpar@2216
   175
writer.writeEdgeMap("weight", weightMap);
alpar@2216
   176
writer.writeEdgeMap("note", noteMap);
alpar@2216
   177
\endcode
alpar@2216
   178
alpar@2216
   179
With \ref lemon::GraphWriter::writeNode() "writeNode()"
alpar@2216
   180
and \ref lemon::GraphWriter::writeEdge() "writeEdge()"
alpar@2216
   181
functions you can designate Nodes and
alpar@2216
   182
Edges in the graph. For example, you can write out the source and target node
alpar@2216
   183
of a maximum flow instance.
alpar@2216
   184
alpar@2216
   185
\code
alpar@2216
   186
writer.writeNode("source", sourceNode);
alpar@2216
   187
writer.writeNode("target", targetNode);
alpar@2216
   188
alpar@2216
   189
writer.writeEdge("observed", edge);
alpar@2216
   190
\endcode
alpar@2216
   191
alpar@2216
   192
With \ref lemon::GraphWriter::writeAttribute() "writeAttribute()"
alpar@2216
   193
function you can write an attribute to the file.
alpar@2216
   194
alpar@2216
   195
\code
alpar@2216
   196
writer.writeAttribute("author", "Balazs DEZSO");
alpar@2216
   197
writer.writeAttribute("version", 12);
alpar@2216
   198
\endcode
alpar@2216
   199
alpar@2216
   200
After you give all write commands you must call the
alpar@2216
   201
\ref lemon::GraphWriter::run() "run()" member
alpar@2216
   202
function, which executes all the writing commands.
alpar@2216
   203
alpar@2216
   204
\code
alpar@2216
   205
writer.run();
alpar@2216
   206
\endcode
alpar@2216
   207
alpar@2216
   208
\subsection reading Reading a graph
alpar@2216
   209
alpar@2216
   210
The file to be read may contain several maps and labeled nodes or edges.
alpar@2216
   211
If you read a graph you need not read all the maps and items just those
alpar@2216
   212
that you need. The interface of the \ref lemon::GraphReader "GraphReader"
alpar@2216
   213
is very similar to
alpar@2216
   214
the \ref lemon::GraphWriter "GraphWriter"
alpar@2216
   215
but the reading method does not depend on the order of the
alpar@2216
   216
given commands.
alpar@2216
   217
alpar@2216
   218
The reader object assumes that each not read value does not contain 
alpar@2216
   219
whitespaces, therefore it has some extra possibilities to control how
alpar@2216
   220
it should skip the values when the string representation contains spaces.
alpar@2216
   221
alpar@2216
   222
\code
alpar@2216
   223
GraphReader<ListGraph> reader(std::cin, graph);
alpar@2216
   224
\endcode
alpar@2216
   225
alpar@2216
   226
The \ref lemon::GraphReader::readNodeMap() "readNodeMap()"
alpar@2216
   227
function reads a map from the \c nodeset section.
alpar@2216
   228
If there is a map that you do not want to read from the file and there are
alpar@2216
   229
whitespaces in the string represenation of the values then you should
alpar@2216
   230
call the \ref lemon::GraphReader::skipNodeMap() "skipNodeMap()"
alpar@2216
   231
template member function with proper parameters.
alpar@2216
   232
alpar@2216
   233
\see QuotedStringReader
alpar@2216
   234
alpar@2216
   235
\code
alpar@2216
   236
reader.readNodeMap("x-coord", xCoordMap);
alpar@2216
   237
reader.readNodeMap("y-coord", yCoordMap);
alpar@2216
   238
alpar@2216
   239
reader.readNodeMap<QuotedStringReader>("label", labelMap);
alpar@2216
   240
reader.skipNodeMap<QuotedStringReader>("description");
alpar@2216
   241
alpar@2216
   242
reader.readNodeMap("color", colorMap);
alpar@2216
   243
\endcode
alpar@2216
   244
alpar@2216
   245
With the \ref lemon::GraphReader::readEdgeMap() "readEdgeMap()"
alpar@2216
   246
member function you can give an edge map
alpar@2216
   247
reading command similar to the NodeMaps. 
alpar@2216
   248
alpar@2216
   249
\code
alpar@2216
   250
reader.readEdgeMap("weight", weightMap);
alpar@2216
   251
reader.readEdgeMap("label", labelMap);
alpar@2216
   252
\endcode
alpar@2216
   253
alpar@2216
   254
With \ref lemon::GraphReader::readNode() "readNode()"
alpar@2216
   255
and \ref lemon::GraphReader::readEdge() "readEdge()"
alpar@2216
   256
functions you can read labeled Nodes and
alpar@2216
   257
Edges.
alpar@2216
   258
alpar@2216
   259
\code
alpar@2216
   260
reader.readNode("source", sourceNode);
alpar@2216
   261
reader.readNode("target", targetNode);
alpar@2216
   262
alpar@2216
   263
reader.readEdge("observed", edge);
alpar@2216
   264
\endcode
alpar@2216
   265
alpar@2216
   266
With \ref lemon::GraphReader::readAttribute() "readAttribute()"
alpar@2216
   267
function you can read an attribute from the file.
alpar@2216
   268
alpar@2216
   269
\code
alpar@2216
   270
std::string author;
alpar@2216
   271
writer.readAttribute("author", author);
alpar@2216
   272
int version;
alpar@2216
   273
writer.writeAttribute("version", version);
alpar@2216
   274
\endcode
alpar@2216
   275
alpar@2216
   276
After you give all read commands you must call the
alpar@2216
   277
\ref lemon::GraphReader::run() "run()" member
alpar@2216
   278
function, which executes all the commands.
alpar@2216
   279
alpar@2216
   280
\code
alpar@2216
   281
reader.run();
alpar@2216
   282
\endcode
alpar@2216
   283
alpar@2216
   284
If you want to lear more, read the \ref read_write_bg "background technics".
alpar@2216
   285
alpar@2216
   286
\author Balazs Dezso
alpar@2216
   287
*/
alpar@2216
   288
}