doc/read_write_bg.dox
author alpar
Fri, 20 Oct 2006 12:05:54 +0000
changeset 2256 b22dfb6c5ff3
child 2391 14a343be7a5a
permissions -rw-r--r--
Graph imlementations actually provide ReferenceMaps.
alpar@2216
     1
namespace lemon {
alpar@2216
     2
/*!
alpar@2216
     3
\page read_write_bg Background of Reading and Writing
alpar@2216
     4
alpar@2216
     5
To read a map (on the nodes or edges)
alpar@2216
     6
the \ref lemon::GraphReader "GraphReader"
alpar@2216
     7
should know how to read a Value from the given map.
alpar@2216
     8
By the default implementation the input operator reads a value from
alpar@2216
     9
the stream and the type of the read value is the value type of the given map.
alpar@2216
    10
When the reader should skip a value in the stream, because you do not
alpar@2216
    11
want to store it in a map, the reader skips a character sequence without 
alpar@2216
    12
whitespaces. 
alpar@2216
    13
alpar@2216
    14
If you want to change the functionality of the reader, you can use
alpar@2216
    15
template parameters to specialize it. When you give a reading
alpar@2216
    16
command for a map you can give a Reader type as template parameter.
alpar@2216
    17
With this template parameter you can control how the Reader reads
alpar@2216
    18
a value from the stream.
alpar@2216
    19
alpar@2216
    20
The reader has the next structure: 
alpar@2216
    21
\code
alpar@2216
    22
struct TypeReader {
alpar@2216
    23
  typedef TypeName Value;
alpar@2216
    24
alpar@2216
    25
  void read(std::istream& is, Value& value);
alpar@2216
    26
};
alpar@2216
    27
\endcode
alpar@2216
    28
alpar@2216
    29
For example, the \c "strings" nodemap contains strings and you do not need
alpar@2216
    30
the value of the string just the length. Then you can implement an own Reader
alpar@2216
    31
struct.
alpar@2216
    32
alpar@2216
    33
\code
alpar@2216
    34
struct LengthReader {
alpar@2216
    35
  typedef int Value;
alpar@2216
    36
alpar@2216
    37
  void read(std::istream& is, Value& value) {
alpar@2216
    38
    std::string tmp;
alpar@2216
    39
    is >> tmp;
alpar@2216
    40
    value = tmp.length();
alpar@2216
    41
  }
alpar@2216
    42
};
alpar@2216
    43
...
alpar@2216
    44
reader.readNodeMap<LengthReader>("strings", lengthMap);
alpar@2216
    45
\endcode  
alpar@2216
    46
alpar@2216
    47
The global functionality of the reader class can be changed by giving a
alpar@2216
    48
special template parameter to the GraphReader class. By default, the
alpar@2216
    49
template parameter is \c DefaultReaderTraits. A reader traits class 
alpar@2216
    50
should provide a nested template class Reader for each type, and a 
alpar@2216
    51
DefaultReader for skipping a value.
alpar@2216
    52
alpar@2216
    53
The specialization of writing is very similar to that of reading.
alpar@2216
    54
alpar@2216
    55
\section u Undirected graphs
alpar@2216
    56
alpar@2216
    57
In a file describing an undirected graph (ugraph, for short) you find an
alpar@2216
    58
\c uedgeset section instead of the \c edgeset section. The first line of
alpar@2216
    59
the section describes the names of the maps on the undirected egdes and all
alpar@2216
    60
next lines describe one undirected edge with the the incident nodes and the
alpar@2216
    61
values of the map.
alpar@2216
    62
alpar@2216
    63
The format handles directed edge maps as a syntactical sugar???, if there
alpar@2216
    64
are two maps with names being the same with a \c '+' and a \c '-' prefix
alpar@2216
    65
then this will be read as a directed map.
alpar@2216
    66
alpar@2216
    67
\code
alpar@2216
    68
@uedgeset
alpar@2216
    69
             label      capacity        +flow   -flow
alpar@2216
    70
32   2       1          4.3             2.0     0.0
alpar@2216
    71
21   21      5          2.6             0.0     2.6
alpar@2216
    72
21   12      8          3.4             0.0     0.0
alpar@2216
    73
\endcode
alpar@2216
    74
alpar@2216
    75
The \c edges section is changed to \c uedges section. This section
alpar@2216
    76
describes labeled edges and undirected edges. The directed edge label
alpar@2216
    77
should start with a \c '+' or a \c '-' prefix to decide the direction
alpar@2216
    78
of the edge. 
alpar@2216
    79
alpar@2216
    80
\code
alpar@2216
    81
@uedges
alpar@2216
    82
uedge 1
alpar@2216
    83
+edge 5
alpar@2216
    84
-back 5
alpar@2216
    85
\endcode
alpar@2216
    86
alpar@2216
    87
There are similar classes to the \ref lemon::GraphReader "GraphReader" and
alpar@2216
    88
\ref lemon::GraphWriter "GraphWriter" which
alpar@2216
    89
handle the undirected graphs. These classes are
alpar@2216
    90
the \ref lemon::UGraphReader "UGraphReader"
alpar@2216
    91
and \ref lemon::UGraphWriter "UGraphWriter".
alpar@2216
    92
alpar@2216
    93
The \ref lemon::UGraphReader::readUEdgeMap() "readUEdgeMap()"
alpar@2216
    94
function reads an undirected map and the
alpar@2216
    95
\ref lemon::UGraphReader::readUEdge() "readUEdge()"
alpar@2216
    96
reads an undirected edge from the file, 
alpar@2216
    97
alpar@2216
    98
\code
alpar@2216
    99
reader.readUEdgeMap("capacity", capacityMap);
alpar@2216
   100
reader.readEdgeMap("flow", flowMap);
alpar@2216
   101
...
alpar@2216
   102
reader.readUEdge("u_edge", u_edge);
alpar@2216
   103
reader.readEdge("edge", edge);
alpar@2216
   104
\endcode
alpar@2216
   105
alpar@2216
   106
\section advanced Advanced features
alpar@2216
   107
alpar@2216
   108
The graph reader and writer classes give an easy way to read and write
alpar@2216
   109
graphs. But sometimes we want more advanced features. In this case we can
alpar@2216
   110
use the more general <tt>lemon reader and writer</tt> interface.
alpar@2216
   111
alpar@2216
   112
The LEMON file format is a section oriented file format. It contains one or
alpar@2216
   113
more sections, each starting with a line identifying its type 
alpar@2216
   114
(the word starting with the \c \@  character).
alpar@2216
   115
The content of the section this way cannot contain line with \c \@ first
alpar@2216
   116
character. The file may contains comment lines with \c # first character.
alpar@2216
   117
alpar@2216
   118
The \ref lemon::LemonReader "LemonReader"
alpar@2216
   119
and \ref lemon::LemonWriter "LemonWriter"
alpar@2216
   120
gives a framework to read and
alpar@2216
   121
write sections. There are various section reader and section writer
alpar@2216
   122
classes which can be attached to a \ref lemon::LemonReader "LemonReader"
alpar@2216
   123
or a \ref lemon::LemonWriter "LemonWriter".
alpar@2216
   124
alpar@2216
   125
There are default section readers and writers for reading and writing
alpar@2216
   126
item sets, and labeled items in the graph. These read and write
alpar@2216
   127
the format described above. Other type of data can be handled with own
alpar@2216
   128
section reader and writer classes which are inherited from the
alpar@2216
   129
\c LemonReader::SectionReader or the
alpar@2216
   130
\ref lemon::LemonWriter::SectionWriter "LemonWriter::SectionWriter"
alpar@2216
   131
classes.
alpar@2216
   132
alpar@2216
   133
The next example defines a special section reader which reads the
alpar@2216
   134
\c \@description sections into a string:
alpar@2216
   135
alpar@2216
   136
\code 
alpar@2216
   137
class DescriptionReader : LemonReader::SectionReader {
alpar@2216
   138
protected:
alpar@2216
   139
  virtual bool header(const std::string& line) {
alpar@2216
   140
    std::istringstream ls(line);
alpar@2216
   141
    std::string head;
alpar@2216
   142
    ls >> head;
alpar@2216
   143
    return head == "@description";
alpar@2216
   144
  }
alpar@2216
   145
alpar@2216
   146
  virtual void read(std::istream& is) {
alpar@2216
   147
    std::string line;
alpar@2216
   148
    while (getline(is, line)) {
alpar@2216
   149
      desc += line;
alpar@2216
   150
    }
alpar@2216
   151
  }
alpar@2216
   152
public:
alpar@2216
   153
alpar@2216
   154
  typedef LemonReader::SectionReader Parent;
alpar@2216
   155
  
alpar@2216
   156
  DescriptionReader(LemonReader& reader) : Parent(reader) {}
alpar@2216
   157
alpar@2216
   158
  const std::string& description() const {
alpar@2216
   159
    return description;
alpar@2216
   160
  }
alpar@2216
   161
alpar@2216
   162
private:
alpar@2216
   163
  std::string desc;
alpar@2216
   164
};
alpar@2216
   165
\endcode
alpar@2216
   166
alpar@2216
   167
The other advanced stuff of the generalized file format is that 
alpar@2216
   168
multiple edgesets can be stored to the same nodeset. It can be used 
alpar@2216
   169
for example as a network traffic matrix.
alpar@2216
   170
alpar@2216
   171
In our example there is a network with symmetric links and there are assymetric
alpar@2216
   172
traffic request on the network. This construction can be stored in an
alpar@2216
   173
undirected graph and in a directed \c ListEdgeSet class. The example
alpar@2216
   174
shows the input with the \ref lemon::LemonReader "LemonReader" class:
alpar@2216
   175
alpar@2216
   176
\code
alpar@2216
   177
ListUGraph network;
alpar@2216
   178
ListUGraph::UEdgeMap<double> capacity;
alpar@2216
   179
ListEdgeSet<ListUGraph> traffic(network);
alpar@2216
   180
ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
alpar@2216
   181
alpar@2216
   182
LemonReader reader(std::cin);
alpar@2216
   183
NodeSetReader<ListUGraph> nodesetReader(reader, network);
alpar@2216
   184
UEdgeSetReader<ListUGraph> 
alpar@2216
   185
  uEdgesetReader(reader, network, nodesetReader);
alpar@2216
   186
uEdgesetReader.readEdgeMap("capacity", capacity);
alpar@2216
   187
EdgeSetReader<ListEdgeSet<ListUGraph> > 
alpar@2216
   188
  edgesetReader(reader, traffic, nodesetReader, "traffic");
alpar@2216
   189
edgesetReader.readEdgeMap("request", request);
alpar@2216
   190
alpar@2216
   191
reader.run();
alpar@2216
   192
\endcode
alpar@2216
   193
alpar@2216
   194
Because both the \ref lemon::GraphReader "GraphReader"
alpar@2216
   195
and the \ref lemon::UGraphReader "UGraphReader" can be converted
alpar@2216
   196
to \ref lemon::LemonReader "LemonReader"
alpar@2216
   197
and it can resolve the label's of the items, the previous
alpar@2216
   198
result can be achived with the \ref lemon::UGraphReader "UGraphReader"
alpar@2216
   199
class, too.
alpar@2216
   200
alpar@2216
   201
alpar@2216
   202
\code
alpar@2216
   203
ListUGraph network;
alpar@2216
   204
ListUGraph::UEdgeSet<double> capacity;
alpar@2216
   205
ListEdgeSet<ListUGraph> traffic(network);
alpar@2216
   206
ListEdgeSet<ListUGraph>::EdgeMap<double> request(network);
alpar@2216
   207
alpar@2216
   208
UGraphReader<ListUGraph> reader(std::cin, network);
alpar@2216
   209
reader.readEdgeMap("capacity", capacity);
alpar@2216
   210
EdgeSetReader<ListEdgeSet<ListUGraph> > 
alpar@2216
   211
  edgesetReader(reader, traffic, reader, "traffic");
alpar@2216
   212
edgesetReader.readEdgeMap("request", request);
alpar@2216
   213
alpar@2216
   214
reader.run();
alpar@2216
   215
\endcode
alpar@2216
   216
alpar@2216
   217
\author Balazs Dezso
alpar@2216
   218
*/
alpar@2216
   219
}