doc/lgf.dox
author Peter Kovacs <kpeter@inf.elte.hu>
Sat, 07 Oct 2017 15:48:00 +0200
changeset 1410 d9f79b81ef6c
parent 1250 97d978243703
permissions -rw-r--r--
Change the default graph type of Vf2 and Vf2pp (#597)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2013
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 namespace lemon {
    20 /*!
    21 
    22 
    23 
    24 \page lgf-format LEMON Graph Format (LGF)
    25 
    26 The \e LGF is a <em>column oriented</em>
    27 file format for storing graphs and associated data like
    28 node and edge maps.
    29 
    30 Each line with \c '#' first non-whitespace
    31 character is considered as a comment line.
    32 
    33 Otherwise the file consists of sections starting with
    34 a header line. The header lines starts with an \c '@' character followed by the
    35 type of section. The standard section types are \c \@nodes, \c
    36 \@arcs and \c \@edges
    37 and \@attributes. Each header line may also have an optional
    38 \e name, which can be use to distinguish the sections of the same
    39 type.
    40 
    41 The standard sections are column oriented, each line consists of
    42 <em>token</em>s separated by whitespaces. A token can be \e plain or
    43 \e quoted. A plain token is just a sequence of non-whitespace characters,
    44 while a quoted token is a
    45 character sequence surrounded by double quotes, and it can also
    46 contain whitespaces and escape sequences.
    47 
    48 The \c \@nodes section describes a set of nodes and associated
    49 maps. The first is a header line, its columns are the names of the
    50 maps appearing in the following lines.
    51 One of the maps must be called \c
    52 "label", which plays special role in the file.
    53 The following
    54 non-empty lines until the next section describes nodes of the
    55 graph. Each line contains the values of the node maps
    56 associated to the current node.
    57 
    58 \code
    59  @nodes
    60  label  coordinates  size    title
    61  1      (10,20)      10      "First node"
    62  2      (80,80)      8       "Second node"
    63  3      (40,10)      10      "Third node"
    64 \endcode
    65 
    66 The \e LGF files can also contain bipartite graphs, in this case a
    67 \c \@red_nodes and a \c \@blue_nodes sections describe the node set of the
    68 graph. If a map is in both of these sections, then it can be used as a
    69 regular node map.
    70 
    71 \code
    72  @red_nodes
    73  label  only_red_map   name
    74  1      "cherry"       "John"
    75  2      "Santa Claus"  "Jack"
    76  3      "blood"        "Jason"
    77  @blue_nodes
    78  label  name
    79  4      "Elisabeth"
    80  5      "Eve"
    81 \endcode
    82 
    83 The \c \@arcs section is very similar to the \c \@nodes section,
    84 it again starts with a header line describing the names of the maps,
    85 but the \c "label" map is not obligatory here. The following lines
    86 describe the arcs. The first two tokens of each line are
    87 the source and the target node of the arc, respectively, then come the map
    88 values. The source and target tokens must be node labels.
    89 
    90 \code
    91  @arcs
    92          capacity
    93  1   2   16
    94  1   3   12
    95  2   3   18
    96 \endcode
    97 
    98 If there is no map in the \c \@arcs section at all, then it must be
    99 indicated by a sole '-' sign in the first line.
   100 
   101 \code
   102  @arcs
   103          -
   104  1   2
   105  1   3
   106  2   3
   107 \endcode
   108 
   109 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
   110 also store the edge set of an undirected graph. In such case there is
   111 a conventional method for store arc maps in the file, if two columns
   112 have the same caption with \c '+' and \c '-' prefix, then these columns
   113 can be regarded as the values of an arc map.
   114 
   115 The \c \@attributes section contains key-value pairs, each line
   116 consists of two tokens, an attribute name, and then an attribute
   117 value. The value of the attribute could be also a label value of a
   118 node or an edge, or even an edge label prefixed with \c '+' or \c '-',
   119 which regards to the forward or backward directed arc of the
   120 corresponding edge.
   121 
   122 \code
   123  @attributes
   124  source 1
   125  target 3
   126  caption "LEMON test digraph"
   127 \endcode
   128 
   129 The \e LGF can contain extra sections, but there is no restriction on
   130 the format of such sections.
   131 
   132 */
   133 }
   134 
   135 //  LocalWords:  whitespace whitespaces