COIN-OR::LEMON - Graph Library

source: lemon-tutorial/lgf.dox @ 31:02083323ff2c

Last change on this file since 31:02083323ff2c was 31:02083323ff2c, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Add preliminary pages about LGF and tools

File size: 5.9 KB
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-2008
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 */
19namespace lemon {
21[PAGE]sec_lgf[PAGE] Input-Output for Graphs
23\todo Clarify this section.
25LEMON provides a versatile file format for storing graphs
26and related node and arc maps.
27Such a format should be really flexible, it should be able to store arbitrary
28number of maps of arbitrary value types.
29On the other hand, the file size and the ease of processing are also critical
30to support storing huge graphs, which is a major goal of LEMON.
31These requirements forbid using complicated and deeply structured formats
32like XML.
33That is why a compact file format is designed for LEMON instead of using
34hierarchical formats, such as GraphML, GXL or GML.
36The LEMON Graph Format (LGF) comprises different sections, for
37example a digraph is stored in a \c @nodes and an \c @arcs
38section. These parts use column oriented formats, each
39column belongs to a map in the graph. The first line of the section associate
40names to these maps, which can be used to refer them.
41Note that this simple idea makes it possible to extend the files with
42new maps (columns) at any
43position without having to modify the codes using these files.
45The \c label map has special role, it must store unique values, which in turn
46can be used to refer
47to the nodes and arcs in the file. Finally, the first two column of the
48\c @arcs section is anonymous, they indicate the source and target nodes,
52  @nodes
53  label coordinate
54  0     (20,100)
55  1     (40,120)
56  ...
57  41    (600,100)
58  @arcs
59            label length
60  0    1    0     16
61  0    2    1     12
62  2    12   2     20
63  ...
64  36   41   123   21
65  @attributes
66  source 0
67  target 41
68  caption "A shortest path problem"
71The \ref DigraphReader and \ref DigraphWriter classes are used
72to read and write a digraph and corresponding maps. By default, a map
73can be used with these classes if its value type has standard I/O
74operators (\c operator<<(ostream&, T) and \c operator>>(istream&, T&)).
75Otherwise, a function object
76can be specified which converts the value type to \c std::string.
77The above LGF file can be scanned as follows.
80  ListDigraph g;
81  ListDigraph::NodeMap<dim2::Point<int> > coord(g);
82  ListDigraph::ArcMap<int> length(g);
83  ListDigraph::Node src;
84  std::string title;
86  digraphReader(g, std::cin)
87    .nodeMap("coord", coord)
88    .arcMap("length", length)
89    .attribute("caption", title)
90    .node("source", src)
91    .run();
94Apart from LGF, the library can also interpret other graph
95formats, such as the well-known DIMACS format or the NAUTY graph6
100The \e LGF is a <em>column oriented</em>
101file format for storing graphs and associated data like
102node and edge maps.
104Each line with \c '#' first non-whitespace
105character is considered as a comment line.
107Otherwise the file consists of sections starting with
108a header line. The header lines starts with an \c '@' character followed by the
109type of section. The standard section types are \c \@nodes, \c
110\@arcs and \c \@edges
111and \@attributes. Each header line may also have an optional
112\e name, which can be use to distinguish the sections of the same
115The standard sections are column oriented, each line consists of
116<em>token</em>s separated by whitespaces. A token can be \e plain or
117\e quoted. A plain token is just a sequence of non-whitespace characters,
118while a quoted token is a
119character sequence surrounded by double quotes, and it can also
120contain whitespaces and escape sequences.
122The \c \@nodes section describes a set of nodes and associated
123maps. The first is a header line, its columns are the names of the
124maps appearing in the following lines.
125One of the maps must be called \c
126"label", which plays special role in the file.
127The following
128non-empty lines until the next section describes nodes of the
129graph. Each line contains the values of the node maps
130associated to the current node.
133 @nodes
134 label  coordinates  size    title
135 1      (10,20)      10      "First node"
136 2      (80,80)      8       "Second node"
137 3      (40,10)      10      "Third node"
140The \c \@arcs section is very similar to the \c \@nodes section,
141it again starts with a header line describing the names of the maps,
142but the \c "label" map is not obligatory here. The following lines
143describe the arcs. The first two tokens of each line are
144the source and the target node of the arc, respectively, then come the map
145values. The source and target tokens must be node labels.
148 @arcs
149         capacity
150 1   2   16
151 1   3   12
152 2   3   18
155The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can
156also store the edge set of an undirected graph. In such case there is
157a conventional method for store arc maps in the file, if two columns
158has the same caption with \c '+' and \c '-' prefix, then these columns
159can be regarded as the values of an arc map.
161The \c \@attributes section contains key-value pairs, each line
162consists of two tokens, an attribute name, and then an attribute
163value. The value of the attribute could be also a label value of a
164node or an edge, or even an edge label prefixed with \c '+' or \c '-',
165which regards to the forward or backward directed arc of the
166corresponding edge.
169 @attributes
170 source 1
171 target 3
172 caption "LEMON test digraph"
175The \e LGF can contain extra sections, but there is no restriction on
176the format of such sections.
Note: See TracBrowser for help on using the repository browser.