[PAGE]sec_lgf[PAGE] Input-Output for Graphs

 [PAGE]sec_lgf[PAGE] LEMON Graph Format

 \todo Clarify this section.

 LEMON provides a versatile file format for storing graphs and related

 node and arc maps. Such a format should be really flexible, it should be

 able to store arbitrary number of maps of arbitrary value types.

 On the other hand, the file size and the ease of processing are also critical

 to support huge graphs, which is a major goal of LEMON.

 These requirements forbid using complicated and deeply structured formats

 like XML. That is why a compact text file format is designed for LEMON

 instead of using hierarchical formats (such as GraphML, GXL or GML).

 LEMON provides a versatile file format for storing graphs

 The LEMON Graph Format (LGF) consists of several sections, for example a

 and related node and arc maps.

 digraph is stored in a <tt>\@nodes</tt> and an <tt>\@arcs</tt> section.

 Such a format should be really flexible, it should be able to store arbitrary

 These parts use column oriented formats, each column belongs to a map in

 number of maps of arbitrary value types.

 the graph. The first line of the section associates names to these maps,

 On the other hand, the file size and the ease of processing are also critical

 which can be used to refer them. Note that this simple idea makes it

 to support storing huge graphs, which is a major goal of LEMON.

 possible to extend the files with new maps (columns) at any position

 These requirements forbid using complicated and deeply structured formats

 without having to modify the codes using these files.

 like XML.

 Other data can also be added to an LGF file as individual properties

 That is why a compact file format is designed for LEMON instead of using

 in an <tt>\@attributes</tt> section. This part can be used to specify

 hierarchical formats, such as GraphML, GXL or GML.

 certain nodes or arcs, or store meta data for the file, such as copyright

 notice.

 The LEMON Graph Format (LGF) comprises different sections, for

 For example, a shortest path problem, which is represented as a directed

 example a digraph is stored in a \c @nodes and an \c @arcs

 graph with some node and arc maps, can be stored in LGF format as follows.

 section. These parts use column oriented formats, each

 column belongs to a map in the graph. The first line of the section associate

 names to these maps, which can be used to refer them.

 Note that this simple idea makes it possible to extend the files with

 new maps (columns) at any

 position without having to modify the codes using these files.

 The \c label map has special role, it must store unique values, which in turn

 can be used to refer

 to the nodes and arcs in the file. Finally, the first two column of the

 \c @arcs section is anonymous, they indicate the source and target nodes,

 respectively.

 The \ref DigraphReader and \ref DigraphWriter classes are used

 In the <tt>\@nodes</tt> section, the \c label map has special role,

 to read and write a digraph and corresponding maps. By default, a map

 it must store unique values, which in turn can be used to refer to the nodes

 can be used with these classes if its value type has standard I/O

 in the file.

 operators (\c operator<<(ostream&, T) and \c operator>>(istream&, T&)).

 The first two columns of the <tt>\@arcs</tt> section are anonymous, they

 Otherwise, a function object

 store the source and target nodes, respectively.

 can be specified which converts the value type to \c std::string.

 The above LGF file can be scanned as follows.

 The \ref DigraphReader and \ref DigraphWriter classes can used

 to read and write data in LGF format.

 For example, the above file can be read as follows.

   digraphReader(g, std::cin)

   digraphReader(g, "digraph.lgf")

     .nodeMap("coord", coord)

     .nodeMap("coordinate", coord)

 Apart from LGF, the library can also interpret other graph

 Note that the \ref DigraphReader class is used through the \ref digraphReader()

 formats, such as the well-known DIMACS format or the NAUTY graph6

 function with several named parameters.

 format.

 <hr>

 \note By default, a map can be used with these classes if its value type

 has standard I/O operators (\c operator<<(ostream&, T) and \c

 operator>>(istream&, T&)). Otherwise, a function object can be specified

 which converts the value type to \c std::string.

 The \e LGF is a <em>column oriented</em>

 The following code demonstrates how the above digraph with the maps and

 file format for storing graphs and associated data like

 attributes can be written into the standard output in LGF Format.

 node and edge maps.

 Each line with \c '#' first non-whitespace

 character is considered as a comment line.

 Otherwise the file consists of sections starting with

 a header line. The header lines starts with an \c '@' character followed by the

 type of section. The standard section types are \c \@nodes, \c

 \@arcs and \c \@edges

 and \@attributes. Each header line may also have an optional

 \e name, which can be use to distinguish the sections of the same

 type.

 The standard sections are column oriented, each line consists of

 <em>token</em>s separated by whitespaces. A token can be \e plain or

 \e quoted. A plain token is just a sequence of non-whitespace characters,

 while a quoted token is a

 character sequence surrounded by double quotes, and it can also

 contain whitespaces and escape sequences.

 The \c \@nodes section describes a set of nodes and associated

 maps. The first is a header line, its columns are the names of the

 maps appearing in the following lines.

 One of the maps must be called \c

 "label", which plays special role in the file.

 The following

 non-empty lines until the next section describes nodes of the

 graph. Each line contains the values of the node maps

 associated to the current node.

  @nodes

   digraphWriter(g, std::cout)

  label  coordinates  size    title

     .nodeMap("coordinate", coord)

  1      (10,20)      10      "First node"

     .arcMap("length", length)

  2      (80,80)      8       "Second node"

     .node("source", src)

  3      (40,10)      10      "Third node"

     .attribute("caption", title)

     .run();

 The \c \@arcs section is very similar to the \c \@nodes section,

 For more information, see a more detailed \ref lgf-format

 it again starts with a header line describing the names of the maps,

 "description of the LGF format" and the \ref io_group module

 but the \c "label" map is not obligatory here. The following lines

 in the reference manual.

 describe the arcs. The first two tokens of each line are

 the source and the target node of the arc, respectively, then come the map

 values. The source and target tokens must be node labels.

 \code

  @arcs

          capacity

  1   2   16

  1   3   12

  2   3   18

 \endcode

 The \c \@edges is just a synonym of \c \@arcs. The \@arcs section can

 also store the edge set of an undirected graph. In such case there is

 a conventional method for store arc maps in the file, if two columns

 has the same caption with \c '+' and \c '-' prefix, then these columns

 can be regarded as the values of an arc map.

 The \c \@attributes section contains key-value pairs, each line

 consists of two tokens, an attribute name, and then an attribute

 value. The value of the attribute could be also a label value of a

 node or an edge, or even an edge label prefixed with \c '+' or \c '-',

 which regards to the forward or backward directed arc of the

 corresponding edge.

 \code

  @attributes

  source 1

  target 3

  caption "LEMON test digraph"

 \endcode

 The \e LGF can contain extra sections, but there is no restriction on

 the format of such sections.