Changeset 44:a9f8282eb6b7 in lemon-tutorial
Legend:
- Unmodified
- Added
- Removed
-
lgf.dox
r33 r44 19 19 namespace lemon { 20 20 /** 21 [PAGE]sec_lgf[PAGE] Input-Output for Graphs21 [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 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. 32 The LEMON Graph Format (LGF) consists of several sections, for example a 33 digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section. 34 These parts use column oriented formats, each column belongs to a map in 35 the graph. The first line of the section associates names to these maps, 36 which can be used to refer them. Note that this simple idea makes it 37 possible to extend the files with new maps (columns) at any position 38 without having to modify the codes using these files. 39 Other data can also be added to an LGF file as individual properties 40 in an <tt>\@attributes</tt> section. This part can be used to specify 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 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. 44 For example, a shortest path problem, which is represented as a directed 45 graph with some node and arc maps, can be stored in LGF format as follows. 50 46 51 47 \code … … 56 52 ... 57 53 41 (600,100) 54 58 55 @arcs 59 56 label length … … 63 60 ... 64 61 36 41 123 21 62 65 63 @attributes 66 64 source 0 67 target 4168 65 caption "A shortest path problem" 69 66 \endcode 70 67 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. 68 In the <tt>\@nodes</tt> section, the \c label map has special role, 69 it must store unique values, which in turn can be used to refer to the nodes 70 in the file. 71 The first two columns of the <tt>\@arcs</tt> section are anonymous, they 72 store the source and target nodes, respectively. 73 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 78 \code … … 84 83 std::string title; 85 84 86 digraphReader(g, std::cin)87 .nodeMap("coord ", coord)85 digraphReader(g, "digraph.lgf") 86 .nodeMap("coordinate", coord) 88 87 .arcMap("length", length) 88 .node("source", src) 89 89 .attribute("caption", title) 90 .node("source", src)91 90 .run(); 92 91 \endcode 93 92 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. 93 Note that the \ref DigraphReader class is used through the \ref digraphReader() 94 function with several named parameters. 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 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. 101 The following code demonstrates how the above digraph with the maps and 102 attributes can be written into the standard output in LGF Format. 131 103 132 104 \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" 105 digraphWriter(g, std::cout) 106 .nodeMap("coordinate", coord) 107 .arcMap("length", length) 108 .node("source", src) 109 .attribute("caption", title) 110 .run(); 138 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, 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. 116 For more information, see a more detailed \ref lgf-format 117 "description of the LGF format" and the \ref io_group module 118 in the reference manual. 177 119 178 120 [TRAILER]
Note: See TracChangeset
for help on using the changeset viewer.
