kpeter@31
|
1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*-
|
kpeter@31
|
2 |
*
|
kpeter@31
|
3 |
* This file is a part of LEMON, a generic C++ optimization library.
|
kpeter@31
|
4 |
*
|
kpeter@32
|
5 |
* Copyright (C) 2003-2010
|
kpeter@31
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
kpeter@31
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
kpeter@31
|
8 |
*
|
kpeter@31
|
9 |
* Permission to use, modify and distribute this software is granted
|
kpeter@31
|
10 |
* provided that this copyright notice appears in all copies. For
|
kpeter@31
|
11 |
* precise terms see the accompanying LICENSE file.
|
kpeter@31
|
12 |
*
|
kpeter@31
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
kpeter@31
|
14 |
* express or implied, and with no claim as to its suitability for any
|
kpeter@31
|
15 |
* purpose.
|
kpeter@31
|
16 |
*
|
kpeter@31
|
17 |
*/
|
kpeter@31
|
18 |
|
kpeter@31
|
19 |
namespace lemon {
|
kpeter@31
|
20 |
/**
|
kpeter@44
|
21 |
[PAGE]sec_lgf[PAGE] LEMON Graph Format
|
kpeter@31
|
22 |
|
kpeter@44
|
23 |
LEMON provides a versatile file format for storing graphs and related
|
kpeter@44
|
24 |
node and arc maps. Such a format should be really flexible, it should be
|
kpeter@44
|
25 |
able to store arbitrary number of maps of arbitrary value types.
|
kpeter@44
|
26 |
On the other hand, the file size and the ease of processing are also critical
|
kpeter@44
|
27 |
to support huge graphs, which is a major goal of LEMON.
|
kpeter@44
|
28 |
These requirements forbid using complicated and deeply structured formats
|
kpeter@44
|
29 |
like XML. That is why a compact text file format is designed for LEMON
|
kpeter@44
|
30 |
instead of using hierarchical formats (such as GraphML, GXL or GML).
|
kpeter@31
|
31 |
|
kpeter@44
|
32 |
The LEMON Graph Format (LGF) consists of several sections, for example a
|
kpeter@44
|
33 |
digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section.
|
kpeter@44
|
34 |
These parts use column oriented formats, each column belongs to a map in
|
kpeter@44
|
35 |
the graph. The first line of the section associates names to these maps,
|
kpeter@44
|
36 |
which can be used to refer them. Note that this simple idea makes it
|
kpeter@44
|
37 |
possible to extend the files with new maps (columns) at any position
|
kpeter@44
|
38 |
without having to modify the codes using these files.
|
kpeter@44
|
39 |
Other data can also be added to an LGF file as individual properties
|
kpeter@44
|
40 |
in an <tt>\@attributes</tt> section. This part can be used to specify
|
kpeter@44
|
41 |
certain nodes or arcs, or store meta data for the file, such as copyright
|
kpeter@44
|
42 |
notice.
|
kpeter@31
|
43 |
|
kpeter@44
|
44 |
For example, a shortest path problem, which is represented as a directed
|
kpeter@44
|
45 |
graph with some node and arc maps, can be stored in LGF format as follows.
|
kpeter@31
|
46 |
|
kpeter@31
|
47 |
\code
|
kpeter@31
|
48 |
@nodes
|
kpeter@31
|
49 |
label coordinate
|
kpeter@31
|
50 |
0 (20,100)
|
kpeter@31
|
51 |
1 (40,120)
|
kpeter@31
|
52 |
...
|
kpeter@31
|
53 |
41 (600,100)
|
kpeter@44
|
54 |
|
kpeter@31
|
55 |
@arcs
|
kpeter@31
|
56 |
label length
|
kpeter@31
|
57 |
0 1 0 16
|
kpeter@31
|
58 |
0 2 1 12
|
kpeter@31
|
59 |
2 12 2 20
|
kpeter@31
|
60 |
...
|
kpeter@31
|
61 |
36 41 123 21
|
kpeter@44
|
62 |
|
kpeter@31
|
63 |
@attributes
|
kpeter@31
|
64 |
source 0
|
kpeter@31
|
65 |
caption "A shortest path problem"
|
kpeter@31
|
66 |
\endcode
|
kpeter@31
|
67 |
|
kpeter@44
|
68 |
In the <tt>\@nodes</tt> section, the \c label map has special role,
|
kpeter@44
|
69 |
it must store unique values, which in turn can be used to refer to the nodes
|
kpeter@44
|
70 |
in the file.
|
kpeter@44
|
71 |
The first two columns of the <tt>\@arcs</tt> section are anonymous, they
|
kpeter@44
|
72 |
store the source and target nodes, respectively.
|
kpeter@44
|
73 |
|
kpeter@44
|
74 |
The \ref DigraphReader and \ref DigraphWriter classes can used
|
kpeter@44
|
75 |
to read and write data in LGF format.
|
kpeter@44
|
76 |
For example, the above file can be read as follows.
|
kpeter@31
|
77 |
|
kpeter@31
|
78 |
\code
|
kpeter@31
|
79 |
ListDigraph g;
|
kpeter@31
|
80 |
ListDigraph::NodeMap<dim2::Point<int> > coord(g);
|
kpeter@31
|
81 |
ListDigraph::ArcMap<int> length(g);
|
kpeter@31
|
82 |
ListDigraph::Node src;
|
kpeter@31
|
83 |
std::string title;
|
kpeter@31
|
84 |
|
kpeter@44
|
85 |
digraphReader(g, "digraph.lgf")
|
kpeter@44
|
86 |
.nodeMap("coordinate", coord)
|
kpeter@31
|
87 |
.arcMap("length", length)
|
kpeter@44
|
88 |
.node("source", src)
|
kpeter@31
|
89 |
.attribute("caption", title)
|
kpeter@31
|
90 |
.run();
|
kpeter@31
|
91 |
\endcode
|
kpeter@31
|
92 |
|
kpeter@44
|
93 |
Note that the \ref DigraphReader class is used through the \ref digraphReader()
|
kpeter@44
|
94 |
function with several named parameters.
|
kpeter@31
|
95 |
|
kpeter@44
|
96 |
\note By default, a map can be used with these classes if its value type
|
kpeter@44
|
97 |
has standard I/O operators (\c operator<<(ostream&, T) and \c
|
kpeter@44
|
98 |
operator>>(istream&, T&)). Otherwise, a function object can be specified
|
kpeter@44
|
99 |
which converts the value type to \c std::string.
|
kpeter@31
|
100 |
|
kpeter@44
|
101 |
The following code demonstrates how the above digraph with the maps and
|
kpeter@44
|
102 |
attributes can be written into the standard output in LGF Format.
|
kpeter@31
|
103 |
|
kpeter@31
|
104 |
\code
|
kpeter@44
|
105 |
digraphWriter(g, std::cout)
|
kpeter@44
|
106 |
.nodeMap("coordinate", coord)
|
kpeter@44
|
107 |
.arcMap("length", length)
|
kpeter@44
|
108 |
.node("source", src)
|
kpeter@44
|
109 |
.attribute("caption", title)
|
kpeter@44
|
110 |
.run();
|
kpeter@31
|
111 |
\endcode
|
kpeter@44
|
112 |
|
kpeter@44
|
113 |
Apart from LGF, the library can also handle other graph
|
kpeter@44
|
114 |
formats, such as the well-known DIMACS format.
|
kpeter@31
|
115 |
|
kpeter@44
|
116 |
For more information, see a more detailed \ref lgf-format
|
kpeter@44
|
117 |
"description of the LGF format" and the \ref io_group module
|
kpeter@44
|
118 |
in the reference manual.
|
kpeter@31
|
119 |
|
alpar@33
|
120 |
[TRAILER]
|
kpeter@31
|
121 |
*/
|
kpeter@31
|
122 |
}
|