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 \@nodes and an \@arcs 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 \@attributes 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 \@nodes 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 \@arcs 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 > coord(g);
kpeter@31: ListDigraph::ArcMap 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: }