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