COIN-OR::LEMON - Graph Library

source: lemon/doc/lgf.dox @ 1356:138714057145

Last change on this file since 1356:138714057145 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 4.1 KB
RevLine 
[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 *
[1270]5 * Copyright (C) 2003-2013
[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
19namespace lemon {
20/*!
21
22
23
[236]24\page lgf-format LEMON Graph Format (LGF)
[156]25
26The \e LGF is a <em>column oriented</em>
27file format for storing graphs and associated data like
28node and edge maps.
29
30Each line with \c '#' first non-whitespace
31character is considered as a comment line.
32
33Otherwise the file consists of sections starting with
34a header line. The header lines starts with an \c '@' character followed by the
35type of section. The standard section types are \c \@nodes, \c
36\@arcs and \c \@edges
37and \@attributes. Each header line may also have an optional
38\e name, which can be use to distinguish the sections of the same
39type.
40
41The 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,
44while a quoted token is a
45character sequence surrounded by double quotes, and it can also
[209]46contain whitespaces and escape sequences.
[156]47
48The \c \@nodes section describes a set of nodes and associated
[192]49maps. The first is a header line, its columns are the names of the
[156]50maps appearing in the following lines.
51One of the maps must be called \c
52"label", which plays special role in the file.
53The following
54non-empty lines until the next section describes nodes of the
55graph. Each line contains the values of the node maps
56associated 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
[1192]66The \e LGF files can also contain bipartite graphs, in this case a
[1250]67\c \@red_nodes and a \c \@blue_nodes sections describe the node set of the
[1192]68graph. If a map is in both of these sections, then it can be used as a
69regular 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
83The \c \@arcs section is very similar to the \c \@nodes section,
84it again starts with a header line describing the names of the maps,
85but the \c "label" map is not obligatory here. The following lines
86describe the arcs. The first two tokens of each line are
87the source and the target node of the arc, respectively, then come the map
[156]88values. The source and target tokens must be node labels.
89
90\code
91 @arcs
[212]92         capacity
[156]93 1   2   16
94 1   3   12
95 2   3   18
96\endcode
97
[1067]98If there is no map in the \c \@arcs section at all, then it must be
99indicated 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
[313]109The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
[201]110also store the edge set of an undirected graph. In such case there is
111a conventional method for store arc maps in the file, if two columns
[1067]112have the same caption with \c '+' and \c '-' prefix, then these columns
[201]113can be regarded as the values of an arc map.
[156]114
115The \c \@attributes section contains key-value pairs, each line
[201]116consists of two tokens, an attribute name, and then an attribute
117value. The value of the attribute could be also a label value of a
118node or an edge, or even an edge label prefixed with \c '+' or \c '-',
119which regards to the forward or backward directed arc of the
120corresponding edge.
[156]121
122\code
123 @attributes
124 source 1
125 target 3
126 caption "LEMON test digraph"
127\endcode
128
[162]129The \e LGF can contain extra sections, but there is no restriction on
130the format of such sections.
131
[156]132*/
133}
134
135//  LocalWords:  whitespace whitespaces
Note: See TracBrowser for help on using the repository browser.