[209] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
[156] | 2 | * |
---|
[209] | 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
[156] | 4 | * |
---|
[463] | 5 | * Copyright (C) 2003-2009 |
---|
[156] | 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 | |
---|
[236] | 24 | \page lgf-format LEMON Graph Format (LGF) |
---|
[156] | 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 |
---|
[209] | 46 | contain whitespaces and escape sequences. |
---|
[156] | 47 | |
---|
| 48 | The \c \@nodes section describes a set of nodes and associated |
---|
[192] | 49 | maps. The first is a header line, its columns are the names of the |
---|
[156] | 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 |
---|
[212] | 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" |
---|
[156] | 64 | \endcode |
---|
| 65 | |
---|
| 66 | The \c \@arcs section is very similar to the \c \@nodes section, |
---|
[192] | 67 | it again starts with a header line describing the names of the maps, |
---|
[156] | 68 | but the \c "label" map is not obligatory here. The following lines |
---|
| 69 | describe the arcs. The first two tokens of each line are |
---|
| 70 | the source and the target node of the arc, respectively, then come the map |
---|
| 71 | values. The source and target tokens must be node labels. |
---|
| 72 | |
---|
| 73 | \code |
---|
| 74 | @arcs |
---|
[212] | 75 | capacity |
---|
[156] | 76 | 1 2 16 |
---|
| 77 | 1 3 12 |
---|
| 78 | 2 3 18 |
---|
| 79 | \endcode |
---|
| 80 | |
---|
[313] | 81 | The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can |
---|
[201] | 82 | also store the edge set of an undirected graph. In such case there is |
---|
| 83 | a conventional method for store arc maps in the file, if two columns |
---|
| 84 | has the same caption with \c '+' and \c '-' prefix, then these columns |
---|
| 85 | can be regarded as the values of an arc map. |
---|
[156] | 86 | |
---|
| 87 | The \c \@attributes section contains key-value pairs, each line |
---|
[201] | 88 | consists of two tokens, an attribute name, and then an attribute |
---|
| 89 | value. The value of the attribute could be also a label value of a |
---|
| 90 | node or an edge, or even an edge label prefixed with \c '+' or \c '-', |
---|
| 91 | which regards to the forward or backward directed arc of the |
---|
| 92 | corresponding edge. |
---|
[156] | 93 | |
---|
| 94 | \code |
---|
| 95 | @attributes |
---|
| 96 | source 1 |
---|
| 97 | target 3 |
---|
| 98 | caption "LEMON test digraph" |
---|
| 99 | \endcode |
---|
| 100 | |
---|
[162] | 101 | The \e LGF can contain extra sections, but there is no restriction on |
---|
| 102 | the format of such sections. |
---|
| 103 | |
---|
[156] | 104 | */ |
---|
| 105 | } |
---|
| 106 | |
---|
| 107 | // LocalWords: whitespace whitespaces |
---|