alpar@209: /* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@156:  *
alpar@209:  * This file is a part of LEMON, a generic C++ optimization library.
alpar@156:  *
alpar@440:  * Copyright (C) 2003-2009
alpar@156:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@156:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@156:  *
alpar@156:  * Permission to use, modify and distribute this software is granted
alpar@156:  * provided that this copyright notice appears in all copies. For
alpar@156:  * precise terms see the accompanying LICENSE file.
alpar@156:  *
alpar@156:  * This software is provided "AS IS" with no warranty of any kind,
alpar@156:  * express or implied, and with no claim as to its suitability for any
alpar@156:  * purpose.
alpar@156:  *
alpar@156:  */
alpar@156: 
alpar@156: namespace lemon {
alpar@156: /*!
alpar@156: 
alpar@156: 
alpar@156: 
ladanyi@236: \page lgf-format LEMON Graph Format (LGF)
alpar@156: 
alpar@156: The \e LGF is a <em>column oriented</em>
alpar@156: file format for storing graphs and associated data like
alpar@156: node and edge maps.
alpar@156: 
alpar@156: Each line with \c '#' first non-whitespace
alpar@156: character is considered as a comment line.
alpar@156: 
alpar@156: Otherwise the file consists of sections starting with
alpar@156: a header line. The header lines starts with an \c '@' character followed by the
alpar@156: type of section. The standard section types are \c \@nodes, \c
alpar@156: \@arcs and \c \@edges
alpar@156: and \@attributes. Each header line may also have an optional
alpar@156: \e name, which can be use to distinguish the sections of the same
alpar@156: type.
alpar@156: 
alpar@156: The standard sections are column oriented, each line consists of
alpar@156: <em>token</em>s separated by whitespaces. A token can be \e plain or
alpar@156: \e quoted. A plain token is just a sequence of non-whitespace characters,
alpar@156: while a quoted token is a
alpar@156: character sequence surrounded by double quotes, and it can also
alpar@209: contain whitespaces and escape sequences.
alpar@156: 
alpar@156: The \c \@nodes section describes a set of nodes and associated
kpeter@192: maps. The first is a header line, its columns are the names of the
alpar@156: maps appearing in the following lines.
alpar@156: One of the maps must be called \c
alpar@156: "label", which plays special role in the file.
alpar@156: The following
alpar@156: non-empty lines until the next section describes nodes of the
alpar@156: graph. Each line contains the values of the node maps
alpar@156: associated to the current node.
alpar@156: 
alpar@156: \code
alpar@156:  @nodes
kpeter@212:  label  coordinates  size    title
kpeter@212:  1      (10,20)      10      "First node"
kpeter@212:  2      (80,80)      8       "Second node"
kpeter@212:  3      (40,10)      10      "Third node"
alpar@156: \endcode
alpar@156: 
deba@1024: The \e LGF files can also contain bipartite graphs, in this case a
alpar@1076: \c \@red_nodes and a \c \@blue_nodes sections describe the node set of the
deba@1024: graph. If a map is in both of these sections, then it can be used as a
deba@1024: regular node map.
deba@1024: 
deba@1024: \code
deba@1024:  @red_nodes
deba@1024:  label  only_red_map   name
deba@1024:  1      "cherry"       "John"
deba@1024:  2      "Santa Claus"  "Jack"
deba@1024:  3      "blood"        "Jason"
deba@1024:  @blue_nodes
deba@1024:  label  name
deba@1024:  4      "Elisabeth"
deba@1024:  5      "Eve"
deba@1024: \endcode
deba@1024: 
deba@1024: The \c \@arcs section is very similar to the \c \@nodes section,
deba@1024: it again starts with a header line describing the names of the maps,
deba@1024: but the \c "label" map is not obligatory here. The following lines
deba@1024: describe the arcs. The first two tokens of each line are
deba@1024: the source and the target node of the arc, respectively, then come the map
alpar@156: values. The source and target tokens must be node labels.
alpar@156: 
alpar@156: \code
alpar@156:  @arcs
kpeter@212:          capacity
alpar@156:  1   2   16
alpar@156:  1   3   12
alpar@156:  2   3   18
alpar@156: \endcode
alpar@156: 
alpar@949: If there is no map in the \c \@arcs section at all, then it must be
alpar@949: indicated by a sole '-' sign in the first line.
alpar@949: 
alpar@949: \code
alpar@949:  @arcs
alpar@949:          -
alpar@949:  1   2
alpar@949:  1   3
alpar@949:  2   3
alpar@949: \endcode
alpar@949: 
kpeter@313: The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
deba@201: also store the edge set of an undirected graph. In such case there is
deba@201: a conventional method for store arc maps in the file, if two columns
alpar@949: have the same caption with \c '+' and \c '-' prefix, then these columns
deba@201: can be regarded as the values of an arc map.
alpar@156: 
alpar@156: The \c \@attributes section contains key-value pairs, each line
deba@201: consists of two tokens, an attribute name, and then an attribute
deba@201: value. The value of the attribute could be also a label value of a
deba@201: node or an edge, or even an edge label prefixed with \c '+' or \c '-',
deba@201: which regards to the forward or backward directed arc of the
deba@201: corresponding edge.
alpar@156: 
alpar@156: \code
alpar@156:  @attributes
alpar@156:  source 1
alpar@156:  target 3
alpar@156:  caption "LEMON test digraph"
alpar@156: \endcode
alpar@156: 
deba@162: The \e LGF can contain extra sections, but there is no restriction on
deba@162: the format of such sections.
deba@162: 
alpar@156: */
alpar@156: }
alpar@156: 
alpar@156: //  LocalWords:  whitespace whitespaces