doc/graph_io.dox
changeset 1538 777834118f73
parent 1527 7ceab500e1f6
child 1540 7d028a73d7f2
equal deleted inserted replaced
6:8a16f7282397 7:251784438baa
     7 The standard graph IO enables to store graphs and additional maps
     7 The standard graph IO enables to store graphs and additional maps
     8 in a flexible and efficient way. 
     8 in a flexible and efficient way. 
     9 
     9 
    10 \section format The general file format
    10 \section format The general file format
    11 
    11 
    12 The file contains at most four sections in the following order:
    12 The file contains sections in the following order:
    13 
    13 
    14 \li nodeset
    14 \li nodeset
    15 \li edgeset
    15 \li edgeset
    16 \li nodes
    16 \li nodes
    17 \li edges
    17 \li edges
       
    18 \li attributes
    18 
    19 
    19 The nodeset section starts with the following line:
    20 The nodeset section starts with the following line:
    20 
    21 
    21 <tt>\@nodeset</tt>
    22 <tt>\@nodeset</tt>
    22 
    23 
    76 
    77 
    77 
    78 
    78 The file may contain empty lines and comment lines. The comment lines
    79 The file may contain empty lines and comment lines. The comment lines
    79 start with an \c # character.
    80 start with an \c # character.
    80 
    81 
       
    82 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
       
    84 be a string without whitespace, the value can be from various type.
       
    85 
       
    86 \code
       
    87 @attributes
       
    88 title "Four colored plan graph"
       
    89 author "Balazs DEZSO"
       
    90 copyright "Lemon Library"
       
    91 version 12
       
    92 \endcode
       
    93 
       
    94 \code
       
    95 @end
       
    96 \endcode
       
    97 =======
    81 The file ends with the 
    98 The file ends with the 
    82 
    99 
    83 <tt> \@end </tt>
   100 <tt> \@end </tt>
    84 
   101 
    85 line.
   102 line.
   137 \code
   154 \code
   138 writer.writeNode("source", sourceNode);
   155 writer.writeNode("source", sourceNode);
   139 writer.writeNode("target", targetNode);
   156 writer.writeNode("target", targetNode);
   140 
   157 
   141 writer.writeEdge("observed", edge);
   158 writer.writeEdge("observed", edge);
       
   159 \endcode
       
   160 
       
   161 With \c writeAttribute() function you can write an attribute to the file.
       
   162 
       
   163 \code
       
   164 writer.writeAttribute("author", "Balazs DEZSO");
       
   165 writer.writeAttribute("version", 12);
   142 \endcode
   166 \endcode
   143 
   167 
   144 After you give all write commands you must call the \c run() member
   168 After you give all write commands you must call the \c run() member
   145 function, which executes all the writing commands.
   169 function, which executes all the writing commands.
   146 
   170 
   195 \code
   219 \code
   196 reader.readNode("source", sourceNode);
   220 reader.readNode("source", sourceNode);
   197 reader.readNode("target", targetNode);
   221 reader.readNode("target", targetNode);
   198 
   222 
   199 reader.readEdge("observed", edge);
   223 reader.readEdge("observed", edge);
       
   224 \endcode
       
   225 
       
   226 With \c readAttribute() function you can read an attribute from the file.
       
   227 
       
   228 \code
       
   229 std::string author;
       
   230 writer.readAttribute("author", author);
       
   231 int version;
       
   232 writer.writeAttribute("version", version);
   200 \endcode
   233 \endcode
   201 
   234 
   202 After you give all read commands you must call the \c run() member
   235 After you give all read commands you must call the \c run() member
   203 function, which executes all the commands.
   236 function, which executes all the commands.
   204 
   237 
   254 should provide an inner template class Reader for each type, and an 
   287 should provide an inner template class Reader for each type, and an 
   255 DefaultReader for skipping a value.
   288 DefaultReader for skipping a value.
   256 
   289 
   257 The specialization of  writing should be very similar to that of reading.
   290 The specialization of  writing should be very similar to that of reading.
   258 
   291 
       
   292 \section undir Undir graphs
       
   293 
       
   294 In the undir graph format there is an \c undiredgeset section instead of
       
   295 the \c edgeset section. The first line of the section describes the 
       
   296 undirected egdes' names and all next lines describes one undirected edge
       
   297 with the the incident nodes and the values of the map.
       
   298 
       
   299 The format handles the directed edge maps as a syntactical sugar, if there
       
   300 is two map which names are the same with a \c '+' and a \c '-' prefix
       
   301 then it can be read as an directed map.
       
   302 
       
   303 \code
       
   304 @undiredgeset
       
   305              id    capacity +flow -flow
       
   306 32   2       1     4.3      2.0	  0.0
       
   307 21   21      5     2.6      0.0   2.6
       
   308 21   12      8     3.4      0.0   0.0
       
   309 \endcode
       
   310 
       
   311 The \c edges section changed to \c undiredges section. This section
       
   312 describes labeled edges and undirected edges. The directed edge label
       
   313 should start with a \c '+' and a \c '-' prefix what decide the direction
       
   314 of the edge. 
       
   315 
       
   316 \code
       
   317 @undiredges
       
   318 undiredge 1
       
   319 +edge 5
       
   320 -back 5
       
   321 \endcode
       
   322 
       
   323 There are similar classes to the \c GraphReader ans \c GraphWriter
       
   324 which handle the undirected graphs. These classes are the 
       
   325 \c UndirGraphReader and \UndirGraphWriter.
       
   326 
       
   327 The \c readUndirMap() function reads an undirected map and the
       
   328 \c readUndirEdge() reads an undirected edge from the file, 
       
   329 
       
   330 \code
       
   331 reader.readUndirEdgeMap("capacity", capacityMap);
       
   332 reader.readEdgeMap("flow", flowMap);
       
   333 ...
       
   334 reader.readUndirEdge("undir_edge", undir_edge);
       
   335 reader.readEdge("edge", edge);
       
   336 \endcode
       
   337 
       
   338 \section advanced Advanced features
       
   339 
       
   340 The graph reader and writer classes gives an easy way to read and write
       
   341 graphs. But sometimes we want more advanced features. This way we can
       
   342 use the more general lemon reader and writer interface.
       
   343 
       
   344 The lemon format is an section oriented file format. It contains one or
       
   345 more section, each starts with a line with \c \@ first character.
       
   346 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.
       
   348 
       
   349 The \c LemonReader and \c LemonWriter gives a framework to read and
       
   350 write sections. There are various section reader and section writer
       
   351 classes which can be attached to a \c LemonReader or a \c LemonWriter.
       
   352 
       
   353 There are default section readers and writers for reading and writing
       
   354 item sets, and labeled items in the graph. These reads and writes
       
   355 the format described above. Other type of data can be handled with own
       
   356 section reader and writer classes which are inherited from the
       
   357 \c LemonReader::SectionReader or the \c LemonWriter::SectionWriter classes.
       
   358 
       
   359 The next example defines a special section reader which reads the
       
   360 \c \@description sections into a string:
       
   361 
       
   362 \code 
       
   363 class DescriptionReader : LemonReader::SectionReader {
       
   364 protected:
       
   365   virtual bool header(const std::string& line) {
       
   366     std::istringstream ls(line);
       
   367     std::string head;
       
   368     ls >> head;
       
   369     return head == "@description";
       
   370   }
       
   371 
       
   372   virtual void read(std::istream& is) {
       
   373     std::string line;
       
   374     while (getline(is, line)) {
       
   375       desc += line;
       
   376     }
       
   377   }
       
   378 public:
       
   379 
       
   380   typedef LemonReader::SectionReader Parent;
       
   381   
       
   382   DescriptionReader(LemonReader& reader) : Parent(reader) {}
       
   383 
       
   384   const std::string& description() const {
       
   385     return description;
       
   386   }
       
   387 
       
   388 private:
       
   389   std::string desc;
       
   390 };
       
   391 \endcode
       
   392 
       
   393 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 
       
   395 by example as a network traffic matrix.
       
   396 
       
   397 In 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
       
   399 undirected graph and in an directed NewEdgeSetAdaptor class. The example
       
   400 shows the input with the LemonReader class:
       
   401 
       
   402 \code
       
   403 UndirListGraph network;
       
   404 UndirListGraph::UndirEdgeSet<double> capacity;
       
   405 NewEdgeSetAdaptor<UndirListGraph> traffic(network);
       
   406 NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
       
   407 
       
   408 LemonReader reader(std::cin);
       
   409 NodeSetReader nodesetReader(reader, network);
       
   410 UndirEdgeSetReader undirEdgesetReader(reader, network, nodesetReader);
       
   411 undirEdgesetReader.readEdgeMap("capacity", capacity);
       
   412 EdgeSetReader edgesetReader(reader, traffic, nodesetReader);
       
   413 edgesetReader.readEdgeMap("request", request);
       
   414 
       
   415 reader.run();
       
   416 \endcode
       
   417 
       
   418 Because the GraphReader and the UndirGraphReader can be converted
       
   419 to LemonReader and it can resolve the ID's of the items, the previous
       
   420 result can be achived with the UndirGraphReader class also.
       
   421 
       
   422 
       
   423 \code
       
   424 UndirListGraph network;
       
   425 UndirListGraph::UndirEdgeSet<double> capacity;
       
   426 NewEdgeSetAdaptor<UndirListGraph> traffic(network);
       
   427 NewEdgeSetAdaptor<UndirListGraph>::EdgeSet<double> request(network);
       
   428 
       
   429 UndirGraphReader reader(std::cin, network);
       
   430 reader.readEdgeMap("capacity", capacity);
       
   431 EdgeSetReader edgesetReader(reader, traffic, reader);
       
   432 edgesetReader.readEdgeMap("request", request);
       
   433 
       
   434 reader.run();
       
   435 \endcode
       
   436 
   259 \author Balazs Dezso
   437 \author Balazs Dezso
   260 */
   438 */
   261 }
   439 }