/* -*- mode: C++; indent-tabs-mode: nil; -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library.

  *

  * Copyright (C) 2003-2010

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 namespace lemon {

 /**

 [PAGE]sec_lgf[PAGE] LEMON Graph Format

 LEMON provides a versatile file format for storing graphs and related

 node and arc maps. Such a format should be really flexible, it should be

 able to store arbitrary number of maps of arbitrary value types.

 On the other hand, the file size and the ease of processing are also critical

 to support huge graphs, which is a major goal of LEMON.

 These requirements forbid using complicated and deeply structured formats

 like XML. That is why a compact text file format is designed for LEMON

 instead of using hierarchical formats (such as GraphML, GXL or GML).

 The LEMON Graph Format (LGF) consists of several sections, for example a

 digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section.

 These parts use column oriented formats, each column belongs to a map in

 the graph. The first line of the section associates names to these maps,

 which can be used to refer them. Note that this simple idea makes it

 possible to extend the files with new maps (columns) at any position

 without having to modify the codes using these files.

 Other data can also be added to an LGF file as individual properties

 in an <tt>\@attributes</tt> section. This part can be used to specify

 certain nodes or arcs, or store meta data for the file, such as copyright

 notice.

 For example, a shortest path problem, which is represented as a directed

 graph with some node and arc maps, can be stored in LGF format as follows.

 \code

   @nodes

   label coordinate

   0     (20,100)

   1     (40,120)

   ...

   41    (600,100)

   @arcs

             label length

   0    1    0     16

   0    2    1     12

   2    12   2     20

   ...

   36   41   123   21

   @attributes

   source 0

   caption "A shortest path problem"

 \endcode

 In the <tt>\@nodes</tt> section, the \c label map has special role,

 it must store unique values, which in turn can be used to refer to the nodes

 in the file.

 The first two columns of the <tt>\@arcs</tt> section are anonymous, they

 store the source and target nodes, respectively.

 The \ref DigraphReader and \ref DigraphWriter classes can used

 to read and write data in LGF format.

 For example, the above file can be read as follows.

 \code

   ListDigraph g;

   ListDigraph::NodeMap<dim2::Point<int> > coord(g);

   ListDigraph::ArcMap<int> length(g);

   ListDigraph::Node src;

   std::string title;

   digraphReader(g, "digraph.lgf")

     .nodeMap("coordinate", coord)

     .arcMap("length", length)

     .node("source", src)

     .attribute("caption", title)

     .run();

 \endcode

 Note that the \ref DigraphReader class is used through the \ref digraphReader()

 function with several named parameters.

 \note By default, a map can be used with these classes if its value type

 has standard I/O operators (\c operator<<(ostream&, T) and \c

 operator>>(istream&, T&)). Otherwise, a function object can be specified

 which converts the value type to \c std::string.

 The following code demonstrates how the above digraph with the maps and

 attributes can be written into the standard output in LGF Format.

 \code

   digraphWriter(g, std::cout)

     .nodeMap("coordinate", coord)

     .arcMap("length", length)

     .node("source", src)

     .attribute("caption", title)

     .run();

 \endcode

 Undirected graphs can be stored in LGF format in almost the same way.

 The <tt>\@arcs</tt> section can also be called <tt>\@edges</tt>, they are

 identical. The only speciality is that arc maps can be distinguished from

 edge maps using a \c + or \c - prefix before the name of the map.

 For example,

 \code

   @edges

             label  +length  -length  

   0    1    0      10       20

   ...

 \endcode

 In conjunction with undirected graphs, the classes \ref GraphReader and

 \ref GraphWriter can be used.

 For more information, see the \ref lgf-format "description of the LGF format"

 and the \ref io_group module in the reference manual.

 For a working example, see \ref lgf_demo.cc in the demo directory

 of the LEMON source.

 \note Apart from LGF, the library can also handle other graph

 formats, such as the well-known DIMACS format.

 [TRAILER]

 */

 }