Changes between Version 7 and Version 8 of GSoC2010Ideas

Timestamp:

03/14/10 06:54:29 (15 years ago)

Author:

Peter Kovacs

Comment:

--

GSoC2010Ideas

@@ -27 +27 @@
 ----
 
-== Multi thread support & thread safe graph maps ==
+== Multi-thread support & thread safe graph maps ==
 mentor: Péter Kovács
 
@@ -72 +72 @@
 
  - knowledge of C++ language
- - basic knowledge in graph theory
+ - basic knowledge of graph theory
  - English language knowledge
 
@@ -107 +107 @@
 
 By taking part in this project, you will get familiar with the LEMON library and the basic principles 2D rendering and perhaps with GUI design.
+
+----
+
+== Binary graph format ==
+mentor: Alpár Jüttner
+
+=== Background ===
+
+LEMON has its own text file format, [http://lemon.cs.elte.hu/pub/doc/1.1.2/lgf-format.html LGF (LEMON Graph Format)] for storing graphs and related data (typically node and arc maps). This format makes it possible to handle graphs in a convenient and flexible way and it can be easily read and written both by hand and by a program. However, combinatorial optimization tasks usually require working with very large graphs, i.e. graphs containing millions of nodes and arcs. Storing such a huge graph in a text format takes a large amount of space (e.g. several GBs), however compact the format is (not to mention complicated structured formats, such as XML).
+
+Therefore, it would be quite useful to have a binary graph format that could provide (almost) the same functionalities as LGF but require much less space. In addition, the reading and writing operations could also be made much faster using such a compact binary format.
+
+=== The task ===
+
+ - Design an appropriate binary graph format. It could be called e.g. LBF (LEMON Binary Format).
+ - Develop convenient functions for reading and writing data in this format (with similar interfaces to the LGF tools).
+ - Develop LGF->LBF and LBF->LGF converter tools.
+
+Related tickets: #225, #297.
+
+=== Application conditions ===
+
+ - knowledge of C++ language
+ - English language knowledge
+
+=== Benefits of participating ===
+
+By taking part in this project, you can get familiar with the LEMON library, especially with the LGF related tools.