lgf.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 28 Feb 2010 19:38:57 +0100
changeset 53 0f695eac7e07
parent 33 598cd0b266d3
child 56 11bd4cea8379
permissions -rw-r--r--
Show demo files in the menu
kpeter@31
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@31
     2
 *
kpeter@31
     3
 * This file is a part of LEMON, a generic C++ optimization library.
kpeter@31
     4
 *
kpeter@32
     5
 * Copyright (C) 2003-2010
kpeter@31
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@31
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@31
     8
 *
kpeter@31
     9
 * Permission to use, modify and distribute this software is granted
kpeter@31
    10
 * provided that this copyright notice appears in all copies. For
kpeter@31
    11
 * precise terms see the accompanying LICENSE file.
kpeter@31
    12
 *
kpeter@31
    13
 * This software is provided "AS IS" with no warranty of any kind,
kpeter@31
    14
 * express or implied, and with no claim as to its suitability for any
kpeter@31
    15
 * purpose.
kpeter@31
    16
 *
kpeter@31
    17
 */
kpeter@31
    18
kpeter@31
    19
namespace lemon {
kpeter@31
    20
/**
kpeter@44
    21
[PAGE]sec_lgf[PAGE] LEMON Graph Format
kpeter@31
    22
kpeter@44
    23
LEMON provides a versatile file format for storing graphs and related
kpeter@44
    24
node and arc maps. Such a format should be really flexible, it should be
kpeter@44
    25
able to store arbitrary number of maps of arbitrary value types.
kpeter@44
    26
On the other hand, the file size and the ease of processing are also critical
kpeter@44
    27
to support huge graphs, which is a major goal of LEMON.
kpeter@44
    28
These requirements forbid using complicated and deeply structured formats
kpeter@44
    29
like XML. That is why a compact text file format is designed for LEMON
kpeter@44
    30
instead of using hierarchical formats (such as GraphML, GXL or GML).
kpeter@31
    31
kpeter@44
    32
The LEMON Graph Format (LGF) consists of several sections, for example a
kpeter@44
    33
digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section.
kpeter@44
    34
These parts use column oriented formats, each column belongs to a map in
kpeter@44
    35
the graph. The first line of the section associates names to these maps,
kpeter@44
    36
which can be used to refer them. Note that this simple idea makes it
kpeter@44
    37
possible to extend the files with new maps (columns) at any position
kpeter@44
    38
without having to modify the codes using these files.
kpeter@44
    39
Other data can also be added to an LGF file as individual properties
kpeter@44
    40
in an <tt>\@attributes</tt> section. This part can be used to specify
kpeter@44
    41
certain nodes or arcs, or store meta data for the file, such as copyright
kpeter@44
    42
notice.
kpeter@31
    43
kpeter@44
    44
For example, a shortest path problem, which is represented as a directed
kpeter@44
    45
graph with some node and arc maps, can be stored in LGF format as follows.
kpeter@31
    46
kpeter@31
    47
\code
kpeter@31
    48
  @nodes
kpeter@31
    49
  label coordinate
kpeter@31
    50
  0     (20,100)
kpeter@31
    51
  1     (40,120)
kpeter@31
    52
  ...
kpeter@31
    53
  41    (600,100)
kpeter@44
    54
kpeter@31
    55
  @arcs
kpeter@31
    56
            label length
kpeter@31
    57
  0    1    0     16
kpeter@31
    58
  0    2    1     12
kpeter@31
    59
  2    12   2     20
kpeter@31
    60
  ...
kpeter@31
    61
  36   41   123   21
kpeter@44
    62
kpeter@31
    63
  @attributes
kpeter@31
    64
  source 0
kpeter@31
    65
  caption "A shortest path problem"
kpeter@31
    66
\endcode
kpeter@31
    67
kpeter@44
    68
In the <tt>\@nodes</tt> section, the \c label map has special role,
kpeter@44
    69
it must store unique values, which in turn can be used to refer to the nodes
kpeter@44
    70
in the file.
kpeter@44
    71
The first two columns of the <tt>\@arcs</tt> section are anonymous, they
kpeter@44
    72
store the source and target nodes, respectively.
kpeter@44
    73
kpeter@44
    74
The \ref DigraphReader and \ref DigraphWriter classes can used
kpeter@44
    75
to read and write data in LGF format.
kpeter@44
    76
For example, the above file can be read as follows.
kpeter@31
    77
kpeter@31
    78
\code
kpeter@31
    79
  ListDigraph g;
kpeter@31
    80
  ListDigraph::NodeMap<dim2::Point<int> > coord(g);
kpeter@31
    81
  ListDigraph::ArcMap<int> length(g);
kpeter@31
    82
  ListDigraph::Node src;
kpeter@31
    83
  std::string title;
kpeter@31
    84
kpeter@44
    85
  digraphReader(g, "digraph.lgf")
kpeter@44
    86
    .nodeMap("coordinate", coord)
kpeter@31
    87
    .arcMap("length", length)
kpeter@44
    88
    .node("source", src)
kpeter@31
    89
    .attribute("caption", title)
kpeter@31
    90
    .run();
kpeter@31
    91
\endcode
kpeter@31
    92
kpeter@44
    93
Note that the \ref DigraphReader class is used through the \ref digraphReader()
kpeter@44
    94
function with several named parameters.
kpeter@31
    95
kpeter@44
    96
\note By default, a map can be used with these classes if its value type
kpeter@44
    97
has standard I/O operators (\c operator<<(ostream&, T) and \c
kpeter@44
    98
operator>>(istream&, T&)). Otherwise, a function object can be specified
kpeter@44
    99
which converts the value type to \c std::string.
kpeter@31
   100
kpeter@44
   101
The following code demonstrates how the above digraph with the maps and
kpeter@44
   102
attributes can be written into the standard output in LGF Format.
kpeter@31
   103
kpeter@31
   104
\code
kpeter@44
   105
  digraphWriter(g, std::cout)
kpeter@44
   106
    .nodeMap("coordinate", coord)
kpeter@44
   107
    .arcMap("length", length)
kpeter@44
   108
    .node("source", src)
kpeter@44
   109
    .attribute("caption", title)
kpeter@44
   110
    .run();
kpeter@31
   111
\endcode
kpeter@44
   112
 
kpeter@44
   113
Apart from LGF, the library can also handle other graph
kpeter@44
   114
formats, such as the well-known DIMACS format.
kpeter@31
   115
kpeter@44
   116
For more information, see a more detailed \ref lgf-format
kpeter@44
   117
"description of the LGF format" and the \ref io_group module
kpeter@44
   118
in the reference manual.
kpeter@31
   119
alpar@33
   120
[TRAILER]
kpeter@31
   121
*/
kpeter@31
   122
}