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