# HG changeset patch # User Peter Kovacs # Date 1266194853 -3600 # Node ID 02083323ff2c489e6bde4f7a81e4092bccabf21d # Parent 7d70e97356868cf1953c9060a3112ef83e7fb3fa Add preliminary pages about LGF and tools diff -r 7d70e9735686 -r 02083323ff2c lgf.dox --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lgf.dox Mon Feb 15 01:47:33 2010 +0100 @@ -0,0 +1,179 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2008 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +namespace lemon { +/** +[PAGE]sec_lgf[PAGE] Input-Output for Graphs + +\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 storing 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 file format is designed for LEMON instead of using +hierarchical formats, such as GraphML, GXL or GML. + +The LEMON Graph Format (LGF) comprises different sections, for +example a digraph is stored in a \c @nodes and an \c @arcs +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. + +\code + @nodes + label coordinate + 0 (20,100) + 1 (40,120) + ... + 41 (600,100) + @arcs + label length + 0 1 0 16 + 0 2 1 12 + 2 12 2 20 + ... + 36 41 123 21 + @attributes + source 0 + target 41 + caption "A shortest path problem" +\endcode + +The \ref DigraphReader and \ref DigraphWriter classes are used +to read and write a digraph and corresponding maps. 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 above LGF file can be scanned as follows. + +\code + ListDigraph g; + ListDigraph::NodeMap > coord(g); + ListDigraph::ArcMap length(g); + ListDigraph::Node src; + std::string title; + + digraphReader(g, std::cin) + .nodeMap("coord", coord) + .arcMap("length", length) + .attribute("caption", title) + .node("source", src) + .run(); +\endcode + +Apart from LGF, the library can also interpret other graph +formats, such as the well-known DIMACS format or the NAUTY graph6 +format. + +
+ +The \e LGF is a column oriented +file format for storing graphs and associated data like +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 +tokens 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. + +\code + @nodes + label coordinates size title + 1 (10,20) 10 "First node" + 2 (80,80) 8 "Second node" + 3 (40,10) 10 "Third node" +\endcode + +The \c \@arcs section is very similar to the \c \@nodes section, +it again starts with a header line describing the names of the maps, +but the \c "label" map is not obligatory here. The following lines +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. + +*/ +} diff -r 7d70e9735686 -r 02083323ff2c toc.txt --- a/toc.txt Mon Feb 15 01:24:45 2010 +0100 +++ b/toc.txt Mon Feb 15 01:47:33 2010 +0100 @@ -16,12 +16,17 @@ ** sec_digraph_types ** sec_undir_graphs ** sec_special_graphs +*_sec_maps +**_sec_map_concepts +**_own_maps +**_algs_with_maps * sec_graph_adaptors * sec_lp -*_sec_lgf -*_sec_tools +* sec_lgf +* sec_tools +** sec_aux_structures **_sec_time_count **_sec_random -**_sec_graph_to_eps +** sec_graph_to_eps **_sec_glemon * sec_license diff -r 7d70e9735686 -r 02083323ff2c tools.dox --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/tools.dox Mon Feb 15 01:47:33 2010 +0100 @@ -0,0 +1,67 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +namespace lemon { +/** +[PAGE]sec_tools[PAGE] Tools + +\todo Clarify this section. + +[SEC]sec_aux_structures[SEC] Auxiliary Data Structures +Graph algorithms depend on various auxiliary data structures and algorithms. +For example, heaps play an important role in Dijkstra and Prim +algorithms, both the theoretical and practical performance of them +are determined by the applied heap implementation. + +LEMON implements various such auxiliary tools. For instance, +several data structures are available for maintaining \e disjoint \e sets. +\ref UnionFind is the classical union-find data structure, which is +used to implement the \ref Kruskal algorithm. +The \ref UnionFindEnum and \ref HeapUnionFind classes are used in +matching algorithms, the first one supports the enumeration of the +items stored in the sets, while the second one also assigns priorities to the +elements and an item having minimum priority can be retrieved set-wise. + + +[SEC]sec_graph_to_eps[SEC] Graph to EPS + +Another nice feature of the library is \ref graphToEps(), a highly +configurable graph displaying tool (using EPS output format). +Originally, it was developed to evaluate the flexibility and scalability +of LEMON's approach to implement named parameters. Later it +has been evolved into a versatile tool featuring above 35 named +parameters. The following code demonstrates its typical use. + +\code + graphToEps(g, "graph.eps") + .coords(coords) + .title("Sample EPS figure") + .copyright("(c) 2003-2010 LEMON Project") + .absoluteNodeSizes().absoluteArcWidths() + .nodeScale(2).nodeSizes(sizes) + .nodeShapes(shapes) + .nodeColors(composeMap(palette, colors)) + .arcColors(composeMap(palette, acolors)) + .arcWidthScale(.4).arcWidths(widths) + .nodeTexts(id).nodeTextSize(3) + .run(); +\endcode + +[TRAILER] +*/ +}