[1118] | 1 | namespace lemon { |
---|
[1114] | 2 | /*! |
---|
| 3 | |
---|
| 4 | |
---|
| 5 | \page graph-io-page Graph Input-Output |
---|
| 6 | |
---|
[1522] | 7 | The standard graph IO enables to store graphs and additional maps |
---|
[1118] | 8 | in a flexible and efficient way. |
---|
[1114] | 9 | |
---|
| 10 | \section format The general file format |
---|
| 11 | |
---|
[1522] | 12 | The file contains at most four sections in the following order: |
---|
[1114] | 13 | |
---|
| 14 | \li nodeset |
---|
| 15 | \li edgeset |
---|
| 16 | \li nodes |
---|
| 17 | \li edges |
---|
| 18 | |
---|
[1522] | 19 | The nodeset section starts with the following line: |
---|
| 20 | |
---|
| 21 | <tt>\@nodeset</tt> |
---|
| 22 | |
---|
| 23 | The next line contains the names of the nodemaps, separated by whitespaces. Each |
---|
| 24 | following line describes a node in the graph: it contains the values of the |
---|
| 25 | maps in the right order. The map named "id" should contain unique values |
---|
| 26 | because it is regarded as an ID-map. For example: |
---|
[1114] | 27 | |
---|
| 28 | \code |
---|
| 29 | @nodeset |
---|
| 30 | id x-coord y-coord color |
---|
| 31 | 3 1.0 4.0 blue |
---|
| 32 | 5 2.3 5.7 red |
---|
| 33 | 12 7.8 2.3 green |
---|
| 34 | \endcode |
---|
| 35 | |
---|
| 36 | The edgeset section is very similar to the nodeset section, it has |
---|
[1522] | 37 | the same coloumn oriented structure. It starts with the line |
---|
| 38 | |
---|
| 39 | <tt>\@edgeset</tt> |
---|
| 40 | |
---|
| 41 | The next line contains the whitespace separated list of names of the maps. |
---|
[1118] | 42 | Each of the next lines describes one edge. The first two elements in the line |
---|
[1522] | 43 | are the IDs of the source and target (or tail and head) node of the edge as they occur in the ID node |
---|
| 44 | map. You can also have an optional ID map on the edges for later reference. |
---|
[1114] | 45 | |
---|
| 46 | \code |
---|
| 47 | @edgeset |
---|
| 48 | id weight label |
---|
| 49 | 3 5 a 4.3 a-edge |
---|
| 50 | 5 12 c 2.6 c-edge |
---|
| 51 | 3 12 g 3.4 g-edge |
---|
| 52 | \endcode |
---|
| 53 | |
---|
[1333] | 54 | The next section contains <em>labeled nodes</em> (i.e. nodes having a special |
---|
[1118] | 55 | label on them). The section starts with |
---|
[1522] | 56 | |
---|
| 57 | <tt> \@nodes </tt> |
---|
| 58 | |
---|
| 59 | Each of the next lines contains a label for a node in the graph |
---|
| 60 | and then the ID described in the nodeset section. |
---|
[1114] | 61 | |
---|
| 62 | \code |
---|
| 63 | @nodes |
---|
| 64 | source 3 |
---|
| 65 | target 12 |
---|
| 66 | \endcode |
---|
| 67 | |
---|
[1333] | 68 | The last section describes the <em>labeled edges</em> |
---|
| 69 | (i.e. edges having a special label on them). It starts with \c \@edges |
---|
[1114] | 70 | and then each line contains the name of the edge and the ID. |
---|
| 71 | |
---|
| 72 | \code |
---|
| 73 | @nodes |
---|
| 74 | observed c |
---|
| 75 | \endcode |
---|
| 76 | |
---|
| 77 | |
---|
| 78 | The file may contain empty lines and comment lines. The comment lines |
---|
| 79 | start with an \c # character. |
---|
| 80 | |
---|
[1522] | 81 | The file ends with the |
---|
| 82 | |
---|
| 83 | <tt> \@end </tt> |
---|
| 84 | |
---|
| 85 | line. |
---|
| 86 | |
---|
[1114] | 87 | |
---|
| 88 | \section use Using graph input-output |
---|
[1522] | 89 | The graph input and output is based on reading and writing commands. The user |
---|
| 90 | adds reading and writing commands to the reader or writer class, then he |
---|
[1118] | 91 | calls the \c run() method that executes all the given commands. |
---|
[1114] | 92 | |
---|
| 93 | \subsection write Writing a graph |
---|
| 94 | |
---|
| 95 | The \c GraphWriter class provides the graph output. To write a graph |
---|
[1526] | 96 | you should first give writing commands to the writer. You can declare |
---|
[1118] | 97 | write command as \c NodeMap or \c EdgeMap writing and labeled Node and |
---|
[1114] | 98 | Edge writing. |
---|
| 99 | |
---|
| 100 | \code |
---|
[1333] | 101 | GraphWriter<ListGraph> writer(std::cout, graph); |
---|
[1114] | 102 | \endcode |
---|
| 103 | |
---|
[1394] | 104 | The \c writeNodeMap() function declares a \c NodeMap writing command in the |
---|
[1522] | 105 | \c GraphWriter. You should give a name of the map and the map |
---|
| 106 | object as parameters. The NodeMap writing command with name "id" should write a |
---|
[1333] | 107 | unique map because it is regarded as ID map. |
---|
[1114] | 108 | |
---|
| 109 | \see IdMap, DescriptorMap |
---|
| 110 | |
---|
| 111 | \code |
---|
| 112 | IdMap<ListGraph, Node> nodeIdMap; |
---|
[1394] | 113 | writer.writeNodeMap("id", nodeIdMap); |
---|
[1114] | 114 | |
---|
[1394] | 115 | writer.writeNodeMap("x-coord", xCoordMap); |
---|
| 116 | writer.writeNodeMap("y-coord", yCoordMap); |
---|
| 117 | writer.writeNodeMap("color", colorMap); |
---|
[1114] | 118 | \endcode |
---|
| 119 | |
---|
[1394] | 120 | With the \c writeEdgeMap() member function you can give an edge map |
---|
[1333] | 121 | writing command similar to the NodeMaps. |
---|
[1114] | 122 | |
---|
| 123 | \see IdMap, DescriptorMap |
---|
[1522] | 124 | |
---|
[1114] | 125 | \code |
---|
| 126 | DescriptorMap<ListGraph, Edge, ListGraph::EdgeMap<int> > edgeDescMap(graph); |
---|
[1394] | 127 | writer.writeEdgeMap("descriptor", edgeDescMap); |
---|
[1114] | 128 | |
---|
[1394] | 129 | writer.writeEdgeMap("weight", weightMap); |
---|
| 130 | writer.writeEdgeMap("label", labelMap); |
---|
[1114] | 131 | \endcode |
---|
| 132 | |
---|
[1522] | 133 | With \c writeNode() and \c writeEdge() functions you can designate Nodes and |
---|
| 134 | Edges in the graph. For example, you can write out the source and target node |
---|
| 135 | of a maximum flow instance. |
---|
[1114] | 136 | |
---|
| 137 | \code |
---|
[1394] | 138 | writer.writeNode("source", sourceNode); |
---|
| 139 | writer.writeNode("target", targetNode); |
---|
[1114] | 140 | |
---|
[1394] | 141 | writer.writeEdge("observed", edge); |
---|
[1114] | 142 | \endcode |
---|
| 143 | |
---|
| 144 | After you give all write commands you must call the \c run() member |
---|
[1522] | 145 | function, which executes all the writing commands. |
---|
[1114] | 146 | |
---|
| 147 | \code |
---|
| 148 | writer.run(); |
---|
| 149 | \endcode |
---|
| 150 | |
---|
| 151 | \subsection reading Reading a graph |
---|
| 152 | |
---|
[1118] | 153 | The given file format may contain several maps and labeled nodes or edges. |
---|
[1114] | 154 | If you read a graph you need not read all the maps and items just those |
---|
| 155 | that you need. The interface of the \c GraphReader is very similar to |
---|
[1522] | 156 | the GraphWriter but the reading method does not depend on the order of the |
---|
[1114] | 157 | given commands. |
---|
| 158 | |
---|
[1522] | 159 | The reader object assumes that each not readed value does not contain |
---|
[1118] | 160 | whitespaces, therefore it has some extra possibilities to control how |
---|
| 161 | it should skip the values when the string representation contains spaces. |
---|
[1114] | 162 | |
---|
| 163 | \code |
---|
[1333] | 164 | GraphReader<ListGraph> reader(std::cin, graph); |
---|
[1114] | 165 | \endcode |
---|
| 166 | |
---|
[1394] | 167 | The \c readNodeMap() function reads a map from the \c \@nodeset section. |
---|
[1522] | 168 | If there is a map that you do not want to read from the file and there are |
---|
| 169 | whitespaces in the string represenation of the values then you should |
---|
[1114] | 170 | call the \c skipNodeMap() template member function with proper parameters. |
---|
| 171 | |
---|
| 172 | \see QuotedStringReader |
---|
[1522] | 173 | |
---|
[1114] | 174 | \code |
---|
[1394] | 175 | reader.readNodeMap("x-coord", xCoordMap); |
---|
| 176 | reader.readNodeMap("y-coord", yCoordMap); |
---|
[1114] | 177 | |
---|
[1394] | 178 | reader.readNodeMap<QuotedStringReader>("label", labelMap); |
---|
[1114] | 179 | reader.skipNodeMap<QuotedStringReader>("description"); |
---|
| 180 | |
---|
[1394] | 181 | reader.readNodeMap("color", colorMap); |
---|
[1114] | 182 | \endcode |
---|
| 183 | |
---|
[1394] | 184 | With the \c readEdgeMap() member function you can give an edge map |
---|
[1114] | 185 | reading command similar to the NodeMaps. |
---|
| 186 | |
---|
| 187 | \code |
---|
[1394] | 188 | reader.readEdgeMap("weight", weightMap); |
---|
| 189 | reader.readEdgeMap("label", labelMap); |
---|
[1114] | 190 | \endcode |
---|
| 191 | |
---|
[1394] | 192 | With \c readNode() and \c readEdge() functions you can read labeled Nodes and |
---|
[1114] | 193 | Edges. |
---|
| 194 | |
---|
| 195 | \code |
---|
[1394] | 196 | reader.readNode("source", sourceNode); |
---|
| 197 | reader.readNode("target", targetNode); |
---|
[1114] | 198 | |
---|
[1394] | 199 | reader.readEdge("observed", edge); |
---|
[1114] | 200 | \endcode |
---|
| 201 | |
---|
| 202 | After you give all read commands you must call the \c run() member |
---|
[1522] | 203 | function, which executes all the commands. |
---|
[1114] | 204 | |
---|
| 205 | \code |
---|
| 206 | reader.run(); |
---|
| 207 | \endcode |
---|
| 208 | |
---|
[1527] | 209 | \section types Background of Reading and Writing |
---|
| 210 | To read a map (on the nodes or edges) |
---|
| 211 | the \c GraphReader should know how to read a Value from the given map. |
---|
[1114] | 212 | By the default implementation the input operator reads a value from |
---|
| 213 | the stream and the type of the readed value is the value type of the given map. |
---|
| 214 | When the reader should skip a value in the stream, because you do not |
---|
[1527] | 215 | want to store it in a map, the reader skips a character sequence without |
---|
[1114] | 216 | whitespace. |
---|
| 217 | |
---|
| 218 | If you want to change the functionality of the reader, you can use |
---|
| 219 | template parameters to specialize it. When you give a reading |
---|
| 220 | command for a map you can give a Reader type as template parameter. |
---|
[1333] | 221 | With this template parameter you can control how the Reader reads |
---|
[1114] | 222 | a value from the stream. |
---|
| 223 | |
---|
| 224 | The reader has the next structure: |
---|
| 225 | \code |
---|
| 226 | struct TypeReader { |
---|
| 227 | typedef TypeName Value; |
---|
| 228 | |
---|
| 229 | void read(std::istream& is, Value& value); |
---|
| 230 | }; |
---|
| 231 | \endcode |
---|
| 232 | |
---|
[1527] | 233 | For example, the \c "strings" nodemap contains strings and you do not need |
---|
[1114] | 234 | the value of the string just the length. Then you can implement own Reader |
---|
| 235 | struct. |
---|
| 236 | |
---|
| 237 | \code |
---|
| 238 | struct LengthReader { |
---|
| 239 | typedef int Value; |
---|
| 240 | |
---|
| 241 | void read(std::istream& is, Value& value) { |
---|
| 242 | std::string tmp; |
---|
| 243 | is >> tmp; |
---|
| 244 | value = tmp.length(); |
---|
| 245 | } |
---|
| 246 | }; |
---|
| 247 | ... |
---|
[1394] | 248 | reader.readNodeMap<LengthReader>("strings", lengthMap); |
---|
[1114] | 249 | \endcode |
---|
| 250 | |
---|
| 251 | The global functionality of the reader class can be changed by giving a |
---|
[1526] | 252 | special template parameter to the GraphReader class. By default, the |
---|
[1118] | 253 | template parameter is \c DefaultReaderTraits. A reader traits class |
---|
[1114] | 254 | should provide an inner template class Reader for each type, and an |
---|
| 255 | DefaultReader for skipping a value. |
---|
| 256 | |
---|
[1527] | 257 | The specialization of writing should be very similar to that of reading. |
---|
[1114] | 258 | |
---|
[1333] | 259 | \author Balazs Dezso |
---|
[1114] | 260 | */ |
---|
[1333] | 261 | } |
---|