kpeter@31: /* -*- mode: C++; indent-tabs-mode: nil; -*-
kpeter@31:  *
kpeter@31:  * This file is a part of LEMON, a generic C++ optimization library.
kpeter@31:  *
kpeter@32:  * Copyright (C) 2003-2010
kpeter@31:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
kpeter@31:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
kpeter@31:  *
kpeter@31:  * Permission to use, modify and distribute this software is granted
kpeter@31:  * provided that this copyright notice appears in all copies. For
kpeter@31:  * precise terms see the accompanying LICENSE file.
kpeter@31:  *
kpeter@31:  * This software is provided "AS IS" with no warranty of any kind,
kpeter@31:  * express or implied, and with no claim as to its suitability for any
kpeter@31:  * purpose.
kpeter@31:  *
kpeter@31:  */
kpeter@31: 
kpeter@31: namespace lemon {
kpeter@31: /**
kpeter@44: [PAGE]sec_lgf[PAGE] LEMON Graph Format
kpeter@31: 
kpeter@44: LEMON provides a versatile file format for storing graphs and related
kpeter@44: node and arc maps. Such a format should be really flexible, it should be
kpeter@44: able to store arbitrary number of maps of arbitrary value types.
kpeter@44: On the other hand, the file size and the ease of processing are also critical
kpeter@44: to support huge graphs, which is a major goal of LEMON.
kpeter@44: These requirements forbid using complicated and deeply structured formats
kpeter@44: like XML. That is why a compact text file format is designed for LEMON
kpeter@44: instead of using hierarchical formats (such as GraphML, GXL or GML).
kpeter@31: 
kpeter@44: The LEMON Graph Format (LGF) consists of several sections, for example a
kpeter@44: digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section.
kpeter@44: These parts use column oriented formats, each column belongs to a map in
kpeter@44: the graph. The first line of the section associates names to these maps,
kpeter@44: which can be used to refer them. Note that this simple idea makes it
kpeter@44: possible to extend the files with new maps (columns) at any position
kpeter@44: without having to modify the codes using these files.
kpeter@44: Other data can also be added to an LGF file as individual properties
kpeter@44: in an <tt>\@attributes</tt> section. This part can be used to specify
kpeter@44: certain nodes or arcs, or store meta data for the file, such as copyright
kpeter@44: notice.
kpeter@31: 
kpeter@44: For example, a shortest path problem, which is represented as a directed
kpeter@44: graph with some node and arc maps, can be stored in LGF format as follows.
kpeter@31: 
kpeter@31: \code
kpeter@31:   @nodes
kpeter@31:   label coordinate
kpeter@31:   0     (20,100)
kpeter@31:   1     (40,120)
kpeter@31:   ...
kpeter@31:   41    (600,100)
kpeter@44: 
kpeter@31:   @arcs
kpeter@31:             label length
kpeter@31:   0    1    0     16
kpeter@31:   0    2    1     12
kpeter@31:   2    12   2     20
kpeter@31:   ...
kpeter@31:   36   41   123   21
kpeter@44: 
kpeter@31:   @attributes
kpeter@31:   source 0
kpeter@31:   caption "A shortest path problem"
kpeter@31: \endcode
kpeter@31: 
kpeter@44: In the <tt>\@nodes</tt> section, the \c label map has special role,
kpeter@44: it must store unique values, which in turn can be used to refer to the nodes
kpeter@44: in the file.
kpeter@44: The first two columns of the <tt>\@arcs</tt> section are anonymous, they
kpeter@44: store the source and target nodes, respectively.
kpeter@44: 
kpeter@44: The \ref DigraphReader and \ref DigraphWriter classes can used
kpeter@44: to read and write data in LGF format.
kpeter@44: For example, the above file can be read as follows.
kpeter@31: 
kpeter@31: \code
kpeter@31:   ListDigraph g;
kpeter@31:   ListDigraph::NodeMap<dim2::Point<int> > coord(g);
kpeter@31:   ListDigraph::ArcMap<int> length(g);
kpeter@31:   ListDigraph::Node src;
kpeter@31:   std::string title;
kpeter@31: 
kpeter@44:   digraphReader(g, "digraph.lgf")
kpeter@44:     .nodeMap("coordinate", coord)
kpeter@31:     .arcMap("length", length)
kpeter@44:     .node("source", src)
kpeter@31:     .attribute("caption", title)
kpeter@31:     .run();
kpeter@31: \endcode
kpeter@31: 
kpeter@44: Note that the \ref DigraphReader class is used through the \ref digraphReader()
kpeter@44: function with several named parameters.
kpeter@31: 
kpeter@44: \note By default, a map can be used with these classes if its value type
kpeter@44: has standard I/O operators (\c operator<<(ostream&, T) and \c
kpeter@44: operator>>(istream&, T&)). Otherwise, a function object can be specified
kpeter@44: which converts the value type to \c std::string.
kpeter@31: 
kpeter@44: The following code demonstrates how the above digraph with the maps and
kpeter@44: attributes can be written into the standard output in LGF Format.
kpeter@31: 
kpeter@31: \code
kpeter@44:   digraphWriter(g, std::cout)
kpeter@44:     .nodeMap("coordinate", coord)
kpeter@44:     .arcMap("length", length)
kpeter@44:     .node("source", src)
kpeter@44:     .attribute("caption", title)
kpeter@44:     .run();
kpeter@31: \endcode
kpeter@44:  
kpeter@44: Apart from LGF, the library can also handle other graph
kpeter@44: formats, such as the well-known DIMACS format.
kpeter@31: 
kpeter@44: For more information, see a more detailed \ref lgf-format
kpeter@44: "description of the LGF format" and the \ref io_group module
kpeter@44: in the reference manual.
kpeter@31: 
alpar@33: [TRAILER]
kpeter@31: */
kpeter@31: }