COIN-OR::LEMON - Graph Library

Changeset 44:a9f8282eb6b7 in lemon-tutorial


Ignore:
Timestamp:
02/22/10 00:42:19 (14 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
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.