COIN-OR::LEMON - Graph Library

source: lemon-tutorial/lgf.dox

Last change on this file was 56:11bd4cea8379, checked in by Peter Kovacs <kpeter@…>, 14 years ago

Slightly extend LGF section

File size: 4.6 KB
Line 
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-2010
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[PAGE]sec_lgf[PAGE] LEMON Graph Format
22
23LEMON provides a versatile file format for storing graphs and related
24node and arc maps. Such a format should be really flexible, it should be
25able to store arbitrary number of maps of arbitrary value types.
26On the other hand, the file size and the ease of processing are also critical
27to support huge graphs, which is a major goal of LEMON.
28These requirements forbid using complicated and deeply structured formats
29like XML. That is why a compact text file format is designed for LEMON
30instead of using hierarchical formats (such as GraphML, GXL or GML).
31
32The LEMON Graph Format (LGF) consists of several sections, for example a
33digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section.
34These parts use column oriented formats, each column belongs to a map in
35the graph. The first line of the section associates names to these maps,
36which can be used to refer them. Note that this simple idea makes it
37possible to extend the files with new maps (columns) at any position
38without having to modify the codes using these files.
39Other data can also be added to an LGF file as individual properties
40in an <tt>\@attributes</tt> section. This part can be used to specify
41certain nodes or arcs, or store meta data for the file, such as copyright
42notice.
43
44For example, a shortest path problem, which is represented as a directed
45graph with some node and arc maps, can be stored in LGF format as follows.
46
47\code
48  @nodes
49  label coordinate
50  0     (20,100)
51  1     (40,120)
52  ...
53  41    (600,100)
54
55  @arcs
56            label length
57  0    1    0     16
58  0    2    1     12
59  2    12   2     20
60  ...
61  36   41   123   21
62
63  @attributes
64  source 0
65  caption "A shortest path problem"
66\endcode
67
68In the <tt>\@nodes</tt> section, the \c label map has special role,
69it must store unique values, which in turn can be used to refer to the nodes
70in the file.
71The first two columns of the <tt>\@arcs</tt> section are anonymous, they
72store the source and target nodes, respectively.
73
74The \ref DigraphReader and \ref DigraphWriter classes can used
75to read and write data in LGF format.
76For example, the above file can be read as follows.
77
78\code
79  ListDigraph g;
80  ListDigraph::NodeMap<dim2::Point<int> > coord(g);
81  ListDigraph::ArcMap<int> length(g);
82  ListDigraph::Node src;
83  std::string title;
84
85  digraphReader(g, "digraph.lgf")
86    .nodeMap("coordinate", coord)
87    .arcMap("length", length)
88    .node("source", src)
89    .attribute("caption", title)
90    .run();
91\endcode
92
93Note that the \ref DigraphReader class is used through the \ref digraphReader()
94function with several named parameters.
95
96\note By default, a map can be used with these classes if its value type
97has standard I/O operators (\c operator<<(ostream&, T) and \c
98operator>>(istream&, T&)). Otherwise, a function object can be specified
99which converts the value type to \c std::string.
100
101The following code demonstrates how the above digraph with the maps and
102attributes can be written into the standard output in LGF Format.
103
104\code
105  digraphWriter(g, std::cout)
106    .nodeMap("coordinate", coord)
107    .arcMap("length", length)
108    .node("source", src)
109    .attribute("caption", title)
110    .run();
111\endcode
112
113Undirected graphs can be stored in LGF format in almost the same way.
114The <tt>\@arcs</tt> section can also be called <tt>\@edges</tt>, they are
115identical. The only speciality is that arc maps can be distinguished from
116edge maps using a \c + or \c - prefix before the name of the map.
117For example,
118
119\code
120  @edges
121            label  +length  -length 
122  0    1    0      10       20
123  ...
124\endcode
125
126In conjunction with undirected graphs, the classes \ref GraphReader and
127\ref GraphWriter can be used.
128 
129For more information, see the \ref lgf-format "description of the LGF format"
130and the \ref io_group module in the reference manual.
131For a working example, see \ref lgf_demo.cc in the demo directory
132of the LEMON source.
133
134\note Apart from LGF, the library can also handle other graph
135formats, such as the well-known DIMACS format.
136
137[TRAILER]
138*/
139}
Note: See TracBrowser for help on using the repository browser.