11 LEMON Graph Format

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).

The LEMON Graph Format (LGF) consists of several sections, for example a digraph is stored in a @nodes and an @arcs section. These parts use column oriented formats, each column belongs to a map in the graph. The first line of the section associates 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. Other data can also be added to an LGF file as individual properties in an @attributes section. This part can be used to specify certain nodes or arcs, or store meta data for the file, such as copyright notice.

For example, a shortest path problem, which is represented as a directed graph with some node and arc maps, can be stored in LGF format as follows.

  @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
  caption "A shortest path problem"

In the @nodes section, the label map has special role, it must store unique values, which in turn can be used to refer to the nodes in the file. The first two columns of the @arcs section are anonymous, they store the source and target nodes, respectively.

The DigraphReader and DigraphWriter classes can used to read and write data in LGF format. For example, the above file can be read as follows.

  ListDigraph g;
  ListDigraph::NodeMap<dim2::Point<int> > coord(g);
  ListDigraph::ArcMap<int> length(g);
  ListDigraph::Node src;
  std::string title;

  digraphReader(g, "digraph.lgf")
    .nodeMap("coordinate", coord)
    .arcMap("length", length)
    .node("source", src)
    .attribute("caption", title)
    .run();

Note that the DigraphReader class is used through the digraphReader() function with several named parameters.

Note:
By default, a map can be used with these classes if its value type has standard I/O operators (operator<<(ostream&, T) and operator>>(istream&, T&)). Otherwise, a function object can be specified which converts the value type to std::string.
The following code demonstrates how the above digraph with the maps and attributes can be written into the standard output in LGF Format.

  digraphWriter(g, std::cout)
    .nodeMap("coordinate", coord)
    .arcMap("length", length)
    .node("source", src)
    .attribute("caption", title)
    .run();

Undirected graphs can be stored in LGF format in almost the same way. The @arcs section can also be called @edges, they are identical. The only speciality is that arc maps can be distinguished from edge maps using a + or - prefix before the name of the map. For example,

  @edges
            label  +length  -length  
  0    1    0      10       20
  ...

In conjunction with undirected graphs, the classes GraphReader and GraphWriter can be used.

For more information, see the description of the LGF format and the Input-Output module in the reference manual. For a working example, see lgf_demo.cc in the demo directory of the LEMON source.

Note:
Apart from LGF, the library can also handle other graph formats, such as the well-known DIMACS format.
<< 10 Linear Programming Interface | Home | 12 Tools >>
doxygen