|
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 */ |
|
18 |
|
19 namespace lemon { |
|
20 /** |
|
21 [PAGE]sec_lgf[PAGE] Input-Output for Graphs |
|
22 |
|
23 \todo Clarify this section. |
|
24 |
|
25 LEMON provides a versatile file format for storing graphs |
|
26 and related node and arc maps. |
|
27 Such a format should be really flexible, it should be able to store arbitrary |
|
28 number of maps of arbitrary value types. |
|
29 On the other hand, the file size and the ease of processing are also critical |
|
30 to support storing huge graphs, which is a major goal of LEMON. |
|
31 These requirements forbid using complicated and deeply structured formats |
|
32 like XML. |
|
33 That is why a compact file format is designed for LEMON instead of using |
|
34 hierarchical formats, such as GraphML, GXL or GML. |
|
35 |
|
36 The LEMON Graph Format (LGF) comprises different sections, for |
|
37 example a digraph is stored in a \c @nodes and an \c @arcs |
|
38 section. These parts use column oriented formats, each |
|
39 column belongs to a map in the graph. The first line of the section associate |
|
40 names to these maps, which can be used to refer them. |
|
41 Note that this simple idea makes it possible to extend the files with |
|
42 new maps (columns) at any |
|
43 position without having to modify the codes using these files. |
|
44 |
|
45 The \c label map has special role, it must store unique values, which in turn |
|
46 can be used to refer |
|
47 to 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, |
|
49 respectively. |
|
50 |
|
51 \code |
|
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" |
|
69 \endcode |
|
70 |
|
71 The \ref DigraphReader and \ref DigraphWriter classes are used |
|
72 to read and write a digraph and corresponding maps. By default, a map |
|
73 can be used with these classes if its value type has standard I/O |
|
74 operators (\c operator<<(ostream&, T) and \c operator>>(istream&, T&)). |
|
75 Otherwise, a function object |
|
76 can be specified which converts the value type to \c std::string. |
|
77 The above LGF file can be scanned as follows. |
|
78 |
|
79 \code |
|
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; |
|
85 |
|
86 digraphReader(g, std::cin) |
|
87 .nodeMap("coord", coord) |
|
88 .arcMap("length", length) |
|
89 .attribute("caption", title) |
|
90 .node("source", src) |
|
91 .run(); |
|
92 \endcode |
|
93 |
|
94 Apart from LGF, the library can also interpret other graph |
|
95 formats, such as the well-known DIMACS format or the NAUTY graph6 |
|
96 format. |
|
97 |
|
98 <hr> |
|
99 |
|
100 The \e LGF is a <em>column oriented</em> |
|
101 file format for storing graphs and associated data like |
|
102 node and edge maps. |
|
103 |
|
104 Each line with \c '#' first non-whitespace |
|
105 character is considered as a comment line. |
|
106 |
|
107 Otherwise the file consists of sections starting with |
|
108 a header line. The header lines starts with an \c '@' character followed by the |
|
109 type of section. The standard section types are \c \@nodes, \c |
|
110 \@arcs and \c \@edges |
|
111 and \@attributes. Each header line may also have an optional |
|
112 \e name, which can be use to distinguish the sections of the same |
|
113 type. |
|
114 |
|
115 The 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, |
|
118 while a quoted token is a |
|
119 character sequence surrounded by double quotes, and it can also |
|
120 contain whitespaces and escape sequences. |
|
121 |
|
122 The \c \@nodes section describes a set of nodes and associated |
|
123 maps. The first is a header line, its columns are the names of the |
|
124 maps appearing in the following lines. |
|
125 One of the maps must be called \c |
|
126 "label", which plays special role in the file. |
|
127 The following |
|
128 non-empty lines until the next section describes nodes of the |
|
129 graph. Each line contains the values of the node maps |
|
130 associated to the current node. |
|
131 |
|
132 \code |
|
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" |
|
138 \endcode |
|
139 |
|
140 The \c \@arcs section is very similar to the \c \@nodes section, |
|
141 it again starts with a header line describing the names of the maps, |
|
142 but the \c "label" map is not obligatory here. The following lines |
|
143 describe the arcs. The first two tokens of each line are |
|
144 the source and the target node of the arc, respectively, then come the map |
|
145 values. The source and target tokens must be node labels. |
|
146 |
|
147 \code |
|
148 @arcs |
|
149 capacity |
|
150 1 2 16 |
|
151 1 3 12 |
|
152 2 3 18 |
|
153 \endcode |
|
154 |
|
155 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can |
|
156 also store the edge set of an undirected graph. In such case there is |
|
157 a conventional method for store arc maps in the file, if two columns |
|
158 has the same caption with \c '+' and \c '-' prefix, then these columns |
|
159 can be regarded as the values of an arc map. |
|
160 |
|
161 The \c \@attributes section contains key-value pairs, each line |
|
162 consists of two tokens, an attribute name, and then an attribute |
|
163 value. The value of the attribute could be also a label value of a |
|
164 node or an edge, or even an edge label prefixed with \c '+' or \c '-', |
|
165 which regards to the forward or backward directed arc of the |
|
166 corresponding edge. |
|
167 |
|
168 \code |
|
169 @attributes |
|
170 source 1 |
|
171 target 3 |
|
172 caption "LEMON test digraph" |
|
173 \endcode |
|
174 |
|
175 The \e LGF can contain extra sections, but there is no restriction on |
|
176 the format of such sections. |
|
177 |
|
178 */ |
|
179 } |