| 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-2009 |
|---|
| 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 |
|---|
