COIN-OR::LEMON - Graph Library

Changeset 44:a9f8282eb6b7 in lemon-tutorial


Ignore:
Timestamp:
02/22/10 00:42:19 (8 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Rework the LGF section

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lgf.dox

    r33 r44  
    1919namespace lemon { 
    2020/** 
    21 [PAGE]sec_lgf[PAGE] Input-Output for Graphs 
     21[PAGE]sec_lgf[PAGE] LEMON Graph Format 
    2222 
    23 \todo Clarify this section. 
     23LEMON provides a versatile file format for storing graphs and related 
     24node and arc maps. Such a format should be really flexible, it should be 
     25able to store arbitrary number of maps of arbitrary value types. 
     26On the other hand, the file size and the ease of processing are also critical 
     27to support huge graphs, which is a major goal of LEMON. 
     28These requirements forbid using complicated and deeply structured formats 
     29like XML. That is why a compact text file format is designed for LEMON 
     30instead of using hierarchical formats (such as GraphML, GXL or GML). 
    2431 
    25 LEMON provides a versatile file format for storing graphs 
    26 and related node and arc maps. 
    27 Such a format should be really flexible, it should be able to store arbitrary 
    28 number of maps of arbitrary value types. 
    29 On the other hand, the file size and the ease of processing are also critical 
    30 to support storing huge graphs, which is a major goal of LEMON. 
    31 These requirements forbid using complicated and deeply structured formats 
    32 like XML. 
    33 That is why a compact file format is designed for LEMON instead of using 
    34 hierarchical formats, such as GraphML, GXL or GML. 
     32The LEMON Graph Format (LGF) consists of several sections, for example a 
     33digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section. 
     34These parts use column oriented formats, each column belongs to a map in 
     35the graph. The first line of the section associates names to these maps, 
     36which can be used to refer them. Note that this simple idea makes it 
     37possible to extend the files with new maps (columns) at any position 
     38without having to modify the codes using these files. 
     39Other data can also be added to an LGF file as individual properties 
     40in an <tt>\@attributes</tt> section. This part can be used to specify 
     41certain nodes or arcs, or store meta data for the file, such as copyright 
     42notice. 
    3543 
    36 The LEMON Graph Format (LGF) comprises different sections, for 
    37 example a digraph is stored in a \c @nodes and an \c @arcs 
    38 section. These parts use column oriented formats, each 
    39 column belongs to a map in the graph. The first line of the section associate 
    40 names to these maps, which can be used to refer them. 
    41 Note that this simple idea makes it possible to extend the files with 
    42 new maps (columns) at any 
    43 position without having to modify the codes using these files. 
    44  
    45 The \c label map has special role, it must store unique values, which in turn 
    46 can be used to refer 
    47 to the nodes and arcs in the file. Finally, the first two column of the 
    48 \c @arcs section is anonymous, they indicate the source and target nodes, 
    49 respectively. 
     44For example, a shortest path problem, which is represented as a directed 
     45graph with some node and arc maps, can be stored in LGF format as follows. 
    5046 
    5147\code 
     
    5652  ... 
    5753  41    (600,100) 
     54 
    5855  @arcs 
    5956            label length 
     
    6360  ... 
    6461  36   41   123   21 
     62 
    6563  @attributes 
    6664  source 0 
    67   target 41 
    6865  caption "A shortest path problem" 
    6966\endcode 
    7067 
    71 The \ref DigraphReader and \ref DigraphWriter classes are used 
    72 to read and write a digraph and corresponding maps. By default, a map 
    73 can be used with these classes if its value type has standard I/O 
    74 operators (\c operator<<(ostream&, T) and \c operator>>(istream&, T&)). 
    75 Otherwise, a function object 
    76 can be specified which converts the value type to \c std::string. 
    77 The above LGF file can be scanned as follows. 
     68In the <tt>\@nodes</tt> section, the \c label map has special role, 
     69it must store unique values, which in turn can be used to refer to the nodes 
     70in the file. 
     71The first two columns of the <tt>\@arcs</tt> section are anonymous, they 
     72store the source and target nodes, respectively. 
     73 
     74The \ref DigraphReader and \ref DigraphWriter classes can used 
     75to read and write data in LGF format. 
     76For example, the above file can be read as follows. 
    7877 
    7978\code 
     
    8483  std::string title; 
    8584 
    86   digraphReader(g, std::cin) 
    87     .nodeMap("coord", coord) 
     85  digraphReader(g, "digraph.lgf") 
     86    .nodeMap("coordinate", coord) 
    8887    .arcMap("length", length) 
     88    .node("source", src) 
    8989    .attribute("caption", title) 
    90     .node("source", src) 
    9190    .run(); 
    9291\endcode 
    9392 
    94 Apart from LGF, the library can also interpret other graph 
    95 formats, such as the well-known DIMACS format or the NAUTY graph6 
    96 format. 
     93Note that the \ref DigraphReader class is used through the \ref digraphReader() 
     94function with several named parameters. 
    9795 
    98 <hr> 
     96\note By default, a map can be used with these classes if its value type 
     97has standard I/O operators (\c operator<<(ostream&, T) and \c 
     98operator>>(istream&, T&)). Otherwise, a function object can be specified 
     99which converts the value type to \c std::string. 
    99100 
    100 The \e LGF is a <em>column oriented</em> 
    101 file format for storing graphs and associated data like 
    102 node and edge maps. 
    103  
    104 Each line with \c '#' first non-whitespace 
    105 character is considered as a comment line. 
    106  
    107 Otherwise the file consists of sections starting with 
    108 a header line. The header lines starts with an \c '@' character followed by the 
    109 type of section. The standard section types are \c \@nodes, \c 
    110 \@arcs and \c \@edges 
    111 and \@attributes. Each header line may also have an optional 
    112 \e name, which can be use to distinguish the sections of the same 
    113 type. 
    114  
    115 The standard sections are column oriented, each line consists of 
    116 <em>token</em>s separated by whitespaces. A token can be \e plain or 
    117 \e quoted. A plain token is just a sequence of non-whitespace characters, 
    118 while a quoted token is a 
    119 character sequence surrounded by double quotes, and it can also 
    120 contain whitespaces and escape sequences. 
    121  
    122 The \c \@nodes section describes a set of nodes and associated 
    123 maps. The first is a header line, its columns are the names of the 
    124 maps appearing in the following lines. 
    125 One of the maps must be called \c 
    126 "label", which plays special role in the file. 
    127 The following 
    128 non-empty lines until the next section describes nodes of the 
    129 graph. Each line contains the values of the node maps 
    130 associated to the current node. 
     101The following code demonstrates how the above digraph with the maps and 
     102attributes can be written into the standard output in LGF Format. 
    131103 
    132104\code 
    133  @nodes 
    134  label  coordinates  size    title 
    135  1      (10,20)      10      "First node" 
    136  2      (80,80)      8       "Second node" 
    137  3      (40,10)      10      "Third node" 
     105  digraphWriter(g, std::cout) 
     106    .nodeMap("coordinate", coord) 
     107    .arcMap("length", length) 
     108    .node("source", src) 
     109    .attribute("caption", title) 
     110    .run(); 
    138111\endcode 
     112  
     113Apart from LGF, the library can also handle other graph 
     114formats, such as the well-known DIMACS format. 
    139115 
    140 The \c \@arcs section is very similar to the \c \@nodes section, 
    141 it again starts with a header line describing the names of the maps, 
    142 but the \c "label" map is not obligatory here. The following lines 
    143 describe the arcs. The first two tokens of each line are 
    144 the source and the target node of the arc, respectively, then come the map 
    145 values. The source and target tokens must be node labels. 
    146  
    147 \code 
    148  @arcs 
    149          capacity 
    150  1   2   16 
    151  1   3   12 
    152  2   3   18 
    153 \endcode 
    154  
    155 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can 
    156 also store the edge set of an undirected graph. In such case there is 
    157 a conventional method for store arc maps in the file, if two columns 
    158 has the same caption with \c '+' and \c '-' prefix, then these columns 
    159 can be regarded as the values of an arc map. 
    160  
    161 The \c \@attributes section contains key-value pairs, each line 
    162 consists of two tokens, an attribute name, and then an attribute 
    163 value. The value of the attribute could be also a label value of a 
    164 node or an edge, or even an edge label prefixed with \c '+' or \c '-', 
    165 which regards to the forward or backward directed arc of the 
    166 corresponding edge. 
    167  
    168 \code 
    169  @attributes 
    170  source 1 
    171  target 3 
    172  caption "LEMON test digraph" 
    173 \endcode 
    174  
    175 The \e LGF can contain extra sections, but there is no restriction on 
    176 the format of such sections. 
     116For more information, see a more detailed \ref lgf-format 
     117"description of the LGF format" and the \ref io_group module 
     118in the reference manual. 
    177119 
    178120[TRAILER] 
Note: See TracChangeset for help on using the changeset viewer.